Lecture 5 — Valid Arguments (cont’d), Quantified Statements

lecture
discrete-math
logic
quantifiers
valid-arguments

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

  1. Apply the ideas from last lecture to determine the validity of an argument, including looking for truth values that would demonstrate an argument is invalid.
  2. Gain fluency in translating quantified statements (English to/from symbolic form).
  3. Be able to determine if a quantified statement is true or false.

Student 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\)”.

Can you revise the symbols for the common domains? See the domains table in quantified-statements. The one to be careful with is \(\mathbb{N}\), which is defined as \(\{0,1,2,\dots\}\) by some sources and \(\{1,2,3,\dots\}\) by others — prefer \(\mathbb{Z}^{\geq 0}\) or \(\mathbb{Z}^+\) when you need to be unambiguous.

Activity 1 — 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:

  1. \(q \to p\)
  2. \(\sim p \leftrightarrow r\)
  3. \(\sim s \to q\)
  4. \(\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.

Solution 2 — rules of inference and laws of logical equivalence

Goal: \(\sim r\).

  1. \(q \to p\) (premise)
  2. \(\sim p \leftrightarrow r\) (premise)
  3. \(\sim s \to q\) (premise)
  4. \(\sim s\) (premise)
  5. \(q\) — from 3 and 4 by Modus Ponens
  6. \(p\) — from 1 and 5 by Modus Ponens
  7. \((\sim p \to r) \land (r \to \sim p)\) — by definition of \(\leftrightarrow\), from 2
  8. \(r \to \sim p\) — from 7 by Specialization
  9. \(\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

The definitions, the \(\forall\)/\(\exists\) table, the associated English words and the translation examples are all collected in quantified-statements.

Q3 from the pre-class questions

True or false? \(\exists y \in \mathbb{Z}\) such that \(y^2 - y = 0\).

Student comment: how can we say it is true for all cases if we only use numbers that will allow it to be true? What if you choose \(y = 2\)?

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. Note that 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\).

Activity 2 — 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 raised here: \(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.

Activity 3 — 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 \(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 \(y = x^3\) is increasing
(e) \(\forall x \in \mathbb{R}, (x > 0\) or \(x < 0)\) Every real number is positive or negative. F \(x = 0\) is neither

See also