Write Your Own Proofs. Amy Babich

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

> 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 statement as either true or false. Also, write two versions of the negation of each statement, one in symbols and one in words. In Exercise 13, recall that ε is pronounced “epsilon.”

       1. (∃x ∈ )(x ∉ )

       2. (∃x ∈ ) (∀y ∈ )(y ≤ x)

       3. (∀x ∈ )((x > 0) ⟶ (x ∈ ))

      

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