Philosophical aspects of the foundations of mathematics
Let us complete our initiation
to the foundations of mathematics by more philosophical aspects :
how the mathematical realm is structured by a growing block
flow of its own "time", independent of our time.
- First, 1.A to 1.C will explain this "time" as affecting model theory ;
- then, its role in set theory (clarifying the distinction of sets among classes) will
be explored in 1.D, 2.A, 2.B, 2.C ;
- finally, a more detailed description
in terms of ordinal analysis is given in a
separate article, assuming familiarity with ordinals.
These complements are not needed to continue
with Part 2 (2.1 to 2.10 except for small remarks in 2.2, 2.7 and 2.10), Part 3 and more, while 2.A-2.C
assumes both Part 1 down to 1.D and Part 2 down to 2.7.
1.A. Time in model theory
The time order between interpretations of expressions
The interpretations of expressions of a theory T in a model M depend on each
other, thus come as calculated after each other. This time order follows the construction
order from sub-expressions to expressions containing them.
For example, to make sense of the formula xy+x=3, the free variables
x and y must take values first; then, xy takes a value, obtained by
multiplying them. From this, xy+x takes a value, and then the
whole formula (xy+x=3) takes a Boolean value, depending on the values
of x and y. Finally, taking for example the ground formula ∀x,
∃y, xy+x=3, its Boolean value (which is false in the world of
real numbers), «is calculated from» those taken by the previous formula for all
possible values of x and y, and therefore comes after them.
The interpretations of a finite list of expressions may be gathered by a single other
expression, taking them as sub-expressions. This big expression is interpreted
after them all, but still belongs to the same theory.
Now for a single expression to handle an infinite set of expressions (such as the
range of all expressions of T, or just all terms or all statements), these
expressions must be treated as objects (values of a variable).
If T is a foundational theory, it can define (or construct) a system
looking like this, so that, in any standard model of T (in a
sense we shall specify later), this definition will designate an exact copy of this set
of expressions.
However, the systematic interpretation of all expressions of
T in M cannot fit any definition by a single expression of T interpreted in the
same M. Namely, this forms a part of the combined system [T,M] beyond
M, to be described by a one-model
theory (1MT) which, even if it can be developed from T, anyway requires
another interpretation, at a meta level over M.
The infinite time between models
Without trying to formalize the model theory MT of first-order logic (which will be
approached in the next sections) let us sketch a classification of its components (mixing
notions, structures and axioms) into parts according to what they describe. Most issues
are unchanged by restricting consideration to an 1MT, with model a single system
[T,M] of a theory T with a model M, when these T and
M (as may be specified by the chosen variant of 1MT) are big enough to roughly contain any
theory and any system.
- A Theory theory TT (and similarly a one-theory theory 1TT) itself made of
successive groups of components which roughly follow the layers of the theory T it describes :
- A description of "abstract types" and "symbols" ;
- The described notions of "expressions" and "statements" ;
- 1TT may be seen as the extension of TT by unary predicate symbols τ, L,
X which respectively select the classes
of components of T (its types, symbols and axioms) from the given ranges of "all available
ones"; or only X if "types" and "symbols" in TT only meant those of the considered theory.
- Proof theory extends 1TT by the notion of "proof", and thus also those of "theorem" and
"contradiction". This may also be simply constructed from TT's notion of "proof" for logically valid statements,
since a proof of a theorem amounts to a proof of logical validity of its implication from some axioms.
- A Systems Theory describing M by interpreting there the types and structure
symbols of T given from 1TT (if the types list and the language of T are finite
and explicitly given then the role of its one-system theory may be played by T itself;
otherwise it involves the meta-notions of "types" and "structures").
- The description of the interpretations (attribution of values) of all expressions
of T in M, for any values of their free variables; thus also, interpretations
of all statements. This is needed to express M⊨T
(the truth of all axioms of T in M) if the axioms list is infinite.
This last part describes a part of [T,M] which is determined by the
combination of both systems T and M
but not directly contained in them : it is built after them.
The metaphor of the usual time
I can speak of «what I meant at that time»: it has a sense if that past saying had one,
as I got that meaning and I remember it. But mentioning «what I mean» in isolation, would
not itself inform on what it is, as it might be anything, and becomes absurd in a phrase that
modifies or contradicts this meaning («the opposite of what I mean»). Mentioning
«what I will tell tomorrow», even if I already knew what I will say, would not suffice to
already provide its meaning either: in case I will mention «what I told about yesterday» (thus
now) it would make a vicious circle; but even if the form of my future saying ensured that its
meaning will exist tomorrow, this would still not provide it today. Regardless my speculations,
the actual meaning of expressions yet to be uttered will only arise in their time, from
the context that will come.
By lack of interest to describe phrases without their meaning, we'd rather focus on
previously uttered expressions, while just "living" the present ones and ignoring future ones.
So, my current universe of the past that I can describe today, includes the one I could
describe yesterday, but also my yesterday's comments about it and their meaning. I can thus
describe today things outside the universe I could describe yesterday. Meanwhile I neither
learned to speak Martian nor acquired a new transcendental intelligence, but the same
language applies to a broader universe with new objects. As these new objects are of the
same kinds as the old ones, my universe of today may look similar to that of yesterday;
but from one universe to another, the same expressions can take different meanings.
Like historians, each mathematical theory can only «at any given time» describe a
system of past mathematical objects. Its interpretation in this system, «happens» forming
a mathematical present outside this realm (beyond this past). Then, describing this act
of interpretation, means expanding the scope of our descriptions : the model
[T,M] of 1MT, encompassing the interpretations of all expressions of T
in the present system M of past objects, is the next realm of the past, coming once
the infinite totality of current interpretations (in M) of expressions of T
becomes past.
The strength hierarchy of theories
While these successive models are separated by "infinite times", they form an endless
succession, reflected by an endless hierarchy between the theories which respectively
describe them.
This hierarchy will be referred to as a comparison of strength of theories (this
forms a preorder). Namely, a theory
A is called stronger than a theory B if (a copy of) B can be found
as contained in A or a possible development of A; they are as strong
if this also goes vice-versa. Indeed, developments are mere "finite moves" neglected by
the concept of strength which aims to report "infinite moves" only. (Other
definitions of strength order, often but maybe not always equivalent, will come in 2.C).
Many strengths will be represented by versions of set theory, thus letting
us call "universes" these successive models. So, any set theory being meant as
describing some universe of «all mathematical objects», this merely is at any time
the current «everything», made of our past, while this description itself forms
something else beyond this «everything».
Strengthening axioms of set theory
While we shall focus on set theories accepting other notions than sets (as announced in 1.4), the difference
with traditional set theories (with only sets as objects) can be ignored, as any worthy set
theory formalized in our way is as strong as one with only sets, and similarly vice versa.
Our set theories, beyond their common list of basic, "necessary" symbols and axioms
(2.1 and 2.2) will mainly differ by strength,
according to their choices of optional strengthening axioms (sometimes coming
with primitive symbols), whose role will be further commented in 1.D and 2.C.
The main strengthening axioms are :
- Infinity (4.4) : there exists an infinite set, or equivalently a set ℕ of all
natural numbers;
- The Specification schema amounts to generalizing the use of the set builder to unary
predicates A defined using open quantifiers. But this amounts to recognizing
the universe and other classes as kinds of sets (though not objects of any single kind)
and hides the possible dependence of the result on the universe (range of all objects),
which will often be conceived as variable (2.A). These oddities are usually limited by
rejecting the set builder notation as inappropriate, leaving this as an axiom schema
(∀A)∀SetE, ∃SetF, ∀x,
x ∈ F ⇔ (x∈E ∧ A(x))
- Out of the scope of this introduction, the Collection schema implies
the Replacement schema, which implies the Specification schema, with
possible converses depending on other axioms.
- Powerset (2.7)
The main foundational theories
As a simplified introduction, here are some of the main foundational theories (all
first-order theories, even "second-order arithmetic"), ordered by increasing strength
(while infinities of other strengths also exist between and beyond them).
- Let us call Finite Objects theories (FOT) these 3 theories which are of the same strength:
- First-order arithmetic
(Z1), reducing induction to an axiom schema by second-order universal elimination.
- Finite Set Theory (FST), with Specification schema and negation of Infinity
- Theory theory (TT).
- Several subsystems
of second-order arithmetic, equivalent to versions of set theory
featuring successively more elaborate results of ordinary mathematics (analysis...);
Model theory (MT), which can interpret all expressions in all
countable systems (= made of ℕ with any structures given as sets), is among the weakest of these.
- Second-order arithmetic (Z2), formalizable as set theory with Infinity and
Specification (does Replacement make it stronger ?), or (almost equivalently
but in a different formalism) Infinity and the powerset of only ℕ;
- Mc Lane set theory, with Infinity and Powerset, is the comfortable one for most needs;
- Zermelo set theory is slightly stronger, with Infinity, Powerset and Specification.
- Zermelo-Fraenkel set theory (ZF) is much stronger, with Infinity,
Powerset and Replacement; it implies Collection.
The hardest part of Gödel's proof of his famous incompleteness
theorems, was to develop TT from Z1, so that the incompleteness results
first proven for TT also affect Z1. This difficulty can be skipped by focusing on TT and FST,
ignoring Z1. Developing TT from FST is easy (once TT is formalized), but
developing either from Z1 is harder. A solution is to develop the "sets only" version
of FST from Z1 by defining the BIT predicate
(to serve as ∈) and proving its basic properties ; the difficulty to do so can be skipped
by accepting these as primitive.
Other languages:
FR : Temps en
théorie des modèles