Lecture Overview L5−P. 1

Predicates Predicate reasoning examples (Ordinary) mathematical induction Inductive proof examples Predicates L5−P. 2

Predicates are similar to propositions but depend on variables P (x, y, z) denotes a predicate on variables x, y, z

P (x): x is a prime number. Q(x): x > 2. R(x): x is an odd number.

Predicates are not propositions because they can be true or false depending on the value of the variable x.

When the value of x is not specified, we say x is unbound.

Predicates are like functions from the domains of the variables to propositions. P (2) is true. R(2) is false. P (4) ∨ R(3) is true. Q(3) ∧ R(4) is false. Q(1) ⇒ R(2) is true.

Quantifiers L5−P. 3

Propositions may assert — something is true for all or some elements of a given domain (e.g., all natural numbers).

When a particular universe of discourse is agreed upon in advance then:

“∀” means “for all”, ∀xP (x) is a statement that is true: iff P (x) is true for every x in the universe of discourse.

“∃” means “there exists.” ∃xP (x) is true iff P (x) is true for at least one x in the universe of discourse.

“∄” mean “there does not exist” (“there is no”).

“∃!” means “there exists exactly one.”

∀x ∈ S” means “for every x in the set S.”

(∀x ∈ S)P (x) is equivalent to ∀x(x ∈ S ⇒ P (x)).

Quantifiers turn predicates into propositions L5−P. 4

∀x(P (x) ∧ Q(x) ⇒ R(x))

Each occurrence of x is associated with the ∀ quantifier.

The quantifier makes the variable to be bound.

Thus, ∀x(P (x) ∧ Q(x) ⇒ R(x)) is a predicate.

P (x): x is a prime number. Q(x): x > 2. R(x): x is an odd number.

Every prime number greater than 2 is an odd number.

Quantifiers Cont. L5−P. 5

∀x∃y is different from ∃y∀x:

Suppose S(x, y) means student x falls asleep in class y.

What is? ∀y∃xS(x, y) :

“In every class, some student falls asleep.” And what is? ∃x∀yS(x, y) :

“There exists a student who falls asleep in every class.”

Deduction rules involving quantifiers L5−P. 6

Deduction rules for arbitrary propositions: e.g., Modus ponens: Given that P and P ⇒ Q are both true Conclude: Q

Deduction rules for propositions with quantifiers:

¬[∀xS(x)] is equivalent to ∃x¬S(x). Example: ∀xS(x) : For all primes x > 2, x is odd. ∃x¬S(x) : There is some prime x > 2 such that x is not odd. (Domain of discourse: Primes > 2)

¬[∃xS(x)] is equivalent to ∀x¬S(x). Example: ∃xS(x) : There is an even prime. ∀x¬S(x) : All primes are not even. (Domain of discourse: Primes)

Manipulating Quantifiers in Proofs L5−P. 7

We reason about propositions with quentfiers (predicates with quantifiers that bound variables) Using the following rules:

Universal Generalization UG: To prove something is true for all x (∀x), we can show that it works for an arbitrary fixed x.

Universal Instantiation UI: If a statement is true for all x (∀x), then it is true for any particular x we want to study.

Existential Generalization EG: If we have exhibited one x that satisfies some property, we have proved one exists (∃x).

Existential Instantiation EI: If we know that some x exists satisfying a property (∃x), then we can choose one and use it in the proof.

Predicate reasoning examples L5−P. 8

Prove: ∀n ∈ N(n^{2} + n is even).

1. Fix n ∈ N.

2. n^{2} + n is even. ???

3. QED Universal Generalization (UG)

Fix any arbiterary element n and prove for it.

To show step 2, we can use cases:

Prove: ∀n ∈ N(n^{2} + n is even).

1. Fix n ∈ N.

2. n^{2} + n is even.

1. If n is odd then n^{2} + n is even. ???

2. If n is even then n^{2} + n is even.???

3. QED Cases

Predicate reasoning examples, Cont. L5−P. 9

3. QED 2. If n is even then n^{2} + n is even.

1. Assume n is even.

2. n^{2} + n is even.

1. ∃x ∈ N(n = 2x)

Definition of “even”

2. Choose x ∈ N, n = 2x Existential Instantiation (EI) (If exists one, can choose one.)

3. n^{2} + n = 4x^{2} + 2x =

2(2x^{2} + x) Algebra

4. ∃y ∈ N(n^{2} + n = 2y) Existential Generalization (EG) (If you have one, then one exists.)

5. QED Definition of “even”

3. QED Implication 1. If n is odd then n^{2} + n is even.

1. Assume n is odd.

2. n^{2} + n is even.

1. ∃x ∈ N(n = 2x + 1)

Definition of “odd”

2. Choose x ∈ N, n = 2x + 1 EI

3. n^{2} + n = 4x^{2} + 4x + 1 + 2x + 1 =

2(2x^{2} + 3x + 1) Algebra

4. ∃y ∈ N(n^{2} + n = 2y)

EG

5. QED — Definition of “even”

3. QED — Implication Quentifire reasoning \sqrt{2}, Ex. L5−P. 11

Prove: \sqrt{2} is irrational.

1. \sqrt{2} rational ⇒ false 1. Assume \sqrt{2} rational.

2. false

1. Choose a, b ∈ N^{+}, \sqrt{2} = \frac{a}{b}, lowest terms. Basic properties of rationals, EI

2. 2b^{2} = a^{2} — Algebra

3. a^{2} is even. — EG, definition of “even”

4. a is even. — ???

5. Choose c ∈ N, a = 2c.

Definition of “even”, EI

6. 4c^{2} = a^{2} = 2b^{2} — Algebra

7. 2c^{2} = b^{2} Algebra

8. b^{2} is even — EG, definition of “even”

9. b is even. — ???

10. a, b aren’t in lowest terms, 1.2.4, 1.2.9 11. QED — 1.2.1, 1.2.10, propositional logic

3. QED — Implication

2. QED — Contradiction