🤔Proof Theory Unit 1 – Intro to Proof Theory & Math Logic

Key Concepts and Definitions

• Logic studies the principles of valid reasoning and inference
• Proofs demonstrate the truth of a statement using a sequence of logical steps
• Propositions are declarative sentences that are either true or false
• Predicates are properties or relations that can be true or false for a given input
• Axioms are statements accepted as true without proof and serve as the starting point for deriving other truths
• Inference rules specify how new propositions can be derived from existing ones (modus ponens, modus tollens)
• Soundness ensures that a logical system proves only true statements
  • If the axioms are true and the inference rules are valid, the system is sound
• Completeness ensures that a logical system can prove all true statements

Foundations of Logic

• Logic is concerned with the study of arguments and reasoning
• Arguments consist of premises (assumptions) and a conclusion
• Valid arguments have conclusions that necessarily follow from their premises
  • In a valid argument, if the premises are true, the conclusion must be true
• Invalid arguments may have true premises but a false conclusion
• Soundness combines validity with true premises
  • A sound argument is both valid and has true premises
• Consistency ensures that a set of statements does not contain contradictions
• Logical connectives (and, or, not, if-then) are used to form compound propositions
• Truth tables define the meaning of logical connectives by listing all possible truth value combinations

Types of Proofs

• Direct proof assumes the premises are true and uses logical steps to reach the conclusion
• Proof by contradiction assumes the negation of the conclusion and derives a contradiction, proving the original conclusion
• Proof by contraposition proves the contrapositive of a statement (if not Q, then not P)
• Proof by cases divides a problem into exhaustive cases and proves each case separately
• Proof by induction proves a statement for all natural numbers by proving a base case and an inductive step
  • The base case proves the statement for the first value (usually 0 or 1)
  • The inductive step proves that if the statement holds for n, it also holds for n+1
• Proof by construction provides an explicit example or algorithm to demonstrate the truth of a statement
• Nonconstructive proofs prove the existence of an object without providing an explicit example

Propositional Logic

• Propositional logic deals with propositions and their relationships
• Atomic propositions are the most basic units and cannot be broken down further
• Compound propositions are formed by combining atomic propositions using logical connectives
• The main logical connectives are:
  • Negation (not, ¬): reverses the truth value of a proposition
  • Conjunction (and, ∧): true only when both propositions are true
  • Disjunction (or, ∨): true when at least one proposition is true
  • Implication (if-then, →): false only when the antecedent is true and the consequent is false
  • Biconditional (if and only if, ↔): true when both propositions have the same truth value
• Logical equivalence (≡) means that two propositions have the same truth value for all possible truth assignments
• De Morgan's laws describe the relationship between negation, conjunction, and disjunction:
  • ¬(P ∧ Q) ≡ (¬P) ∨ (¬Q)
  • ¬(P ∨ Q) ≡ (¬P) ∧ (¬Q)

Predicate Logic

• Predicate logic extends propositional logic by introducing predicates and quantifiers
• Predicates are functions that map objects to truth values
  • Example: "is even" is a predicate that maps integers to true or false
• Quantifiers express the quantity of objects that satisfy a predicate
• The universal quantifier (∀) asserts that a predicate holds for all objects in a domain
  • ∀x P(x) means "for all x, P(x) is true"
• The existential quantifier (∃) asserts that a predicate holds for at least one object in a domain
  • ∃x P(x) means "there exists an x such that P(x) is true"
• The domain of discourse specifies the set of objects over which quantifiers range
• Nested quantifiers allow for expressing more complex statements
  • ∀x ∃y P(x, y) means "for all x, there exists a y such that P(x, y) is true"
• Quantifier negation rules:
  • ¬(∀x P(x)) ≡ ∃x ¬P(x)
  • ¬(∃x P(x)) ≡ ∀x ¬P(x)

Formal Systems and Axioms

• A formal system consists of a language, axioms, and inference rules
• The language specifies the symbols and formulas allowed in the system
• Axioms are the starting assumptions of the system
  • They are accepted as true without proof
• Inference rules define how new formulas can be derived from existing ones
  • Modus ponens: from P and P → Q, infer Q
  • Modus tollens: from ¬Q and P → Q, infer ¬P
• Theorems are formulas that can be derived from the axioms using inference rules
• Consistency ensures that a formal system does not contain contradictions
  • A system is consistent if it cannot prove both a formula and its negation
• Completeness ensures that all true statements can be proven within the system
• Gödel's incompleteness theorems show that in any consistent formal system containing arithmetic, there are true statements that cannot be proven within the system

Proof Techniques and Strategies

• Understand the statement to be proven
  • Identify the premises, conclusion, and key terms
• Choose an appropriate proof technique based on the structure of the statement
• Break the proof into smaller, manageable steps
• Use definitions, axioms, and previously proven theorems
• Work forward from the premises or backward from the conclusion
• Look for patterns or similarities to known proofs
• Consider proof by contradiction if a direct proof is not apparent
• For proofs involving sets or functions, consider element-wise arguments
• For proofs involving inequalities, consider the properties of the underlying order relation
• Write each step clearly and justify each inference
• Review the proof for clarity, correctness, and completeness

Applications and Examples

• Proving the irrationality of √2 using a proof by contradiction
• Proving the infinitude of primes using Euclid's classic proof
• Proving the Pythagorean theorem using a geometric argument
• Proving the fundamental theorem of arithmetic (unique prime factorization) using the Euclidean algorithm
• Proving the correctness of algorithms using induction (e.g., the correctness of merge sort)
• Proving the unsolvability of the halting problem using a diagonalization argument
• Proving the completeness and soundness of propositional logic using truth tables and semantic arguments
• Proving the compactness theorem in first-order logic using the ultraproduct construction