STEP-BY-STEP LESSON · §3.1
Predicates and Quantified Statements I
Connect a predicate to its domain and quantifier.
Before you begin
Variables
In x+y=0, each variable keeps its chosen value throughout the statement. If x=3, only y=−3 satisfies this condition.
x+y=0; x=3 ⇒ y=−3
The condition x>0 depends on the permitted values of x. Specify the domain: integers.
x∈ℤ
Conditional Statements
In p→q, p is the hypothesis and q the conclusion. The implication fails only when p is true and q false.
p→q≡¬p∨q
The equivalent contrapositive reverses and negates both parts: if not q, then not p. The converse q→p is not equivalent in general.
p→q≡¬q→¬p
Symbols
- P(x)
- predicate
- ∀
- for every
- ∃
- there exists
Definitions and notation for this topic
Universal quantifier
∀
Requires the condition to hold for every object in the domain.
One counterexample is enough to refute a universal statement.
The domain and the predicate’s scope are part of the statement. Over an empty domain, ∀x∈D P(x) is true because there is no counterexample.
Separate glossary example
∀x∈{2,3,4}: x²>x
Existential quantifier
∃
Asserts that at least one object satisfies the condition.
The value 3 works. Existence does not require uniqueness.
The witness must belong to the stated domain. An existential statement over an empty domain is false; more than one witness is permitted.
Separate glossary example
∃x∈{2,3,4}: x²+2=11
Predicate
P(x)
A condition involving a variable; substituting a value or quantifying the variable produces a statement.
P(x) does not mean P multiplied by x.
P(x,y) may have several free variables. Binding every free variable produces a closed formula. Alternatively, assigning values to the free variables lets you evaluate the predicate; the same free variable keeps the same value throughout that evaluation.
Separate glossary example
P(x): x > 2; P(3) is true.
Domain of discourse
The set of objects over which a variable ranges.
A domain can contain numbers, people, or other objects.
Separate glossary example
∀x ∈ ℤ: x² ≥ 0
Free / bound variable
(∀x∈D P(x)) ∧ Q(x)
An occurrence of a variable is bound when it lies in the scope of a quantifier that binds it; otherwise that occurrence is free.
The same printed variable name can have both kinds of occurrence. Parentheses delimit the quantifier’s scope; this formula still depends on the free x.
Separate glossary example
In (∀x∈D P(x)) ∧ Q(x), the x in P(x) is bound; the x in Q(x) is free.
∀x P(x,y)
Satisfy
Make a condition true when the object is substituted into it.
Replacing x with 3 gives the true equality 3+2=5.
Separate glossary example
The number 3 satisfies x+2=5.
For all / for every / for each
Spoken forms of ∀: the requirement applies to every object in the stated domain.
Include the domain when reading: integer says which objects are being considered.
Separate glossary example
For every integer x, x²≥0.
There exists / for some
Phrases asserting that at least one object has the required property.
The value k=3 works. The phrase for some does not mean exactly one.
Separate glossary example
There exists an integer k such that 6=2k.
Step by step
Step 1 / 6
A condition with an object slot
P(x) is a condition whose truth depends on x. For P(x): x>2, specify allowed values first.
D={1,2,3}The domain specifies every case being discussed.
Worked example
For D={−2,−1,0,1,2} and P(x):x²=1, decide both ∃x∈D P(x) and ∀x∈D P(x).
- Compute the squares in the listed order: 4,1,0,1,4.
- The values −1 and 1 satisfy P, so at least one witness exists and the existential statement is true.
- For x=0, P is false. A single counterexample suffices, so the universal statement is false.
Read the claim and its domain
A domain tells you which objects are allowed. A predicate is a condition on those objects. In P(n) → Q(n), a counterexample must satisfy P(n) and fail Q(n). A case that fails P(n) does not refute the conditional. The words 'every' and 'some' ask different questions: all permitted objects, or at least one witness.
Worked example
Decide: for every integer n, if n > 0, then n² ≥ n. Would the same claim be true over the real numbers?
Take an arbitrary integer n satisfying the hypothesis n > 0.
n ∈ ℤ, n > 0 ⇒ n ≥ 1
Why: There is no integer strictly between 0 and 1. This is where the integer domain matters.
Multiply n ≥ 1 by the positive number n.
n² ≥ n
Why: Multiplication by a positive number preserves the inequality. The conclusion now follows for every integer meeting the hypothesis.
Over the reals, test n = 1/2.
1/2 > 0; (1/2)² = 1/4 < 1/2
Why: This value satisfies the hypothesis and violates the conclusion, so it refutes the real-number version. Zero and negative values would not do that.
Self-review goal: Given a proposed counterexample, name the domain, check the hypothesis, and check the conclusion separately. Distinguish an existential witness from a universal claim.
Optional self-check
Does one witness show that the property holds for all?
Show answer
No, it establishes only existence.