🧠Thinking Like a Mathematician Unit 2 – Logic and Proof Techniques in Math

Key Concepts and Definitions

• Logic the study of reasoning, arguments, and the principles of correct inference
• Proposition a declarative sentence that is either true or false, but not both
• Premise a statement or assumption used as the basis for an argument or conclusion
• Conclusion the final statement in an argument, derived from the premises
• Argument a series of propositions, with one (the conclusion) claimed to follow from the others (the premises)
• Valid argument an argument in which the conclusion necessarily follows from the premises, regardless of their truth values
• Sound argument a valid argument with true premises, ensuring a true conclusion
• Tautology a proposition that is always true, regardless of the truth values of its component statements
• Contradiction a proposition that is always false, regardless of the truth values of its component statements

Logical Operators and Truth Tables

• Logical operators symbols used to connect propositions and create compound statements
• Negation (¬) the operator that reverses the truth value of a proposition
• Conjunction (∧) the "and" operator, which is true only when both propositions are true
• Disjunction (∨) the "or" operator, which is true when at least one of the propositions is true
• Implication (→) the "if-then" operator, which is false only when the antecedent is true and the consequent is false
• Biconditional (↔) the "if and only if" operator, which is true when both propositions have the same truth value
• Truth table a table that displays all possible truth values for a compound proposition
  • Each row represents a unique combination of truth values for the component propositions
  • The final column shows the truth value of the compound proposition for each combination

Types of Statements and Propositions

• Simple proposition a proposition that cannot be broken down into simpler propositions
• Compound proposition a proposition formed by combining two or more simple propositions using logical operators
• Conditional statement a proposition of the form "if P, then Q" (P → Q), where P is the antecedent and Q is the consequent
  • Converse the conditional statement formed by swapping the antecedent and consequent (Q → P)
  • Inverse the conditional statement formed by negating both the antecedent and consequent (¬P → ¬Q)
  • Contrapositive the conditional statement formed by negating and swapping the antecedent and consequent (¬Q → ¬P)
• Biconditional statement a proposition of the form "P if and only if Q" (P ↔ Q), which is true when P and Q have the same truth value
• Quantified statement a proposition that includes a quantifier, such as "for all" (∀) or "there exists" (∃)
  • Universal quantifier (∀) indicates that a property holds for all elements in a set
  • Existential quantifier (∃) indicates that a property holds for at least one element in a set

Methods of Proof

• Direct proof a method of proving a conditional statement (P → Q) by assuming P is true and logically deriving Q
• Proof by contradiction (reductio ad absurdum) a method of proving a statement by assuming its negation and deriving a contradiction
• Proof by contrapositive a method of proving a conditional statement (P → Q) by proving its contrapositive (¬Q → ¬P)
• Proof by cases a method of proving a statement by considering all possible cases and showing that the statement holds in each case
• Mathematical induction a method of proving a statement for all natural numbers by proving a base case and an inductive step
  • Base case prove the statement holds for the smallest value (usually 0 or 1)
  • Inductive step assume the statement holds for n and prove it holds for n+1
• Proof by counterexample a method of disproving a universal statement by providing a single counterexample

Inductive and Deductive Reasoning

• Inductive reasoning a method of reasoning that draws a general conclusion from specific observations or examples
  • Inductive arguments are not necessarily valid, as the conclusion may be false even if the premises are true
  • Strength of an inductive argument depends on the quality and quantity of the observations
• Deductive reasoning a method of reasoning that draws a specific conclusion from general premises or axioms
  • Deductive arguments are valid if the conclusion necessarily follows from the premises
  • Soundness of a deductive argument depends on the truth of the premises
• Axioms statements that are assumed to be true without proof, serving as the foundation for deductive reasoning
• Theorems statements that are proven using deductive reasoning, based on axioms and previously proven theorems
• Lemmas intermediate results used in the proof of a theorem, often proven separately for clarity and organization

Common Fallacies and Pitfalls

• Fallacy an error in reasoning that leads to an invalid or unsound argument
• Affirming the consequent the fallacy of concluding P from the premises (P → Q) and Q
• Denying the antecedent the fallacy of concluding ¬Q from the premises (P → Q) and ¬P
• Begging the question (petitio principii) the fallacy of assuming the conclusion in the premises, resulting in a circular argument
• False dilemma (false dichotomy) the fallacy of presenting only two options when more exist, often framing the argument misleadingly
• Equivocation the fallacy of using a word or phrase with multiple meanings in an ambiguous or misleading way
• Appeal to authority (argumentum ad verecundiam) the fallacy of claiming something is true because an authority figure says so, without proper evidence
• Hasty generalization the fallacy of drawing a broad conclusion from insufficient or unrepresentative evidence
• Post hoc ergo propter hoc the fallacy of concluding that one event caused another simply because it occurred first

Applications in Mathematics

• Foundations of mathematics logic serves as the basis for rigorous mathematical reasoning and proof
• Set theory uses logical concepts and notation to define and manipulate sets, the building blocks of mathematics
• Number theory relies on logical arguments to prove properties of integers and other number systems
• Analysis (calculus) uses logical reasoning to define and prove properties of functions, limits, derivatives, and integrals
• Algebra employs logical methods to solve equations, manipulate expressions, and study abstract structures
• Geometry and topology use logical axioms and deductive reasoning to prove theorems about shapes, spaces, and their properties
• Combinatorics and graph theory apply logical principles to counting problems, discrete structures, and optimization
• Probability and statistics use logical arguments to derive and justify methods for quantifying uncertainty and making inferences from data

Practice Problems and Examples

• Prove that the square root of 2 is irrational using a proof by contradiction
• Use a truth table to determine whether the proposition $((P \rightarrow Q) \wedge (Q \rightarrow R)) \rightarrow (P \rightarrow R)$ is a tautology
• Prove the theorem "If n is an odd integer, then $n^2$ is also odd" using a direct proof
• Prove the statement "For all natural numbers n, $1 + 2 + 3 + \ldots + n = \frac{n(n+1)}{2}$" using mathematical induction
• Identify the fallacy in the following argument "If I study hard, I will get an A on the exam. I got an A on the exam, therefore I studied hard."
• Use a proof by contrapositive to show that "If $x^2$ is even, then x is even" for all integers x
• Prove the theorem "If a, b, and c are integers such that a|b and b|c, then a|c" using a direct proof (where a|b means "a divides b")
• Provide a counterexample to disprove the statement "For all real numbers x and y, $(x + y)^2 = x^2 + y^2$"