Layer 0 — Logic: The Foundation of Reasoning¶

Key Metrics

Attribute	Value
Position	Layer 0 — the absolute bedrock
Dependencies	None (this is the starting point)
Enables	Every subsequent layer
Key results	Soundness, Completeness, Compactness, Incompleteness
Historical span	Aristotle (~350 BCE) → Frege (1879) → Gödel (1931) → Turing (1936)

Core Idea¶

Logic is the language and rulebook of valid reasoning. It answers two questions:

What counts as a well-formed statement? (syntax)
When does a statement follow from other statements? (semantics and proof theory)

Every mathematical proof — in every layer — is ultimately a chain of logical deductions. Logic does not tell us what to study; it tells us how to be certain about whatever we study.

Key Structures¶

Propositional Logic¶

The simplest formal system. Atomic propositions \(P, Q, R, \ldots\) are combined with connectives:

Connective	Symbol	Meaning
Negation	\(\lnot P\)	"not \(P\)"
Conjunction	\(P \land Q\)	"\(P\) and \(Q\)"
Disjunction	\(P \lor Q\)	"\(P\) or \(Q\)" (inclusive)
Implication	\(P \to Q\)	"if \(P\) then \(Q\)"
Biconditional	\(P \leftrightarrow Q\)	"\(P\) if and only if \(Q\)"

A tautology is a formula true under every truth-value assignment. The canonical example:

\[ P \lor \lnot P \qquad \text{(Law of Excluded Middle)} \]

A formula is satisfiable if it is true under some assignment. The distinction between tautology and satisfiability is the seed of computational complexity theory (SAT is NP-complete).

Predicate Logic (First-Order Logic)¶

Propositional logic cannot express "for all \(x\)" or "there exists an \(x\) such that." Predicate logic adds:

Variables: \(x, y, z, \ldots\)
Predicates: \(P(x)\), \(R(x, y)\)
Quantifiers:
- Universal: \(\forall x \, P(x)\) — "for every \(x\), \(P(x)\) holds"
- Existential: \(\exists x \, P(x)\) — "there is some \(x\) for which \(P(x)\) holds"
Functions and constants: \(f(x)\), \(c\)

The expressive leap is enormous. Predicate logic can formalize:

\[ \forall \varepsilon > 0 \;\; \exists \delta > 0 \;\; \forall x \;\; (|x - a| < \delta \implies |f(x) - f(a)| < \varepsilon) \]

This is the \(\varepsilon\)-\(\delta\) definition of continuity — a statement in Layer 5 (Analysis) that is written in the language of Layer 0.

Proof Systems¶

A proof system is a set of rules for deriving conclusions from premises. Two major frameworks:

Natural Deduction (Gentzen, 1935): Rules are introduction and elimination rules for each connective. For example, \(\land\)-introduction says: from \(P\) and \(Q\), infer \(P \land Q\).

Sequent Calculus (Gentzen, 1935): Proofs manipulate sequents \(\Gamma \vdash \Delta\), meaning "from the assumptions \(\Gamma\), at least one of \(\Delta\) follows." The cut-elimination theorem shows that any proof can be transformed into one without "detours" — a foundational result for proof theory.

Model Theory¶

Model theory studies the relationship between formal languages and the structures that satisfy them.

A model (or structure) for a first-order language assigns:

A non-empty domain (universe)
Interpretations for each predicate, function, and constant symbol

A sentence \(\varphi\) is true in a model \(\mathcal{M}\) (written \(\mathcal{M} \models \varphi\)) if it holds under the model's interpretation. Key results:

Löwenheim-Skolem Theorem

If a first-order theory has an infinite model, it has models of every infinite cardinality.

Consequence: First-order logic cannot pin down the "size" of its models. You cannot write a first-order sentence that is true only in \(\mathbb{R}\) and not in some countable structure. This is a fundamental expressiveness limitation.

Knowledge Gap

The precise relationship between the upward and downward Löwenheim-Skolem theorems and their dependence on the Axiom of Choice needs verification against a primary model theory reference (e.g., Chang & Keisler or Hodges).

To resolve: Check whether the upward direction requires full AC or only a weaker choice principle.

Computability Theory¶

Turing machines (1936) formalize the intuitive notion of "mechanical computation." A Turing machine reads and writes symbols on an infinite tape according to a finite table of rules.

Church-Turing Thesis

Every effectively computable function is computable by a Turing machine.

This is not a theorem in the strict sense — it cannot be proved, because "effectively computable" is an informal notion. But it is universally accepted and has never been refuted.

The halting problem is the first concrete example of an undecidable problem:

Undecidability of the Halting Problem (Turing, 1936)

There is no Turing machine \(H\) that, given any program \(P\) and input \(x\), correctly decides whether \(P\) halts on \(x\).

Proof sketch. Suppose such \(H\) exists. Define a machine \(D\) that, on input \(P\), runs \(H(P, P)\) and does the opposite: if \(H\) says "halts," \(D\) loops forever; if \(H\) says "loops," \(D\) halts. Now ask: does \(D\) halt on input \(D\)? Either answer leads to contradiction. \(\square\)

This is the computability-theoretic cousin of Gödel's incompleteness — both arise from self-referential diagonal arguments.

Historical Trigger¶

timeline
    title The Evolution of Formal Logic
    ~350 BCE : Aristotle's syllogistic logic
              : First systematic study of valid argument forms
    1847 : Boole's algebraic logic
         : Logic as algebraic computation
    1879 : Frege's Begriffsschrift
         : First complete system of predicate logic
    1901 : Russell's Paradox
         : Naive comprehension is inconsistent
    1910-13 : Principia Mathematica
             : Russell & Whitehead attempt a complete foundation
    1929 : Gödel's Completeness Theorem
         : First-order logic is complete
    1931 : Gödel's Incompleteness Theorems
         : No consistent system can prove all truths of arithmetic
    1936 : Church & Turing
         : Undecidability and the formalization of computation

The arc is: informal reasoning → formal syntax → a paradox forces axiomatization → the axiomatized system turns out to have inherent limits.

Key Proofs¶

Soundness of Propositional Logic Foundational¶

Soundness

If \(\Gamma \vdash \varphi\) (i.e., \(\varphi\) is provable from \(\Gamma\)), then \(\Gamma \models \varphi\) (i.e., \(\varphi\) is true in every model of \(\Gamma\)).

Why it matters: Soundness guarantees that the proof system never lies. Every theorem it produces is genuinely true. Without soundness, proofs would be meaningless symbol-pushing.

Proof-sketch

By structural induction on the derivation of \(\Gamma \vdash \varphi\). Each axiom is verified to be a tautology, and each inference rule (e.g., modus ponens) is verified to preserve truth. Since the base cases are true and each step preserves truth, the conclusion is true. \(\square\)

What it unlocks: The soundness of propositional logic is inherited by every system built on top of it. It is the warranty on the entire mathematical supply chain.

Gödel's Completeness Theorem (First-Order Logic) Foundational¶

Completeness (Gödel, 1929)

If \(\Gamma \models \varphi\) (i.e., \(\varphi\) is true in every model of \(\Gamma\)), then \(\Gamma \vdash \varphi\) (i.e., \(\varphi\) is provable from \(\Gamma\)).

This is the converse of soundness. Together, soundness and completeness say:

\[ \Gamma \vdash \varphi \iff \Gamma \models \varphi \]

Provability and truth coincide — but only for first-order logic. Higher-order logics sacrifice completeness for expressiveness.

Gödel's First Incompleteness Theorem Insight¶

First Incompleteness Theorem (Gödel, 1931)

Any consistent formal system \(F\) capable of expressing basic arithmetic contains a sentence \(G_F\) such that:

\(G_F\) is true (in the standard model \(\mathbb{N}\)), but
\(G_F\) is not provable in \(F\), and
\(\lnot G_F\) is not provable in \(F\).

In short: \(F\) is incomplete.

The Gödel sentence. The core idea is self-reference. Gödel constructs a sentence \(G_F\) that, when decoded, says:

\[ G_F \equiv \text{"This sentence is not provable in } F\text{."} \]

If \(F\) could prove \(G_F\), then \(G_F\) would be false (it claims to be unprovable), contradicting the assumed soundness of \(F\). So \(G_F\) is not provable. But then what \(G_F\) says is true — there really is a true sentence \(F\) cannot prove.

Proof-sketch

Gödel numbering: Assign a unique natural number to every symbol, formula, and proof in \(F\).
Representability: Show that the relation "the number \(n\) encodes a proof of the formula with Gödel number \(m\)" is expressible in \(F\) (because \(F\) can do basic arithmetic).
Diagonal lemma: Construct a sentence \(G_F\) with Gödel number \(g\) such that \(F \vdash G_F \leftrightarrow \lnot \text{Prov}_F(\ulcorner G_F \urcorner)\), where \(\text{Prov}_F\) is the provability predicate.
Derive the contradiction: If \(F \vdash G_F\), then by soundness \(G_F\) is true, meaning \(G_F\) is not provable — contradiction. So \(F \nvdash G_F\). But then \(G_F\) is true (its content is that it is unprovable, and it is). And \(F \nvdash \lnot G_F\) because \(G_F\) is true and \(F\) is consistent. \(\square\)

What it means: No single formal system can capture all mathematical truth. There will always be true statements that escape the net. This is not a defect of any particular system — it is an intrinsic feature of sufficiently powerful formal reasoning.

Gödel's Second Incompleteness Theorem Insight¶

Second Incompleteness Theorem (Gödel, 1931)

If \(F\) is a consistent formal system capable of expressing basic arithmetic, then \(F\) cannot prove its own consistency.

Formally: \(F \nvdash \text{Con}(F)\), where \(\text{Con}(F)\) is the arithmetic sentence asserting "\(F\) is consistent."

Why it matters: You cannot pull yourself up by your own bootstraps. If you want to know that \(F\) is consistent, you must use a stronger system — which then has its own unprovable consistency statement. The chain never terminates.

The Halting Problem and Church-Turing Insight¶

The undecidability of the halting problem (sketched above) is the computational mirror of incompleteness. Both results use diagonal arguments, and both establish inherent limits on formal methods:

Result	Domain	Limit
Incompleteness	Provability	Not all truths are provable
Halting problem	Computability	Not all questions are decidable

Knowledge Gap

The precise technical relationship between Gödel's incompleteness and the undecidability of the halting problem — specifically, whether one can be derived from the other in a strong formal sense — merits a careful treatment citing Soare or Odifreddi.

To resolve: Verify the reduction path: Incompleteness → existence of a recursively enumerable but non-recursive set → undecidability of the halting problem (and conversely).

Connections¶

Dependencies¶

None. Logic is Layer 0 — it presupposes no mathematical content. (It does presuppose a meta-language and informal reasoning, but these are pre-mathematical.)

Upward Impact¶

Target Layer	What Logic Provides
Set Theory (1)	The formal language in which ZFC axioms are stated; the proof rules used to derive consequences
Number Systems (2)	First-order Peano Arithmetic is formulated in predicate logic
All layers	Every proof in every layer is a chain of logical deductions

Logic is the only layer that every other layer depends on directly.

Sources & Further Reading¶

Enderton, H. B. A Mathematical Introduction to Logic (2^nd ed., 2001). — Standard undergraduate text covering propositional and predicate logic, completeness, and compactness.
Gödel, K. "On Formally Undecidable Propositions" (1931). — The original incompleteness paper. Difficult but historically essential.
Turing, A. M. "On Computable Numbers, with an Application to the Entscheidungsproblem" (1936). — Introduces Turing machines and proves the undecidability of the halting problem.
Smith, P. An Introduction to Gödel's Theorems (2^nd ed., 2013). — The most accessible modern treatment of incompleteness.
Marker, D. Model Theory: An Introduction (2002). — Graduate-level model theory; covers Löwenheim-Skolem and compactness in depth.

title: Glossary tags: - reference - glossary

Glossary¶

A working reference of essential terms spanning all nine layers of the mathematical hierarchy. Terms are grouped alphabetically; hover-tooltip definitions are provided at the bottom for use across the knowledge base.

A¶

Term	Definition
Abelian Group	A group \((G, \ast)\) in which the operation is commutative: \(a \ast b = b \ast a\) for all \(a, b \in G\).
Algebraic Closure	A field extension in which every non-constant polynomial has a root. \(\mathbb{C}\) is the algebraic closure of \(\mathbb{R}\).
Axiom	A statement accepted without proof that serves as a starting point for a deductive system.
Axiom of Choice	For any collection of non-empty sets, there exists a function selecting one element from each set. Equivalent to Zorn's lemma and the well-ordering theorem.

B¶

Term	Definition
Bijection	A function that is both injective (one-to-one) and surjective (onto), establishing a one-to-one correspondence between two sets.
Boolean Algebra	An algebraic structure capturing the laws of classical logic: complement, meet, join, with identities \(0\) and \(1\).

C¶

Term	Definition
Cardinality	A measure of the "size" of a set. Two sets have equal cardinality if a bijection exists between them.
Category	A collection of objects and morphisms (arrows) between them, equipped with composition and identity morphisms satisfying associativity and identity laws.
Cauchy Sequence	A sequence \((a_n)\) in a metric space where for every \(\varepsilon > 0\) there exists \(N\) such that \(d(a_m, a_n) < \varepsilon\) for all \(m, n > N\).
Commutative Ring	A ring in which multiplication is commutative: \(ab = ba\).
Complex Number	An element of \(\mathbb{C} = \{a + bi \mid a, b \in \mathbb{R}\}\), where \(i^2 = -1\).
Conjecture	A mathematical statement believed to be true but not yet proven.
Continuity	A function \(f\) is continuous at \(a\) if \(\lim_{x \to a} f(x) = f(a)\). Intuitively, small changes in input produce small changes in output.
Convergence	A sequence \((a_n)\) converges to \(L\) if for every \(\varepsilon > 0\) there exists \(N\) such that (
Corollary	A result that follows directly from a theorem with little or no additional proof.

D¶

Term	Definition
Dedekind Cut	A partition of \(\mathbb{Q}\) into two non-empty sets \((A, B)\) where every element of \(A\) is less than every element of \(B\) and \(A\) has no greatest element. Used to construct \(\mathbb{R}\).
Derivative	The instantaneous rate of change of \(f\) at \(x\): \(f'(x) = \lim_{h \to 0} \frac{f(x+h) - f(x)}{h}\).
Distribution	A probability measure on a measurable space describing the likelihood of outcomes for a random variable.

E¶

Term	Definition
Eigenvalue	A scalar \(\lambda\) such that \(Av = \lambda v\) for some non-zero vector \(v\) (the eigenvector) and linear map \(A\).

F¶

Term	Definition
Field	A commutative ring with unity in which every non-zero element has a multiplicative inverse. Examples: \(\mathbb{Q}\), \(\mathbb{R}\), \(\mathbb{C}\).
Functor	A structure-preserving map between categories, sending objects to objects and morphisms to morphisms while respecting composition and identities.

G¶

Term	Definition
Graph	A combinatorial structure \(G = (V, E)\) consisting of vertices \(V\) and edges \(E \subseteq V \times V\).
Group	A set \(G\) with a binary operation satisfying closure, associativity, existence of identity, and existence of inverses.

H¶

Term	Definition
Homeomorphism	A continuous bijection whose inverse is also continuous. Two spaces are homeomorphic if they are "topologically the same."
Homomorphism	A structure-preserving map between algebraic structures (groups, rings, etc.).

I¶

Term	Definition
Injection	A function \(f\) where \(f(a) = f(b) \implies a = b\). Also called "one-to-one."
Integral	The Riemann or Lebesgue integral measures the "accumulated value" of a function over a domain. \(\int_a^b f(x)\,dx\).
Irrational Number	A real number that cannot be expressed as a ratio of integers. Examples: \(\sqrt{2}\), \(\pi\), \(e\).
Isomorphism	A bijective homomorphism — a structure-preserving map with a structure-preserving inverse. Two objects are isomorphic if they are "algebraically the same."

L¶

Term	Definition
Lemma	A proven statement used as a stepping stone toward a larger theorem.
Limit	The value that a function or sequence approaches as the input or index approaches some value.

M¶

Term	Definition
Manifold	A topological space that locally resembles \(\mathbb{R}^n\). Smooth manifolds carry differentiable structure.
Measure	A function assigning a non-negative extended real number to subsets of a space, generalizing length, area, and volume. Must be countably additive.
Morphism	An arrow in a category — a generalization of "structure-preserving map" that abstracts functions, homomorphisms, and continuous maps.

N¶

Term	Definition
Natural Transformation	A family of morphisms connecting two functors \(F, G : \mathcal{C} \to \mathcal{D}\) that commutes with every morphism in \(\mathcal{C}\).

P¶

Term	Definition
Predicate	A statement containing one or more variables that becomes a proposition when values are substituted. Example: \(P(x) \equiv x > 5\).
Prime	A natural number \(p > 1\) whose only divisors are \(1\) and \(p\). The fundamental building blocks of \(\mathbb{N}\) under multiplication.
Proof	A finite sequence of logical deductions establishing the truth of a statement from axioms and previously proven results.

Q¶

Term	Definition
Quantifier	A logical symbol binding a variable: the universal quantifier \(\forall\) ("for all") and the existential quantifier \(\exists\) ("there exists").

R¶

Term	Definition
Random Variable	A measurable function from a probability space to \(\mathbb{R}\) (or \(\mathbb{R}^n\)).
Ring	A set equipped with two operations (addition and multiplication) where addition forms an abelian group, multiplication is associative, and multiplication distributes over addition.

S¶

Term	Definition
Surjection	A function \(f: A \to B\) where every element of \(B\) is the image of at least one element of \(A\). Also called "onto."

T¶

Term	Definition
Tautology	A propositional formula that is true under every truth-value assignment. Example: \(P \lor \lnot P\).
Theorem	A mathematical statement proven true within a formal system.
Topology	The study of properties preserved under continuous deformations. A topology on a set \(X\) is a collection of "open" subsets closed under arbitrary unions and finite intersections.
Transcendental Number	A real or complex number that is not a root of any non-zero polynomial with integer coefficients. Examples: \(\pi\), \(e\).
Tree	A connected acyclic graph. Equivalently, a graph on \(n\) vertices with exactly \(n - 1\) edges and no cycles.

V¶

Term	Definition
Vector Space	A set \(V\) over a field \(F\) equipped with addition and scalar multiplication satisfying eight axioms (closure, associativity, distributivity, identity elements, inverses).

Z¶

Term	Definition
ZFC	Zermelo-Fraenkel set theory with the Axiom of Choice — the standard axiomatic foundation for modern mathematics.