USA: +1(669)289-8683 
Sign in
<<
p
>p
>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 de ne its inverse image
(or preimage) as f1(C) := fx 2 X : f(x) 2 Cg. Notice that f1(C) X and that
f1(C) makes sense even if f does not have an inverse. Let C Y and D Y .
Prove that
f1(C [ D) = f1(C) [ f1(D)
f1(C \ D) = f1(C) \ f1(D):
Note that these set equalities above easily generalise to arbitrary (i.e. `in nite’)
collections of sets.
4. Use the principle of mathematical induction to prove the following identity:
1 + r + r2 + + rn =
1 r
n+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 de nition 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 de ned 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 de ne addition + on Z as follows: we de ne [(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 de ne 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 de ne 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 de ne + and on Q: for every [(m; n)]; [(a; b)] 2 Q,
we de ne [(m; n)] + [(a; b)] = [(m b + a n; n b)] and [(m; n)] [(a; b)] = [(m a; n b)]
(can you motivate these de nitions?)
(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)]
1. (a) Given any two propositions P and Q, prove de Morgan’s laws in propositional logic:
-(PVQ) = (-P)^(-Q),
-(PAQ) = (-P) v(Q).
(b) Prove de Morgan’s laws in set theory: Given two sets A, B C X, show that
(AUB) = An BC,
(An B) = AⓇUB
Recall that the complement of A CX is the set Aº := {1 € X : * & A}.
(c) Explain briefly how the results of part (a) and (b) are related. Notice that the
symbols V and can be easily remembered via the symbols (which you may be
more familiar with) in set theory U and n.
2. (a) Suppose PE N. Show that if p’ 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 V5 is irrational.
(c) Suppose you try the same argument to prove V7 is irrational. The proof must fail,
but where exactly does it fail?
3. Consider a function f :X HY and let ASX and B CX
(a) Show that f(AUB) = f(A) U f(B)
(b) Show that f(An B) Cf(A) n f(B)
(c) Prove that the converse statement f(A) n f(B) Cf(An B) is false (Hint: find a
counterexample)
(d) Give an extra condition on f and prove that with your extra condition we have
f(A) n f(B) = f(ANB)
(e) Consider a function f : X HY. Given a subset C CY, we define its inverse image
(or preimage) as f-(C):= {r € X : f(x) € C}. Notice that f-1(C) X and that
F-1(C) makes sense even if f does not have an inverse. Let C C Y and D CY.
Prove that
f'(CUD) = f-(CUF-‘(D)
f-(COD) = f-‘(C) nf-(D).
Note that these set equalities above easily generalise to arbitrary (i.e. ‘infinite’)
collections of sets.
4. Use the principle of mathematical induction to prove the following identity:
1 – pp+1
1+r+p2 + … + pelle
for r #1.
1-r
=
5. In class, we saw an axiomatic foundation of N. Making use of the notion of successor, we
can make an appropriate definition 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:
(mi, ni) ~ (m2, n2) if mi + n2 = n1 + m2
(Perhaps after the end of this problem, I recommend coming back and trying to under-
stand why the equivalence relation defined as above would work to construct Z. Try to
draw a picture.)
(a) Show that ~ is an equivalence relation on Nx N (recall the cancellative law: m+n=
m+l, for m, n, l e N, then n=l)
(b) Show that if (mi, ni) ~(m2, n2) and (a1, bı) ~ (a2, b2), then (mi + a1, n1 +bi) ~
(m2 + a2, n2 + b2)
Call Z the set of equivalence classes in N ~ N with respect to the relation ~. That
is, Z := {[(m,n)] : (m, n) E N N}. Recall that [(m,n)] denotes the equivalence
class of N. We now identify a copy of N inside of Z. For every n e N, we declare
((n +1,1)] to be the corresponding element in Z (i.e. we have set up a bijection from N
to {z e Z: z= ((n + 1, 1)] for some n e N}). That is, when we think of the natural
number n as an integer, we use ((n +1,1)] e Z.
–
Prove that
f-‘(CUD) = f (C)uf-‘(D)
f-‘(COD) = f-(C) nf-(D).
Note that these set equalities above easily generalise to arbitrary (i.e. ‘infinite’)
collections of sets.
4. Use the principle of mathematical induction to prove the following identity:
1+r+p? +…+mon
1 – poh+1
for r +1.
1-r
5. In class, we saw an axiomatic foundation of N. Making use of the notion of successor, we
can make an appropriate definition 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 x N and the following relation:
(mi, ni) ~ (m2, n2) if mi + n2 = n1 + m2
(Perhaps after the end of this problem, I recommend coming back and trying to under-
stand why the equivalence relation defined as above would work to construct Z. Try to
draw a picture.)
(a) Show that is an equivalence relation on NxN (recall the cancellative law: m+n=
m+l, for m, n, l e N, then n= l)
(b) Show that if (mi, n1) ~ (m2, n2) and (a1, b1) ~ (a2, b2), then (mi + 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:= {[(m, n)] : (m,n) E N N}. Recall that [(m, n) denotes the equivalence
class of N. We now identify a copy of N inside of Z. For every n e N, we declare
[(n +1,1)] to be the corresponding element in Z (i.e. we have set up a bijection from N
to {z e Z: z = [(n +1,1)] for some n e N}). That is, when we think of the natural
number n as an integer, we use [(n +1,1)] € Z.
(c) Use part (b) to show the following: if [(mi, n1)] = [(m2, n2)] and [(a1, b1)]
[(az, b2)], then [(mi + a1, ni+b1)] = [(m2 +22, N2 + b2)]
Part (c) shows us how to define addition + on Z as follows: we define [(m, n)]+[(a,b)] =
[(m+a,n+b)]
(d) Show that for every [(m, n)] = 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) € 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 EN
(f) Show that every integer [(m, n)] € 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 find it useful to distinguish three case: m > n, m = n and m n, and similarly n – mEN
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 define 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 define Q. Consider the set Zx (Z\{0}) and the
following relation:
(m1, nu) ~ (m2, n2) if min2 = n1m2.
(Again, try to draw a picture)
(a) Show that is an equivalence relation on Zx (Z {0})
(b) Show that if (mi, ni) ~ (m2, n2) and (ai, bı) ~ (a2, b2), then
(m1.b1+a1.n1, N1.b) ~(m2.b2 + 22. n2, n. 62)
and that (m1.21,n1.b) ~(m2.09, n2 · 62)
Call Q the set of equivalence classes in Zx (Z\{0}) with respect to the equivalence
relaiton ~. Notice that the equivalence class [(m, n)) € Q is nothing but what we usually
denote by . Part (b) allows us to define + and · on Q: for every [(m, n)], [(a,b)] E Q,
we define [(m, n)] + [(a,b)] = [(m·b+an, n – b)] and [(m, n)] · [(a,b)] = [(m·a, n- b)]
(can you motivate these definitions?)
(C) Now, we want to find a copy of Z inside Q. For every n e Z, determine a rational
number [(a,b)] € Q that corresponds to n. (Hint: intuitively, we want to write an
integer as a fraction).
(d) Show that for every [(m, n) E Q, we have [(m, n)] + [(0,1)] = [(m, n)] and [(m, n)].
[(1,1)] = [(m, n)]
6. In Problem 4, we constructed the integers Z. With some work we can define the multi-
plication on
. on Z. In this exercise, we will assume that we already have a knowledge of Z
together with + and .. Our goal is to define Q. Consider the set Zx (Z\{0}) and the
following relation:
(m1, nu) ~ (m2, n2) if mi.n2 = n1.m2.
(Again, try to draw a picture)
(a) Show that is an equivalence relation on Zx (Z {0})
(b) Show that if (mi, ni)~ (m2, n2) and (ai, bı) ~ (a2, b2), then
(m1.b1+a1.n1, N1.b) ~(m2.b2 + 22. n2, n. 62)
and that (m1.01, n. b) ~(m2.12, 12 · 62)
Call Q the set of equivalence classes in Zx (Z\{0}) with respect to the equivalence
relaiton ~. Notice that the equivalence class [(m, n)] Q is nothing but what we usually
denote by m Part (b) allows us to define + and on Q: for every [(m, n)], [(a,b)] E Q,
we define (m, n)] + [(a,b)] = [(m.b+a.n, n.b)] and [(m, n)] · [(a,b)] = [(m.a,n. b)]
(can you motivate these definitions?)
(C) Now, we want to find a copy of Z inside Q. For every n e Z, determine a rational
number [(a, b)] € Q that corresponds to n. (Hint: intuitively, we want to write an
integer as a fraction).
(d) Show that for every [(m,n) € Q, we have [(m,n)] + [(0,1)] = [(m, n)and [(m,n)] ·
[(1,1)] = [(m,n)]
(e) For every [(m, n)] € Q, find [(a,b)] € Q such that [(m, n)] + [(a, b)] = [(0,1)]
(f) For every [(m, n)] € Q\{[(0,1)]}, find [(a,b)) € Q such that [(m, n)]-[(a,b)] = [(1,1)]
