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