The Lumenary · Grades 6–8

Set-builder notation, quantifiers and infinite sets

Name: ______________________

Date: ______________________

You will learn to

Read and write sets in set-builder notation, such as $\{n \in \N : n \text{ is even}\}$
Translate between everyday sentences and statements using $\forall$ and $\exists$ , and negate them correctly
Explain why the order of mixed quantifiers matters, and why a statement about every element of the empty set is true
Prove that $\N$ and the even numbers are infinite, and explain why “infinity” is not a very large natural number

1.
List the elements of $\{n \in \N : n^2 < 30\}$ . (Remember that $\N = \{0, 1, 2, \dots\}$ .)
2.
Which sentence is the denial (negation) of “Every train from Mombasa arrived on time today”?
- A.No train from Mombasa arrived on time today.
- B.At least one train from Mombasa did not arrive on time today.
- C.Every train from Mombasa arrived late today.
- D.At least one train from Mombasa arrived on time today.
3.
Is the statement “Every element of the empty set is greater than $100$ ” true or false?
- A.True
- B.False, because no element is greater than $100$
- C.Neither: the statement is meaningless
4.
Which of these statements are true? Choose all that apply.
- A. $\forall x \in \Z\ \exists y \in \Z,\ y < x$
- B. $\exists y \in \Z\ \forall x \in \Z,\ y < x$
- C. $\exists y \in \N\ \forall x \in \N,\ y \le x$
- D. $\forall x \in \N\ \exists y \in \N,\ y < x$
5.
Let $S$ be the set of students in a class, and let $M(t, s)$ mean “ $t$ has met $s$ ”. Which statement says “There is a student whom every student in the class has met”?
- A. $\exists s \in S\ \forall t \in S,\ M(t, s)$
- B. $\forall t \in S\ \exists s \in S,\ M(t, s)$
- C. $\exists s \in S\ \exists t \in S,\ M(t, s)$
- D. $\forall s \in S\ \forall t \in S,\ M(t, s)$
6.
Which sentence is the denial of “Every country has a city with more than a million people”?
- A.Some country has no city with more than a million people.
- B.Every country has a city with at most a million people.
- C.No country has a city with more than a million people.
- D.Some country has a city with at most a million people.
7.
How many elements does the set $\{x \in \Z : -3 \le 2x + 1 \le 7\}$ have?
8.
Lena wants to prove that the even numbers are infinite. She is given a non-empty finite list of even natural numbers whose largest entry is $M$ . Which number is certainly an even number missing from the list, whatever the list is?
- A. $M + 1$
- B. $M + 2$
- C. $2M$
- D. $M / 2$
9.
Which Lean statement says that there is no largest natural number?
- A.∀ x : Nat, ∃ y, y > x
- B.∃ y : Nat, ∀ x, y > x
- C.∀ x y : Nat, y > x
- D.∃ x y : Nat, y > x
10.
Pierre de Fermat believed (around 1640) that every number $2^{2^k} + 1$ is prime. Write first_counterexample(prop, limit), which returns the first k in range(limit) for which prop(k) is False, or None if there is none. Then use it with the is_prime function provided to test Fermat's claim for $k = 0, 1, \dots, 5$ .
Computational — Practice

Answer key — Set-builder notation, quantifiers and infinite sets

1.
$0^2, 1^2, \dots, 5^2$ are $0, 1, 4, 9, 16, 25$ , all less than $30$ , while $n \ge 6$ gives $n^2 \ge 36$ . So the set is $\{0, 1, 2, 3, 4, 5\}$ .
2.
By Theorem 1(a), $\neg(\forall x,\ P(x))$ is $\exists x,\ \neg P(x)$ : “at least one train from Mombasa did not arrive on time today”.
3.
The denial would be “there is an $x \in \varnothing$ with $x \le 100$ ”, which is false because $\varnothing$ has no elements. So the statement is true (vacuously). By the same reasoning “every element of $\varnothing$ is less than $0$ ” is true as well — no contradiction, since there is nothing in $\varnothing$ that would have to satisfy both.
4.
(a) is true ( $y = x - 1$ ). (b) is false: $x = y$ would give $y < y$ . (c) is true: $y = 0$ . (d) is false: $x = 0$ has no smaller natural number. Notice how the answers depend on both the order of the quantifiers and the set ( $\Z$ or $\N$ ).
5.
“There is a student $s$ such that every student $t$ has met $s$ ”: $\exists s \in S\ \forall t \in S,\ M(t, s)$ . The version $\forall t\ \exists s$ is weaker: everyone has met someone.
6.
In symbols the statement is $\forall c\ \exists t,\ t \text{ is a city of } c \text{ with more than a million people}$ . Its denial is $\exists c\ \forall t,\ \neg(\dots)$ : some country has no city with more than a million people.
7.
$-3 \le 2x + 1 \le 7$ means $-4 \le 2x \le 6$ , i.e. $-2 \le x \le 3$ . So the set is $\{-2, -1, 0, 1, 2, 3\}$ , with $6$ elements.
8.
$M + 2$ works: it is even because $M$ is, and $M + 2 > M \ge$ every entry, so it is not on the list. ( $2M$ fails for the list $0$ , which shows why proofs must cover every case — including the smallest.) Since every finite list misses an even number, the even numbers cannot be listed: they are infinite.
9.
∀ x : Nat, ∃ y, y > x — for every natural number there is a bigger one, so none is the largest. The swapped statement ∃ y, ∀ x, y > x is false, as Theorem 2 shows.
10.
```
def is_prime(n):
    if n < 2:
        return False
    d = 2
    while d * d <= n:
        if n % d == 0:
            return False
        d += 1
    return True


def first_counterexample(prop, limit):
    for k in range(limit):
        if not prop(k):
            return k
    return None
```
first_counterexample(lambda k: is_prime(2 ** (2 ** k) + 1), 6) returns 5: the numbers $3, 5, 17, 257, 65537$ are prime, but $2^{32} + 1 = 4294967297 = 641 \cdot 6700417$ , as Leonhard Euler discovered in 1732. One counterexample refutes “for all $k$ ”. Notice also that a search returning None (as for $n^2 \bmod 4$ ) proves nothing beyond the cases it checked.