MATH 101 U 2nd Semester AY 2014-2015

Examination 2 Answer Key May 4 2015

Total: 110 points

1. Check for the following key points:
the set leading to russells paradox and the explanation why there is a paradox
the three desirable properties of an axiom system: consistency, completeness, finite describability
a statement on which property the paradox doesnt satisfy
2. Proof
Let A, B C. We wish to show that C B A A B = C.
() Consider x A B x A or x B.
Case 1: x A. Since A C, then x C.
Case 2: x B. Since B C, then x C.
Hence, A B C

Suppose x / A B x (A B)C x (AC B C ) x AC and x B C . By as-

sumption, x
/ C B x/ C or x B. But x B C , so by disjuctive syllogism, x
/ C.
Hence, C A B.

Therefore, A B = C.

() Let x C B. By assumption, x A. Hence, C B A.

Therefore C B A A B = C.
3. 3.1 Let z Z. z z = 0 and m|0. Hence, m is reflexive.
Let x, y Z such that x m y m|(x y) z Z such that x y = mz
y x = m(z), where z Z. Thus, m|y x y m x. Hence, m is symmetric.
Let x, y, w Z such that x m y and y m w m|(x y) and m|(y w)
z1 , z2 Z such that x y = mz1 and y w = mz2
x w = m(z1 + z2 ), where z1 + z2 Z. Let z = z1 + z2 . Thus , x w = mz x m y.
Hence, m is transitive.
3.2 Let a, b, c, d Z, such that a m b and c m d. Then, m|(a b) and m|(c d)
z1 , z2 Z such that a b = mz1 and c d = mz2
(a + c) (b + d) = m(z1 + z2 ) where z1 + z2 Z
m|(a + c) (b + d) (a + c) m (b + d)
3.3 z Z, z [z]. Hence, [z] 6= z Z.
Consider [z1 ], [z2 ], some z1 , z2 Z. Suppose [z1 ] [z2 ] 6= z [z1 ] [z2 ]
z [z1 ] and z [z2 ] z m z1 and z m z2
k1 , k2 Z such that mk1 = z z1 and mk2 = z z2 z1 z2 = m(k2 k1 ).
Since k2 k1 Z, then z1 m z2 . Consequently, [z1 ] = [z2 ].
[
Let x [zi ] x [zk ], some k in some indexing set I x m zk m|(x zk )
i
p Z such that x zk = mp x = mp zk . Since mp, zk Z, then x Z.

Let x Z. By the Division Algorithm, ! q,[

r Z such that x = mq + r, where 0 r < m
x r = mq m|x r x [r] x [zi ].
i
[
Therefore [zi ] = Z
i
Z
3.4 = {[0], [1], ..., [m 1]}.
m
[r] = {r + km|k Z}
The Division Algorithm states that, ! q, r Z such that x = mq + r, where 0 r < m
x r = mq. Hence r = 0, 1, 2, ..., m 1 which are the representatives of all possible
equivalence classes.
4. 4.1 Let (x, [x1 ]), (x, [x2 ]) . Hence x [x1 ] and x [x2 ] x m x1 and x m x2
k1 , k2 Z such that x x1 = mk1 and x x2 = mk2 .
x1 x2 = m(k2 k1 ), where k2 k1 Z
x1 m x2 [x1 ] = [x2 ]. Hence is a function.
 Z
4.2 Let [z] . Clearly, (z) = [z]. Hence, is onto.
m
4.3 Consider 0 and m Z. We see that (0) = [0] = [m] = (m). Hence, is not injective.
4.4 Consider the mapping : Z [z], where k 7 z + mk.
is a linear function of k.
Suppose (z1 ) = (z2 ) z + mz1 = z + mz2 z1 = z2 . Hence, is injective.
Consider y [z]. Then y = z + mk, some k Z. Hence, (k) = y. Hence, is onto.
Therefore, is bijective and consequently, [z] Z.
5. Let f be a function from C to D, and let A and B be subsets of C.
Consider y f (A B). Since f (A B) Imf , then x A B such that f (x) = y.
x A B = x A or x B = f (x) f (A) or f (x) f (B) = y = f (x) f (A) f (B).
Therefore, f (A B) f (A) f (B).
6. Let f and g be permutations of A 6= .
Show g f is a function.
It is obvious from how the functions were defined that Dgf = A.
Let (x, z1 ), (x, z2 ) g f .
Then y1 , y2 A such that (x, y1 ) f and (y1 , z1 ) g and (x, y2 ) f and (y2 , z2 ) g.
Since f is a function then y1 = y2 . We now have (y1 , z1 ), (y1 , z2 ) g.
Since g is a function, z1 = z2 .
g f is a function
Show g f is injective.
Let (g f )(x1 ) = (g f )(x2 ), some x1 , x2 A.
= g(f (x1 )) = g(f (x2 ))
Since g is injective, f (x1 ) = f (x2 ).
Since f is injective, x1 = x2 .
g f is injective.
Show g f is surjective.
Consider z A.
Since g is bijective, then y A such that g(y) = z.
Also, since f is bijective, then x A such that f (x) = y.
We now see that (g f )(x) = z.
Hence g f is surjectve.

Therefore, g f is a permutation of A.
Show (g f )1 = f 1 g1.
() Let (z, x) (g f )1 .
= (x, z) g f = y A such that (x, y) f and (y, z) g
= (y, x) f 1 and (z, y) g 1 .
= (z, x) f 1 g 1 .
(g f )1 f 1 g1.
() Let (z, x) f 1 g1
= y A such that (z, y) g 1 and (y, x) f 1 .
= (x, y) f and (y, z) g
= (x, z) g f
= (z, x) (g f )1 .

(g f )1 = f 1 g1.
7. Here, x y iff x is a multiple of y.

We consider a subset of (a) with the same number of elements as a.

Take {{1}, {2}, {3}, {1, 2}, {2, 3}, {1, 3}, {1, 2, 3}}. Below are the corresponding poset diagrams.

8. 8.1 Reflexivity: Consider (x, y) A A. Since x x and y = y, then (x, y)(x, y).
 Antisymmetry: Consider (x1 , y1 ) and (x2 , y2 ) AA such that (x1 , y1 )(x2 , y2 ) and (x2 , y2 )(x1 , y1 ).
= x1 x2 , x2 x1 , and y1 = y2 .
= x1 = x2 and y1 = y2 .
Thus, (x1 , y1 ) = (x2 , y2 ).
Transitivity: Consider (x1 , y1 ), (x2 , y2 ), (x3 , y3 ) AA such that (x1 , y1 )(x2 , y2 ) and (x2 , y2 )(x3 , y3 ).
= x1 x2 x3 and y1 = y2 = y3
Hence, (x1 , y1 )(x3 , y3 ).
Therefore, is a partial order on A A.
8.2 Below is the poset diagram.

8.3 Maximal Elements: (5, 1), (5, 2), (5, 3), (5, 4), (5, 5)
Minimal Elements: (1, 1), (1, 2), (1, 3), (1, 4), (1, 5)
8.4 is not a linear order because there are elements which are not comparable. Take (1, 1) and (1, 2)
as examples.
8.5 Take any totally ordered subset. Consider {(1, 1), (2, 1), (3, 1), (4, 1), (5, 1)}.
9. 9.1 Z has subsets which do not have a first element. Take Z which doesnt have a first element.
9.2 The Well Ordering Principle: If A is a non-empty set then there exists a total ordering of A
such that A is well-ordered.

(The version for N: Every non-empty subset T of N has a least element.)

9.3 Consider the lexicographical arrangement 0, 1, 1, 2, 2, 3, 3, ....
Q
10. Let : iI Ai F , where F is the set of all choice functions defined on {Ai |i I}.
Define (a1 , a2 , ..., an , ...) = {(A1 , a1 ), (A2 , a2 ), ..., (An , an ), ...}.
10.1 We wish to show that is a bijection.

Consider f1 = {(A1 , a1 ), (A2 , a2 ), ..., (An , an ), ...}, f2 = {(A1 , a01 ), (A2 , a02 ), ..., (An , a0n ), ...} F .
Suppose f1 6= f2 .
= k I such that (Ak , ak ) 6= (Ak , a0k ).
= ak 6= a0k
= (a1 , a2 , ..., an , ...) 6= (a01 , a02 , ..., a0n , ...)
Hence, is a function.

Let (a1 , a2 , ..., an , ..) = ((b1 , b2 , ..., bn , ...).

= {(A1 , a1 ), (A2 , a2 ), ..., (An , an ), ...} = {(A1 , b1 ), (A2 , b2 ), ..., (An , bn ), ...}
Since (Ai , ai ) 6= (Ak , bk ) for i 6= k, then it must be the case that (Ai , ai ) = (Ai , bi ), i I.
= ai = b1 , i.
Hence (a1 , a2 , ..., an , ..) = ((b1 , b2 , ..., bn , ...) making injective.

Consider f1 F . Then f1 = {(A1 , a1 ), (A2 , a2 ), ..., (An , an ), ...}, for some ai Ai . We see
that (a1 , a2 , ..., an , ..) = f1 . Hence, is injective.
Q Q
Therefore, : iI Ai F is a bijection, and iI Ai and F are equivalent.
10.2 Any choice function would do.
Take for instance {([1], 1), ([2], 2), ([3], 3), ([4], 4), ([0], 5)}.

end of answer key