Proofs, Proposition, Logical Induction, Axioms

# Proofs, Proposition, Logical Induction, Axioms ### Proofs #### General Proofs Method to Ascertain Truth in Society * Experiments and Observability * Establishing Falsehood * Sampling and Counter Examples * Established by Jury and Judges * Word of God * Word of your Boss * Customer is right * Authority can establish truth #### Mathematical Proofs Mathematicas proofs are different A Mathematical proof is a verification of a proposition by a chain of logical deductions from a base set of axioms Three key ideas in the defintion are 1. Preposition 2. Logical Deduction 3. Axiom A proof is a sequence of logical deductions from axioms and poreviously proved statements that concludes with the proposition in question ### Proposition A Proposition is a statement (communication) that is either True or False Some Examples * 2+3=5 -> True proposition, 1+1=3 -> False proposition * "who are you" is not a proposition as it is neither true nor false * $\forall$ n $\epsilon$ N, n2+n+41 is a prime number * p(n) ::= n2 + n + 41 * ::= means "equal by definition" * For all n in the set of Natural numbers such that ... * N is a Universe of Discourse * $\forall$ is a Quantifier * n2+n+41 is a prime number => A predicate * $\exists$ a,b,c,d $\epsilon$ N+, a4+b4+c4 = d4 * There exists a, b, c, d in the set of positive natural numbers such that ... * $\exists$ is a Quantifier * N+ is a Universe of Discourse * Ex: 313 (x3+y3) = z3 * Proved to be false, but for a number greater than 1000 digits * The regions in any map can be colored in 4 colors so that adjacent regions have different colors * Every even integer but 2 is the sum of 2 primes * 24 = 11+13 * Goldsberg conjecture * Fermat's Last Theorem * xn+yn=zn for some integer n > 2 * Goldbach conjecture * Every even integer greater than 2 is the sum of two primes * Reimann Hypothesis * Poincare Hypothesis * $\forall$ n $\epsilon$ Z, n>=2 => n2 >= 4 * => means implies * Z means Integers (Both + & -) * * $\forall$ n $\epsilon$ Z, n>=2 <=> n2 >= 4 * <=> means if and only if (iff) * this means implication both ways #### Theorems Important true propositions are called theorems #### Lemma A lemma is a preliminary proposition useful for providing later propositions Sometimes a lemma turns out to be far more important than the theorem it was originally used to prove #### Corollary A corollary is a proposition that follows in just a few logical steps from a theorem #### Predicate A Predicate is a proposition whose truth depends on the value of one or more variable * Ex: P(n) ::= "n is a perfect square" * This predicate is true for P(4) and false for P(5) * This notation of predicate is similar to ordinary function notation * Predicate Notation: P(n) ::= n2+1 => results in true or false for various values of n * Function Notation: p(n) = n2+1 => results in a numerical value for various values of n ### Axioms Axioms are propositions that are assumed to be True (No proofs) * Ex: There is a straight line segment between every pair of points * Ex: if a = b, b = c, then a = c * Following Axioms are defined in the context of different Geometry and is only believed to be True with that context and False otherwise * Euclidian Geometry: Given a line L and a point P not on L, there is exactly one line through P parallel to L * Spherical Geometry: Given a line L and a point P not on L, there is no line through P parallel to L * Hyberbolic Geometry: Given a line L and a point P not on L, there is infinite lines through P parallel to L Two guiding principles * Consistent * A set of axioms is consistent if no propositions to be proved both True and False * Complete * A set of axioms is said to be complete if it can be used to prove every proposition is either True or False Kurt Godel (1930) proved that there is no set of axioms that are both consistent and complete. if you want consistenty, there will true facts that cannot be proved ### Logical Deductions Logical deductions or inference rules are used to prove new propositions using previously proved ones The fundamental inference rule is modus ponens. This rule says that a proof of P together with a proof that P implies Q is a proof of Q This is represented in following notation Rule. $$\frac{\text{P, P IMPLIES Q}}{Q}$$ Statement above the line called the *antecedents* are proved then we can consider the statement below the line called the *conclusion* or *consequent* to also be proved A key requirement of an inference rule is that it must be sound Some natural sound inference rules are Rule. $$\frac{\text{P IMPLIES Q, Q IMPLIES R}}{\text{P IMPLIES R}}$$ Rule. $$\frac{\text{NOT(P) IMPLIES NOT(Q)}}{\text{Q IMPLIES P}}$$ #### Implication An Implication p => q is true if p is False or q is True p => q translates to if p, then q Truth Table p | q | p=>q --- | --- | ---- T | T | T T | F | F F | T | T F | F | T #### If and Only If (iff) If and only if means p <=> q is true if implies is True both ways p => q is True and q => p is True Truth Table p | q | p=>q | q=>p | p<=>q --- | --- | ---- | ---- | ----- T | T | T | T | T T | F | F | T | F F | T | T | F | F F | F | T | T | T ### Axiomatic Method Euclid's axiom and proof approach is called axiomatic method remains the foundation for mathematics today. A Handful of axioms called Zermelo-Fraenkel with Choice axioms (ZFC) together with a few logical deduction rules appear to be sufficient to derive essentially all of mathematics ### Patterns of Proof #### Proving Implies ##### Method 1 1. Write "Assume P." 2. Show that Q logically follows ##### Prove the Contrapositive A implication P => Q is logically equivalent to it's contrapositive NOT(Q) => NOT$P$ 1. Write "We prove the contrapositive:" and then state the contrapositive 2. Proceed as in Method 1 #### Proving IFF Ex: Two triangles have the same side lengths if and only if two side lengths and the angle between those sides are the same ##### Prove Each statement Implies the Other 1. Write "We prove P implies Q and vice-versa" 2. Write "First, we show P implies Q" using one of the methods for Implies 3. Write "First, we show Q implies P" using one of the methods for Implies ##### Construct a chain of Iffs 1. Write "We construct a chain of if-and-only-if implications" 2. Prove P is equivalent to a second statement which is equivalent to a third statement and so forth until you reach Q #### Proof by Cases Breaking a complicated proof into cases and proving each case separately is a common useful proof strategy #### Proof by Contradiction In a proof by contradiction, or indirect proof, you show that if a proposition were false, then some false fact would be true. since a false fact by definition can't be true, the proposition must be true In order to prove a proposition P by contradiction 1. Write, "We use proof by contradiction" 2. Write, "Suppose P is false" 3. Deduce something known to be false (a logical contradiction) 4. Write, "This is a contradiction. Therefore, P must be true" ### Good Proofs One purpose of a proof is to establish the truth of an assertion with absolute certainty, and mechanically checkable proofs of enormous length or complexity can accomplish this, but humanly intelligible proofs are the only ones that help someone understand the subject. A good proof must be clear. Correctness and Clarity usually go together. 1. State your Game plan 2. Keep a linear flow 3. A proof is an essay, not a calculation 4. Avoid excessive symbolism 5. Revise and Simplify 6. Introduce notation thoughtfully 7. Structure long proofs 8. Be wary of the "obvious" 9. Finish