Transcript Exercises for CS3511 Week 31 (first week of practical)

Exercises for CS1512
Week 12
Sets
(questions)
1. List the members of these sets:
a. {x | x is an integer  x >0  x<12}
b. {x | x is the square of an integer and x<100}
c. {x | x is an integer such that x2 = 2}
2. For each of the following sets, determine
whether 2 is an element of that set
a. {2,{3}}
b. {{2},{2,{2}}}
c. {{{2}}}
3. Give the cardinality of the sets in questions 1
and 2.
4. Which of the following statements are true?
a.
b.
c.
d.
e.
f.
g.
1{0,1,2,3}
{0,1,2}{0,1,2,3}
{0,1,2}{0,1,2,3}
0
{0} 
{} {}
{}
5. Suppose AB and BC. Prove or disprove
a. AC.
b. ABC
c. CDD
d. C  P(C)
4. Translate into English and determine the
truth value of each of the following: (R is
the set of real numbers.)
a.
b.
c.
d.
e.
xR(x2x)
xR(x2-1)
xR(x2x)
xRyR(y=x+1)
xRyR(y=x2)
5. This exercise explores Russell’s paradox.
General: This is just to keep good students interested. students have
been exposed to a very informal brand of set theory, in which certain
questions have no definite answer. It’s only when set theory is
axiomatised that Russell’s paradox really arises as an undeniable
problem.
First some easy bits:
a.
b.
c.
Is it true that {a}{a}? Why (not)?
Students may think this easier than it is. Normally of course it’s false, but what
if a is between an infinite number of pairs of brackets? Better not mention this
and just observe that a<>{a}.
Define S={x|x{a,b,c}}. What is S? {a,b,c}
Define T={a,b,c,d,e}. What is {xT|x{a,b,c}}. {d,e}
Now for the hard part:
d. Define V={x|xx}. Is VV? Why (not)? Can’t tell! Using the defining property of
the set to answer the question, you obtain VV VV, which doesn’t tell you
much.
e.
Define W={x|xx}. Is WW? Why (not)? This is Russell’s paradox. Using the
defining property of the set, you derive that WW and WW. (Proving both p
and p is what mathematicians call a paradox.)