Unit 1: Logic and Proofs

I. Orientation

Logic provides a formal language for distinguishing valid reasoning from invalid reasoning, while proof applies logical rules to establish mathematical claims. The unit depends on precise statements, clearly defined domains, valid inference rules, and arguments whose conclusions follow necessarily from their premises.

• Proposition: A declarative sentence having exactly one truth value—true (T) or false (F). For example, “7 is prime” is true, whereas a question is not a proposition.
• Logical connectives:
  • ¬p: negation, “not (p).”
  • p ∧ q: conjunction, “(p) and (q).”
  • p ∨ q: inclusive disjunction, “(p) or (q), or both.”
  • p → q: implication, “if (p), then (q).”
  • p ↔ q: biconditional, “(p) if and only if (q).”
• Truth convention: An implication (p\to q) is false only when (p) is true and (q) is false.
• Quantifiers:
  • (\forall x\,P(x)): (P(x)) holds for every (x) in the stated domain.
  • (\exists x\,P(x)): (P(x)) holds for at least one (x) in the domain.
• Proof standard: Every step must follow from a definition, hypothesis, established result, or valid rule of inference.
• Common number sets: (\mathbb Z) denotes the integers, (\mathbb Q) the rational numbers, and (\mathbb R) the real numbers.

II. Foundations of Mathematical Logic — Statements, Forms, and Scope

A. Propositional logic

Propositional logic studies how propositions are combined and how the truth of a compound proposition depends on its components.

• Truth table: For propositions (p) and (q), the principal connectives behave as follows:

p  q | ¬p | p ∧ q | p ∨ q | p → q | p ↔ q
T  T |  F |   T   |   T   |   T   |   T
T  F |  F |   F   |   T   |   F   |   F
F  T |  T |   F   |   T   |   T   |   F
F  F |  T |   F   |   F   |   T   |   T

• Terminology:
  • A tautology is always true, such as (p\lor\neg p).
  • A contradiction is always false, such as (p\land\neg p).
  • A contingency is true for some assignments and false for others.
• Conditional forms: For (p\to q):
  • Converse: (q\to p).
  • Inverse: (\neg p\to\neg q).
  • Contrapositive: (\neg q\to\neg p).
  • Only the contrapositive is logically equivalent to the original implication.
• Necessary and sufficient conditions: In (p\to q), (p) is sufficient for (q), while (q) is necessary for (p).
• Inference rules:
  • Modus ponens: from (p) and (p\to q), infer (q).
  • Modus tollens: from (p\to q) and (\neg q), infer (\neg p).

B. Propositional equivalences

Two compound propositions are logically equivalent when they have the same truth value under every possible assignment.

• Notation: (P\equiv Q) means that (P\leftrightarrow Q) is a tautology; (P) and (Q) denote compound propositions.
• Identity and domination laws:

p ∧ T ≡ p        p ∨ F ≡ p
p ∨ T ≡ T        p ∧ F ≡ F

• Idempotent and double-negation laws:

p ∨ p ≡ p        p ∧ p ≡ p
¬(¬p) ≡ p

• Commutative and associative laws:

p ∨ q ≡ q ∨ p
p ∧ q ≡ q ∧ p
(p ∨ q) ∨ r ≡ p ∨ (q ∨ r)
(p ∧ q) ∧ r ≡ p ∧ (q ∧ r)

Here (p,q,r) are propositions.

• Distributive laws:

p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)

• De Morgan’s laws:

¬(p ∧ q) ≡ ¬p ∨ ¬q
¬(p ∨ q) ≡ ¬p ∧ ¬q

• Conditional equivalences:

p → q ≡ ¬p ∨ q
p ↔ q ≡ (p → q) ∧ (q → p)
¬(p → q) ≡ p ∧ ¬q

• Verification methods: Equivalence may be proved by matching truth-table columns or by transforming one expression using established laws.

C. Quantifiers

Quantifiers convert predicates—sentences containing variables—into propositions by specifying how many domain elements satisfy them.

• Predicate and domain: In (P(x)), (P) is a property and (x) ranges over a specified universe; changing the domain may change the truth value.
• Universal quantifier: (\forall x\,P(x)) asserts that no domain element is an exception.
• Existential quantifier: (\exists x\,P(x)) requires at least one witness (a) for which (P(a)) is true.
• Negation rules:

¬∀x P(x) ≡ ∃x ¬P(x)
¬∃x P(x) ≡ ∀x ¬P(x)

The first says “not every” means “at least one does not”; the second says “none exists” means “every element fails.”

• Order of quantifiers: Quantifier order generally matters:
  • (\forall x\,\exists y\,(x<y)) is true over (\mathbb Z): choose (y=x+1).
  • (\exists y\,\forall x\,(x<y)) is false over (\mathbb Z): there is no greatest upper integer.
• Bound and free variables: In (\forall x\,P(x,y)), (x) is bound by the quantifier, but (y) remains free; an expression with a free variable is not yet a proposition.

III. Fundamental Proof Methods — Establishing Implications

A. Introduction to proof

A mathematical proof is a finite, logically valid argument showing that a conclusion follows from explicit hypotheses and accepted facts.

• Typical theorem form: A claim “if (P), then (Q)” has hypothesis (P) and conclusion (Q).
• Definitions as tools: Definitions must be expanded precisely; for example, an integer (n) is even exactly when (n=2k) for some (k\in\mathbb Z).
• Universal claims: To prove (\forall x\,P(x)), choose an arbitrary domain element (x) and prove (P(x)) without imposing unjustified restrictions.
• Existential claims: To prove (\exists x\,P(x)), provide a witness and verify it. For example, (x=2) proves that an even prime exists.
• Inference chain: Each statement should be connected to previous statements rather than merely supported by numerical experimentation.

B. Direct proof

A direct proof assumes the hypothesis of an implication and derives its conclusion through definitions and established results.

• General structure:

Assume P.
Use P, definitions, and known results to derive Q.
Therefore P → Q.

Here (P) is the hypothesis and (Q) is the conclusion.

• Worked example: If (m) and (n) are even integers, then (m+n) is even.
  • Since (m) and (n) are even, (m=2a) and (n=2b) for some (a,b\in\mathbb Z).
  • Therefore (m+n=2a+2b=2(a+b)).
  • Because (a+b\in\mathbb Z), the definition of evenness shows that (m+n) is even.
• Best use: Direct proof is natural when the hypothesis supplies algebraic forms or inequalities that readily lead to the conclusion.

C. Proof by contraposition

Proof by contraposition establishes (P\to Q) by proving its logically equivalent contrapositive (\neg Q\to\neg P).

• Logical basis:

P → Q ≡ ¬Q → ¬P

Here (P) and (Q) are propositions.

• Method: Assume the conclusion (Q) is false, then derive that the hypothesis (P) must also be false.
• Worked example: If (n^2) is even, then (n) is even.
  • Prove the contrapositive: if (n) is odd, then (n^2) is odd.
  • Write (n=2k+1), where (k\in\mathbb Z).
  • Then (n^2=4k^2+4k+1=2(2k^2+2k)+1), which is odd.
  • Hence the original implication follows.
• Best use: Contraposition is effective when (\neg Q) has a simpler mathematical form than (P).

D. Vacuous and trivial proof

Vacuous and trivial proofs establish an implication through the truth conditions of (P\to Q), rather than by a substantial deduction from (P).

1. Vacuous proof:

   • Principle: Prove (\neg P); an implication with a false hypothesis is true.
   • Concrete case: “If an integer (n) satisfies (n^2<0), then (n=5)” is vacuously true because no integer has a negative square.
   • Limitation: It proves the implication but does not prove that any object satisfies its hypothesis.

2. Trivial proof:

   • Principle: Prove (Q) independently; an implication with a true conclusion is true.
   • Concrete case: “If (8) is odd, then (2+2=4)” is true because the conclusion is true.
   • Distinction: Vacuous proof makes (P) false; trivial proof makes (Q) true.

IV. Proof Construction and Evaluation — Strategy, Alternatives, and Errors

A. Proof strategy

Proof strategy means selecting a valid method that matches the logical form and mathematical content of a claim.

• Parse the statement: Identify hypotheses, conclusions, quantifiers, domain, and definitions before manipulating symbols.
• Work from both ends: Ask what the hypothesis provides and what would be sufficient to obtain the conclusion; exploratory backward reasoning must be rewritten as a forward-valid proof.
• Choose by form:
  • Use direct proof for accessible implications.
  • Use contraposition when negating the conclusion is useful.
  • Use contradiction when assuming failure creates an impossibility.
  • Prove both directions for a biconditional.
• Use cases carefully: If possibilities are exhaustive, such as “(n) is even or odd,” proving the result in every case proves the full claim.
• Maintain generality: For a universal theorem, an example can suggest a pattern but cannot establish it.

B. Proof by contradiction

Proof by contradiction assumes the negation of the desired conclusion and derives an impossibility.

• Logical form:

Assume ¬P.
Derive R ∧ ¬R.
Therefore P.

Here (P) is the desired proposition and (R) is some proposition whose truth and falsity are both derived.

• Contradiction types: The argument may produce (R\land\neg R), violate a hypothesis, conflict with a definition, or imply an impossibility such as (0=1).
• Worked example: To prove there is no greatest integer, assume (g\in\mathbb Z) is greatest. Then (g+1\in\mathbb Z) and (g+1>g), contradicting the definition of (g) as greatest.
• Distinction from contraposition: Contraposition proves (\neg Q\to\neg P); contradiction assumes the negation of the entire target and derives falsehood.

C. Proof of equivalence and counterexamples

Equivalence proofs establish that two conditions have identical truth, while counterexamples disprove universal claims by exhibiting a single failure.

1. Proof of equivalence:

   • Biconditional method: To prove (P\leftrightarrow Q), prove both (P\to Q) and (Q\to P).
   • Extended equivalence: For (P\leftrightarrow Q\leftrightarrow R), a cycle (P\to Q), (Q\to R), and (R\to P) is sufficient.
   • Precision: Proving only one direction establishes implication, not equivalence.

2. Counterexamples:

   • Principle: To refute (\forall x\,P(x)), provide one domain element (a) for which (\neg P(a)).
   • Concrete case: The claim “every prime is odd” is false because (2) is prime and even.
   • Limitation: Examples cannot prove a universal statement, but one valid counterexample can disprove it.

D. Mistakes in proof

Proof errors arise when a step is logically invalid, a definition is misused, or the argument proves less than the stated claim.

• Affirming the consequent: From (P\to Q) and (Q), inferring (P) is invalid; rain implies wet ground, but wet ground need not imply rain.
• Denying the antecedent: From (P\to Q) and (\neg P), inferring (\neg Q) is invalid.
• Assuming the conclusion: Using (Q) to prove (Q) is circular reasoning unless (Q) has already been independently established.
• Illegal algebra: Dividing by an expression without proving it is nonzero can produce false results.
• Quantifier confusion: Proving (P(a)) for one chosen (a) does not prove (\forall x\,P(x)); one witness proves only an existential claim.
• Unjustified converse: A theorem (P\to Q) does not automatically provide (Q\to P).
• Example-based proof: Checking many cases supports a conjecture but does not prove an infinite universal statement.
• Undefined variables: Every variable must have a declared domain, and each introduced symbol must retain a consistent meaning.
• Incomplete contradiction: Merely obtaining a surprising statement is insufficient; the derived result must genuinely conflict with a premise, definition, or established fact.