Munkres Chapter 1 Section 1
Problem: Prove the distributive laws for union and intersection, and prove DeMorgan’s laws.
a) We claim that . To see this we denote the right side by and the left side by , then if and only if but by the distributive laws of the “and” and “or” operators (just draw a simple truth table) this is equivalent to
but this is just the logical statement that . The exact same, (but reversing the arrows…haha not category theory) gives that . It follows that as desired.
b) We now claim that . Once again we denote the LHS by and the RHS by . Then, implies that , which implies that . 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
which says that . Once again, using the exact same logic in reverse we get that from where it follows that .
c) We claim in general that if are subsets of some universal set , then
To see this we once again denote the LHS by and the RHS by . Then, if then and so for some . It follows that and thus . Conversely, if then f0r some and thus and so and so . The conclusion follows.
We now claim that
To do this we note that
And thus if we keep to our LHS-RHS notation we see that from where it follows from elementary set theory that .
Problem: Determine which of he following statements are true for all sets (contained in some universal set ). 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 or .
k) The converse of j)
l) The converse of j), assuming that and are non-empty.
a) The right hand implication is clearly true since . That said, the left hand implication is false. Clearly given any non-empty set we have that but it is not true that .
b) If the LHS statement is true then for each we have that and so , i.e. . The other direction is not correct though. Consider the sets then but it is not true that .
c) This two-sided implication is true. To see the right implications we note that if then and so that and so it follows that . Conversely, if then for each we have that and so .
d) The right hand implications is not false. Take for example and . Then it is true that but it is not true that . 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 as the universal set. Then, if and then which is equal to . The inclusion is true thought since means that or that but since it follows that . Thus, .
f) Let’s just see what the LHS is equal to. but this is equal to (DeMorgan’s law) but this is equal but this is equal to since the left set is a subset of . It clearly follows that but the inclusion may be strict by considering
g) The LHS is equal to and the RHS is which is equal to . Thus, they are, in fact, equal.
h) The RHS is (prime denotes complement in the universal set) which is equal to by distributivity laws . The LHS is . Clearly the neither inclusion holds (in general) since the LHS is always contains elements of and the RHS is contains only elements of (if it contains any).
i) The LHS is which distributing gives which is equal to which is equal . So, yes, they are equal.
j) This implication is true. If then and thus and so
k) No, the converse is not true. Consider then . But, clearly is not true.
l) In this case it is true. Let then for some (we know there exists some, since ) we have that and so . The other direction works the same.
m) This equality is false. Consider the intervals . Note then that (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 . To see this we note that if then we may assume WLOG that and thus and so and so
n) This is true. To see this we note that if then and so and so in particular or . Conversely, if then and which says that and and so and so that
o) This is true. Note that if and only if which is true if and only if which is true if and only if or and so
p) This is true. Note that if and only if which is true if and only if . But, this is true if and only if (because by the first part we must have and so the last two are just “tricks”) which is true if and only if which is just a fancy way of saying
q) This equality does not hold in general. If then but . The, inclusion does hold though. To see this let then and so in particular but and so
Remark: God that was horrendous…
a)Write the contrapostive and converse of the following statement: “If latex x^2-x>0$” and determine which (if any) of the three statements are true.
b) Do the same for the statement “if then .
a) Contrapositive says then . The negation says that if then
We note that then . 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.
Problem: Let and $laetx B$ 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
a) There exists some such that
b) For every it is true that
c) There exists some such that
d) For every it is true that
Problem: Let be a non-empty collection of sets. Determine the truth of each of the following statements about their converses:
a) Of course this is true, it’s the definition.
b) Clearly not. Take the elements of 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.
Problem: Write the contrapositive of each of the statements of Exercise 5.
a) If for every it is true that then
b) If for some it is true that then
c) If for some then
d) IF for every then
Problem: Given sets and , express each of the following sets in terms of and using the symbols and .
a) The set is
b) The set is
c) The set is
Problem: If a set has two elements, show that has four elements. How may elements does have if has one element? Three elements? No elements? Why is called the power set of ?
Proof: We prove that . To do this we let .
Partition into two blocks, namely
Note, that clearly . Now, given we have two choices, either or . Thus, excluding for a second each element of is paired with an element of is a unique way. It follows that . But, noting that in fact for each we have that it follows that . Thus,
Thus, noting that we can easily prove by induction that
Problem: Formulate and prove a generalized version of DeMorgan’s theorem.
Proof: Already did, cf. problem one.
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
c) No, notice that as well as but .
e) No, notice that but .