Write Your Own Proofs. Amy Babich

to the set .

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

      For each x ∃ , there exists y ∈ such that x + y = 0.

      Negation: (∃x ∈ )(∀y ∈ )(x + y ≠ 0)

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

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

      For each x ∈ , for each y ∈ , if x > y then there exists z ∈ such that x > z > y.

      Negation: (∃x ∈ )(∃y ∈ )((x > y) ∧ (∀z ∈ )((x ≤ z) ∨ (z ≤ y))) There exist x ∈ , y ∈ such that x > y and for all z ∈ , x ≤ z or z ≤ y.

      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.

      (∀x ∈ )(∀y ∈ )((x > y) ⟶ (∃z ∈ )(x > z > y))

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

      ¬((∀x ∈ )(∀y ∈ )((x > y) ⟶ (∃z ∈ )(x > z > y)))

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

      (∃x ∈ )(∃y ∈ )(¬((x > y) ⟶ (∃z ∈ )(x > z > y)))

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

      (∃x ∈ )(∃y ∈ )((x > y) ∧ ¬(∃z ∈ )(x > z > y))

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

      (∃x ∈ )(∃y ∈ )((x > y) ∧ (∀z ∈ )(¬(x > z > y)))

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

      (∃x ∈ )(∃y ∈ )((x > y) ∧ (∀z ∈ )(¬((x > z) ∧ (z > y))))

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

      (∃x ∈ )(∃y ∈ )((x > y) ∧ (∀z ∈ )(¬(x > z) ∨ ¬(z > y)))

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

      (∃x ∈ )(∃y ∈ )((x > y) ∧ (∀z ∈ )((x ≤ z) ∨ (z ≤ y)))

      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