1. (a) Given any two propositions P and Q, prove de Morgan’s laws in propositional logic:
:(P _ Q) = (:P) ^ (:Q);
:(P ^ Q) = (:P) _ (:Q):
(b) Prove de Morgan’s laws in set theory: Given two sets A;B X, show that
(A [ B)c = Ac Bc;
(A B)c = Ac [ Bc:
Recall that the complement of A X is the set Ac := fx 2 X : x =2 Ag.
(c) Explain brie
y how the results of part (a) and (b) are related. Notice that the
symbols _ and ^ can be easily remembered via the symbols (which you may be
more familiar with) in set theory [ and .
2. (a) Suppose p 2 N. Show that if p2 is divisible by 5 then p is also divisible by 5 (Hint:
write p = 5s + r with appropriate conditions for s and r).
(b) Prove that
p
5 is irrational.
(c) Suppose you try the same argument to prove
p
4 is irrational. The proof must fail,
but where exactly does it fail?
3. Consider a function f : X 7! Y and let A X and B X
(a) Show that f(A [ B) = f(A) [ f(B)
(b) Show that f(A B) f(A) f(B)
(c) Prove that the converse statement f(A) f(B) f(A B) is false (Hint: nd a
counterexample)
(d) Give an extra condition on f and prove that with your extra condition we have
f(A) f(B) f(A B)
(e) Consider a function f : X 7! Y . Given a subset C Y , we dene its inverse image
(or preimage) as f 1(C) := fx 2 X : f(x) 2 Cg. Notice that f 1(C) X and that
f 1(C) makes sense even if f does not have an inverse. Let C Y and D Y .
Prove that
f 1(C [ D) = f 1(C) [ f 1(D)
f 1(C D) = f 1(C) f 1(D):
Note that these set equalities above easily generalise to arbitrary (i.e. `innite’)
collections of sets.
4. Use the principle of mathematical induction to prove the following identity:
1 + r + r2 + + rn =
1 rn+1
1 r
for r 6= 1:
5. In class, we saw an axiomatic foundation of N. Making use of the notion of successor, we
can make an appropriate denition of + (i.e. addition behaves as we learnt way back).
Furthermore, we can make sense of m n when m > n. You may assume these two
facts from now on. Now, you will be guided through a foundational construction of Z.
Consider the set N N and the following relation:
(m1; n1) (m2; n2) if m1 + n2 = n1 + m2
(Perhaps after the end of this problem, I recommend coming back and trying to under-
stand why the equivalence relation dened as above would work to construct Z. Try to
draw a picture.)
(a) Show that is an equivalence relation on NN (recall the cancellative law: m+n =
m + `, for m; n; ` 2 N, then n = `)
(b) Show that if (m1; n1) (m2; n2) and (a1; b1) (a2; b2), then (m1 + a1; n1 + b1)
(m2 + a2; n2 + b2)
Call Z the set of equivalence classes in N N with respect to the relation . That
is, Z := f[(m; n)] : (m; n) 2 N Ng. Recall that [(m; n)] denotes the equivalence
class of N. We now identify a copy of N inside of Z. For every n 2 N, we declare
[(n + 1; 1)] to be the corresponding element in Z (i.e. we have set up a bijection from N
to fz 2 Z : z = [(n + 1; 1)] for some n 2 Ng). That is, when we think of the natural
number n as an integer, we use [(n + 1; 1)] 2 Z.
(c) Use part (b) to show the following: if [(m1; n1)] = [(m2; n2)] and [(a1; b1)] =
[(a2; b2)], then [(m1 + a1; n1 + b1)] = [(m2 + a2; n2 + b2)]
Part (c) shows us how to dene addition + on Z as follows: we dene [(m; n)]+[(a; b)] =
[(m + a; n + b)].
(d) Show that for every [(m; n)] 2 Z, we have [(m; n)] + [(1; 1)] = [(m; n)]
Part (d) tells us that [(1; 1)] is the additive identitiy in (Z; +); i.e. it is what we usually
denote by 0.
(e) Show that for every [(m; n)] 2 Z, we have [(m; n)] + [(n;m)] = [(1; 1)]
Part (e) tells us that the additive inverse of [(m; n)] is [(n;m)] and we write [(n;m)] =
[(m; n)]. In particular, we have made sense of what we usually denote by n for n 2 N
(f) Show that every integer [(m; n)] 2 Z is either a natural number (i.e. of the form
[(a; 1)], 0 (i.e. of the form [(a; a)]), or the opposite of a natural number. Hint:
you may nd it useful to distinguish three case: m > n, m = n and m < n.
Furthermore, remember that m n 2 N when m > n, and similarly n m 2 N
when n > m).
Part (f) tells us that Z is nothing but the natural numbers, their negatives, and zero.
That is, Z is what we usually think of as the integers.
6. In Problem 4, we constructed the integers Z. With some work we can dene the multi-
plication on Z. In this exercise, we will assume that we already have a knowledge of Z
together with + and . Our goal is to dene Q. Consider the set Z (Z n f0g) and the
following relation:
(m1; n1) (m2; n2) if m1 n2 = n1 m2:
(Again, try to draw a picture)
(a) Show that is an equivalence relation on Z (Z n f0g)
(b) Show that if (m1; n1) (m2; n2) and (a1; b1) (a2; b2), then
(m1 b1 + a1 n1; n1 b1) (m2 b2 + a2 n2; n2 b2)
and that (m1 a1; n1 b1) (m2 a2; n2 b2)
Call Q the set of equivalence classes in Z (Z n f0g) with respect to the equivalence
relaiton . Notice that the equivalence class [(m; n)] 2 Q is nothing but what we usually
denote by m
n . Part (b) allows us to dene + and on Q: for every [(m; n)]; [(a; b)] 2 Q,
we dene [(m; n)] + [(a; b)] = [(m b + a n; n b)] and [(m; n)] [(a; b)] = [(m a; n b)]
(can you motivate these denitions?)
(c) Now, we want to nd a copy of Z inside Q. For every n 2 Z, determine a rational
number [(a; b)] 2 Q that corresponds to n. (Hint: intuitively, we want to write an
integer as a fraction).
(d) Show that for every [(m; n) 2 Q, we have [(m; n)] + [(0; 1)] = [(m; n)] and [(m; n)]
[(1; 1)] = [(m; n)]
(e) For every [(m; n)] 2 Q, nd [(a; b)] 2 Q such that [(m; n)] + [(a; b)] = [(0; 1)]
(f) For every [(m; n)] 2 Qnf[(0; 1)]g, nd [(a; b)] 2 Q such that [(m; n)][(a; b)] = [(1; 1)]
0 comments