Abstract Nonsense

Crushing one theorem at a time

Munkres Chapter one Section one


1.

Problem: Check the distributive laws for union and intersection. Also,  check DeMorgan’s laws.

Proof: Our first goal is to check that A\cup\left(B\cap C\right)=\left(A\cup B\right)\cap\left(A\cap C\right) and A\cap\left(B\cup C\right)=\left(A\cap B\right)\cup\left(A\cap C\right). To verify the fist we notice that

x\in A\cup\left(B\cap C\right)\Leftrightarrow x\in A\text{ or }x\in\left(B\cap C\right)\Leftrightarrow x\in A\text{ or }\left(x\in B\text{ and }x\in C\right)

which by the distributive laws of  ‘and’ and ‘or’ (easily checked by a truth table) we see that this is equivalent to

\left(x\in A\text{ or }x\in B\right)\text{ and }\left(x\in A\text{ or }x\in C\right)\Leftrightarrow x\in\left(A\cup B\right)\cap\left(A\cup C\right)

from where the conclusion follows. The other case is completely analogous.

Now, we aim to prove that U-\left(A\cup B\right)=\left(U-A\right)\cap\left(U-B\right) and U-\left(A\cap B\right)=\left(U-A\right)\cup\left(U-B\right). To do this we let x\in U-\left(A\cup B\right). Now, if x\in A,B we’d have that x\in A\cup B and so x\notin A\text{ and }x\notin B and so x\in U-A\text{ and }x\in U-B and so x\in\left(U-A\right)\cap\left(U-B\right). Conversely, if x\in\left(U-A\right)\cap\left(U-B\right) we see that x\in U-A\text{ and }x\in U-B. If x\in A or x\in B we’d have that x\notin U-A or x\notin U-B, and either way x\notin\left(U-A\right)\cap\left(U-B\right). It follows that x is in neither, i.e. x\notin A\cup B\implies x\in U-\left(A\cup B\right). The conclusion follows.

To get the other DeMorgan’s law we merely note that (changing U- to \prime)

\left(A\cap B\right)\prime=\left(\left(A\prime\right)\prime\cap\left(B\prime\right)\prime\right)\prime=\left(\left(A\prime\cup B\prime\right)\prime\right)\prime=A\prime\cup B\prime

2.

Problem: Determine which of the following statements are true for all sets A,B,C and D. If a double implication fails, determine whether one or the other of the possible implications holds. IF an equality fails, determine whether the statement becomes true if the equals sign is replaced by an inclusion.

a) A\subseteq B and A\subseteq C iff A\subseteq B\cup C

b) A\subseteq B or A\subseteq C iff A\subseteq B\cup C

c) A\subseteq B and A\subseteq C iff A\subseteq B\cap C

d) A\subseteq B or A\subseteq C iff A\subseteq B\cap C

e) A-\left(A-B\right)=B

f) A-\left(B-A\right)=A-B

g) A\cap\left(B-C\right)=\left(A\cap B\right)-\left(A\cap C\right)

h) A\cup\left(B-C\right)=\left(A\cup B\right)-\left(A\cup C\right)

i) \left(A\cap B\right)\cup\left(A-B\right)=A

j) A\subseteq C and B\subseteq D implies \left(A\times B\right)\subseteq \left(C\times D\right)

k) The converse of j)

l) The converse of j) assuming that A and B are non-empty

m) \left(A\times B\right)\cup\left(C\times D\right)=\left(A\cup C\right)\times\left(B\cup D\right)

n) \left(A\times B\right)\cap\left(C\times D\right)=\left(A\cap C\right)\times\left(B\cap D\right)

o) A\times\left(B-C\right)=\left(A\times B\right)-\left(A\times C\right)

p) \left(A-B\right) \times\left(C-D\right)=\left(A\times C-B\times C\right)-\left(A\times D\right)

q) \left(A\times B\right)-\left(C\times D\right)=\left(A-C\right)\times\left(B-D\right)

Proof:

a)

\implies: Let x\in A then x\in B and thus x\in B\cup C and so A\subseteq B\cup C

\Leftarrow: This isn’t necessarily true. Consider A=\{1,2,3\},B=\{1,2\},C=\{3\}.

b)

\implies: Let x\in A then x\in B or x\in C and so x\in B\cup C. Thus, A\subseteq B\cup C.

\Leftarrow: This is also wrong, the same counterexample being applicable.

c)

\implies: Let x\in A then x\in B and x\in C and so x\in B\cap C. Thus, A\subseteq B\cap C.

\Leftarrow: Clearly since A\subseteq B\cap C\subseteq B,C

d)

\implies: Not true. Take A=B\ne\varnothing and C=\varnothing

\Leftarrow: This is true, considering it’s a weaker formulation of the second direction in the last problem.

e)  Clearly not since the LHS is a subset of A. For example, \{1,2\}-\left(\{1,2\}-\{3\}\right)=\varnothing.

f) No. If A=B\ne\varnothing then the LHS is non-empty and the RHS is.

g) This is true. The RHS may be manipulated into the LHS as follows

\left(A\cap B\right)-\left(A\cap C\right)=A\cap B\cap\left(A\cap C\right)\prime=B\cap A\cap\left(A\prime\cup C\prime\right)

(the last part by DeMorgan’s) which upon distribution of A gives

B\cap\left[\left(A\cap A\prime\right)\cup\left(A\cap C\prime\right)\right]=B\cap A\cap C\prime=A\cap\left(B\cap C\prime\right)=A\cap\left(B-C\right)

h) Not true. Note that if A=B=C\ne\varnothing this says that

A=A\cup\varnothing=A\cup\left(B-C\right)=\left(A\cup B\right)-\left(A\cup C\right)=A-A=\varnothing

i) This makes sense, if you read it it would say “Everything that’s in both A and B plus everything that is in A but not in B gives everything in A.” Formally

\left(A\cap B\right)\cup\left(A-B\right)=A\cap B\cup\left(A\cap B\prime\right)

and so by distribution this equals

A\cap\left(\left(B\cup A\right)\cap\left(B\cup B\prime\right)\right)=A\cap \left(B\cup A\right)=A

j) This is true. Let (x,y)\in A\times B, then x\in A\implies x\in C and x\in B\implies x\in D, thus (x,y)\in C\times D.

k) This is not always true. Let A=C=\varnothing and B=\mathbb{R},D=\{1\} then the LHS and RHS of the inclusion are empty yet B\not\subseteq D.

l) Then, this is true. Let x\in A, since B\ne\varnothing there exists some y\in B, and thus (x,y)\in A\times B. Thus, (x,y)\in C\times D and so x\in C. A similar procedure shows B\subseteq D

Remark: This shows why sometimes it’s perilous to just go “let x\in…”

m) This is false. Let A=\{1,2\},B=\{3,4\},C=\{5,6\},D=\{7,8\}. Evidently (1,8)\in \left(A\cup C\right)\times \left(B\cup D\right) but (1,8)\notin \left(A\times B\right)\cup\left(C\times D\right)

n) This is true. Let (x,y)\in \left(A\times B\right)\cap\left(C\times D\right) then

(x,y)\in A\times B\text{ and }(x,y)\in C\times D

or

\left(x\in A\text{ and }y\in B\right)\text{ and }\left(x\in C\text{ and }y\in D\right).

or equivalently

\left(x\in A\text{ and} x\in C\right)\text{ and }\left(y\in B\text{ and }x\in D\right)

or equivalently

x\in A\cap C\text{ and }y\in B\cap D\Leftrightarrow (x,y)\in\left(A\cap C\right)\times\left(B\cap D\right)

o) This is true. Let (x,y)\in A\times\left(B-C\right), then:

x\in A\text{ and }y\in B-C\implies x\in A\text{ and }\left(y\in B\text{ and }y\notin C\right)

or (and this looks weird)

x\in A\text{ and }x\in A\text{ and }y\in B\text{ and }y\notin C

or

\left(x\in A\text{ and }y\in B\right)\text{ and }\left(x\in A\text{ and }y\notin C\right)

or

(x,y)\in A\times B\text{ and }(x,y)\notin A\times C

or

(x,y)\in \left(A\times B\right)-\left(A\times C\right)

And so \text{LHS}\subseteq\text{RHS}. Conversely, let (x,y)\in \left(A\times B\right)-\left(A\times C\right). Then,

(x,y)\in A\times B\text{ and }(x,y)\notin A\times C

(now, (x,y)\notin A\times C if x\notin A\text{ and }y\in C, x\in A\text{ and }y\notin C, and x\notin A\text{ and }y\notin C. But, since the first and the last are impossible since the first part of the statement says x\in A we may conclude that the second is true) thus

\left(x\in A\text{ and }y\in B\right)\text{ and }\left(x\in A\text{ and }y\notin C\right)

or

x\in A\text{ and }y\in B\text{ and }y\notin C

or

x\in A\text{ and }y\in B-C\implies (x,y)\in A\times \left(B-C\right)

p) This is true. Note that (a,b)\in \left(A-B\right)\times\left(C-D\right) iff a\in A-B\text{ and }b\in C-D which is true iff \left(a\in A\text{ and } a\notin B\right)\text{ and }\left(b\in C\text{ and}b\notin D\right). But, this is true iff \left(a\in A\text{ and }b\in C\right)\left(a\notin B\text{ or }b\notin C\right)\text{ and }\left(a\notin A\text{ or }b\notin D\right). (this ilast part was trick since we know that a\in A.) which is true iff (a,b)\in A\times C\text{ and }(a,b)\notin B\times C\text{ and }(a,b)\notin A\times D.

q) This isn’t true in general. Try \mathbb{R}\supseteq A=B=C\ne\varnothing and D=\mathbb{R}-A

Remark: I did these in more detail earlier, if you search for them.

3.

Problem:

a) Write the contrapositive and converse of the statement “If x>0, then x^2-x>0” and determine which of the statements are true

b) Do the same for the statement “If x>0, then x^2-x>0

Proof:

a) The contrapositive is ” If x^2-x\leqslant 0 then x\geqslant 0 which is false x=\frac{-1}{2}. The converse is “If x^2-x>0, then x<0” which is false “x=2

b) The contrapositive is “If x^2-x\leqslant 0, then x\leqslant 0 which is true. The converse is ” if x^2-x>0, then x>0” which is not true x=-1

4.

Problem: Let A and B be sets of real numbers. Write the negation of each of the following statements

a) For every a\in A, it is true that a^2\in B

b) For at least one a\in A, it is true that a^2\in B

c) For every a\in A, it is true that a^2\notin B

d) For at least one a\notin A, it is true that a^2\in B

Proof:

I’m going to write these in set notation

a) \exists a\in A\backepsilon a^2\notin B

b) \forall a\in A, a^2\notin B

c) \exists a\in A\backepsilon a^2\in B

d) \forall a\notin A,a^2\notin B

5.

Problem: Let \left\{U_{\alpha}\right\}_{\alpha\in\mathcal{A}}  be a nonempty class of sets. Determine the truth of each of the following statements and their converses

a) \displaystyle x\in\bigcup_{\alpha\in\mathcal{A}}U_{\alpha}\implies x\in U_{\alpha_0},\text{ }\text{ for some }\alpha_0\in\mathcal{A}

b) \displaystyle x\in \bigcup_{\alpha\in\mathcal{A}}U_{\alpha}\implies x\in U_\alpha,\text{ }\forall \alpha\in\mathcal{A}

c) \displaystyle x\in\bigcap_{\alpha\in\mathcal{A}}U_{\alpha}\implies x\in U_{\alpha_0}\text{ for some }\alpha_0\in\mathcal{A}

d) \displaystyle x\in\bigcap_{\alpha\in\mathcal{A}}U_{\alpha}\implies x\in U_{\alpha},\text{ }\forall \alpha\in\mathcal{A}

Proof:

a) This implication is true, as well as it’s converse (this is the definition of union)

b) The implication is false. Consider \left\{\{1\},\{2\}\right\}, then clearly 1\in\{1\}\cup\{2\} but 1\notin\{2\}

c) The implication is true. The converse is false though. In the above, class of sets we see that 1\in\{1\} but 1\notin \{1\}\cap\{2\}=\varnothing

d) The implication, and it’s converse are true. This is the definition of intersection.

6.

Problem: Write the contrapositive of each statements in exercise 5

Proof:

a) If x\notin U_{\alpha} for every \alpha\in\mathcal{A} then \displaystyle x\notin\bigcup_{\alpha\in\mathcal{A}}U_{\alpha}

b) If there exists \alpha_0\in\mathcal{A} such that x\notin U_{\alpha_0}, then \displaystyle x\notin\bigcup_{\alpha\in\mathcal{A}}U_{\alpha}

c) If for every \alpha\in\mathcal{A} it is true that \displaystyle x\notin U_{\alpha} then x\notin\bigcap_{\alpha\in\mathcal{A}}U_{\alpha}

d) If there exists some \alpha_0\in\mathcal{A} such that x\notin U_{\alpha_0}, then \displaystyle x\notin\bigcap_{\alpha\in\mathcal{A}}U_{\alpha}

7.

Problem: Given sets A,B and C, express each of the following sets in terms of A,B, and C, using the smbols \cup,\cap, and -.

D=\left\{x:x\in A\text{ and }\left(x\in B\text{ or }x\in C\right)\right\}

E=\left\{x:\left(x\in A\text{ and }x\in B\right)\text{ or }x\in C\right\}

F=\left\{x:x\in A\text{ and }\left(x\in B\implies x\in C\right)\right\}

Proof:

a) D= A\cap\left(B\cup C\right)

b) E=\left(A\cap B\right)\cup C

c) F=A\cap B\cap C

8.

Problem: If a set A has two elements, show that \mathcal{P}(A) has four elements. How many elements does \mathcal{P}(A) have if A has one element? Three elements? No elements? Why is \mathcal{P}\left(A\right) called the power set of A?

Proof:

Lemma: Let Y^X=\left\{f\mid f:X\to Y\right\}. Then, \mathcal{P}\left(X\right)\cong \{0,1\}^{X}

Proof: Let \varphi:\mathcal{P}(X)\to\{0,1\}^{X}:E\mapsto \Psi_E where

\Psi_E(x)=\begin{cases} 0 \quad\text{if}\quad x\notin E\\1\quad\text{if}\quad x\in E\end{cases}

To see that \varphi is injective suppose that A\ne B\subseteq X, then WLOG there is some x\in A-B and so \Psi_A(x)=1\ne0=\psi_B(x), thus \Psi_A\ne\Psi_B.  Next, to prove surjectivity let \Psi:X\to\{0,1\} and let E=\Psi^{-1}\left(\{1\}\right), evidently \varphi\left(E\right)=\Psi. It follows that \varphi is a bijection, and the lemma is proved. \blacksquare

It follows that if \text{card }X=n then \text{card }\mathcal{P}(X)=\text{card }\{0,1\}^n=2^n.

Remark: Alternatively, one may find a recurrence relation solution to this problem. Namely, let n=\text{card }\mathcal{P}\left(\{1,\cdots,m\}\right). Then, if one paritions \{1,\cdots,m+1\} into those sets which contain m+1 and those that don’t one can see that each block of the partition has n elements, and thus

\text{card }\mathcal{P}\left(\{1,\cdots,m\}\right)=2n=2\text{card }\mathcal{P}\left(\{1,\cdots,n\}\right)

and thus noting that \text{card }\mathcal{P}\left(\varnothing\right)=1 one may conclude that \text{card }\mathcal{P}\left(\{1,\cdots,m\}\right)=2^m

9.

Problem: Formulate and prove DeMorgan’s laws for arbitrary unions and intersections.

a)

Claim: Let \left\{U_{\alpha}\right\}_{\alpha\in\mathcal{A}},\text{ }\mathcal{A}\ne\varnothing be a class of subsets of some universal set U, then

\displaystyle U-\bigcup_{\alpha\in\mathcal{A}}U_{\alpha}=\bigcap_{\alpha\in\mathcal{A}}\left(U-U_{\alpha}\right)

Proof: If \displaystyle x\in\bigcup_{\alpha\in\mathcal{A}}U_{\alpha} then x\in U_{\alpha_0} for some \alpha_0\in\mathcal{A}. Thus, x\notin U-U_{\alpha_0} and so \displaystyle x\notin\bigcap_{\alpha\in\mathcal{A}}\left(U-U_{\alpha}\right). Conversely, suppose that x\notin\bigcap_{\alpha\in\mathcal{A}}\left(U-U_{\alpha}\right) then there exists some \alpha_0\in\mathcal{A} such that x\notin U-U_{\alpha_0}\implies x\in U_{\alpha_0}. It follows that \displaystyle x\in\bigcup_{\alpha\in\mathcal{A}}U_{\alpha} and so finally x\notin U-\bigcup_{\alpha\in\mathcal{A}}U_{\alpha}. The conclusion follows.

Corollary:

\displaystyle U-\bigcap_{\alpha\in\mathcal{A}}U_{\alpha}=\bigcup_{\alpha\in\mathcal{A}}\left(U-U_{\alpha}\right)

Proof: We merely note that

\displaystyle U-\bigcap_{\alpha\in\mathcal{A}}U_{\alpha}=U-\bigcap_{\alpha\in\mathcal{A}}\left(U-\left(U-U_{\alpha}\right)\right)

which by our last proven claim is

\displaystyle U-\left(U-\bigcup_{\alpha\in\mathcal{A}}\left(U-U_{\alpha}\right)\right)=\bigcup_{\alpha\in\mathcal{A}}\left(U-U_{\alpha}\right)

10.

Problem: Let \mathbb{R}  denote the set of real numbers. For each of the following subsets of \mathbb{R}, determine whether it is equal to the cartesian product of two subsets of \mathbb{R}

a) A=\left\{(x,y):x\in\mathbb{Z}\right\}

b) B=\left\{(x,y):0<y\leqslant1\right\}

c) C=\left\{(x,y):y>x\right\}

d) D=\left\{(x,y):x\notin\mathbb{Z}\text{ and }y\in\mathbb{Z}\right\}

e) E=\left\{(x,y):x^2+y^2<1\right\}

Proof:

a) This is, namely A=\mathbb{Z}\times\mathbb{R}

b) This is, namely B=\mathbb{R}\times(0,1]

c) This is not. To see this suppose that C=X\times Y. We see that (0,1)\in X\times Y and thus 1\in Y,0\in X. Also, (2,3)\in X\times Y and so 2\in X,3\in Y. But, (2,1)\notin C and thus C\ne\left\{(x,y):x\in X\text{ and }y\in Y\right\}, which is a contradiction.

d) This is, namely D=\left(\mathbb{R}-\mathbb{Z}\right)\times\mathbb{Z}

e) This is not, using the same argument as in c), first noting that (0,.85),(.85,0)\in E

Advertisements

September 23, 2010 - Posted by | Fun Problems, Munkres, Topology | , , , , ,

No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: