Proof I. Suppose a and b are sets. Prove that a is a subset of b, iff the union of a and b is a subset of b (remember that iff, is a biconditional). (->)Let's assume that a is a subset of b. We need to show that any member of the union of a and b is a member of b. Suppose c (an arbitrary element) is a member of the union of a and b. That means it's either (1) a member of a or (2) a member of b, by the definition of union of sets. (1) If c is a member of a, and a is a subset of b, by the definition of subset, c is a member of b. (2) is c is a member of b, it's trivially a member of b. Either way, c is a member of b. (<-)Let's assume that a union b is a subset of b. We need to show that a is a subset of b. Suppose d (an arbitrary element) is a member of a. Then, by the definition of union, it's a member of the union of a and b. But, since the union of a and b is a subset of b, by the definition of subset, d is a member of b. Proof II. Show that U{{a,b}} = {a,b} We do this by extensionality. That is, we are going to prove that every member of U{{a,b}} is a member of {a,b} and viceversa. Suppose c is a member of U{{a,b}}. Show that it's a member of {a,b}. By the definition of union of single sets, we know that there is a set which is a member of {{a,b}} and that c is a member of that set. Call that set d. Since d is a member of the unit set {{a,b}}, by def. of unit set, we know that d = {a,b}. We also know that c is a member of d, and hence {a,b}. Suppose c is a member of {a,b}. We also know that {a,b} is a member of its unit set, {{a,b}}, by definition of unit set. Then, there is a set such that is a member of {{a,b}} and c is a member of it. By def. of union of single sets, we know that c is a member of U{{a,b}} Proof III. Show that given any two sets a and b, the intersection of their powersets is not equal to the null set. By definition, the intersection of two sets is the set that contains all members that the two sets have in common. For the intersection of two powersets to be empty, it would mean that the two powersets did not have any members in common. However, we know that powersets are sets of all the subsets of a particular set. We also know that any set has the empty set as its subset. So, to a minimun, both the powerset of a and the powerset of b will have the empty set as their member. Hence, the smallest intersection you can get from two powersets will be {{}}, the unit set of the empty set. [note, the empty set is a member, so this set has at least one member, and is thus not an empty set. After all, if you put an empty box inside another, the second one is no longer empty, righ?] Multiple choice answers: 1. b The membership relation is not transitive. Consider the element a, the set {a,b} and the set {{a,b}, c}. Is a a member of the third set? NO, only {a,b} and c are. 2. e {z : z=a v z=b} is not an arbitrary constant such as c,d,e... It's a set that contains all things that are either a or b. Hence, it's really {a,b} by the definition of pair set. {a,b} is not arbitrary in this case, it appears on line 2. 3. d The union of {1,2} and {3,4,5} is {1,2,3,4,5}. The intersection of that with {2,4,6,8} is the set which has all the common members, there- fore its's {2,4} 4. b We don't know R is antisymmetric. R is not irreflexive, since it's reflexive. It's not intransitive, since it's transitive. It's the equivalent relation by definition. b is what is left. 5. d R = { : x,y e N and y=x+2}. Rxy therefore means that x and y are numbers and that y is equal to x+2. Is it reflexive? is x = x+2? No. Is it symmetric? If y = x+2, is x = y+2? No. Is it transitive? If x = y+2 and y = z+2, is x = z+2? No, take x = 4, y = 2, z = 0. Is it intrasitive then? Is it true that if x = y+2, y = z+2, then it's definitely not the case that x = z+2? Yes. Finally, R is not connected since it's not true that for any two numbers that are not equal, either one or the other is equal to two plus the other. Consider 1 and 0. 6. b R = {: x,y e N and y > x +1}. Rxy therefore means that x and y are numbers, and that y is greater than x + 1. Is this relation reflexive? Is it true that x > x + 1? No, so you can rule out answers a and b which both require reflexivity. Is it a strict linear ordering? No, because it is not connected. It's not true that for any two numbers x and y that are not the same, either x > y+1, or y > x+1. Consider x = 0, and y = 1. Is it true that 0 > 1+1? No. Is it true that 1 > 0+1? No. That's an example that rules out answer d. What about b? For R to be a partial ordering, it must be irreflexive and transitive. Is it true that this is never true: x > x+1? Yes. Is the relation transitive? If x > y+1, and y > z+1, is x > z+1? If x is greater than (y+1), then it must be greater than any number which is less than y+1. z+1 is less than y by itself, so it must be less than y+1, so x must be greater than it. [note, this is more of an explanation than a proof] 7. c We use the axiom of extensionality to prove that two sets are identical, by proving that they have the same members. 8. e If a is a member of b, then we know b has to be a set (urelements have no members) If a is a member of b, then b must have at least a as its members, and so it's not empty. If a is a member of b, then {a} is a subset of b. Why? because all members of {a} namely a, are members of b. It follows from the def. of subset. {a} is a member of the powerset of P(b) follows from the line above, by the definition of powerset. 9. a a and b were arbitrary when it was said that they belonged to A. But was not. Once you assume that a and b are in A, the goal is to try to prove that either or holds. Assuming one of them is a mistake and makes the proof trivially. It's as if I told you this: I am going to prove to you that if I put any two students in a class, either one of them will be madly in love with the other or viceversa. Then I take two students where one of them is madly in love with the other, place them in a classroom and then tell you: "see! I told you!". You'd say I cheated and chose the two students on purpose, to make my point, and not arbitrarily. 10. a Suppose you have A be {0,1,2}. Therefore, you will have AXA be {<0,0>, <0,1>, <0,2> <1,0>, <1,1>, <1,2>, <2,0>, <2,1>, <2,2>} Then, suppose you take R (which is a subset of AXA) and let it contain <0,1>. Because R is symmetric, you must also have <1,0> in R. But wait, R is also transitive, which means that if <1,0> is in R, and <0,1> is in R, then <1,1> must be in R. Similarly with <0,0>. Now, the complete R is (as we picked it): {<0,0>, <1,1> <0,1>, <1,0>}. Is it reflexive on the field of R? Sure, the field of R is {0,1}. And it's true that R11 and R00.