Axiomatic Systems
Table of Contents
1. Introduction to Axiomatic Systems
An axiomatic system is a set of axioms used to derive theorems without assuming any previously established truth other than the axioms themselves. It provides a foundation for mathematical and logical reasoning by starting with self-evident truths (axioms) and building up complex results through deduction.
Key Properties of Axiomatic Systems:
- Consistency: No contradictions can be derived.
- Completeness: Every statement in the system can be either proven or disproven.
- Independence: No axiom can be derived from the others.
2. Components of Axiomatic Systems
Axioms
Statements accepted without proof; the foundational assumptions of the system.
Definitions
Precise descriptions of terms used in the system.
Rules of Inference
Methods for deriving new statements from existing ones.
Theorems
Statements proven using axioms, definitions, and rules of inference.
3. Types of Axiomatic Systems
Euclidean Axiomatic Systems
Based on Euclid's Elements, these systems have a small number of axioms that are intuitively obvious truths about geometry.
Example: "Given any two distinct points, there exists exactly one line containing them."
Non-Euclidean Axiomatic Systems
Systems that modify one or more of Euclid's axioms, particularly the parallel postulate.
Example: In hyperbolic geometry, "Through a point not on a given line, there exist at least two lines parallel to the given line."
Formal Axiomatic Systems
Completely symbolic systems where axioms are strings of symbols and rules are purely syntactic.
Example: Peano axioms for natural numbers, ZFC set theory.
Group Axioms
A simple example of an axiomatic system defining algebraic structures known as groups.
Example: Axioms for closure, associativity, identity element, and inverse element.
4. Examples of Axiomatic Systems
Euclidean Geometry
Axioms:
- A straight line can be drawn between any two points.
- A line segment can be extended indefinitely.
- Given a point and a distance, a circle can be drawn with the point as center and the distance as radius.
- All right angles are equal.
- Through a point not on a line, exactly one line can be drawn parallel to the given line (Parallel Postulate).
Example Theorem: The sum of angles in a triangle equals 180°.
Peano Axioms (Natural Numbers)
Axioms:
- 0 is a natural number.
- For every natural number n, S(n) is a natural number (where S is the successor function).
- 0 is not the successor of any natural number.
- If S(m) = S(n), then m = n.
- If a set contains 0 and contains the successor of every number in the set, then the set contains all natural numbers (Induction Axiom).
Example Theorem: 1 + 1 = 2, where 1 = S(0) and 2 = S(S(0)).
Group Theory
Axioms: For a set G with operation *, the following hold:
- Closure: For all a, b ∈ G, a * b ∈ G.
- Associativity: For all a, b, c ∈ G, (a * b) * c = a * (b * c).
- Identity: There exists e ∈ G such that for all a ∈ G, e * a = a * e = a.
- Inverse: For every a ∈ G, there exists b ∈ G such that a * b = b * a = e.
Example: The set of integers ℤ with the operation of addition forms a group.
Propositional Logic
Axioms:
- P → (Q → P)
- (P → (Q → R)) → ((P → Q) → (P → R))
- (¬P → ¬Q) → (Q → P)
Rule of Inference: Modus Ponens - From P and P → Q, derive Q.
Example Theorem: P → P (Law of Identity).
Zermelo-Fraenkel Set Theory (ZFC)
Some Key Axioms:
- Axiom of Extensionality: Two sets are equal if and only if they have the same elements.
- Axiom of Pairing: For any two sets, there exists a set containing exactly these two sets as elements.
- Axiom of Power Set: For any set, there exists a set containing all its subsets.
- Axiom of Infinity: There exists an infinite set.
- Axiom of Choice: For any collection of non-empty sets, it is possible to select exactly one element from each set.
Example Theorem: The existence of the Cartesian product of any two sets.
5. Ways to Solve Problems in Axiomatic Systems
Direct Proof
Start with known axioms and apply rules of inference to directly reach the desired conclusion.
Example: To prove that the sum of two even numbers is even:
- Define even numbers as those of form 2k for some integer k.
- Let a = 2m and b = 2n for integers m, n.
- Then a + b = 2m + 2n = 2(m + n).
- Since m + n is an integer, a + b is of form 2k, hence even.
Proof by Contradiction
Assume the negation of the statement to be proved, derive a contradiction with the axioms or known theorems.
Example: Proving that √2 is irrational:
- Assume √2 is rational, so √2 = a/b where a, b are integers with no common factors.
- Then 2 = a²/b², so a² = 2b².
- Therefore, a² is even, which means a is even.
- If a is even, a = 2k for some integer k.
- Then 2b² = a² = (2k)² = 4k², so b² = 2k².
- Therefore, b² is even, which means b is even.
- But this contradicts our assumption that a and b have no common factors.
- Therefore, √2 cannot be rational.
Mathematical Induction
Prove a base case, then show that if the statement holds for some k, it must hold for k+1.
Example: Proving that 1 + 2 + 3 + ... + n = n(n+1)/2 for all positive integers n:
- Base case: For n = 1, we have 1 = 1(1+1)/2 = 1, which is true.
- Inductive hypothesis: Assume the formula holds for some k: 1 + 2 + ... + k = k(k+1)/2.
- Inductive step: We need to show it holds for k+1:
1 + 2 + ... + k + (k+1) = k(k+1)/2 + (k+1) = (k+1)(k/2 + 1) = (k+1)(k+2)/2
Which is the formula for n = k+1. - By the principle of mathematical induction, the formula holds for all positive integers n.
Proof by Contrapositive
Instead of proving P → Q, prove the equivalent statement ¬Q → ¬P.
Example: Proving "If n² is even, then n is even."
- We prove the contrapositive: "If n is not even (i.e., n is odd), then n² is not even (i.e., n² is odd)."
- If n is odd, then n = 2k + 1 for some integer k.
- Then n² = (2k + 1)² = 4k² + 4k + 1 = 2(2k² + 2k) + 1.
- Since 2k² + 2k is an integer, n² is of the form 2m + 1, which is odd.
- Therefore, if n² is even, n must be even.
Natural Deduction
A formal system using introduction and elimination rules for logical connectives.
Example: Proving P → P using natural deduction:
- Assume P (as a premise).
- Since we have P, we can conclude P (identical to our premise).
- By the → introduction rule, we can conclude P → P by discharging our assumption.