SUNY Geneseo Department of Mathematics
Monday, March 1
Math 239 03
Spring 2021
Prof. Doug Baldwin
(No.)
Based on section 2.4 of our textbook and this discussion of advanced topics in quantifiers.
Write each of the following statements using the quantifier symbols “∃” and “∀” instead of English words. For statements that involve the word “not,” try to find two symbolic forms, one that uses the logical “not” symbol (“¬”) and one that doesn’t:
“For every natural number there is some greater natural number.”
The basic solution looks like this: (∀ n ∈ ℕ)((∃ x ∈ ℕ)(x > n))
The double parentheses around “((∃ x ∈ ℕ)(x > n))” emphasize that it is the statement quantified by “(∀ n ∈ ℕ),” i.e., that quantifiers apply left-to-right. Normally that’s implicit, and one would just write (∀ n ∈ ℕ)(∃ x ∈ ℕ)(x > n).
“It’s not the case that for every natural number there is some smaller natural number.”
Our first version made the “not” explicit: ¬(∀ n ∈ ℕ)(∃ x ∈ ℕ)(x < n)
Then we eliminated the “not” by realizing that the negation of a universal quantifier is an existential one, and vice versa: (∃ n ∈ ℕ) ¬((∃ x ∈ ℕ)(x < n)) ≡ (∃ n ∈ ℕ) ((∀ x ∈ ℕ)( x ≥ n)). In words this last statement is “there exists some natural number n such that all natural numbers x are greater than or equal to n,” which is a reasonable equivalent to “it’s not the case that for every natural number there is some smaller natural number.”
“For every pair of real numbers x and y there is some other real number between x and y.”
Our first version was (∀ x ∈ ℝ)(∀ y ∈ ℝ)(∃ n ∈ ℝ)(x < n < y), or equivalently, only use 1 quantifier for both x and y: (∀ x,y ∈ ℝ)(∃ n ∈ ℝ)(x < n < y).
This is close, but the part about x being less than y doesn’t work for all x and y values. We need some way to restrict y to only those reals greater than x.
One way is to define a set of reals greater than y right where we need it: (∀ x ∈ ℝ)(∀ y ∈ {z∈ℝ|z>x})(∃ n ∈ ℝ)(x < n < y).
But using set builder notation inside a quantifier is hard to read. We could break it out of the quantifier by defining some additional notation, but that’s also not completely readable: “For any real number x, define G(x) to be the set {z∈ℝ|z>x}. Then (∀ x ∈ ℝ)(∀ y ∈ G(x))(∃ n ∈ ℝ)(x < n < y).”
The most popular way to solve the problem would be with a conditional: “(∀ x ∈ ℝ)(∀ y ∈ ℝ)(if x < y, then (∃ n ∈ ℝ)(x < n < y)).”
“Some integer is even.”
This might look like there’s only one quantifier, but the definition of “even” has a quantifier in it: n is even if and only if there exists some integer k such that n = 2k.
So the statement “some integer is even” looks like this: (∃ n ∈ ℤ) (∃ m ∈ ℤ)(n = 2m)
Look at general patterns for proving quantified statements.
There’s no additional reading for this. The reading you’ve already done in section 2.4 sets the stage for it, but doesn’t look at proofs quite as explicitly as I want to.
But do look at and share ideas on the proof-related questions in the advanced quantifiers discussion.