## 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 and . To verify the fist we notice that

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

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

Now, we aim to prove that and . To do this we let . Now, if we’d have that and so and so and so . Conversely, if we see that . If or we’d have that or , and either way . It follows that is in neither, i.e. . The conclusion follows.

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

2.

**Problem: **Determine which of the following statements are true for all sets and . 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) and iff

b) or iff

c) and iff

d) or iff

e)

f)

g)

h)

i)

j) and implies

k) The converse of j)

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

m)

n)

o)

p)

q)

**Proof:**

a)

: Let then and thus and so

: This isn’t necessarily true. Consider .

b)

: Let then or and so . Thus, .

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

c)

: Let then and and so . Thus, .

: Clearly since

d)

: Not true. Take and

: 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 . For example, .

f) No. If then the LHS is non-empty and the RHS is.

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

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

h) Not true. Note that if this says that

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

and so by distribution this equals

j) This is true. Let , then and , thus .

k) This is not always true. Let and then the LHS and RHS of the inclusion are empty yet .

l) Then, this is true. Let , since there exists some , and thus . Thus, and so . A similar procedure shows

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

m) This is false. Let . Evidently but

n) This is true. Let then

or

.

or equivalently

or equivalently

o) This is true. Let , then:

or (and this looks weird)

or

or

or

And so . Conversely, let . Then,

(now, if , , and . But, since the first and the last are impossible since the first part of the statement says we may conclude that the second is true) thus

or

or

p) This is true. Note that iff which is true iff . But, this is true iff . (this ilast part was trick since we know that .) which is true iff .

q) This isn’t true in general. Try and

*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 , then ” and determine which of the statements are true

**b) **Do the same for the statement “If , then

**Proof:**

**a) **The contrapositive is ” If then which is false . The converse is “If , then ” which is false “

**b) **The contrapositive is “If , then which is true. The converse is ” if , then ” which is not true

4.

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

a) For every , it is true that

b) For at least one , it is true that

c) For every , it is true that

d) For at least one , it is true that

**Proof:**

I’m going to write these in set notation

**a) **

**b) **

**c) **

**d) **

5.

**Problem: **Let be a nonempty class of sets. Determine the truth of each of the following statements and their converses

**a) **

** b) **

**c) **

**d) **

**Proof:**

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

**b) **The implication is false. Consider , then clearly but

**c) **The implication is true. The converse is false though. In the above, class of sets we see that but

**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 for every then

**b) **If there exists such that , then

**c) **If for every it is true that then

**d) **If there exists some such that , then

7.

**Problem: **Given sets and , express each of the following sets in terms of and , using the smbols and .

**Proof:**

**a) **

**b) **

**c) **

8.

**Problem: **If a set has two elements, show that has four elements. How many elements does have if has one element? Three elements? No elements? Why is called the power set of ?

**Proof:**

**Lemma: **Let . Then,

**Proof: **Let where

To see that is injective suppose that , then WLOG there is some and so , thus . Next, to prove surjectivity let and let , evidently . It follows that is a bijection, and the lemma is proved.

It follows that if then .

*Remark:* Alternatively, one may find a recurrence relation solution to this problem. Namely, let . Then, if one paritions into those sets which contain and those that don’t one can see that each block of the partition has elements, and thus

and thus noting that one may conclude that

9.

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

**a) **

**Claim: **Let be a class of subsets of some universal set , then

**Proof:** If then for some . Thus, and so . Conversely, suppose that then there exists some such that . It follows that and so finally . The conclusion follows.

**Corollary:**

**Proof:** We merely note that

which by our last proven claim is

10.

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

**a) **

**b) **

**c) **

**d) **

**e) **

**Proof:**

**a) **This is, namely

**b) **This is, namely

**c) **This is not. To see this suppose that . We see that and thus . Also, and so . But, and thus , which is a contradiction.

**d) **This is, namely

**e) **This is not, using the same argument as in c), first noting that

No comments yet.

## Leave a Reply