Write Your Own Proofs. Amy Babich

For all x ∈ , there exists y ∈ such that for all z ∈ , z < y or z > x.

      32. For all x ∈ , if x ∉ then for all k ∈ , if kx ∈ then k = 0.

      33. There exists x ∈ such that for each y ∈ , y < x or y > x.

      34. There exists x ∈ such that x ≠ 0 and for all y ∈ , if y > 0 then y > x.

      35. There exists x ∈ such that x² ∉ .

      36. For all x, y ∈ , if xy = 0 then x = 0 or y = 0.

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 B if and only if there exists x ∈ A such that x ∉ B.

      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 ∈ | x < 6}.

       2. Let E be the set of even positive integers. The set E may be written in set builder notation as E = {n ∈ | (∃k ∈ )(n = 2k)}.

       3. The empty set may be written as {x ∈ | x > 2 and x < 2}.

      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 ∈ | there exists k ∈ such that n = 3k} is the same as {k ∈ | there exists n ∈ such that k = 3n}. The names of the variables do not matter. The variables in set builder notation are what we call “dummy variables.”

      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 ∈ | x ≤ 17} introduces the set S as a subset of the familiar set of natural numbers, . We could define a set T as {x ∈ S | x > 5}, thus introducing T as a subset of S. We do not usually employ such notation as {x | x > 5}, for the following reason.

      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