Précis of epistemology/The foundations of mathematics

Mathematics can be defined as the science of everything that is logically possible, all beings and all concepts that can be studied in a theory. For a mathematical being to exist, it is enough that a theory correctly determines its existence, one does not ask that it exists in tangible and observable reality.

First-order logic provides the means to make theories with a finite number of fundamental concepts applied to a domain, finite or not, of individuals. To reason with the principles of first-order logic about all the concepts that can be applied to individuals of a specified domain, it suffices to consider concepts (properties and relations) as new individuals and to give oneself a new attribution relation, which relates properties (relations) to the individuals to which they are attributed (to the n-tuples of individuals). We can thus found the second-order logic and higher order logics. Set theory is a simpler way of making a theory of everything that is logically possible, while remaining within the framework of first order logic. As it is a little confusing for the beginner, this chapter begins by outlining a more natural way to found mathematics, starting with the theory of natural numbers.

Natural numbers and Peano's axioms

Dedekind (1888) and Peano (1889) gave axiom systems sufficient to prove most of its theorems. Peano arithmetic can be considered as the most fundamental mathematical theory. And it suffices to prove a great part of the greatest theorems, even those of differential and integral calculus, because the theorems on real numbers can be translated into theorems on natural numbers.

In the present formalism, all natural numbers are named from 0 and from a single operator s (the successor of):

1=s0, 2=s1=ss0, 3=sss0, ...

Peano's axioms:

• 0 is a natural number.
• A natural number n always has a unique successor sn which is also a natural number.
• Two different natural numbers have different successors.
• 0 is not the successor of any natural number.

For all natural numbers n and p :

• their sum n + p exists and is unique, likewise for their unique product n.p
• 0 + 0 = 0
• n + sp = sn + p = s (n + p)
• 0.0 = 0
• n.sp = n.p + n
• sn.p = n.p + p

The principle of infinite induction:

• Any set of natural numbers that contains 0 and always contains the successor of each of its elements contains all natural numbers.

To make arithmetic we need to reason about sets of natural numbers. We may therefore think of completing the axioms of Peano by axioms on the existence of sets of numbers, but this is not necessary. Arithmetic formulas with one free variable are enough to name sets of numbers. For example the formula A(n) defined by There exists p such that n = 2.p names the set of all even numbers. With such arithmetic formulas one can define very many sets of natural numbers, enough for most theoretical purposes, but not all.

Peano's arithmetic is both quite simple and very powerful. By reasoning about numbers, we can reason about all the sets of beings that we can number. When we study a logically possible world, it does not matter how its individuals are identified. Whether they are numbered or represented in another way does not change the logically possible world studied. What matters are the concepts (properties and relations) attributed to individuals, not how individuals are identified. This is why Peano's arithmetic is very powerful. It gives the means to reason on very many logically possible worlds.

Zermelo's theory of sets

The theory of sets makes it possible to make the theory of all concepts, because a concept can be represented by its extension, the set of beings for which it is true. The concept of an even number can be represented by the set of even numbers. The relation is greater than between numbers can be represented by the set of all pairs of numbers (x, y) such that x is greater than y .

To make a theory of sets, the most natural is to start with beings that are not sets, natural numbers for example, or other beings, which we take as elements of the sets we define.

A pure set theory studies only sets. All beings whose existence is postulated by the theory are always sets. It is a little confusing for the beginner. How can we make sets from scratch? We start from the empty set {}, which contains no elements. We can then define new sets: {{}}, {{}, {{}}} ...

Natural numbers can be represented by sets. We can for example identify 0 to the empty set {}, 1 to {0}, 2 to {0,1} and more generally n to {0 ... n-1}. All other numbers can be constructed from natural numbers.

To study logically possible worlds, it does not matter how individuals are identified. They can be represented by numbers, or systems of numbers or sets. A logically possible world is not determined by how its individuals are identified but by the properties and relations it attributes to them. This is why a pure theory of sets makes it possible to make a theory of everything that is logically possible.

A function (an operator) f can be represented by a relation: y=f(x), or z=f(x,y) ...

A relation can be represented by a set of pairs, or triples, or n-tuples.

A couple (x,y) can be represented by a set, {{x}, {x,y}} for example. A triplet can be represented from the pairs: (x,y,z) = ((x,y),z) for example. The same goes for all n-tuples.

As a pure set theory gives the means to represent all individuals, all properties, all relations, all functions, it gives the means to reason about everything that is logically possible.

To prove the existence of all natural numbers, it suffices to postulate that 0 is a natural number and that the successor of a natural number is always a natural number. To prove the existence of sets we proceed in a fairly similar way, we start from the empty set {} and we prove the existence of new sets built from sets of which we have already proved the existence.

Zermelo's axioms (1908)

• The axiom of extensionality: Two sets are equal when they have the same elements.
• The axiom of the empty set: There is an empty set.
• The axiom of the pair: If two sets exist, there is a set of which they are the only two elements.
• The axiom of the sum set: If a set exists, the set of all the elements of its elements also exists.
• The axiom of infinity: There is a set that contains all natural numbers.
• The axiom of separation: If E is a set and if A(x) is a well-defined formula about sets then the set of all x in E such that A(x) is true exists.
• The axiom of the power set: If a set exists, the set of all of its parts, or subsets, also exists.
• The axiom of choice: It will be presented below.

The first axiom is the essential characteristic of sets. If two beings are different when they have exactly the same elements then they are not sets.

The next three axioms make it possible to construct natural numbers. The union of two sets is the sum set of their pair. The successor of a set x is the union x U {x} . We then define: 0 = {} , 1 = 0 U {0} = {0} , 2 = 1 U {1} = {0,1} ...

The fifth and sixth axioms prove the existence of the set N of natural numbers. This is the set that contains all natural numbers and is included in all sets that contain all natural numbers. We thus find the principle of mathematical induction as a consequence of the definition of the set of natural numbers.

From there, the seventh axiom makes it possible to build the hierarchy of the first infinite sets: N , the set P(N) of all parts of N , P(P(N)) = P ²(N) , P(P(P(N))) = P³(N) ...

The axiom of separation can be compared to a sculptor's chisel. We build sets by giving ourselves large sets, like large blocks of marble, and we cut them with a chisel, with the axiom of separation.

To formulate these axioms with the means of first-order logic, it suffices to give oneself two fundamental relations, the relation of belonging to a set, is an element of, and the relation of equality =, and to postulate that the domain of all individuals is the domain of all sets (or all the sets that interest us).

• The axiom of extensionality: For all x and all y, x = y if and only if for all z (z is an element of x if and only if z is an element of y)
• The axiom of the empty set: There exists x such that for all y, y is not an element of x
• The axiom of the pair: For all x and all y there exists z such that for all w (w is an element of z if and only if (w = x or w = y))
• The axiom of the sum set: For all x there exists y such that for all z (z is an element of y if and only if (there exists w such that (w is an element of x and z is an element of w))

To formulate the axiom of infinity, we start by defining the relation of succession between sets: y is the successor of x if and only if y = xU {x}

y = xU {x} if and only if for all z (z is an element of y if and only if (z is an element of x or z = x))

The existence of the successor of x for any set x is guaranteed by the axiom of the pair and the axiom of the sum.

• The axiom of infinity: There exists x such that ({} is an element of x and for all y, if y is an element of x then yU {y} is an element of x)
• The separation axiom: For any well-defined formula A (x) and all y there exists z such that for all w (w is an element of z if and only if (A(w) and w is an element of y))

To formulate the axiom of the power set, we start by defining the inclusion relation between sets: x is included in y, or x is a part of y, or a subset of y, if and only if any element of x is also an element of y.

x is included in y if and only if for all z, if z is an element of x then z is an element of y

• The axiom of the power set: For all x there exists y such that for all z (z is an element of y if and only if z is included in x)

These axioms do not make it possible to define all the sets. In particular, the existence of the set {N, P(N), P(P(N)) ...} which contains all the Pⁿ(N) for all natural numbers n can not be proved from the Zermelo axioms. It can be proved with a new axiom, the replacement axiom, proposed by Fraenkel (1922), much more powerful to prove the existence of large infinite sets. But even with this new axiom, there are still sets that the theory can not define.

For ordinary mathematics, and even for very advanced mathematics, Zermelo's theory is more than enough to build all the sets we want to build and to prove everything we want to prove. In particular, real numbers, spaces constructed from real numbers, the functions defined in them, the spaces of these functions, the functions of functions, and therefore all the objects of Calculus, can all be constructed by limiting ourselves to the first levels of the hierarchy of infinite sets. The large infinite sets that Zermelo's theory does not allow to construct are much more rarely used.

The interpretation of the axiom of separation poses a difficulty. What is a well-defined formula? According to Fraenkel, any formula well formed from the fundamental predicates is element of and is equal to , and logical connectors, is a well-defined formula. The axiom of separation can always be applied to them. But Zermelo was not convinced by this approach, because these so-called sensible formulas can contain affirmations on all sets, as if the universe of all sets had an objective existence. But we do not know what such a universe could be. We therefore do not always know what meaning to give to the formulas used to define the sets in ZFC. This theory leads to prove the existence of ill-defined sets. However, an ill-defined set is not a set, it does not exist. So ZFC is false.

To correct Fraenkel's error, it suffices to require well-defined formulas to which the separation axiom is applied that they contain only bounded quantifiers, that is to say that they do not contain statements about all sets, but only on all elements of already defined sets. With these limitations, and without the replacement axiom, we have sufficient power for current mathematics.

The axiom of choice

The most direct way to prove that a set exists is to define it, which amounts to constructing it from already defined sets. The empty set is enough to start the construction of all the sets we define. But we can also give indirect evidence of existence. We prove that a set exists and has certain properties without defining it explicitly, without constructing it, without precisely saying which set we are talking about.

The indirect proofs of existence enable us to prove that one can always make a finite number of arbitrary choices to prove the existence of a set. More precisely, if one has a finite list of non-empty and disjoint sets, one can prove that there exists at least one set which contains one element and only one of each set of the list. We did not build this new ensemble, we did not choose its elements, we simply proved that it exists. The logical principles and the axioms of construction of finite sets are enough to prove its existence. But if the list of non-empty and disjoint sets is infinite, these principles and axioms can not prove the existence of a set that contains one element and only one of each set of the list. The axiom of choice states precisely that such a set exists (Zermelo 1904):

The axiom of choice: If E is a set of non-empty and disjoint sets then there exists a set which contains one element and only one of each element of E.

Russell's paradox

Instead of the separation axiom of Zermelo, we could have thought of a simpler axiom:

Frege's axiom: If A(x) is a sensible formula then the set of all x such that A(x) exists.

This axiom was proposed by Frege (1879) to found all mathematics, but Russell (1901, published in 1903) realized that it led to a contradiction. x is not an element of x is a sensible formula. In general, sets are not elements of themselves, but there could be exceptions, like the set of all sets. The set of all x such that x is not an element of x, of all sets that are not elements of themselves, exists, if we adopt the axiom of Frege. Is it element of itself? From its definition it follows that it is an element of itself if and only if it is not an element of itself. This is absurd, so this set can not exist, so Frege's axiom is false.

Zermelo's theory makes it possible to define very large sets but still not the set of all sets. Otherwise, the axiom of separation would make it possible to define the set of all the sets which are not elements of themselves and the theory would be contradictory. We will show later that it is true and therefore consistent. It therefore does not allow the construction of paradoxical sets which would lead it to a contradiction.

In general, a set theory does not allow us to define the set of all the sets that it allows to define. Otherwise this set would be an element of itself, and with the axiom of separation, the theory would be contradictory, because the set of all the sets definable in the theory which are not elements of themselves would be definable in the theory. If the theory is well defined, the set of all sets definable in the theory is also well defined, but it is not definable in the theory. This is one of the reasons for the incompleteness of the foundations of mathematics.

The set of all definable sets in Zermelo's theory is not definable in Zermelo's theory, but it is definable in a more powerful theory. For example, the replacement axiom provides the means to define it.

The uncountable infinite

A set is countable when we can identify all its elements by numbering them, with natural numbers: 0, 1, 2, 3, 4 ... A countable set can be finite or infinite. The set of all natural numbers is infinite and countable. Cantor (1874) proved that there are larger infinite sets. In particular, the set of sets of natural numbers is not countable.

It is proved by reduction to absurdity. Suppose that the set of sets of natural numbers is countable. That means they can all be identified by a number. Let us then define the set C of the numbers that are not in the set bearing their number and let n be the number of C . But if n is not in C then it is in C by definition of C . So it must be in C . But then it is not in C , still by definition of C . n is in C if and only if it is not in C . It is an absurdity. So the set C can not exist. Hence the set of sets of natural numbers is not countable.

The set of beings defined and named by a theory is always countable, because to define and name we use a finite alphabet. One can always number the words formed from a finite alphabet. Just arrange them in order of length, then in alphabetical order for words of the same length. The number of a word is then its serial number.

Uncountability is one of the reasons for the incompleteness of the foundations of mathematics. A theory can only define a countable set of sets, so it can never define all the elements of an uncountable set, it never provides the means to completely fill uncountable sets.

Two sets have the same cardinality when there is a bijection from one to the other. This means that we can identify all the elements of one by the elements of the other. A bijection from E to F is a function which has E as its domain and which is such that each element of F has a unique antecedent. Two finite sets which have the same cardinality therefore necessarily have the same number of elements. The concept of cardinality generalizes the concept of a number of elements to infinite sets. Two sets, finite or infinite, have the same cardinality if and only if they have the same number of elements. With this definition Cantor founded a theory of infinite numbers.

A set is countable infinite when it has the same cardinality as the set of natural numbers.

Cantor showed that a set cannot have the same cardinality as the set of its parts. He concluded that there are many infinite numbers, not just the number of natural numbers.

Well-ordered sets and infinite induction

The concept of well-ordered set makes it possible to specify the concept of a process in which each step is determined as soon as the previous steps have been passed. When such a process is finite, each of its n steps can be numbered by the natural numbers from 1 to n. When a process is infinite, each of its steps can be identified by an element of a well-ordered set.

A set E is totally ordered if and only if there exists a relation < such that for all x, y and z in E,

• if (x<y and y<z) then x<z
• if x<y then not y<x
• x<y or y<x or x=y

In order for a step-by-step process to be determined, the first of the remaining steps must always be determined. Therefore, we require for the order of steps that a set of subsequent steps always has a first element (or a smallest element). This leads to impose on the order relation on E the following property:

If it is not empty, the set of strict upper bounds of any part of E has a first element.

(x is a strict upper bound of y if and only if x is strictly greater (or after) all the elements of y.)

It can be proved that this property of strict upper bounds is equivalent to the following (if E is a totally ordered set):

Any non-empty part of E has a first element.

A set is well-ordered if and only if (it is totally ordered and each of its non-empty parts has a first element).

The set of natural numbers is the smallest well-ordered infinite set for its natural relation of order. Larger well-ordered sets can be defined simply by adding steps after an infinite succession of steps.

The principle of infinite induction can be generalized to all well-ordered sets:

If x is a set which contains the first element of a well-ordered set y and which always contains the element z of y when it contains all the elements of y strictly before z then x contains all the elements of y.

It is proved by reduction to absurdity: if it is not empty, the set of all the elements of y which are not in x has a first element. The existence of this first element contradicts one or the other of the conditions on x. Therefore the set of all the elements of y that are not in x is empty.

Two well-ordered sets E and F represent the same ordinal if and only if they are isomorphic. This means that there exists a bijection f from E to F such that x<y if and only if f(x)<f(y).

Like cardinals, ordinals can be thought of as numbers, finite or infinite. But the arithmetic of ordinals is finer than that of cardinals, because two well-ordered infinite sets can have the same cardinality while representing very different ordinals.

How are sets well defined?

Apart from the empty set, all the sets of a pure set theory are defined from previously defined sets. Sets are well defined when they are always defined by respecting the following three conditions:

• For a newly defined set, we must be able to give a well-ordered list of sets, finite or infinite, such that each set of the list is defined from previously defined sets. The first item in the list is always the empty set. The last item in the list is the newly defined set.
• The elements of a newly defined set must always be previously defined sets or parts of previously defined sets.
• The atomic truths of belonging to a newly defined set must be determined by the definition of the set and the atomic truths of belonging to previously defined sets and their parts.

Instead of the second condition, we can consider a more restrictive condition: the elements of a newly defined set must be previously defined sets. But this condition could prohibit the definition of the set of parts of an infinite set, because it is uncountable. Since the set of parts of a well-defined set is itself well-defined, it must be accepted that a well-defined set may have as its elements sets that have not been previously defined.

Frege's axiom does not respect the second condition, because the elements of a newly defined set are not necessarily previously defined sets or parts of such sets.

In Fraenkel's formulation (ZFC) the separation axiom does not respect the third condition, because the use of unbounded quantifiers means that the atomic truths of belonging to a newly defined set are determined by all atomic truths of belonging to all sets, not only by atomic truths of belonging to previously defined sets. To respect the third condition, all the quantifiers used in the definition of a set must be bounded by previously defined sets.

All the set construction axioms proposed by Zermelo respect the three conditions, provided that the quantifiers are bounded in the definition of the sets constructed with the separation axiom.

What are the definable sets in Zermelo's theory?

We can define all natural numbers from an initial number, zero, and a number constructor function, the successor of. Likewise, we can define all definable sets in Zermelo's theory from initial sets and constructors of sets. The initial sets are the empty set and the set of all natural numbers. The fundamental constructors are the pair of, the sum-set of, the set of parts of and all the constructors in infinite number that can be defined with the axiom of separation, provided that the quantifiers are bounded in the definition of the sets. Constructors are all finite compositions of fundamental constructors. The definable sets in Zermelo's theory are all those obtained by applying one of these constructors to the empty set and to the set of natural numbers.

The replacement axiom

If R is a well-defined functional relation between sets and if E is a set then we can replace all the elements of E by their functional image and thus obtain a set. More precisely there exists a set which contains all the y such that there exists x in E such that Rxy, and only them.

A relation is functional when it always associates a single element with the same element: For all x, y and z, if Rxy and Rxz then y=z

The interpretation of Fraenkel's axiom poses a difficulty: when is a functional relation well-defined?

In ZFC theory, Fraenkel allows functional relations defined with unbounded quantifiers, hence ill-defined functional relations. In Fraenkel's version, the replacement axiom is therefore false. To apply Fraenkel's axiom correctly, one needs a theory of well-defined functional relations.

A theory of well-defined sets

Zermelo's theory is a theory of well-defined sets, provided that the rule of bounded quantifiers is imposed in the definitions which construct sets with the axiom of separation. But if we want to develop the theory of infinite sets, it is not sufficient. ZFC is much more powerful but it allows ill-defined constructions.

We can define a theory much more powerful than that of Zermelo which allows only well-defined constructions using the fundamental constructors and their finite compositions.

Constructors of the first kind construct sets from sets already constructed. The fundamental constructors of Zermelo's theory (the pair of, the sum-set of, the set of parts of and all the constructors which can be defined with the axiom of separation provided that all quantifiers are bounded in the definition of sets) are constructors of the first kind. The finite compositions of constructors of the first kind are also constructors of the first kind. We introduce two new fundamental constructors: the image-set by and the set obtained by the finite iterations of, which we abbreviate as the infinite set by. They are constructors of the second kind. They construct constructors of the first kind from constructors of the first kind.

If f is a constructor of the first kind with one argument, the image-set by f of is a constructor of the first kind which for any set x constructs the set of all y such that there exists z in x such that y=f(z). The infinite set by f of x is the set whose elements are x, f(x), f(f(x)), f(f(f(x))) ... for all finite iterations of f.

A constructor f can always be defined by a relation: f(x)=y or f(x,y)=z or ...

We will show that all the constructors of the first kind of the present theory can be defined by relations in a pure theory of sets.

{x,y}=z is defined by For all w, w is an element of z if and only if (w=x or w=y)

y is the sum-set of x is defined by For all z, z is an element of y if and only if there exists w such that (w is an element of x and z is an element of w).

y is the set of parts of x is defined by For all z, z is an element of y if and only if z is included in x

Let A(w, y₁ ... y_n) be a statement whose free variables are w, y₁ ... y_n. We suppose that a quantifier in A(w, y₁ ... y_n) is always bounded by one of the y₁ ... y_n. The separation axiom asserts that For all y₁ ... y_n and all x, there exists z such that for all w, w is an element of z if and only if (w is an element of x and A(w, y₁ ... y_n)). This amounts to asserting the existence of a constructor f with n+1 arguments. f(x, y₁ ... y_n)=z is defined by For all w, w is an element of z if and only if (w is element of x and A(w, y₁ ... y_n)). All the constructors defined with the axiom of separation are therefore definable by relations in a pure set theory.

A constructor obtained by composition of constructors which can be defined in the theory is also definable in the theory. For example g(f(x))=y can be defined by There exists z such that f(x)=z and g(z)=y

Let f be a constructor of the first kind with one argument and R the relation which defines it: Rxy if and only if f(x)=y

y is the image-set by f of x is defined by For all z (z is an element of y if and only if there exists w such that (w is an element of x and Rwz))

x is closed for R (or for f ) is defined by For all y and all z if y is an element of x and Ryz then z is an element of x

y is the infinite set by f of x is defined by x is an element of y and y is closed for R and for all z if (x is an element of z and z is closed for R) then y is included in z

We conclude that all the constructors of the first kind of the present theory can be defined by relations in a pure set theory.

To found a theory of well-defined sets, we retain all the axioms of Zermelo, except the axiom of infinity, and we add two schemas of axioms: the replacement axiom and a generalized axiom of infinity.

• The replacement axiom: If R is a relation which defines a constructor of the first kind with one argument then for all x there exists y such that for all z (z is an element of y if and only if there exists w such that (w is an element of x and Rwz))
• A generalized axiom of infinity: If R is a relation which defines a constructor of the first kind with one argument then for all x there exists y such that (x is an element of y and y is closed for R and for all z if (x is an element of z and z is closed for R) then y is included in z)

All constructors of the first kind are obtained by finite composition of the fundamental constructors: the pair of, the sum-set of, the set of parts of, the infinite set by, the image-set by and all the constructors defined with the separation axiom provided that all quantifiers are bounded in the definition of sets.

The set of all definable sets in this theory is obtained by applying all constructors of the first kind to the empty set.

We can enrich this theory with a more powerful axiom of infinity which allows infinite induction for any ordinal.

Consistency proofs

A theory is consistent, or non-contradictory, or coherent, when it never allows to prove both a formula and its negation, otherwise it is inconsistent, contradictory, absurd, incoherent.

Of course we expect a mathematical theory to be consistent. An inconsistent theory does not make the difference between the true and the false.

To prove that a theory is consistent, the most direct way is simply to prove that it is true, that is to say that all its theorems are true. A true theory can not be inconsistent, because if a formula is true, its negation is false and therefore not true.

To prove that all the theorems of a theory are true, it suffices to prove that all its axioms are true, because the logical consequences of true formulas are always true.

The mathematical truth of a formula is always defined from a model, a theoretical being that exists as a thought being. To be mathematically true is to be true of a mathematical model.

To prove that a theory is consistent, it is enough to prove that its axioms are true for a theoretical model.

The truth of Peano's axioms

A model of a theory is defined by defining a set of atomic truths. A formula is atomic when it does not contain logical connectors. The atomic formulas of Peano's arithmetic are the equalities between numerical expressions and the formulas which assert that they are natural numbers. A numerical expression is formed from 0 , s , + and .

For example, ss0 + ss0 = ssss0 (2 + 2 = 4) is an atomic formula, and it is true. The same goes for s0 + (ss0.ss00) is a natural number .

The set of all true numerical equalities can be constructed in many ways. It is a little laborious, because we have to give ourselves enough rules to generate all these elementary truths, without forgetting any, but it is not very difficult, because it is very elementary. Any computer can easily tell the difference between true equalities and others. It is clear that this set of atomic truths exists. Since a true theory is necessarily consistent, the consistency of Peano's axioms has been proved at the same time.

A model of Zermelo's axioms

We can define a model of Zermelo's axioms by taking as universe of sets the set M defined as follows:

Let S(x) = x U P(x) be the union of x and the set of all of its parts. M is the union of N with S(N) , S(S(N)) ... that is to say of all Sⁿ(N) for any natural number n .

Let's show that all axioms are true for this universe M of sets.

From the definition of M, it follows immediately that the axiom of the empty set and the axiom of the infinite are true.

Since Sⁿ(N) is included in Sⁿ⁺¹(N) , Sⁿ(N) is included in S^p(N) if n < p .

Let x and y be two elements of M. So we must have n and p such that x is element of Sⁿ(N) and y is element S^p(N) . If n <= p , x and y are both in S^p(N) and therefore their pair is in S^p+1(N) . If n >= p , {x,y} is in Sⁿ⁺¹(N) . The axiom of the pair is therefore true in M .

Let us show by induction that an element of an element of S^p(N) is also element of S^p(N) . The statement is true for N = S⁰(N) because any natural number n = {0 ... n-1}. Since the elements of the elements of P(x) are in x , the statement is true for Sⁿ⁺¹ (N) if it is true for Sⁿ(N) , so it is true for any natural number n .

As a result, the sum of an element of Sⁿ(N) is included in Sⁿ(N) and is therefore a element of Sⁿ⁺¹(N) . The axiom of the sum is therefore true in M .

It also follows that the subsets of an element of Sⁿ(N) are all included in Sⁿ(N) and therefore they are all elements of Sⁿ⁺¹(N) . The set of the subsets of an element of Sⁿ(N) is therefore included in Sⁿ⁺¹(N) and is therefore an element of Sⁿ⁺²(N) . The power set axiom is thus true in M.

The separation axiom is necessarily true in M , since all subsets of the elements of M are elements of M .

If E is a set of non-empty and disjoint sets and if it is in Sⁿ(N) then the set that chooses an element of each element of E is included in Sⁿ(N) , since the elements of elements of E are in Sⁿ(N) , and so it is an element of Sⁿ⁺¹(N) , hence in M . So the axiom of choice is true in M .

From the truth of its axioms for the set M , we can conclude that Zermelo's theory is consistent. There is however a difference between this consistency proof and the previous one, on the consistency of arithmetic. We have not built explicitly the set of atomic truths. We did not name all the elements of the model and we did not say how to generate the set of true atomic formulas for all these elements. We can not do it, because the set M is uncountable.

Is it necessary to conclude that this proof of consistency is worthless? No. But it awakens a doubt. Are we sure that the set we build exists? To speak of sets of which one can not even name all the elements, does not this take the risk of absurdity?

We know that uncountable sets exist because we can think of them. Nothing forbids thinking about the set of all sets of natural numbers. We can even see it in imagination:

The infinite binary tree is constructed from a root, which separates into two branches, one on the left, the other on the right, which in turn separate into two branches, and so on, infinitely. A path that starts from the root and never stops defines a set of natural numbers. If at step n the path takes the branch to the left then n is part of the set, but not if the path takes the branch to the right. The set of all the paths of the infinite binary tree is thus a representation of the set of all sets of natural numbers. Now one can see in imagination the infinite binary tree by watching it unfold on the horizon. We can see all its paths at a glance, and they are uncountable.

There are uncountably many points on a line, even if it is of finite length. As we can see lines and surfaces, we can see the uncountable.

For the proof of coherence of Zermelo's axioms to be false, it would be necessary for us to be wrong to conceive uncountable sets, that without our knowledge the reasonings on the uncountable lead us to absurdity. But why fear that we may be so fooled by our own reason? It seems that we make no mistake when we reason about all the subsets of a set, even if it is infinite.

To formalize the consistency proof of Zermelo's axioms, it suffices to add to the axioms of Zermelo a widening of the axiom of infinity: There exists a set which contains N and which always contains x U P(x) when it contains x. We thus obtain a more powerful theory which makes it possible to prove the consistency of the previous one. If we want to prove the consistency of this new theory, it suffices to give ourselves a new axiom of infinity. There exists a set which contains M and which always contains x U P(x) when it contains x. We can thus define a series of ever more powerful theories such that the consistency of one can always be proved by the next.

There is no ultimate model for set theories

We define a model for a set theory when we define a set of sets such that all axioms are true when unbounded quantifiers are interpreted as quantifiers bounded to this set of sets. The set of sets plays the role of a universe of all sets studied in the theory. A natural model for a set theory is to take the union of all definable sets in the theory (M is such a natural model for Zermelo's theory). But this model cannot be an ultimate model, because it does not make it possible to define an ultimate truth. When we state a theorem which concerns all sets, its truth goes beyond the truth about the union of all definable sets in the theory. We want it to be true even for sets which are not definable in the theory, because we want it to be really true for all sets, provided they are well defined.

To have an ultimate model, it would be necessary to be able to define well the set of all well-defined sets, but this is not possible, because it would be an element of itself.

We may consider defining an ultimate model $V$ for a set theory as follows:

$V_{0}=\varnothing$ where $\varnothing$ is the empty set {}.

$V_{\alpha }=\bigcup _{\beta <\alpha }{\mathcal {P}}(V_{\beta })$ for each ordinal α, where ${\mathcal {P}}(X)\!$ is the set of parts of $X$.

The class $V$ is then defined as the union of all the $V_{\alpha }$ for all the ordinals α:

$V=\bigcup _{\alpha }V_{\alpha }$

But this class is not well determined. For it to be, the class of all ordinals would have to be well determined beforehand. But an ordinal is essentially a well-ordered set. We cannot define the class of all sets from that of all ordinals, because the second is defined from the first.

For number theories or other particular mathematical beings, the truth of axioms is always established by reference to a model. We have a model which serves as a criterion for the truth of axioms. For set theories, we cannot have an ultimate model, but we still have a truth criterion. The sets whose existence we prove must either be well defined, or their existence must result from that of well-defined sets. In the absence of an ultimate model, it is the requirement of good definitions that serves as a criterion of truth.

The incompleteness of the foundations

Kurt Gödel proved, in 1931, that we can not explicitly give a complete list of all mathematical principles. More precisely, an explicit list of principles can never suffice to prove all the mathematical truths, even if we limit ourselves to the truths about natural numbers. This is Gödel's first incompleteness theorem. The incompleteness of the principles is necessary. It does not come from our lack of imagination or work. Mathematicians are able to give lists of very powerful axioms, which in general suffice to prove all the truths one wishes to prove. But these lists are incomplete in the sense that they are not enough to prove all the mathematical truths. They can be enriched with new, more powerful axioms but they can never be definitively completed. There will always be mathematical truths that they can not prove.

This incompleteness theorem is sometimes misinterpreted as evidence that there are truths that we will never know, that there are sensible questions that we will never be able to answer, that there are solutions that we will never find. This interpretation is a fault of logic. Gödel proved that for any coherent theory T defined by an explicit list of axioms there is at least one truth V that T can not prove. But this does not prove that there is a truth V that no theory can prove. In fact, when we find a truth V unprovable in a theory T , it is generally very easy to define a theory T+ , adding to T a new axiom, which allows to prove V .

The principle of Hilbert (1930), "We must know, we will know", still holds, even after Gödel. Nothing allows to say that there are mathematical truths that we will never know.

We are generally very surprised the first time we hear about Gödel's incompleteness theorem, because we are accustomed to identifying mathematical truth and provability. We know that a theorem is true when we know how to prove it. But this astonishment is easily dispelled when we understand that an explicit list of axioms can not suffice to prove the existence of all mathematical beings, even if we limits ourselves to the most elementary ones, the natural numbers and the sets of natural numbers.

Cantor's theorem, the set of sets of natural numbers is not countable, can be considered as the first theorem on the incompleteness of principles, because it shows that a theory never enables to define explicitly all the sets of natural numbers. More generally, as soon as the sets are uncountable, a theory never enables all of their elements to be explicitly defined.

A theory does not enable us to prove all the true statements that it states because it can never define enough sets to give these proofs. For example, the principle of infinite induction is applied to sets of natural numbers. If sets are not defined in the theory, we cannot use them to define formulas with which to reason by induction. We can conclude that mathematical incompleteness is a consequence of uncountability, since a theory can never define an uncountable number of sets, and therefore there are always sets that it can not define.

We begin by proving Gödel's first incompleteness theorem in a way that eliminates technical difficulties and allows us to focus on the core of the argument, a true statement that says of itself that it is unprovable. Gödel proved that this statement is true under the assumption that the theory T which allows to formulate it is true. But this proof of the truth of the "unprovable" statement can not be formalized in T. The statement is unprovable from the axioms of T but it is not absolutely unprovable, since Gödel has proved its truth. To formalize this proof, one needs a theory which proves that the axioms of T are true. But Tarski has proved that a theory can never define a predicate of truth for itself. This is why the proof of the "unprovable" statement can not be formalized in T.

Cantor's theorem of the uncountability of the set of sets of natural numbers, Gödel's theorems of the incompleteness of provability, Tarski's theorem of the undefinability of truth, and the undecidability theorems of Church and Turing are all manifestations of the same mathematical incompleteness.

We will conclude by showing that the incompleteness of mathematical principles is not very surprising, because if we knew how to find all the solutions of an undecidable problem, we would have a kind of omniscience, we would know how to find all the solutions of all problems.

The first incompleteness theorem of Gödel

The proof here proposed is unconventional. Gödel argues on an arithmetic theory. It shows that formulas can be represented by numbers and that logical consequence relations between formulas can then be represented by relations between numbers. The whole technical difficulty of his proof comes from there: showing that the logical relations between formulas can be determined by numerical relations between the numbers which represent these formulas. This difficulty is eliminated by reasoning not on a theory of numbers but on a theory of formulas.

Nothing forbids to make a theory that allows reasoning on its own formulas. This way is not as convincing as Gödel's, because it does not prove that number theory is incomplete, but only that a weird theory of its own formulas is incomplete. One could even believe that the paradoxical statement that is at the heart of the proof comes only from the weirdness of the theory and fear that there is some inconsistency, so that the theory is not a good mathematical theory. This fear is unfounded. If we do it right, it is easy to make a true and therefore consistent mathematical theory that states truths about its own formulas. This is the easiest and fastest way to prove mathematical incompleteness. But this is not enough to prove the incompleteness of number theory.

The following proof is identical to that of Gödel, except on one point, that one reasons on a theory of formulas, and thus that the formulas are not represented by numbers.

T is a theory that considers its own formulas as individuals, or objects. It contains the binary predicate is a logical consequence of and admits among its axioms the Logical principles. Any finite list of premises can be identified with a single formula, their conjunction.

It also has other predicates and axioms that allow one to reason about how formulas are constructed. In particular, it must make it possible to define a predicate is a formula with one free variable. Formulas that have free variables are neither true nor false. We must assign values ​​to their variables f , x , y ... before their truth can be decided. For example, f is a formula is a formula with a free variable f . The T theory T must also make it possible to define a ternary predicate defined by g is obtained from a formula f with a free variable by substituting x for all the occurrences of its variable . It is supposed that all the axioms have been correctly chosen, so that they are true, and sufficient to prove the most elementary formal truths.

Once the list of its axioms is defined, T allows to define a predicate is provable in T , because to be provable, it suffices to be a logical consequence of a finite conjunction of axioms.

T then allows to define the following predicate:

Gödel (f) equals by definition f is a formula with a free variable and there exists g such that g is not provable in T and g is obtained from f substituting f for all occurrences of its free variable .

Gödel (f) is a formula with one free variable f , because the variable g is bound by the existential quantifier.

We can then prove that Gödel (Gödel (f)) is a true statement but unprovable in T.

Gödel (Gödel (f)) means by definition Gödel (f) is a formula with a free variable and Gödel (Gödel (f)) is not provable in T .

If Gödel (Gödel (f)) was provable in T then it would be false, since it says of itself that it is not provable in T . Now it has been assumed that all the axioms of T are true. All the theorems of T , ie provable statements in T , are therefore also true. As a result, Gödel (Gödel (f)) can not be a theorem of T and therefore it is true, since that is exactly what it says. So we found a true and unprovable statement in T .

To transpose this proof to number theory it suffices to show that the predicates is provable in the theory of numbers and g is obtained from a formula f with a free variable by substituting x for all occurrences of its variable can be represented by arithmetic relations between numbers that represent formulas.

Technical note: to correctly formulate the theory T one must pay attention to the use of variables of formula. f is a variable of formula, but it is not in itself a well-formed formula of T . As a result, For any formula f, f , for example, is not a well-formed formula of T either. A well-formed formula must always contain constant predicates applied to constants or variables. Moreover, when a formula A(f) is applied to another formula B(f) , ie one has formed A(B(f)) , the variable f is free in B(f) but not in A(B(f)) , because B(f) there is a constant.

Uncountability and incompleteness

The proof of Gödel's theorem resembles that of Cantor's theorem, because a formula with a free variable can be considered as the name of the set of all beings for which it is true. Gödel's proof defines the set of all numbers for which it is not provable that they are in the set named by the formula they number.

It is not a priori obvious that the Gödel incompleteness results from the uncountability of the set of sets of numbers. Gödel's true and unprovable statement deals only with numbers, not sets of numbers. One might have hoped that arithmetic would prove all the truths that relate only to numbers, that it does not need to prove the existence of all sets of numbers. But this hope is vain.

To prove arithmetic truths, we use the principle of mathematical induction, which can be stated as follows:

If a set of numbers contains zero and if it always contains the successor of each of its elements then it contains all the natural numbers.

A number theory that does not explicitly deal with sets of numbers applies this principle to formulas with a free variable. These serve to represent sets of numbers.

It is not surprising that an explicit theory can never prove all the truths about numbers, because there are always sets of numbers that it can not define and that may be necessary to prove certain truths on numbers. A true statement about numbers is unprovable when the theory does not define the set of numbers needed to prove it. The following will show that for Gödel's true and unprovable statement, the missing set is the set of numbers of the arithmetic truths.

Tarski's theorem of the undefinability of truth

We can say the truth by simply saying what we have to say, but we can also say it by insisting redundantly and saying that what we say is true. We use a predicate of truth that we can attribute or not to everything we say. Tarski (1933) proved that such a predicate of truth can not exist in a mathematical theory if it is true.

Let us begin by reasoning as above on a theory T which speaks of its own formulas.

If T contained a predicate of truth It is true that , then the formulas It is true that f if and only if f would be true for all formulas f of T. It is true that the snow is white if and only if the snow is white, by definition of the truth. It is with this principle that Tarski founded a theory of mathematical truth (Tarski 1933) that we now understand as the theory of models.

Let's show by reduction to absurdity that a predicate of truth can not exist in the theory T if it is true.

Suppose that a predicate is true is defined in T for all the formulas of T .

Let us define the formula Tarski (f) with a free variable by f is a formula to a free variable and there exists a formula g such that g is not true and g is obtained from f by substitution from f to all occurrences of its free variable.

Tarski (Tarski (f) means by definition that Tarski (Tarski (f)) is not true. Tarski (Tarski (f)) is true if and only if is not true, which is an absurdity, so the predicate is true can not exist in the theory T if it is true.

To transpose this proof to the theory of numbers it suffices to reason on the predicate is the number of a true formula . A number theory never allows to define such a predicate if it is true.

Tarski is at once the theoretician who has been able to define mathematical truth and who has proved that it is undefinable in all mathematical theories.

Tarski's theorem provides another, indirect, proof of Gödel's first incompleteness theorem: If a theory makes it possible to define a predicate of its own provability and if all its theorems are true, then there must be at least one statement true and unprovable, otherwise the predicate of provability would be a predicate of truth.

How to prove the unprovable?

Let's go back to the theory T that defines a predicate of provability is provable in T and a true and unprovable statement in T . By presenting this "unprovable" statement we proved it was true. The proof is easy but it is based on the assumption that the theory T is itself true. But the theory T does not allow to define a predicate of truth for itself, if it is true, only a predicate of provability. Therefore, we can not formalize the informal proof of the "unprovable" statement with the means of the theory T. That is why this provable statement is unprovable in T . But the definition of mathematical truth by Tarski allows us to define a theory T+ with a truth predicate limited to T : is a true formula of T . The informal proof of the true and unprovable statement in T can then be formalized in T+ . The unprovable statement in T is therefore a proved theorem in T+ . But of course T+ is not a complete theory, because we can find a new true and unprovable statement in T+ that requires a truth predicate limited to T+ to be proven .

To formalize in T+ the informal proof, one must prove in T+ that all the theorems of T are true. It is proved by mathematical induction. If a set of formulas contains all the axioms of T and all the immediate logical consequences of its elements, then it contains all the theorems of T , by definition of the set of theorems of T . It is therefore sufficient to prove that all the axioms of T are true, and that the immediate logical consequences of true formulas are equally true, to prove that all the theorems of T are true. But to formalize this informal proof one needs in T+ a predicate of truth for the formulas of T .

To transpose this proof to number theory it suffices to reason about the predicate is the number of a true formula of the theory . One can always enrich an arithmetic theory with new axioms so that this predicate of truth, limited to the initial theory, is definable. It is thus possible to prove in the enriched theory the true and unprovable statement in the initial theory. Just formalize the informal proof.

The second incompleteness theorem of Gödel

Gödel has proved that a consistent theory can never prove its own consistency. This second incompleteness theorem of Gödel is often misinterpreted. It is believed that evidence of consistency is very difficult, or inaccessible, or that it could never be rationally justified because it would be in a vicious circle. But there is a much more direct explanation. The proofs of consistency are sometimes very easy to find, and irrefutable, without any error of logic, and without the slightest doubt being able to subsist, but they can not be formalized within the theory whose consistency is proved, because they require a predicate of truth for this theory. Tarski's theorem of the undefinability of a predicate of truth thus explains Gödel's second incompleteness theorem.

Gödel's second incompleteness theorem: A true theory can not prove its own consistency.

Let's reason about the theory T and its true statement, unprovable in T, Gödel(Gödel(f)).

Let's show by reduction to absurdity that T can not prove its own consistency. If it could, it could prove that Gödel(Gödel(f)) and not Gödel(Gödel(f)) is not provable in T.

But it can prove If not Gödel(Gödel(f)) then (Gödel(Gödel(f)) is provable in T) by definition of Gödel(f). So it could prove If not Gödel(Gödel(f)) then (not Gödel(Gödel(f)) is not provable in T). But not Gödel (Gödel(f)) means that Gödel(Gödel(f)) is provable in T by definition of Gödel(f). So T could prove If not Gödel(Gödel(f)) then ((Gödel(Gödel(f)) is provable in T) is not provable in T.

Moreover, T can prove that For every formula f, if f is provable in T then the formula that states that f is provable in T is provable in T. This point is sometimes considered difficult in Gödel's proof. But for the theory T it is almost obvious, because a proof of a theorem proves at the same time that the theorem is provable. Since T can prove If not Gödel(Gödel(f)) then (Gödel(Gödel(f)) is provable in T), it can also prove If not Gödel(Gödel(f)) then ((Gödel(Gödel(f)) is provable in T) is provable in T).

Since T could draw contradictory conclusions from not Gödel(Gödel(f)), it could prove Gödel (Gödel(f)) by reduction to absurdity. But Gödel(Gödel(f)) says of itself that it is not provable in T. So T would not be true.

As a result, T can not prove its own consistency if it is true.

This reasoning can be transposed to number theory by numbering the formulas.

Are consistency proofs caught in a vicious circle?

The consistency proofs which exhibit a model are formalized in a theory T₊ stronger than the theory T₀ whose consistency it proves, because they define the set of truths of T₀ and this set can not be defined in T₀ . If a theory is absurd, any theory obtained by adding axioms is also absurd. An absurd theory can prove anything, an affirmation and its opposite, including that the absurd is not absurd. Our method of proving the consistency of a theory does not therefore make it possible to differentiate between consistent and inconsistent theories, since a theory "stronger" than an inconsistent theory could prove that it is consistent. That is why it is sometimes believed that such proofs prove nothing, but it is a mistake.

One does not reason on any theory T₀ about which one knows nothing. T₀ is Peano arithmetic or Zermelo's theory, or other theories that we choose to found our mathematical knowledge. We know in advance that these theories allow us to prove truths, because without them we would not have mathematical knowledge, and it seems quite clear that we have some. If we are very pessimistic, we may fear that our formal theories contain wording mistakes that could lead to contradictions and that we do not know it. But there is no doubt that these theories often reveal the truth, unless we give up mathematical knowledge. When we prove that formal theories are true and consistent, we confirm what we already intuitively believe. And one proves to oneself that our natural faculties of reasoning are sufficient to reason correctly on reason. So it is not a vicious circle. It is the virtuous circle of reason that understands itself.

Theories, software and recursively enumerable sets

There is a very close correspondence between mathematical theories and software, computer programs. When we explicitly define a theory, we can always write a program that proves all its theorems. It suffices for it to print in an orderly fashion all the axioms and all the immediate logical consequences of the formulas it has previously printed. This method of searching for proofs has only a theoretical interest. In practice, the computer would print a deluge of formulas without interest before finding a theorem that deserves to be written. And even with the most powerful computers, it would usually be necessary to wait a inordinate time to find proofs or refutations of interesting conjectures.

We can give several definitions, all equivalent, of recursively enumerable sets. The following conditions, chosen from many others, all three define the recursive enumerability of a set E:

• All the atomic truths of belonging to E are theorems, provable statements, of an explicit theory.
• There is a software that always answers yes when we present the name of an element of E, and that does not answer, or answers no, when we present the name of a being which is not in E.
• There is a finite number of initial expressions and a finite number of production rules (Smullyan 1961) sufficient to generate all the atomic truths of belonging to E.

The set of theorems of an explicit theory is always a recursively enumerable set. If we present a theorem to a proof-finder software, it will always come to recognize that it is a theorem, because it examines all the possible proofs, however long they may be. If we present a non-theorem, it will not answer because it will search for eternity for a proof that does not exist.

Undecidable sets and problems

Recursively enumerable sets are always countable. Since all their elements can be named, we can always define their complement in the set of all named beings, as soon as we have fixed a system of designation.

A set is decidable when it and its complement are recursively enumerable, otherwise it is undecidable.

A problem is undecidable when the set of all its solutions is undecidable.

An example of an undecidable set is the set of all truths in Peano's arithmetic. The first incompleteness theorem of Gödel proves that this set of truths is not recursively enumerable and therefore not decidable. If it were recursively enumerable, one could find a complete list of axioms sufficient to prove all the arithmetic truths, but Gödel proved that such a list can not exist.

To say that a problem is undecidable does not mean that we are incapable of solving it, nor that it has solutions that we will never find, it only means that there is no explicitly defined theory that brings all the solutions of the problem. The theories we define can only solve an undecidable problem partially, never completely. With the undecidable problems, we will never have finished, it is the galley assured for eternity. But we can still look for and find solutions, and no solution is a priori inaccessible. It suffices to be creative enough to invent a theory that enables us to find it.

The incompleteness of mathematical principles comes from the existence of undecidable sets. If all sets of truths were recursively enumerable, we could give lists of axioms sufficient to find them all. But undecidability shows that sets of truths are not always recursively enumerable.

Universal machines and theories

A programmable computer is a universal machine, in the sense that it is capable of executing every conceivable program. If the program is written once and for all, in read-only memory (ROM), the computer is only a particular machine.

A universal machine can do everything that other machines, universal or particular, can do. Just give it the program. All universal machines are therefore essentially equivalent. They can all do exactly the same things.

In practice, computers are limited by their computing power and their storage space. But the computing power is only a problem of speed and the storage space can in principle be enlarged without limits. Just imagine a computer mounted on a robot that moves in a database that we can always enlarge.

A universal theory is a theory that can prove all that other theories can prove. For example, logic can be formalized as a universal theory. It suffices to give enough axioms so that all the true formulas of the form C is a logical consequence of P be provable, for all well-formed formulas C and P. As any theorem of any theory is always proved from a finite conjunction of axioms, such a formalization of logic is a universal theory.

By proving that logical relationships between formulas can be represented by arithmetic relations between numbers that represent formulas, Gödel proved that arithmetic is also a universal theory, even if it is limited to first-order Peano's arithmetic.

The existence of universal theories poses a paradox. Like any explicit theory, a universal theory U can not prove all truths. These truths that they can not prove are in principle provable in a richer theory U+ , which has more axioms. But since the initial theory U is universal, it can prove all that U+ can prove, which seems contrary to the assumption that U+ is richer than U . In particular, the consistency proof of first-order arithmetic can be formalized in first-order arithmetic, since it can be formalized in an explicit theory and since first-order arithmetic is a universal theory. But Gödel's second incompleteness theorem seems to forbid such a possibility.

The explanation of this paradox is a little subtle. The U+ theory can be formalized in U, but U "does not know" that U+ is an enrichment of U, ie U can prove that all theorems of U+ are theorems of U+ but it can not prove that the theorems of U+ are worth for itself. It can therefore formalize the proof of its own coherence without saying it explicitly, without affirming that it is about its own coherence.

The undecidability of the halting problem

The halting problem: Given a computer program and an initial state of memory, will the computer halt and provide an answer, or will it work indefinitely without ever giving an answer?

It has been assumed that the computer is not limited in storage space and that it is not influenced externally as it calculates.

Turing proved that the halting problem is undecidable (1936).

The set of pairs (program, initial state) of a machine that halts is recursively enumerable, because a computer can simulate all the others. If it is presented with a program and an initial state, it has only to run the program on the initial state and wait for it to halt. If it halts, the computer responds that it halts. If it does not halt, the computer does not halt and does not respond.

On the other hand, the set of pairs (program, initial state) of a machine that does not halt is not recursively enumerable. It is proved by reduction to absurdity. If it were recursively enumerable, there would be a program P such that for any pair (program p , initial state i ), the machine halts and responds that p does not halt from i whenever it is true. A program can be written in memory and is therefore also a possible initial state. From P we could then write a program P' such that for any program p , the machine halts and responds that p does not halt from the initial state p whenever it is true. And we could give P' as the initial state of memory of the machine running with P' . Is this machine going to halt? By construction, it halts if and only if it does not halt. It is an absurdity. So P' can not exist, and therefore P neither. Hence the set of pairs (program, initial state) of a machine that does not halt is not recursively enumerable. The halting problem is therefore undecidable.

The undecidability of the set of all logical laws

The set of logical laws is a universal theory, because a formula is a theorem of a theory if and only if the affirmation that it results from a finite conjunction of its axioms is a logical law. By knowing all the logical laws, we therefore know all the theorems of all theories.

When a theory is defined with a finite number of axioms, a formula is not a theorem if and only if the statement that it results from the conjunction of axioms is not a logical law.

Fundamental theories (Peano's arithmetic, Zermelo's theory ...) are generally defined with axiom schemas. The axiom of separation, for example, is a schema that makes it possible to formulate as many axioms as there are sensible formulas, in infinite number. The same goes for the principle of mathematical induction when it is formulated in first-order arithmetic. But these theories which have an infinite number of axioms are always equivalent to theories which finitely many axioms. By introducing classes, which are like sets, but too big to really be considered as sets, in the manner of Gödel and Bernays, Zermelo's theory has only a finite number of axioms.

Even when theories have an infinite number of axioms, one always demands that there be a finite number of principles or rules sufficient to mechanically produce all axioms, otherwise the theory is not explicit. This is why explicit theories are always equivalent to theories with finitely many axioms.

If the set of logical laws were decidable, all recursively enumerable sets would be decidable. All the truths of belonging to a recursively enumerable set E are theorems of theory with finitely many axioms. The complement of E is thus the set of all x such that If the axioms then x is in E is not a logical law. If the set of logical laws were decidable, this set would be recursively enumerable, and thus E would be decidable.

The proof of the undecidability of the halting problem shows that there exists at least one recursively enumerable set which is not decidable. The set of logical laws is therefore not decidable.

The proof of the first incompleteness theorem makes it possible to prove more directly the undecidability of the set of logical laws. If the set of logical laws were decidable, the theory T could have enough axioms to prove all the true formulas of the form f is not a logical consequence of g . It could therefore prove all the true formulas of the form f is not provable in T . As Gödel(Gödel(f)) is not provable in T , T could prove it. But Gödel(Gödel(f)) says of itself that it is not provable in T . T could then prove that Gödel(Gödel(f)) is not provable in T , which is absurd. So the set of logical laws is undecidable.

The undecidability of the set of logical laws, or of the Entscheidungsproblem (Hilbert 1928) was proved independently and with different methods by Church and Turing in 1936.

Universality is the cause of undecidability

The problems of which we know how to prove their undecidability are always complete problems, in the sense that if we had a method to find all their solutions, we would at the same time have a method to solve all problems. From this point of view, the incompleteness of mathematical principles is ultimately not very surprising. We do not have to see it as a sign of incapacity, because it is a consequence of the universality of thought. We can reason about all problems, about all theories. We can state universal laws that apply to anything conceivable and thinkable. But we do not have enough methods or principles to solve all the problems. Our methods, even the most powerful ones, can not solve everything. We are only creatures. To know how to find all the solutions of an undecidable problem would be a kind of omniscience, because one would at the same time know how to find all the solutions of all problems.

A finite list of principles is enough to generate all the logical laws. This is Gödel's theorem of the completeness of logic. The set of logical laws is therefore recursively enumerable. But since the set of logical laws is undecidable, the set of formulas which are not logical laws is not recursively enumerable. The logical laws are true in all possible worlds. Negations of logical laws are absurdities, false in all possible worlds. A formula that is neither a logical law, nor the negation of a logical law, is true in some worlds and false in others, it describes possible worlds, worlds that one can imagine. Every finite system of axioms which describes a possible world is such that the negation of its conjunction is not a logical law. The set of formulas which are neither logical laws nor absurdities is the set of all axioms and finite systems of axioms which are about at least one world that can be imagined. To say that it is not recursively enumerable means that we can not give a finite list of principles sufficient to produce all these systems of axioms. Imagination overflows all frames. Whatever the finite list of principles that one gives oneself, there are always possible worlds that it does not allow to study. Mathematical incompleteness is therefore a consequence of the universality and power of imagination.

Next chapter: The truth of relativistic principles >>>