Amy Babich

Write Your Own Proofs


Скачать книгу

For all ximage, there exists yimage such that for all zimage, z < y or z > x.

      32. For all ximage, if ximage then for all kimage, if kximage then k = 0.

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

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

      35. There exists ximage such that x2image.

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

      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 xA, xB. The symbol AB denotes the statement that A is a subset of B.

image

      Remarks. In mathematical definitions, it is customary to write “if” when we mean “if and only if.” Thus the foregoing definition really means that AB if and only if, for all xA, xB.

      Notice that A image B if and only if there exists x ∈ A such that x ∉ B.

      Set builder notation. Let A be a set, and for all xA. let p(x) be a proposition about, x. We can specify a set S as follows:

      S = {xA | p{x)}. The sentence "S = {xA | 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 = {ximage | x < 6}.

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

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

      Remark. In set builder notation, the set {xA | p(x)} is the same as the set {yA | p(y)}. Thus, for example, the set {nimage | there exists kimage such that n = 3k} is the same as {kimage | there exists nimage 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 = {ximage | x ≤ 17} introduces the set S as a subset of the familiar set of natural numbers, image. We could define a set T as {xS | 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