Amy Babich

Write Your Own Proofs


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

to the set image.

       2. Statement: (∀x ∈ image)(∃y ∈ image)(x + y = 0)

      For each ximage, there exists yimage such that x + y = 0.

      Negation: (∃ximage)(∀yimage)(x + y ≠ 0)

      There exists ximage such that for all yimage, x + y ≠ 0.

       3. Statement: (∀x ∈ image)(∀y ∈ image)((x > y) ⟶ (∃z ∈ image)(x > z > y))

      For each ximage, for each yimage, if x > y then there exists zimage such that x > z > y.

      Negation: (∃ximage)(∃yimage)((x > y) ∧ (∀zimage)((xz) ∨ (zy))) There exist ximage, yimage such that x > y and for all zimage, xz or zy.

      Remark. The third example is more complicated than the other two. Hence we offer a step-by-step analysis of the process of negation.

      In Example 3, we negate the following statement.

      (∀ximage)(∀yimage)((x > y) ⟶ (∃zimage)(x > z > y))

      That is, we produce a statement that is logically equivalent to the following.

      ¬((∀ximage)(∀yimage)((x > y) ⟶ (∃zimage)(x > z > y)))

      For our first step, we change the quantifiers at the beginning of the sentence and move the symbol ¬ to their right.

      (∃ximage)(∃yimage)(¬((x > y) ⟶ (∃zimage)(x > z > y)))

      Notice that the statement governed by the two initial quantifiers has the form ¬(pq). Since ¬(pq) is logically equivalent to p ∧ ¬q, we obtain the following sentence.

      (∃ximage)(∃yimage)((x > y) ∧ ¬(∃zimage)(x > z > y))

      Now we transform the sentence ¬(∃zimage)(x > z > y) by changing the quantifier and moving ¬ to the right.

      (∃ximage)(∃yimage)((x > y) ∧ (∀zimage)(¬(x > z > y)))

      Since x > z > y is shorthand for (x > z) ∧ (z > y), we have the following sentence.

      (∃ximage)(∃yimage)((x > y) ∧ (∀zimage)(¬((x > z) ∧ (z > y))))

      Since ¬(pq) is logically equivalent to ¬p ∧ ¬q, we transform the sentence as follows.

      (∃ximage)(∃yimage)((x > y) ∧ (∀zimage)(¬(x > z) ∨ ¬(z > y)))

      Finally, since ¬(a > b) can be written more simply as ab, we get the sentence below.

      (∃ximage)(∃yimage)((x > y) ∧ (∀zimage)((xz) ∨ (zy)))

      Remark. Every step in simplifying a negation moves the symbol ¬ further to the right. When all the ¬ symbols are as far to the right as possible, we have simplified the negation as much as possible.

      Exercises (1.7) Classify each