Philosophical aspects of the foundations of
mathematics
To complete our initiation to the
foundations of mathematics, the following pages (from this one to Concepts of truth),
will present an overview of some deeper, more philosophical and intuitive
aspects of these foundations (much of which may be already
implicitly understood but not well explained by specialists, being not
easily seen as proper objects of scientific works). This includes
- How, while independent of our time, the universe of
pure mathematics is still subject to a flow of its own time in model
theory and set theory.
- The deep meaning of the difference between sets and classes,
in relation to that time; thus, the deep reason for the use of bounded
quantifiers in set theory.
- The justification of the set
generation principle
These things are not necessary for Part 2 (Set Theory, continued)
except to explain the deep meaning and consequences of the fact that
the set exponentiation or power set (2.7) is not justifiable by the
set generation principle. But they will be developed and justified
in more details in parts 4 and 5.
1.A. Time in model theory
The time order between interpretations of expressions
Given a model, expressions do not receive their interpretations all
at once, but only the ones after the others, because these
interpretations depend on each other, thus must be calculated after
each other. This time order of interpretation between expressions,
follows the hierarchical order from sub-expressions to expressions
containing
them.
Take for example, the formula xy+x=3. In order for it
to make sense, the variables x and y must take a
value first. Then, xy takes a value, obtained by multiplying
the values of x and y. Then, xy+x
takes a value based on the previous ones. Then, the whole formula
(xy+x=3) takes a Boolean value (true or false).
But this value depends on those of the free variables 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.
A finite list of formulas in a theory may be interpreted by a single
big formula containing them all. This only requires to successively
integrate (or describe) all individual formulas from the list in the
big one, with no need to represent formulas as objects (values of a
variable). This big formula comes (is interpreted) after them all,
but still belongs to the same theory. But for only one formula to
describe the interpretation of an infinity of formulas (such as all
possible formulas, handled as values of a variable), would require
to switch to the framework of one-model theory.
The metaphor of the usual time
I can speak of «what I told about 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», 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'm
saying»). Mentioning «what I will mention tomorrow», even if I 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. I might try to speculate on it, but the actual
meaning of future statements will only arise once actually expressed
in context. By lack of interest to describe phrases without their
meaning, we should rather restrict our study to past 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 of 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, mathematical theories can only «at every given
time» describe a universe of past mathematical objects, while this
interpretation itself «happens» in a mathematical present outside
this universe.
Even if describing «the universe of all mathematical objects»
(model of set theory), means describing everything, this
«everything» that is described, is only at any time the current
universe, the one of our past ; our act of interpreting
expressions there, forms our present beyond this past. And then,
describing our previous act of description, means adding to this
previous description (this «everything» described) something else
beyond it.
The infinite time between models
As a one-model
theory T' describes a theory T with a model M,
the components (notions and structures)
of the model [T,M] of T', actually fall into 3
categories:
- The components of T and its developments as a formal
system (abstract types, structure symbols, expressions, axioms,
proofs from axioms), that aim to describe the model but remain
outside it and independent of it.
- The components of M (interpretations of types and
structure symbols)
- The interpretation (attribution of values) of all expressions
of T in M, for any values of their free
variables.
This last part of [T,M] is a mathematical construction
determined by the combination of both systems T and M
but it is not directly contained in them : it is built after
them.
So, the model [T,M] of T', encompassing the
present theory T with the interpretation of all its formulas
in the present universe M of past objects, is the next universe
of the past, which will come as the infinity of all current
interpretations (in M) of formulas of T will become
past.
Or can it be otherwise ? Would it be possible for a theory T
to express or simulate the notion of its own formulas and
compute their values ?
Truth undefinability
As we shall see, some theories such as model theory, and set theory
from which it can be developed, are actually able to describe
themselves: they can describe in each model a system looking like
a copy of the same theory, with a notion of "all its formulas"
(including objects that are copies of its own formulas). However
then, a Truth Undefinability theorem will be established, showing that
no single formula (invariant predicate) can ever
give the correct boolean values to all object copies of ground
formulas, in conformity with the values of these formulas in the
same model.
A
strong and rigorous proof will be given later. Here is an easy one.
The Berry paradox
This famous paradox is the idea of "defining" a natural number n
as "the smallest number not definable in less than twenty words".
This would define in 10 words a number... not definable in less than
20 words. But this does not bring a contradiction in mathematics
because it is not a mathematical definition. By making it more
precise, we can form a simple proof of the truth undefinability
theorem (but not a fully rigorous one):
Let us assume a fixed choice of a theory T describing a set
ℕ of natural numbers as part of its model M.
Let H be the set of formulas of T with one free
variable intended to range over this ℕ, and shorter than (for example)
1000 occurrences of symbols (taken from the finite list of symbols
of T, logical symbols and variables).
Consider the formula of T' with one free variable n
ranging over ℕ, expressed as
∀F∈H, F(n) ⇒
(∃k<n, F(k))
This formula cannot be false on more than one number per formula in
H, which are only finitely many (an explicit bound of their number
can be found). Thus it must be true on some numbers.
If it was equivalent to some formula B∈H, we would get
∀n∈ℕ, B(n) ⇔ (∀F∈H,
F(n) ⇒ (∃k<n, F(k)))
⇒ (∃k<n, B(k))
contradicting the existence of a smallest n on which B is true.
The number 1000 was picked in case translating this formula into
T was complicated, ending up in a big formula B, but still in
H. If it was so complicated that 1000 symbols didn't suffice, we could
try this reasoning starting from a higher number. Since the existence of an
equivalent formula in H would anyway lead to a contradiction,
no number we might pick can ever suffice to find one. This shows the
impossibility to translate such formulas of T' into equivalent formulas of
T, by any method much more efficient than the kind of mere
enumeration suggested above.
This infinite time between theories, will develop as an endless
hierarchy of infinities.
On the incompleteness theorem
(to be completed)
....Provability is expressible as the existence of a number which encodes a
proof, made of one existential quantifier
that is unbounded in the sense of arithmetic (∃_{ℕ} p,
) where p is an encoding of the proof, and inside is a formula
where all quantifiers are bounded, i.e. with finite
range (∀x < (...), ...), expressing a verification of this proof.
The time of proving
If no proof of a statement could be found within given
limited resources, it may still be a theorem whose proofs could not be found as they may be any
longer. This is often unpredictable, for deep theoretical reasons which will appear from the study of the
incompleteness theorem and related ones such as Gödel's
speed-up theorem : - It is unlikely to be predicted in advance: intuitively,
a reliable prediction of existence of proof of A would be a small proof of existence of a
larger proof of A, and thus look like a small proof of A itself (though this implication
between provability properties cannot be itself a theorem);
- No amount of vain search can justify to give up, as a theorem may require
indescribably large proofs (thus beyond the resources of any computer or even all the information that our visible universe may contain): by lack of inverse method (construction of proofs from the absence of counter
examples), no limit can be described for the size of the smallest needed proofs for given theorems
(or even logically valid statements beyond tautologies) that would only depend on the size of the
statement, beyond the simplest cases.
Other languages:
FR : Temps en
théorie des modèles