Lecture 5 — Valid Arguments (cont’d), Quantified Statements
Pre-work: Video 006 (Quantified Statements). Finishes the validity material from 2026-08-03-valid-and-invalid-arguments, then opens the quantifier topic — see quantified-statements for the reference definitions and tables this lecture builds on.
Learning goals
- Apply the ideas from Lecture 4 to determine the validity of an argument, including looking for truth values that would demonstrate an argument is invalid.
- Gain fluency in translating quantified statements (English to/from symbolic form).
- Be able to determine if a quantified statement is true or false.
Common questions
What exactly is a predicate? A sentence with a finite number of variables that becomes a statement when particular values are assigned to the variables. Examples: \(x > 0\), “\(x\) divides \(y\)”.
What are the symbols for the common domains? \(\mathbb{R}\) (real), \(\mathbb{Q}\) (rational), \(\overline{\mathbb{Q}}\) (irrational), \(\mathbb{Z}\) (integer), \(\mathbb{N}\) (natural). Written out in full:
\[\mathbb{Z} = \{\dots, -2, -1, 0, 1, 2, \dots\} \qquad \mathbb{Z}^{+} = \{1, 2, 3, \dots\}\]
\[\mathbb{Z}^{\text{even}} = \{\dots, -4, -2, 0, 2, 4, \dots\} \qquad \mathbb{Z}^{\text{nonneg}} = \{0, 1, 2, 3, \dots\} = \mathbb{Z}^{\geq 0}\]
The one to be careful with is \(\mathbb{N}\): both \(\mathbb{N} = \{0,1,2,\dots\}\) and \(\mathbb{N} = \{1,2,3,\dots\}\) are in use, and the ambiguity is not settled. Prefer \(\mathbb{Z}^{\geq 0}\) or \(\mathbb{Z}^+\) when you need to be unambiguous. The nesting diagram for these sets is in quantified-statements, and the fuller domains table is there too.
Worked: determining validity of a four-premise argument
If new messages are queued, then the file system is locked. The file system is not locked if and only if the system is functioning normally. New messages will not be sent to the message buffer only if they are queued. New messages will not be sent to the message buffer. Hence the system is not functioning normally.
Let \(p\) = “the file system is locked”, \(q\) = “new messages are queued”, \(r\) = “the system is functioning normally”, \(s\) = “new messages will be sent to the message buffer”.
The third premise is the awkward one. “\(a\) only if \(b\)” means \(\sim b \to \sim a\), which is equivalent to \(a \to b\) — so “\(\sim s\) only if \(q\)” becomes \(\sim s \to q\). (Recall from conditional-statements that in \(a \to b\), \(a\) is sufficient for \(b\) and \(b\) is necessary for \(a\).)
Symbolically:
- \(q \to p\)
- \(\sim p \leftrightarrow r\)
- \(\sim s \to q\)
- \(\sim s\)
\(\therefore \sim r\)
Solution 1 — assume the conclusion is false and the premises are true
Suppose all the premises are true but the conclusion is false.
- Conclusion false \(\Rightarrow\) \(r\) is true.
- Premise 4 is true \(\Rightarrow\) \(s\) is false.
- Premise 2 is true and \(r\) is true \(\Rightarrow\) \(\sim p\) is true, thus \(p\) is false.
- Premise 1 is true and \(p\) is false \(\Rightarrow\) \(q\) is false.
But now \(s\) is false (so \(\sim s\) is true) and \(q\) is false, which makes premise 3 (\(\sim s \to q\)) false. It is impossible to make all the premises true and the conclusion false, so the argument is valid.
Figure 1: The search for an invalid row, and why it fails. Assuming the conclusion false fixes r, and each premise in turn is then forced to a single truth value with no choice left anywhere — until the last two forced values make premise 3 false, contradicting the assumption that every premise was true. No row can make the premises true and the conclusion false, so the argument is valid.
Every step above had only one value the premise permitted, so the search never branched. When a step does leave a choice open, both branches have to be followed — and a branch that survives to the end is exactly the row that shows the argument invalid.
Solution 2 — rules of inference and laws of logical equivalence
Goal: \(\sim r\).
- \(q \to p\) (premise)
- \(\sim p \leftrightarrow r\) (premise)
- \(\sim s \to q\) (premise)
- \(\sim s\) (premise)
- \(q\) — from 3 and 4 by Modus Ponens
- \(p\) — from 1 and 5 by Modus Ponens
- \((\sim p \to r) \land (r \to \sim p)\) — by definition of \(\leftrightarrow\), from 2
- \(r \to \sim p\) — from 7 by Specialization
- \(\sim r\) — from 6 and 8 by Modus Tollens (and double negation) \(\blacksquare\)
Line 9 can also be reached directly from 6 and 2 by the definition of \(\leftrightarrow\) plus double negation. See valid-argument-forms for the inference rules and determining-argument-validity for more worked comparisons of the two methods.
Quantified statements
| Symbol | Means | Associated English words |
|---|---|---|
| \(\forall\) | “for all” | all, every, any, each, none, no |
| \(\exists\) | “there exists” | there is, some, at least one, not all |
\(\in\) reads “belongs to” / “is an element of”; \(\notin\) reads “is not an element of”. The punctuation is part of the notation: \(\forall\) takes a comma, \(\exists\) takes the words “such that” (abbreviated s.t.).
| English | Symbolic |
|---|---|
| Every rational number is a real number. | \(\forall x \in \mathbb{Q}, x \in \mathbb{R}\) |
| No integer is an irrational number. | \(\forall x \in \mathbb{Z}, x \notin \overline{\mathbb{Q}}\) |
| Some real numbers are rational. | \(\exists x \in \mathbb{R}\) such that \(x \in \mathbb{Q}\) |
| Not all rational numbers are integers. | \(\exists x \in \mathbb{Q}\) such that \(x \notin \mathbb{Z}\) |
The English word does not hand you the symbol: “no”/“none” is universal, becoming \(\forall\) with the predicate negated, while “not all” is existential.
Sometimes you have to work out the quantifier from the context of the English sentence. “If an integer is a square, then it is nonnegative” names no quantifier at all, but it is a \(\forall\) statement:
\[\forall n \in \mathbb{Z}, \text{ if } n \text{ is a square, then } n \geq 0.\]
The full domains table and the negation rules are collected in quantified-statements.
Q3 from the pre-class questions
True or false? \(\exists y \in \mathbb{Z}\) such that \(y^2 - y = 0\).
The statement is true. Within the integers there is an integer for which \(y^2 - y = 0\) — choose \(y = 0\) or \(y = 1\). An existential statement only asks for one witness, so using only the numbers that make it true is allowed, and it does not matter that \(y = 2\) fails. The universal version, \(\forall y \in \mathbb{Z}, y^2 - y = 0\), is false — and \(y = 2\) is precisely what shows that.
Q4 from the pre-class questions — a universal quantified statement
True or false? \(\forall x \in \mathbb{Z}\), if \(6\) is divisible by \(x\), then \(x = 2\).
False. Consider \(x = 3\): we have \(3 \in \mathbb{Z}\), and \(6\) is divisible by \(3\), but \(3 \neq 2\). (Recall \(\sim(p \to q) \equiv p \land \sim q\) — a counterexample needs the hypothesis true and the conclusion false.)
The corrected statement is true: \(\forall x \in \mathbb{Z}\), if \(6\) is divisible by \(x\), then \(x = \pm 1\) or \(\pm 2\) or \(\pm 3\) or \(\pm 6\).
Worked: English to symbolic form
Translate, and determine truth. For (c), let \(P\) be the set of all prime numbers.
| Statement | Symbolic | T/F | Why | |
|---|---|---|---|---|
| (a) | There is a real number that is also an integer. | \(\exists x \in \mathbb{R}\) s.t. \(x \in \mathbb{Z}\) | T | take \(x = 1\) |
| (b) | If a real number is an integer, then it is a rational number. | \(\forall x \in \mathbb{R}\), if \(x \in \mathbb{Z}\) then \(x \in \mathbb{Q}\) | T | \(\mathbb{Z} \subseteq \mathbb{Q}\) |
| (c) | All prime numbers are odd. | \(\forall x \in P, x\) is odd | F | \(x = 2\) is prime but even |
| (d) | If an integer is divisible by 2 then it is divisible by 4. | \(\forall x \in \mathbb{Z}\), if \(2 \mid x\) then \(4 \mid x\) | F | \(x = 2\): \(2 \mid 2\) but \(4 \nmid 2\) |
Two notational points: \(2 \mid 6\) is read “2 divides 6” and is a statement, not a number (see divisibility-and-factorisation); and \(\{\mathbb{Z}\} \neq \mathbb{Z}\), so writing \(x \in \{\mathbb{Z}\}\) would say \(x\) is the set of integers.
Worked: symbolic to English
| Statement | English | T/F | Why | |
|---|---|---|---|---|
| (a) | \(\exists x \in \mathbb{R}\) s.t. \(x^2 = 2\) | There is a real number whose square is 2. | T | \(x = \sqrt{2}\) |
| (b) | \(\forall x \in \{1,2,3,4,5\}, x\) is prime | Every integer from 1 to 5 is prime. | F | \(1\) is not prime |
| (c) | \(\exists x \in \{1,2,3,4,5\}\) s.t. \(x > 4\) | Some integer from 1 to 5 is greater than 4. | T | take \(x = 5 > 4\) |
| (d) | \(\forall x \in \mathbb{R}\), if \(x^3 < 8\) then \(x < 2\) | If the cube of a real number is less than 8 then it is less than 2. | T | see Figure 2 |
| (e) | \(\forall x \in \mathbb{R}, (x > 0\) or \(x < 0)\) | Every real number is positive or negative. | F | \(x = 0\) is neither positive nor negative |
One counterexample is enough for (b). Both \(x = 1\) and \(x = 4\) work, but \(1\) is the more instructive one: it is neither prime nor composite, which is the trap that comes back in 2026-08-06-negation-and-multiple-quantifiers.
For (d), the graph of \(y = x^3\) shows why:
Figure 2: Why ‘if \(x^3 < 8\) then \(x < 2\)’ is true. The cube function is increasing and passes through \((2,8)\), so the whole of the curve to the left of \(x=2\) lies below \(y=8\) and none of the curve to the right does — the two conditions cut the curve at the same place.
Compare (d) with (d) of the English-to-symbolic table above, \(\forall x \in \mathbb{Z}\), if \(2 \mid x\) then \(4 \mid x\), which is false: a universal conditional needs the implication to hold at every point of the domain, and one \(x\) where the hypothesis holds and the conclusion fails sinks it.
See also
- quantified-statements · valid-argument-forms · determining-argument-validity
- 2026-08-06-negation-and-multiple-quantifiers — Lecture 6
- practice-problems — §6 Quantified Statements, with full worked solutions