1.9. Axioms and proofs


An expression is ground if its list of available free variables is empty (all its variables are bound), so that its value only depends on the system where it is interpreted.
In first-order logic, a statement is a ground formula. Thus, a statement A will have a definite Boolean value only depending on the choice of a system M that interprets its language. We denote MA the truth of A in M.
The axioms list of a theory is a set of statements, meant to be all true in some given system(s) called models of the theory. Let us explain.

Realistic vs. axiomatic theories in mathematics and other sciences

Apart from the distinction of nature (mathematical vs. non-mathematical), theories may also differ by the intention of their use, between realism and formalism.

An axiomatic theory is a formally given theory T = (τ, L, X) with an axioms list X, that means to define the class of its models, as that of all systems M interpreting the language L where all axioms (elements of X) are true, which will be denoted MT.

A realistic theory is a theory involved to describe either a fixed or a variable system, i.e. a class of systems, seen as given from some independent reality. Its given axioms are statements which, for some reason, are considered known as true on all these systems. Such a theory is true if all its axioms are indeed true there. In this case, these systems are models, qualified as standard for contrast with other (unintended) models of that theory taken axiomatically.

This truth will usually be ensured for realistic theories of pure mathematics : arithmetic and set theory (though the realistic meaning of set theory will not always be clear depending on considered axioms). These theories will also admit non-standard models, making their realistic and axiomatic meanings effectively differ.
Outside pure mathematics, the truth of realistic theories may be dubious (questionable): non-mathematical statements over non-mathematical systems may be ambiguous (ill-defined), while the truth of theories of applied mathematics may be approximative, or speculative as the intended "real" systems may be unknown (contingent among other possible ones). There, a theory is called falsifiable if, in principle, the case of its falsity can be discovered by comparing its predictions (theorems) with observations. For example, biology is relative to a huge number of random choices silently accumulated by Nature on Earth during billions of years ; it has lots of "axioms" which are falsifiable and require a lot of empirical testing.
Non-realistic theories outside mathematics (not called "axiomatic" by lack of mathematical precision) would be works of fiction describing imaginary or possible future systems.

Euclidean geometry was first conceived as a realistic theory of applied mathematics (for its role of first theory of physics), then became understood as an axiomatic theory of pure mathematics among diverse other, equally legitimate geometries in a mathematical sense; while the real physical space is more accurately described by the non-Euclidean geometry of General Relativity.


A proof of a statement A in a theory T, is a finite model of a one-proof theory (reduction of proof theory to the description of a single proof), having A as "conclusion" and involving a finite list of axioms among those of T.
Suitable full formalizations of the concept of proof for first-order logic could be found by specialists. Those can take the form of formalized (one-)proof theories (as axiomatic theories), or proof verification algorithms (only requiring an amount of computing resources related to the size of a given proof).
But most mathematical works are only partially formalized : semi-formal proofs are used with just enough rigor to give the feeling that a full formalization is possible, without actually writing it ; an intuitive vision of a problem may seem clearer than a formal reasoning. Likewise, this work will present proofs naturally without explicit full formalization : sometimes using natural language articulations, proofs will mainly be written as successions of statements each visibly true thanks to previous ones, premises, axioms, known theorems and rules of proof, especially those of quantifiers (1.10). End of proof is marked by "∎".
Yet without giving details of any proof theory, let us review some general properties.

We say that A is provable in T, or a theorem of T, and write TA if a proof of A in T exists. In practice, we only qualify as theorems the statements known as such, i.e. for which a proof is known. But synonyms for "theorem" are traditionally used according to their importance: a theorem is more important than a proposition; either of them may be deduced from an otherwise less important lemma, and easily implies an also less important corollary.

Any good proof theory needs of course to be sound, which means only "proving" always true statements : provability implies truth in every model (where all axioms are true).

Logical validity

For a given language L, a statement A is called logically valid if it is provable with L, without using any axiom. This might be written ⊢ A but for full accuracy it needs to be written LA (meaning that A is theorem of the theory made of L without axiom, thus of any other theory containing L). Then A is true in every system interpreting L, thanks to the soundness of the logical framework.
The simplest logically valid statements are the tautologies (whose Boolean variables are replaced by statements); others will be given in 1.10.

A proof of A using some axioms can also be seen as a proof of (conjunction of these axioms ⇒ A) without axiom, thus making this implication logically valid.

Refutability and consistency

A refutation of A in T, is a proof of ¬A. If one exists (T ⊢ ¬A), the statement A is called refutable (in T).
A statement is called decidable (in T) if it is provable or refutable.
A contradiction of a theory T is a proof of 0 in T. If one exists (T ⊢ 0), the theory T is called contradictory or inconsistent ; otherwise it is called consistent.
A refutation of A in T amounts to a contradiction of the theory TA obtained by adding A to the axioms of T.
If a statement is both provable and refutable in T then all are, because it means that T is inconsistent, independently of the chosen statement:

⊢ (A ∧ ¬A) ⇔ 0
((TA) ∧ (TB)) ⇔ (TAB)
((TA) ∧ (T ⊢ ¬A)) ⇔ (T ⊢ 0).

So a contradiction can be presented as a proof of A with a refutation of A. In an inconsistent theory, every statement is provable. Its framework being sound, such a theory has no model.

Beyond the required quality of soundness of the proof theoretical part of a logical framework, more remarkable is its converse quality of completeness : that for any axiomatic theory it describes, any statement that is true in all models is provable. In other words, any unprovable statement is false somewhere, and any irrefutable statement is true somewhere. Thus, any consistent theory has existing models, but often a diversity of them, as any undecidable statement is true in some and false in others. Adding some chosen undecidable statements to axioms leads to different consistent theories which can «disagree» without conflict, all truly describing different existing systems. This resolves much of a priori divergence between Platonism and formalism while giving proper mathematical definiteness to the a priori intuitive concepts of "proof", "theorem" and "consistency".

Set theory and Foundations of Mathematics
1. First foundations of mathematics
1.1. Introduction to the foundations of mathematics
1.2. Variables, sets, functions and operations
1.3. Form of theories: notions,..., meta-objects
1.4. Structures of mathematical systems
1.5. Expressions and definable structures
1.6. Logical connectives
1.7. Classes in set theory
1.8. Binders in set theory
1.9. Axioms and proofs
1.10. Quantifiers
1.11. Second-order quantifiers
Philosophical aspects
Time in model theory
Truth undefinability
Introduction to incompleteness
Set theory as unified framework
2. Set theory - 3. Algebra - 4. Arithmetic - 5. Second-order foundations
Other languages:
FR : 1.9. Axiomes et preuves