Notes on Logic: Predicates, Domains, Truth Sets, and Quantifiers

Predicates, statements, and domains

A statement can be true or false; a predicate P(x) becomes a statement when you plug in a specific x from a domain D. The domain is the set of values over which x ranges (the ‘universe’ of discourse).
Domain is often denoted as D (or a particular symbol like the real numbers R, integers Z, positive integers Z+, etc.).
Truth set vs false set:
- Truth set of a predicate P with domain D is the set of all x in D for which P(x) is true:
  \text{Truth set} = {x \in D \mid P(x) \text{ is true} }.
- If you instead collect where P(x) is false, you get the (not usually named) false set.
Example predicate (from the transcript):
- Let P(x) be x^2 > x. This is a predicate on x.
- On a finite domain D = {1,2,3,4,5}, evaluate P(x):
- P(1) is false since 1^2 = 1 is not greater than 1.
- P(2) is true since 4 > 2.
- P(3) is true since 9 > 3.
- P(4) is true since 16 > 4.
- P(5) is true since 25 > 5.
- So the truth set is {2,3,4,5} and the false set is {1} for this domain.
Substitution of the domain for the predicate: you can evaluate the predicate by substituting elements from the given domain into x and checking truth values.
Related note from the transcript: sometimes students confuse whether a given statement with a fixed finite domain is true; domain choice matters for truth values (e.g., positive integers vs all integers vs reals).

Universal vs existential quantifiers

Quantifier meaning:
- Universal quantifier: for every element in the domain, the predicate holds.
- Existential quantifier: there exists at least one element in the domain for which the predicate holds.
Notation:
- Universal: \forall x \in D\; Q(x) (read: for all x in D, Q(x) is true).
- Existential: \exists x \in D\; Q(x) (read: there exists an x in D such that Q(x) is true).
Relationship to truth sets:
- \forall x \in D\; Q(x) is true iff the truth set of Q(x) on D equals D itself (every x in D satisfies Q).
- \exists x \in D\; Q(x) is true iff the truth set is nonempty.
Example 1 (universal over a finite domain):
- Let D = {1,2,3,4,5} and Q(x) be x^2 > x.
- Truth values: Q(1)=false, Q(2)=true, Q(3)=true, Q(4)=true, Q(5)=true.
- Since Q(1) is false, \forall x \in D\; Q(x) is false for this domain.
Example 2 (universal over the reals):
- Let Q(x) be x^2 \ge 0 for x ∈ R.
- This is true for all real x, so \forall x \in \mathbb{R}\; (x^2 \ge 0) is true.
Example 3 (existential):
- Domain D = {5,6,7,8} and Q(x) is x^2 = x.
- Check: 5^2=25 ≠ 5, 6^2=36 ≠ 6, 7^2=49 ≠ 7, 8^2=64 ≠ 8. No x satisfies Q(x).
- Therefore, \exists x \in D\; (x^2 = x) is false for this domain.
Example 4 (existential with a beneficial domain):
- Domain D = Z+ (positive integers). Let Q(x) be x^2 = x.
- Solving gives x(x-1)=0, so x=0 or x=1. Only x=1 lies in Z+.
- So \exists x \in \mathbb{Z}^+\; (x^2 = x) is true (take x=1).
Example 5 (mixed domain and a common existential):
- Domain D = Z+. Let R(x) be x^3 = 8.
- There is x=2 in Z+ that satisfies this, so \exists x \in \mathbb{Z}^+\; (x^3 = 8) is true.

Implication and logical connectives

Implication: If P and Q are statements about x, the conditional is P(x) \rightarrow Q(x).
- The truth table behavior: the implication is false only when P(x) is true and Q(x) is false; otherwise it is true.
- In quantifier form (with a domain D):
  \forall x \in D\; (P(x) \rightarrow Q(x)).
- An important interpretation: the set of x for which P(x) holds is a subset of the set of x for which Q(x) holds:
  {x \in D \mid P(x)} \subseteq {x \in D \mid Q(x)}.
Simple example from the transcript: after introducing the idea, a typical assertion is
- If x is an integer, then x is rational. Formally: \forall x \in \mathbb{Z}\; (\text{Integer}(x) \rightarrow \text{Rational}(x)).
- This is true because every integer is a rational number.
Another example: every real square is nonnegative:
- \forall x \in \mathbb{R}\; (x^2 \ge 0).
- This is true for all real x.
A more geometric example from the transcript:
- For every triangle t, if t is a triangle then t is blue:
  \forall t \in T\; (\text{Triangle}(t) \rightarrow \text{Blue}(t)).
- This statement can be true if every triangle in the interpreted world is blue; otherwise false.
Another domain-oriented example: there exists a pair of objects with a spatial relation (to the right of):
- There exists y such that y is a square and y is to the right of d:
  \exists y\in D\; (\text{Square}(y) \land \text{RightOf}(y,d)).
- The interpretation depends on the specific definition of RightOf and on the domain D for x and y.

Examples involving primes and basic number properties

Prime numbers: definition used in the transcript (standard):
- A prime number is an integer greater than 1 that has no positive divisors other than 1 and itself.
- Examples: 2 is prime; 3 is prime; 4 is not prime (divisible by 2).
Mixed logical statement about primes and evenness:
- There exists n such that n is prime and n is even:
  \exists n \in \mathbb{Z}^+\; (\text{Prime}(n) \land \text{Even}(n)).
- This is true, with n = 2 as the witness, since 2 is prime and even.

Examples highlighting domain dependence and careful interpretation

Domain-dependent truth of statements:
- A statement like \forall x \in D\; (P(x)) is true only if every x in D satisfies P.
- If you change D (e.g., from Z to Z+ to R), the truth value can change dramatically.
A common pitfall discussed in the transcript: ambiguous notation like ∃y such that y is to the right of d depends on how RightOf is defined. Clarify the relation and the domains before evaluating.

Summary of key takeaways

A predicate P(x) becomes a statement when you fix a domain D and a specific x in D.
Truth sets depend on the domain; changing D can change which x satisfy P(x).
Universal quantification asks for all x in D to satisfy the predicate; existential quantification asks for at least one x in D to satisfy it.
Implication P(x) → Q(x) has the familiar truth condition: it is false only when P(x) is true and Q(x) is false.
The relationship between implication and sets: the truth set of P(x) is a subset of the truth set of Q(x) if and only if ∀x ∈ D, P(x) → Q(x).
Examples used in practice include basic arithmetic truths (x^2 ≥ 0 for all x ∈ R), domain-sensitive existence (∃x ∈ D: x^2 = x), and simple universal statements about integers (e.g., integers are rational).
When formalizing, you can write statements in two forms: a natural-language form and a formal quantified form (using ∀, ∃, and domain notation). Both should be equivalent if the domain and predicates are defined consistently.

Quick reference formulas (LaTeX)

Truth set of P on D:
\text{Truth set} = {x \in D \mid P(x) \text{ is true}}.
Universal statement:
\forall x \in D\; Q(x).
Existential statement:
\exists x \in D\; Q(x).
Implication (with quantifier):
\forall x \in D\; (P(x) \rightarrow Q(x)).
Set-based interpretation of implication:
{x \in D \mid P(x)} \subseteq {x \in D \mid Q(x)}.
Prime number definition (informal but standard):
- A prime is an integer $p > 1$ whose only positive divisors are $1$ and $p$.
Example checks (quick):
- For $D = {1,2,3,4,5}$ and $P(x) : x^2 > x$, truth set is ${2,3,4,5}$.
- For $D = \mathbb{R}$ and $Q(x) : x^2 \ge 0$, the statement is true for all $x$.
- For $D = \mathbb{Z}^+$ and $Q(x) : x^3 = 8$, true with witness $x=2$.
A common existential with small domain:
- \exists x \in {5,6,7,8}\; (x^2 = x) is false.

Next steps for study

Practice translating natural-language statements into formal quantifier notation and vice versa.
Work with different domains (Z, Z+, R) to see how truth sets and quantified statements change.
Build intuition around implications and the subset interpretation of predicate truth sets.
Review common edge cases (e.g., equations with no real solutions, existence of witnesses in restricted domains).