Abstract Nonsense

Crushing one theorem at a time

Munkres Chapter 1 Section 1


1.

Problem: Prove the distributive laws for union and intersection, and prove DeMorgan’s laws.

Proof:

a) We claim that A\cup\left(B\cap C\right)=\left(A\cup B\right)\cap \left(B\cup C\right). To see this we denote the right side by P and the left side by Q, then x\in Q if and only if x\in A\text{ or }\left(x\in B\text{ and }x\in C\right) but by the distributive laws of the “and” and “or” operators (just draw a simple truth table) 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)

but this is just the logical statement that x\in\left(A\cup B\right)\cap\left(A\cup C\right)=P. The exact same, (but reversing the arrows…haha not category theory) gives that x\in P\implies x\in Q. It follows that P=Q as desired.

b) We now claim that A\cap\left(B\cup C\right)=\left(A\cap B\right)\cup\left(A\cap C\right). Once again we denote the LHS by Q and the RHS by P. Then, x\in Q implies that x\in A\text{ and }x\in B\cup C, which implies that x\in A\text{ and }\left(x\in B\text{ or }x\in C\right). Once again, constructing a truth table if necessary, we use the distributivity laws of the logical operators “and” and “or” to get the above implies

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

which says that x\in \left(A\cap C\right)\cup \left(A\cap C\right)=P. Once again, using the exact same logic in reverse we get that x\in P\implies x\in Q from where it follows that P=Q.

c) We claim in general that if \left\{U_{\alpha}\right\}_{\alpha\in\mathcal{A}} are 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)

To see this we once again denote the LHS by Q and the RHS by P. Then, if x\notin Q then \displaystyle x\in\bigcup_{\alpha\in\mathcal{A}}U_\alpha and so x\in U_{\alpha_0} for some \alpha_0\in \mathcal{A}. It follows that x\notin U-U_{\alpha_0} and thus \displaystyle x\notin P. Conversely, if x\notin P then x\notin U-U_{\alpha_0} f0r some \alpha_0\in\mathcal{A} and thus x\in U_{\alpha_0} and so \displaystyle x\in\bigcup_{\alpha\in\mathcal{A}}U_{\alpha} and so x\notin Q. The conclusion follows.

We now claim that

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

To do this we note that

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

And thus if we keep to our LHS-RHS notation we see that U-P=U-Q from where it follows from elementary set theory that P=Q.

2.

Problem: Determine which of he following statements are true for all sets A,B,C,D (contained in some universal set U). If a double implications fails, determine whether one or the other statement of the possible implication holds, If an equality fails, determine whether the statement becomes true if the “equals” is related by one or the other of the inclusion symbols \subseteq or \supseteq.

a) A\subseteq B\text{ and }A\subseteq C\Leftrightarrow A\subseteq\left(C\cup B\right)

b) A\subseteq B\text{ or }A\subseteq C\Leftrightarrow A\subseteq\left(B\cup C\right)

c) A\subseteq B\text{ and }A\subseteq C\Leftrightarrow A\subseteq\left(B\cap C\right)

d) A\subseteq B\text{ or }A\subseteq C\Leftrightarrow A\subseteq\left(B\cap C\right)

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\text{ 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)-A\times D

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

Proof:

a) The right hand implication is clearly true since A\subseteq B\text{ and }A\subseteq C\implies A\subseteq B\cap C\subseteq A\cup B. That said, the left hand implication is false. Clearly given any non-empty set B we have that B\subseteq \varnothing\cup B but it is not true that B\subseteq B\text{ and }B\subseteq A.

b) If the LHS statement is true then for each x\in A we have that x\in A\text{ or }x\in B and so x\in A\cup B, i.e. A\subseteq B. The other direction is not correct though. Consider the sets A=\{1,3\},B=\{1,2\},C=\{3,4\} then A\subseteq B\cup C but it is not true that A\subseteq B\text{ or }A\subseteq C.

c) This two-sided implication is true. To see the right implications we note that if x\in A then x\in B and x\in C so that x\in B\cap C and so it follows that A\subseteq B\cap C. Conversely, if A\subseteq B\cap C then for each x\in A we have that x\in B\text{ and }x\in C and so A\subseteq B\text{ and }A\subseteq C.

d) The right hand implications is not false. Take for example A=B=\{1\} and C=\varnothing. Then it is true that A\subseteq B\text{ or }A\subseteq C  but it is not true that A\subseteq B\cap C=\varnothing. The converse is true since it is weaker than the second part of the last statement.

e) The equality is not always true. Consider for example \mathbb{R}=U as the universal set. Then, if A=\{1\} and B=\{2\} then A-\left(A-B\right)=A\cap\left(U-\left(A\cap\left(U-B\right)\right)\right) which is equal to \varnothing\ne B. The \subseteq inclusion is true thought since x\in A-\left(A-B\right) means that x\in A\text{ and }x\notin A-B or that x\in A\text{ and }\left(x\notin A\text{ or }x\in B\right) but since x\in A it follows that x\in A\cap B. Thus, A-\left(A-B\right)=A\cap B\subseteq B.

f) Let’s just see what the LHS is equal to. A-\left(B-A\right)=A\cap\left(U-\left(B\cap\left(U-A\right)\right)\right) but this is equal to A\cap\left(\left(U-B\right)\cup\left(A\right)\right) (DeMorgan’s law)  but this is equal \left(A\cap\left(U-B\right)\right)\cup\left(A\cap A\right) but this is equal to \left(A\cap\left(U-B\right)\right)\cup A=A since the left set is a subset of A. It clearly follows that A-B\subseteq A but the inclusion may be strict by considering \varnothing\subsetneq B\subseteq A

g) The LHS is equal to A\cap\left(B\cap\left(U-C\right)\right) and the RHS is A\cap B\cap\left(\left(U-A\right)\cup \left(U-C\right)\right) which is equal to B\cap\left(\left(A\cap U-A\right)\cup\left(A\cap U-C\right)\right)=B\cap A\cap U-C. Thus, they are, in fact, equal.

h) The RHS is \left(A\cup B\right)\cap\left(A'\cap C'\right) (prime denotes complement in the universal set) which is equal to by distributivity laws \left(\left(A\cap\left(A'\cap C\right)\right)\right)\cup\left(B\cap\left(A'\cap C'\right)\right)=B\cap A'\cap C'. The LHS is A\cup\left(B\cap C'\right)=\left(A\cup B\right)\cap\left(A\cup C'\right). Clearly the neither inclusion holds (in general) since the LHS is always contains elements of A and the RHS is contains only elements of A' (if it contains any).

i) The LHS is \left(A\cap B\right)\cup\left(A-B\right)=\left(A\cap B\right)\cup\left(A\cap B'\right) which distributing gives \left(A\cup\left(A\cap B'\right)\right)\cap\left(B\cup\left(A\cap B'\right)\right) which is equal to A\cap\left(\left(B\cup A\right)\right)\cup\left(B\cup B'\right) which is equal A\cap\left(B\cup A\right)=A. So, yes, they are equal.

j) This implication is true. If (a,b)\in A\times B then a\in A\text{ and }b\in B and thus a\in C\text{ and }b\in D and so (a,b)\in C\times D

k) No, the converse is not true. Consider A=\varnothing, B=\{1\},C=D=\{2\} then A\times B=\varnothing\subseteq C\times D=\{(2,2)\}. But, clearly A\subseteq C\text{ and }B\subseteq D is not true.

l) In this case it is true. Let a\in A then for some (we know there exists some, since B\ne\varnothing) b\in B we have that (a,b)\in A\times B\subseteq C\times D and so a\in C. The other direction works the same.

m) This equality is false. Consider the intervals A=[0,1]=B=[0,1],C=D=[0,2]. Note then that \left(A\times B\right)\cup\left(C\times D\right)\subsetneq \left(A\cup C\right)\times\left(B\cup D\right) (once can picture this as taking the square of side length two whose bottom left hand corner is on the origin. Then, if we carve this square into four smaller squares in the obvious way the LHS is just the upper right and lower left ones whereas the RHS is the full square). In general \left(A\times B\right)\cup\left(C\times D\right)\subseteq\left(A\cup C\right)\times\left(B\cup D\right). To see this we note that if (a,b)\in\left(A\times B\right)\cup\left(C\times D\right) then we may assume WLOG that (a,b)\in A\times B and thus a\in A\text{ and }b\in B and so a\in A\cup C,b\in B\cup D and so (a,b)\in \left(A\cup C\right)\times\left(B\cup D\right)

n) This is true. To see this we note that if (a,b)\in\left(A\cap C\right)\times \left(B\cap D\right) then a\in A\cap C \text{ and }b\in B\cap D and so \left(a\in A\text{ and }a\in C\right)\text{ and }\left(b\in B\text{ and }b\in D\right) and so in particular \left(a\in A\text{ and }b\in B\right)\text{ and }\left(a\in C\text{ and }b\in D\right) or (a,b)\in \left(A\times B\right)\cap\left(C\times D\right). Conversely, if (a,b)\in\left(A\times B\right)\cap\left(C\times D\right) then (a,b)\in A\times B and (a,b)\in C\times D which says that a\in A\text{ and }b\in B and a\in C\text{ and }b\in D and so a\in A\cap C and b\in B\cap D so that (a,b)\in\left(A\cap C\right)\times\left(B\cap D\right)

o) This is true. Note that (a,b)\in \left(A\times B\right)-\left(A\times C\right) if and only if (a,b)\in A\times B\text{ and }(a,b)\notin A\times C which is true if and only if \left(a\in A\text{ and }b\in B\right)\text{ and }\left(a\notin A\text{ or }b\notin C\right) which is true if and only if a\in A\text{ and }b\in B\text{ and }b\notin C or a\in A\text{ and }b\in B-C and so (a,b)\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) if and only if a\in A-B\text{ and }b\in C-D which is true if and only if \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 if and only if \left(a\in A\text{ and }b\in C\right)\text{ and }\left(a\notin B\text{ or }b\notin C\right)\text{ and }\left(a\notin A\text{ and }b\notin D\right) (because by the first part we must have a\in A and so the last two are just “tricks”) which is true if and only if (a,b)\in A\times C\text{ and }(a,b)\notin B\times C\text{ and }(a,b)\notin A\times D which is just a fancy way of saying (a,b)\in A\times C-B\times C-A\times D

q) This equality does not hold in general. If a\in A,b\in B,a\in C,b\notin D then (a,b)\in A\times B-C\times D but (a,b)\notin\left(A-C\right)\times\left(B-D\right). The, \supseteq inclusion does hold though. To see this let (a,b)\in \left(A-C\right)\times\left(B-D\right) then a\in A-C\text{ and }b\in B-D and so in particular (a,b)\in A\times B but (a,b)\notin C\times D and so (a,b)\in A\times B-C\times D

Remark: God that was horrendous…

3.

Problem:

a)Write the contrapostive and converse of the following statement: “If x<0, then latex x^2-x>0$” and determine which (if any) of the three statements are true.

b) Do the same for the statement “if x>0 then x^2-x>0.

Proof:

a) Contrapositive says if x^2-x\leqslant 0 then x\geqslant 0. The negation says that if x<0 then x^2-x\geqslant 0

We note that x^2\leqslant x then 0\leqslant x. Thus, the contrapositive is true. The negation is not true. The actual statement, being logically equivalent to the contrapositive, is true.

b) This is exactly the same idea.

4.

Problem: Let A and $laetx 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 A

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:

a) There exists some a\in A such that a^2\notin B

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

c) There exists some a\in A such that a^2\in B

d) For every a\notin A it is true that a^2\notin B

5.

Problem: Let \mathcal{A} be a non-empty collection of sets. Determine the truth of each of the following statements about their converses:

a) \displaystyle x\in\bigcup_{A\in\mathcal{A}}A\implies x\in A\text{ for some }A\in\mathcal{A}

b) \displaystyle x\in\bigcup_{A\in\mathcal{A}}A\implies x\in A\text{ for every }x\in A

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

d) \displaystyle x\in\bigcap_{A\in\mathcal{A}}A\implies x\in A\text{ for every }A\in\mathcal{A}

Proof:

a) Of course this is true, it’s the definition.

b) Clearly not. Take the elements of \mathcal{A} to be disjoint.

c) Of course! By definition if it’s in the intersections it’s in all of them

d) What I said in the last one.

6.

Problem: Write the contrapositive of each of the statements of Exercise 5.

a) If for every A\in\mathcal{A} it is true that x\notin A then \displaystyle x\notin\bigcup_{A\in\mathcal{A}}A

b) If for some A\in\mathcal{A} it is true that x\notin A then \displaystyle x\notin\bigcup_{A\in\mathcal{A}}A

c) If x\notin A for some A\in\mathcal{A} then \displaystyle x\notin\bigcap_{A\in\mathcal{A}}A

d) IF x\notin A for every A\in\mathcal{A} then \displaystyle x\notin\bigcap_{A\in\mathcal{A}}A

7.

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

Proof:

a) The set is D=\left\{x\in U:x\in A\text{ and}\left(x\in B\text{ or }x\in c\right)\right\}=A\cap\left(B\cup C\right)

b) The set is E=\left\{x\in U:\left(x\in A\text{ and }x\in B\right)\text{ or }x\in C\right\}=\left(A\cap B\right)\cup C

c) The set is F=\left\{x\in U:x\in A\text{ and }\left(x\in B\implies x\in C\right)\right\}=A\cap\left(\left(U-B\right)\cup\left(B\cap c\right)\right)

8.

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

Proof: We prove that \text{card }A=n\implies\text{card }\mathcal{P}(A)=2^n. To do this we let a_n=\text{card }\mathcal{P}(\{1,\cdots,n\}).

Partition \mathcal{P}\left(\{1,\cdots,n+1\}\right) into two blocks, namely

B_1=\left\{S\in\mathcal{P}\left(\{1,\cdots,n+1\}\right):n+1\notin S\right\}

and

B_2=\mathcal{P}\left(\{1,\cdots,n+1\}\right)-B_1.

Note, that clearly \text{card }B_2=\text{card }\mathcal{P}\left(\{1,\cdots,n\}\right)=a_n. Now, given S\in B_1 we have two choices, either S=\{n+1\} or S\cap\{1,\cdots,n\}\ne\varnothing. Thus, excluding \{n+1\} for a second each element of B_1 is paired with an element of \mathcal{P}\left(\{1,\cdots,n\}\right) is a unique way. It follows that \text{card }B_2-\{\{n+1\}\}\leqslant a_n. But, noting that in fact for each S\in\mathcal{P}\left(\{1,\cdots,n+1\}\right)-\{\varnothing\} we have that S\cup\{n+1\}\in B_1 it follows that \text{card }B_2-\{\{n+1\}\}=a_n-1\implies \text{card }B_2=a_n. Thus,

a_{n+1}=\text{card }\mathcal{P}\left(\{1,\cdots,n+1\}\right)=\text{card }B_1+\text{card }B_2=2a_n

Thus, noting that a_0=\text{card }\mathcal{P}(\varnothing)=1 we can easily prove by induction that a_n=2^n

9.

Problem: Formulate and prove a generalized version of DeMorgan’s theorem.

Proof: Already did, cf. problem one.

10.

Problem: Let \mathbb{R} denote the set of real numbers. For each of the following subsets of \mathbb{R}\times\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\leqslant 1\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) Yes, A=\mathbb{Z}\times\mathbb{R}

b) Yes, B=\mathbb{R}\times(0,1]

c) No, notice that (1,2)\in C as well as (3,4) but (3,1)\notin C.

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

e) No, notice that (1,0),(0,1)\in E but (1,1)\notin E.

Advertisements

June 13, 2010 - Posted by | Fun Problems, Munkres, Topology | , , ,

5 Comments »

  1. Cool! How do you type your proofs, by the way? LaTeX? Do you type them directly into the blog or on a word processor first? I can type enough LaTeX to get by in MHF, but for some reason I can’t figure out how to get it so I can type math symbols on a word processor.

    Comment by Ragnarok | June 13, 2010 | Reply

  2. I have a word processor called math type. But, for this you can type it directly into the blog! The code thought is not [math][/math] it’s $ latex $ (without the space between the first $ and latex). All the normal code works!

    Comment by drexel28 | June 14, 2010 | Reply

  3. This is probably just a mistake made after losing one’s mind after that problem 2, but in 3a, the proof of the contrapositive seems wrong. The statement of the converse also isn’t right.

    Comment by Teddy Ni | June 28, 2010 | Reply

  4. I am greatful with you for sharing your work. I suggest you to check the solution 4. d. I think the answer is for every (a∉A) it is true that (a^2∉B).

    Comment by Luis Felipe | July 14, 2011 | Reply

    • Ah yes, thank you. It’s a typo!

      Comment by Alex Youcis | July 14, 2011 | Reply


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: