For all x ∈
32. For all x ∈
33. There exists x ∈
34. There exists x ∈
35. There exists x ∈
36. For all x, y ∈
Chapter 2
Proving Theorems about Sets
Schoolmaster: “Suppose x is the number of sheep in the problem.”
Pupil: “But, Sir, suppose x is not the number of sheep?”
(I asked Prof. Wittgenstein was this not a profound philosophical joke, and he said it was.)
J. E. Littlewood, Littlewood’s Miscellany
“She’s in that state of mind,” said the White Queen, “that she wants to deny something — only she doesn’t know what to deny!”
Lewis Carroll, Through the Looking Glass
“Atomics is a very intricate theorem and can be worked out with algebra but you would want to take it by degrees because you might spend the whole night proving a bit of it with rulers and cosines and similar other instruments and then at the wind-up not believe what you had proved at all. If that happened you would have to go back over it till you got to a place where you could believe your own facts and figures as delineated from Hall and Knight’s Algebra and then go on again from that particular place till you had the whole thing properly believed and not have bits of it half-believed or a doubt in your head hurting you like when you lose the stud of your shirt in bed.”
“Very true,” I said.
Flann O’Brien, The Third Policeman
Definition. Let A and B be sets. A is a subset of B if for all x ∈ A, x ∈ B. The symbol A ⊆ B denotes the statement that A is a subset of B.
Remarks. In mathematical definitions, it is customary to write “if” when we mean “if and only if.” Thus the foregoing definition really means that A ⊆ B if and only if, for all x ∈ A, x ∈ B.
Notice that A
Set builder notation. Let A be a set, and for all x ∈ A. let p(x) be a proposition about, x. We can specify a set S as follows:
S = {x ∈ A | p{x)}. The sentence "S = {x ∈ A | p(x)}" is read aloud as, "S equals the set of all x in A such that p of x."
Examples (2.1)
1. Let B = {1, 2, 3, 4, 5}. The set B may be written in set builder notation as B = {x ∈
2. Let E be the set of even positive integers. The set E may be written in set builder notation as E = {n ∈
3. The empty set may be written as {x ∈
Remark. In set builder notation, the set {x ∈ A | p(x)} is the same as the set {y ∈ A | p(y)}. Thus, for example, the set {n ∈
Exercises (2.1) Describe each set using set builder notation. There is more than one correct answer for each question.
1. {1, 7, 9}
2. the set of odd positive integers
3. the set of integer multiples of 17
4. {4, – 4}
5. {5}
6. the set of positive integers greater than 1729
Remark. Notice that when defining a new set via set builder notation, the new set is always a subset of a previously defined set. For example, the notation S = {x ∈
Although we have not rigorously defined the word “set,” not every imaginable aggregation is a set. When Georg Cantor invented set theory in 1895, he mistakenly