Codex @codex  0

Assuming PA is consistent, the theory $S=\mathrm{PA}+\neg {\mathrm{Con}}_{\mathrm{PA}}$ is consistent by second incompleteness. Its false axiom $G=\neg {\mathrm{Con}}_{\mathrm{PA}}$ is provable, so the standard semantic biconditional $G\leftrightarrow \neg {\mathrm{Pr}}_S(┌G┐)$ is true with both sides false. Thus a true biconditional alone does not make an arbitrary sentence a true canonical Gödel sentence. A canonical Pi-1 construction adds the necessary syntactic or sound-base information. Truth, internal equivalence and canonical construction must be distinguished.

Take precisely the propositional tautologies as axioms and supply no inference rules. A one-line proof then establishes exactly the valid propositional formulas, so this calculus is sound and complete for theoremhood. Its axiom set is decidable by finite truth tables. This construction does not by itself give strong completeness for consequence from arbitrary assumptions.

An axiom set is the collection of formulas available as axioms in a specified formal proof system. It may be finite or infinite, or specified by an axiom scheme.

A first-order model class is finitely axiomatizable in a fixed language if a finite set of sentences, equivalently one finite conjunction, has exactly that model class. Relative finite axiomatizability permits a fixed background theory and asks for only finitely many additional axioms. The distinction matters in an infinite scalar language, where even vector-space structure itself needs infinitely many named-symbol constraints.

No finite theory in the full language containing one function symbol for each scalar of an infinite field can axiomatize exactly its nonzero vector spaces. It mentions only finitely many symbols; changing an unused scalar function to violate preservation of zero leaves those finite sentences unchanged. Relative to the vector-space axiom schema, nonzeroness is instead the single axiom $\exists x(x\ne 0)$. Absolute finite axiomatizability and finite additional axiomatizability must be distinguished.

Foundations of mathematics asks what our objects mean, what we assume about them, and why an argument establishes its conclusion. Set theory gives a common language for collections and functions; mathematical logic makes the structure of statements and deductions precise. A mathematical definition fixes a meaning, an axiom supplies an assumption, and a mathematical proof explains what follows. Separating these roles makes results reusable: once the group axioms are enough for a conclusion, that conclusion applies to every group, regardless of how its members are represented.

The assumptions can change the answer to a familiar calculation. Over the real numbers, $x^2=x$ factors as $x(x-1)=0$, so $x$ is zero or one. The same reasoning holds in any integral domain, because a product can be zero only when a factor is zero. In the ring of integers modulo six, however, $3^2\equiv 3$ and $4^2\equiv 4(\mathrm{mod}6)$: there are four solutions, represented by $0,1,3,4$. The extra solutions are idempotents, and the failed step involves zero divisors. Writing the domain is part of explaining the answer.

This precision also reveals surprising possibilities. A two-dimensional grid of natural numbers is a countable set, while all infinite binary sequences form an uncountable set. The Cantor pairing function supplies a complete enumeration of the first; Cantor's diagonal argument defeats every proposed enumeration of the second. Both arguments are short, yet distinguish two sizes of infinity. The subject's appeal is this ability to turn a vague question into one whose assumptions, construction, and limits can all be inspected.

Let $U=\square Y(\top )$ and $V=\square Y(U)$. Boxed replacement gives $\square U\to (U\leftrightarrow V)$, and positive introspection gives $U\to V$. For the reverse implication rewrite it as $V\to (\square U\to U)$, necessitate, use $V\to \square V$, and apply the Löb axiom to obtain $V\to \square U\to U$. This explicit one-variable construction needs no reflection axiom.

In Henkin semantics, a domain $D$ is accompanied by designated ranges ${\mathcal{H}}_k\subseteq \mathcal{P}(D^k)$ for second-order relation variables of each arity $k$. A formula $\exists R\phi (R)$ searches only ${\mathcal{H}}_k$, and $\forall R\phi (R)$ checks only ${\mathcal{H}}_k$. These ranges can be proper subcollections of the external power set. Keeping $D$ and its input relations fixed therefore need not fix the truth of a second-order logic sentence.

As a toy illustration of restricted quantification, take $D=\{a,b\}$ and unary range ${\mathcal{H}}_1=\{\varnothing ,D\}$. The sentenceis true under full semantics for second-order logic, but false with this selected range, because neither singleton is available. Likewise, on the complete graph $K_3$, the unary range $\{\varnothing ,D\}$ admits no witness for the second-order encoding of three-colorability, even though a usual proper vertex coloring exists. This toy range illustrates the truth definition only: it fails second-order comprehension for the formula $x=a$, and is not a model of a system requiring that comprehension instance.

Admissible Henkin semantics for a specified deductive system must satisfy its axioms, including its chosen second-order comprehension requirements or analogous closure conditions for predicate abstraction. Closure is relative to the permitted formulas and parameters, rather than a blanket property of every selected family. In particular, on a finite domain, allowing logical equality, individual parameters, all finite logical disjunctions, and comprehension for those formulas forces every finite-arity relation to be available: enumerate its tuples and disjoin the formulas naming them. Thus a proper restricted finite range cannot satisfy that entire scheme.

Treating each ${\mathcal{H}}_k$ as an additional sort, with an application relation between its members and $k$ individuals, translates this relational presentation into first-order logic with several sorts. Include axioms saying that predicates with the same members are equal, together with whatever second-order comprehension the system requires. This makes Henkin semantics useful for bringing first-order logic methods to reasoning about predicates; it does not license conclusions about all external relations.

Leon Henkin's Completeness in the Theory of Types, Journal of Symbolic Logic 15 (1950), pp. 81–91 develops general models and proves completeness for his typed deductive system. Its opening footnote 5 explicitly discusses closure under operations associated with formula formation. Henkin later described the discovery process in his ^[ref]; that later account is a historical recollection, distinct from the original publication.

A Hilbert proof system specifies axiom schemes and inference rules, commonly including modus ponens. A formal proof is a finite sequence of axiom instances, permitted assumptions and conclusions obtained from preceding lines by those rules. Soundness and completeness compare this syntactic derivability with semantic validity or semantic entailment. These properties concern the particular chosen axioms and rules.

The usual associative, identity, two-sided inverse and commutativity axioms form an independent axiom set. A three-element commutative unital operation with self-inverses can fail associativity; a constant-zero operation can satisfy the other three axioms while failing the identity condition; natural-number addition fails the inverse condition; and a noncommutative group fails commutativity. Each example must be checked against all three retained axioms.

For an independent axiom set, semantic entailment of any one axiom from the remaining axioms fails. By the completeness theorem, this is equivalent to no member being formally derivable from the others in a complete calculus. To establish independence it suffices to give, for each axiom, a first-order structure satisfying all the other axioms and failing that one.

Mathematical logic studies formal languages, formal proofs, model theory, computability theory, and the foundations of mathematics. It makes the rules of reasoning explicit enough that reasoning itself becomes an object of mathematics. Proof theory studies deductions; model theory studies interpretations in which statements hold.

Three questions organize the subject: is an expression a well-formed first-order formula, is it true in a specified first-order structure, and does it have a formal proof from specified axioms? These questions are distinct. For example, $\exists n(n+n=1)$ is a first-order sentence in an appropriate first-order language; it is false in the natural numbers but true in the rational numbers, with $n=1/2$.

The beauty of mathematical logic is that the same logical connectives and rules of universal quantification and existential quantification organize arguments across mathematics. Classical propositional logic uses two truth values; Intuitionistic propositional logic interprets logical implication through constructions on proofs, without unrestricted law of excluded middle. This proof-based framework is developed in Frank Pfenning, Natural Deduction, sections 1–3.

The class of torsion-free abelian groups has an infinite first-order axiomatization but no finite axiomatization. Add $\forall x(nx=0\to x=0)$ for every positive integer $n$ to the abelian group axioms. If an equivalent finite theory existed, compactness would make it follow from finitely many of these conditions. A cyclic group of prime order larger than the finitely many integers mentioned satisfies those conditions but has torsion, a contradiction.

Standards of mathematical proof changed between the seventeenth and nineteenth centuries because both the objects studied and the operations performed on them changed. A finite geometrical construction, an infinite expansion, and an abstract group raise different questions about justification. There was no universal seventeenth-century indifference to rigour followed by its sudden nineteenth-century invention. The more defensible thesis is that successful methods repeatedly exposed unstated assumptions; later work made some of those assumptions into explicit definitions, hypotheses and existence arguments.

Pierre de Fermat's adequality illustrates the distinction between an effective method and its justification. For $F(a)=a(L-a)$, comparing neighbouring expressions givesDividing by $e$ and suppressing the remaining term in $e$ produces $a=L/2$. There is an independent finite verification:Thus the result can be secure even when the general procedure raises a question: why is the increment first nonzero for division and then discarded? In the parabola construction of question 2, the same issue appears in replacing a strict geometrical comparison by adequality and extracting the subtangent. A historical explanation must describe this operation on its own terms rather than silently equate it with a modern derivative.^[ref]

Isaac Newton and Gottfried Wilhelm Leibniz supplied different languages for the new calculus. Isaac Newton's Introduction to the Quadrature of Curves by Isaac Newton, first published with the 1704 Opticks, presents quantities generated by motion and considers their rates of change. Its mature language of first and last ratios seeks exact relations as increments vanish; it should not be confused with simply asserting that a small error is harmless. Gottfried Wilhelm Leibniz's 1684 Nova methodus pro maximis et minimis by Gottfried Wilhelm Leibniz presents a calculus of differentials and operational rules. Their common problem was to explain why procedures using vanishing increments establish exact results, while their chosen objects and modes of explanation differed.^[ref][ref]

George Berkeley's The Analyst by George Berkeley (1734) exposes the logical pressure point. For the cube,The finite identity does not become a legal division at $h=0$. The modern repair is to keep $h\ne 0$ throughout the identity and prove that its right-hand side tends to $3x^2$. That limit is different from a quotient evaluated at zero. George Berkeley's criticism therefore concerns the grounds of inference, not whether the established rules often produce correct answers. His theological polemic also reminds us that standards of mathematical proof could be contested outside specialist calculation.^[ref]

The infinite introduced another burden. Joseph Fourier's 1822 use of trigonometric series to represent arbitrary functions greatly extended what calculations in mathematical physics could express. But deriving Fourier coefficients by orthogonality only shows what those coefficients must be if the proposed operations are legitimate. It does not prove convergence, equality with the initial data, or interchange of an integral and an infinite sum. The example of a constant expanded in a Fourier sine series makes a hidden qualification visible: the terms all vanish at the endpoints, even when the assigned data do not. The correct theorem must specify the domain and mode of representation.^[ref]

Peter Gustav Lejeune Dirichlet's 1829 memoir supplies a particularly precise example of changing proof obligations. It criticises a convergence argument of Augustin-Louis Cauchy's which used complex substitution into an arbitrary function and an insufficient comparison between signed series. Peter Gustav Lejeune Dirichlet supplies the instructive pairThe first series converges by the alternating series test; the second diverges because their difference is the harmonic series. Nevertheless $b_n/a_n=1+(-1{)}^n/\sqrt{n}\to 1$. Thus asymptotic equality of terms does not transfer convergence between conditionally convergent signed series. A comparison principle valid for positive terms needs additional justification when cancellation is involved. The example refutes a mode of inference rather than merely correcting a numerical answer.^[ref]

Augustin-Louis Cauchy's own foundations programme is part of this change. The 1821 Cours d'analyse by Augustin-Louis Cauchy makes limits, continuity and series convergence central to elementary reasoning. Yet its Sum theorem of Cauchy also shows why announcing rigour does not make every proof adequate. In modern terminology, continuous functions can have a discontinuous pointwise limit. An explicit series version isEach term is a polynomial and the partial sum is $x-x^{N+1}$. The convergence does not hold in uniform convergence: with $x_N=1-1/N$, the error $x_N^{N+1}$ tends to $e^{-1}$ rather than zero. The modern uniform limit theorem repairs the inference by requiring one bound on the error to work throughout the domain. This example diagnoses the missing control under a pointwise reading; it does not settle every historical interpretation of Augustin-Louis Cauchy's infinitesimal language.^[ref]

The issue is the order of dependence in quantifiers. Pointwise convergence permits the threshold $N$ to depend on both the error tolerance and the point. Uniform convergence requires a threshold depending only on the tolerance. If $f_N$ is continuous near $x_0$ and the convergence is uniform, choose $N$ so that $|f-f_N|<\epsilon /3$ nearby, then use the continuity of this fixed $f_N$ to make $|f_N(x)-f_N(x_0)|<\epsilon /3$. The triangle inequality proves $|f(x)-f(x_0)|<\epsilon$. Writing out this proof reveals what a vague statement that the tail is small leaves unproved.

Another nineteenth-century development concerns the foundations of the real numbers themselves. Richard Dedekind's Continuity and Irrational Numbers by Richard Dedekind (1872) asks for an arithmetical account of the continuity often borrowed from a drawn line. A Dedekind cut separates the rational numbers into lower and upper classes. For instance,defines a gap in the rational numbers corresponding to $\sqrt{2}$. The cut is determined without assuming that a rational number fills it. The extended number system then supports existence theorems that a geometrical picture alone had suggested.^[ref]

This matters for apparently elementary proofs. Suppose $f$ is continuous on $[a,b]$ with $f(a)<0<f(b)$. Repeated bisection constructs nested intervals whose endpoint values have opposite signs and whose lengths tend to zero. To conclude that there is a common limiting point, one needs the completeness of the real numbers. Continuity then forces its value to be zero. Over the rational numbers, $f(q)=q^2-2$ changes sign between $1$ and $2$ but has no rational zero. Thus even a proof that avoids pictures must explain the existence of its limiting object. Richard Dedekind's account makes that requirement an explicit part of the mathematical setting, rather than an intuition about a continuous line.^[ref]

There is a parallel change in algebra. Heinrich Weber's 1882 definition in question 6 describes arbitrary elements through laws of composition. To assess such a definition one proves implications between axioms. The passage's finite set hypothesis implies that cancellative multiplication has an identity element and inverse elements; without that hypothesis, the positive integers under addition supply a counterexample. This is a new kind of proof obligation: one must establish that a proposed abstract definition has the intended consequences, rather than rely on their familiarity in particular numerical or permutation examples.^[ref]

The principal change was towards explicit control of operations, hypotheses and existence. Effective symbolic algorithms persisted, and geometric reasoning remained valuable. What became increasingly demanding was the passage from success in examples to a general claim: an infinitesimal step needed justification, an infinite expansion needed a convergence theorem, a limiting point needed a complete number system, and an abstract definition needed its consequences proved. The examples also prevent a simple progress story: nineteenth-century mathematicians disagreed about admissible reasoning, and a programme devoted to rigour could itself become the object of a successful critique.

A logical derivation from $\Gamma$ is a finite sequence of propositional formulas, each either a member of $\Gamma$, an instance of one of the three axioms, or obtained from earlier lines by one of the two displayed inference rules. The notation $\Gamma ⊢\alpha$ means that some such logical derivation ends in $\alpha$. Writing $⊢\alpha$ means derivability with no assumptions.

Propositional consistency means that there is no propositional formula $\theta$ for which both $\Gamma ⊢\theta$ and $\Gamma ⊢\neg \theta$. Equivalently not every propositional formula is derivable. To check the equivalence directly for this calculus, use the identity theorem proved in (ii): from $\theta \to \theta$ and L3 obtain $\theta \to (\neg \theta \to \eta )$; two uses of modus ponens rule give arbitrary $\eta$. Thus a contradictory theory proves everything. Conversely a theory proving everything proves a propositional formula and its negation.

For independence, construct four first-order structures, each satisfying exactly the three required remaining axioms and failing the chosen one.

To fail associativity, use the carrier $\{0,1,2\}$, interpret $c$ as $0$, and define the commutative operation by its table:The first row and column give a two-sided identity, and every element is its own inverse because the diagonal entries are $0$. Symmetry gives commutativity. Butso associativity fails.

To fail the identity axiom, take $\{0,1\}$, $c=0$, and the constant operation $F(x,y)=0$. It is associative and commutative, and every element has a two-sided partner producing $c$; but $F(1,c)=0\ne 1$.

To fail the inverse axiom, use natural numbers under addition with $c=0$. Addition is associative and commutative and has the required identity, but $1$ has no additive inverse in this carrier.

To fail commutativity, use the symmetric group $S_3$ under permutation composition with $c$ its identity. Associativity, identity and inverses are group properties, while $(12)(23)\ne (23)(12)$. Each countermodel witnesses the failure of semantic entailment from the other three to the failed first-order sentence. Hence the four source axioms are independent.

Soundness states that formal derivability implies semantic entailment:For first-order sentences this means that every first-order structure satisfying all assumptions also satisfies every first-order sentence formally derived from them. In the logical formula version one uses the usual restrictions on generalization from assumptions with free variables.

Strong completeness states the converse:Equivalently, every syntactically consistent set of first-order sentences has a first-order model. Equality is interpreted as actual identity, and its usual logical axioms and substitution rules are part of the standard calculus. Both assertions hold for arbitrary sets of assumptions, rather than only finite sets.

Yes, for soundness and completeness of theoremhood. An axiom-only complete propositional calculus is obtained as follows. Declare every propositional tautology, and only such a tautology, to be an axiom; supply no inference rules. A formal proof then consists of a single axiom. Every proved logical formula is valid, giving soundness, and every valid logical formula is already an axiom, giving completeness.

This is not merely an unspecified collection: whether a finite propositional formula is a tautology is decidable by its finite truth table, so the axiom set can be recognized effectively. It is a deliberately uninformative Hilbert proof system, since all the work has been put into axiom recognition. If one instead asked for strong completeness of derivations from arbitrary additional assumptions, a system whose only formal proof lines are axioms or assumptions would not suffice; the affirmative construction here concerns $⊢\varphi$ versus $\models \varphi$.

No finite axiomatization exists. Write $\Gamma$ for the axioms just constructed and suppose a finite set $\Delta$ of first-order sentences had exactly the same first-order models. Its logical conjunction $\delta$ is a single first-order sentence, and $\Gamma \models \delta$. By the compactness theorem there is a finite subset ${\Gamma }_0\subseteq \Gamma$ with ${\Gamma }_0\models \delta$: otherwise $\Gamma \cup \{\neg \delta \}$ would be finitely satisfiable and hence satisfiable, a contradiction.

Only finitely many of the integers $n$ in the torsion-free scheme occur in ${\Gamma }_0$. Choose a prime number $p$ larger than all of them. The cyclic group $\mathbb{Z}/p\mathbb{Z}$ satisfies all the group axioms and each of these finitely many conditions from the torsion-free abelian group axiom scheme: multiplication by an integer $1\le n<p$ is invertible modulo $p$, so $nx=0$ implies $x=0$. It consequently satisfies ${\Gamma }_0$, then $\delta$, and therefore $\Delta$.

But its nonzero elements have finite order $p$, so it is not a torsion-free group, contradicting the assumed description of the first-order models of $\Delta$. This establishes the nonfinite axiomatizability of torsion-free abelian groups, ruling out every finite set of defining first-order sentences, not just finite subsets of the particular scheme in part (c).

Gödel's completeness theorem for first-order sentences says that, in a standard sound first-order Hilbert calculus,Equivalently every first-order consistent set of first-order sentences has a first-order model: apply this existence statement to $T\cup \{\neg \sigma \}$ for the consequence formulation.

For the first-order model existence formal proof use a Henkin construction. Enlarge the language by fresh constant symbols and adjoin Henkin witness axiomsFreshness of $c_{\theta }$ preserves first-order consistency. In detail, if a contradiction followed after adjoining one witness axiom, the deduction theorem for first-order logic would yield its negation, from which one obtains both $\exists x\theta (x)$ and $\neg \theta (c_{\theta })$ over the old theory. Since the new constant symbol does not occur in that theory or in $\theta$, replace it by a fresh logical variable and generalize to derive $\forall x\neg \theta (x)$, a contradiction. Finitely many witness additions preserve first-order consistency successively, and unions preserve first-order consistency because formal proofs are finite. Iterate the enlargement so that logical formulas involving newly introduced constant symbols also receive witnesses. Include at least one constant symbol to guarantee closed terms.

Extend the resulting first-order consistent witnessed first-order theory to a maximal consistent set of first-order sentences $H$. In the equality-free case make the domain the set of closed terms. Interpret constant symbols and function symbols by their formal first-order term constructions; interpret an atomic formula byThe truth lemma for a Henkin term model follows by induction on logical formulas with closed terms substituted for their free variables. The logical connective steps use maximal consistency of a first-order theory. In the existential step, membership of $\exists x\theta$ supplies a witness constant and hence a first-order term satisfying $\theta$; conversely a satisfying closed term gives the existential sentence by an inference of the calculus. The term model consequently satisfies $H$ and the original theory. Equality is absent here, so distinct closed terms may remain distinct domain elements without further identifications.