Predicate Logic and Proofs

the usefulness of predicate logic

• to describe mathematical statements that can’t be sufficiently understood with propositional logic

“.” meaning

to rep commas or “such that”

symbol for “not all”

¬∀

if x satisfies P(x), then x satisfies Q(x)

P(x) → Q(x)

x satisfies both P(x) and Q(x)

P(x) ∧ Q(x)

symbol for “there exists no”

¬∃

in predicate logic, the order of ___________ is important

qualifiers; aka the “there exists” and “for all” → read CAREFULLY

theorem

a true mathematical statement

ex. the sqrt of 2 is an irrational number

the typical form of a mathematical argument

hypotheses (axioms (aka mathematical statements that are accepted w/o proof, defns, already proven Thms) → conclusion

direct proof

P (hypothesis) → Q (conclusion)

• suppose P is true and then proceed from there, with the goal of proving that Q is also true when P is true

indirect proof

Since P → Q (direct proof structure) ≡ ¬Q → ¬P (the contrapositive):

• Suppose the negation of Q is true and then prove that when negation of Q is true, negation of P would also be true

proof by contradiction

Show that the negation of the argument would lead to a contradiction (the negation is an undoubtedly false statement)

• negation of P → Q (direct proof) is P ∧¬Q

• therefore, suppose P is true and Q is false (so the negation of Q is true)

• proceed and show that assuming P is true and Q is false leads to a contradiction in the proof

proof by case

• when the hypothesis must be split into multiple cases and each case → conclusion

• therefore, prove that P1 → Q, P2 → Q, …. Pn → Q

• choose a proof strat to prove each case (direct, indirect, proof by contradiction)

• all cases must be proven true for the argument/theorem to be true

defn of even int

let n be an even int

n = 2k, k being some int

defn of an odd int

let n be an odd int

n = 2k + 1, k being some int

defn of being divisible

let n be an int, and d a non-zero int

n is DIVISIBLE by d if there exists an int k such that n = kd

defn of being indivisible

let n be an int, and d >= 1 an int

then, there exists unique ints k and r such that n = kd + r and 0 < r < d. ***remainder is smaller than divisor**** The number r is the remainder of the division of n by d.

n = kd + r

n = dividend

k = quotient

d = divisor

r = remainder

notation of divisible and indivisible

if d divides n, we write d | n. Otherwise, we write d ∤ n (theres a line crossing the vertical line)

proof of an equivalence

to prove a Thm w the form P ↔ Q, you must prove (P → Q) ∧ (Q → P)

empty proof

• recall that (F (false) → anything) = true

• so for P → Q, if you can show that P (the hypothesis) is false, then P → Q is true

trivial proof

• recall that anything → T is true

• if you can prove that Q is true w/o supposing P is true, then P → Q is true