5/24 TIL: Predicates, Quantifiers

Predicates

A statement is either TRUE or false. But x > 5 is not a statement until we have the value determined for x.

A predicate is a sentence depending on variables which becomes a statement upon substituting values in the domain

Truth Set of a predicate P(x):

{ x ∈ D | P(x) }

shows which of the elements in the domain make the predicate true

Universal Quantifier ∀

"for all" (every)

main use: "quantifying" predicates

∀x ∈ D, P(x) — for all x in the domain, P(x) is true

Existential Quantifier ∃

"there exists" (some)

∃x ∈ D, P(x) — there exists x in the domain, such that P(x) is true

Universal/existential quantifiers turn predicates back into a statement

Negating a universal

~(∀x ∈ D, P(x)) ≡ ∃x ∈ D, ~P(x)

meaning: if it's not the case that for all values some properties are true, there is at least one value where the property is false

Negating logical statements with multiple quantifiers

∀x ∈ D, P(x)) ≡ ∃

Ex) "Every integer has a larger integer"

∀x ∈ Z, P(x) → ∀x ∈ Z, ∃y ∈ Z, y > x -negate→ ∃x ∈ Z, ∀y ∈ Z, y ≤ x