Generally, a binary relation ≺ on a set

∀*A*⊂*X*, (∀*x*∈*X*,
[*x*] ⊂ *A* ⇒ *x*∈*A*) ⇒ *A*=*X*

∀*A*⊂*X*, *A*≠*X*
⇒ ∃*x*∈*X*\*A*, [*x*]⊂*A*

∀*A*⊂*X*, *A*≠∅ ⇒ ∃*x*∈*A*,
*A*∩[*x*] = ∅

∀*A*⊂*X*, *A* ⊂ ≺_{∗}(*A*) ⇒ *A*=∅

Like we get a minimal algebra from any algebra by taking its minimal sub-algebra, we get a well-founded relation from any binary relation ≺ on a set

∀*A*⊂*X*,
(∀*x*∈*X*,
[*x*] ⊂ *A* ⇒ *x*∈*A*)
⇒ *y*∈*A*

∀*A*⊂*X*, *y*∈*A* ⇒ ∃*x*∈*A*,
*A*∩ [*x*] = ∅

Indeed such a sequence contradicts well-foundedness as Im

Similarly to the concept of term with a root *x*, we have the set *T _{x}*
that is the transitive closure of {

*u*_{0}=*y* ∧ *u _{n}*=

- an expression of recursive sequences (
*X*=ℕ) with minimal assumptions on the framework; - another elegant proof comes when
*X*is a term algebra (using minimal subalgebras in products); - a general one will follow the study of Galois connections, with more details on the properties of well-foundedness.

Now let us focus on a more particular case of recursion obtained by further reducing
the sensitivity of Φ: applying to the structure of algebras the same simplification
*L*⋆*E*∋(*s*,*u*) ↦ Im *u* ∈ ℘(*E*) by which
drafts were reduced to well-founded relations, will make interpretations
more generally invariant by any change of domain which preserves the
well-founded relation.

Let us call *set-algebra* a system (*E*,φ) where
φ : ℘(*E*) → *E*, from which we define Φ(*x*,*u*) = φ(Im *u*).
In fact Dom φ may not be all ℘(*E*), but just needs to contain all possible
Im *u* for functions *u* from some [*x*] to *E*.
For example this may be the set of all finite subsets of *E* if all sets [*x*] are finite.

∀*x*,*y*∈*X*, (∀*z*∈*X*,
*z*≺*x* ⇔ *z*≺*y*) ⇒ *x*=*y*.

Condensed drafts became term algebras when their injective stuff was bijective, letting the algebraic structure be defined by the inverse. Now trying to do the same, to serve both as a final well-founded system and an initial set-algebra, we cannot make φ bijective from ℘(

A general idea is that such systems will be models of some set theory, where ≺ plays the role of ∈. While term algebras are essentially unique, looking after similar properties won't make set theory complete either semantically nor logically, but can reduce some of the chaotic diversity of shapes of universes which would otherwise occur.

Thanks to the completeness theorem, the unprovability of a formula in a theory, respectively its irrefutability also called "consistency" (the consistency of the theory where it is added as an axiom), amounts to the existence of models where it is false (resp. true). For set theories and other founding theories, whose consistency cannot be proven in the absolute as we shall see by the incompleteness theorem, we can only talk about the

For example, to see that

A simple modification (similarly to the distinction of variables in drafts) gives models

For simplicity, we shall only discuss here universes only made of sets and eventually elements, but not anything else like functions.

A problem arises to formalize the well-foundedness of a universe

∀*A*, *A*≠∅ ⇒ ∃*x*∈*A*,
*A*∩*x* = ∅

The condition for a set

From set theory we can get

But a good reason to add it as an axiom, is to make the universe actually useful in its intended role as a union of representatives of all extensional well-founded relations, where recursion would be well-defined... by formulas which make sense inside the same universe without the help of any special language for it. Namely, to define the image of any

Any use of this axiom will only apply it to some family of well-founded systems (A similar trick shows the relative consistency of the negation of the foundation axiom : from any extensional but non-well-founded relation we can create a copy related by ∈ as well. Now well-founded recursion can process from any systemX_{i}, ≺_{i})_{i∈I}, indexed by a setI. Then the sum of this family forms itself a well-founded system, which can be condensed into an extensional one, where all (X_{i}, ≺_{i}) are interpreted. Let us admit here that without contradiction, we can assume the existence of a copy (Y, ≺) of that extensional system made of pure elements. Now that copyYcan be changed into a set of sets related by ∈, by the modification of the predicate ∈ giving to each elementyofYthe role of the set [y], itself left as a pure element.∎

The order in ℕ is a well-order. Obviously, the strict order of any well-order is well-founded, extensional and transitive. Less obvious is the converse:

**Proposition.** If a relation ≺ on a set *X* is
well-founded, extensional and transitive then it is a strict total order, thus
defining a well-order.

For any

∀

Thus

Thus ∀

Then

Indeed ⇒ comes from transitivity; ⇐ comes from totality and extensionality (

The restriction of a well-order to any subset is also a
well-order. So any subset of ℕ is well-ordered. In fact the
well-orders on finite sets are the total orders, and they are
isomorphic as soon as they have the same number of elements.

But there are well-orders bigger than ℕ too. The description of
any well-order is always the same: it starts from the smallest
element (0), then the smallest above 0 (1), then the smallest
above 1 (2), and so on up to infinity; then the smallest after all
natural numbers, then the next one, then the next,... and so on to
infinity, then the next... and so on and so forth, even possibly
beyond any description, but this can stop at any time. See Chaitin's
speech for a more explicit description.

An initial segment of a well-ordered set E is a subset of E of
the form {x∈E | x<y} for some y∈E..

A fundamental property is that for any two well-ordered sets
E and F, there exists a unique isomorphism that is either between
E and F, or between E and an initial segment of F, or between an
initial segment of E and F.

An *ordinal* can be defined as an isomorphism class of
well-ordered sets. The traditional study of ordinals, and thus of
well-orders, formalizes each ordinal by its only representative
whose strict well-order is given by the membership predicate (
∈ ) and that are transitive (x∈A∈E ⇒ x∈E). In such conditions we
have {x∈E | x<y}=y, which may simplify things. But the proof of existence of
such an ordinal isomorphic to any well-ordered set, requires the
schema of replacement to be proven. Here we shall call ZF-ordinals
the transitive sets well-ordered by ∈.

In fact most properties of well-orders and their isomorphism
classes can as well be developed without such a representative,
thus without the axiom schema of replacement, though it may be a
little bit more tedious.

Any set of ordinals (as classes of well-ordered sets) is well-ordered by defining "equality" by the isomorphism, and the order between non-isomorphic well-orders is given by which of both sets is isomorphic to an initial segment of the other.

In the case of ZF-ordinals this all simplifies as the same
predicate ∈ defines the strict well-order inside and between
all ordinals.

For any ordinal there is a bigger one obtained by adding an
element after it. In fact, for any well-ordered set E, we can
define the "next" well-ordered set as the set of all initial
segments of E plus E itself. That is E ∪{E} in the case of
ZF-ordinals. And for any set of ordinals we can take their
"union", that is the smallest ordinal that is larger than them
all. This is simply the union as sets in the case of ZF-ordinals.

The concept of

As we already saw, model theory somehow sees all infinities as the same in the sense that they cannot be distinguished by any first-order description, according to the Löwenheim-Skolem theorem; but since this confusion affects the distinction of finiteness itself, it provided the concept non-standard numbers by looking at the formalism of finite countings from a viewpoint where the finiteness of its objects is seen as an illusion.

Among all ordinals in bijection with a given ordinal, there is a
smallest one. Such a smallest ordinal inside a cardinal (an
ordinal not in bijection with any initial segment of itself) will
be chosen to represent this cardinal.

If we could well-order any set (thus, if we accept the axiom of
choice) then we could simply argue that the class of
cardinal-ordinals does not form a set because this has been shown
for cardinals in general.

For example, ℕ is not the biggest cardinal because P(ℕ) is bigger
and any well-order on it gives an ordinal with cardinality
larger than ℕ.

Otherwise the traditional method also uses the axiom schema of
replacement, making it unclear which assumptions are needed to
show that the class of cardinal-ordinals is not a set. However we
can still deduce it from just the powerset axiom, without either
the axiom of choice nor the axioms of replacement, but this is a
little bit more subtle. Here it goes:

For any well-ordered set X, take the set A={R⊂X×X | R is a
well-order of a subset of X}. Then the quotient of A by the
relation of isomorphism, is naturally a well-ordered set whose
ordinal is the smallest ordinal with cardinality strictly larger
than X. Because if it was in bijection with a subset of X then it
would define a well-order of this subset...

This is the smallest uncountable cardinal-ordinal, thus a
candidate as an intermediate cardinal between ℕ and P(ℕ).

According to the above, it can be explicitly constructed out of
P(ℕ), as the quotient of a well-defined subset of P(ℕ) ≈
P(ℕ×ℕ) by a well-defined equivalence relation. Thus there
exists a surjection from P(ℕ) to it.

Using the axiom of choice it can be represented as a subset of
P(ℕ).

The continuum hypothesis takes the form
of the statement "There is a bijection exists between Aleph1 and
P(ℕ)".

Set theory and foundations of mathematics

1. First foundations of mathematics

2. Set theory (continued)

3. Algebra 1

4.1. Finiteness and countability

4.2. The Completeness Theorem

4.3. Non-standard models of Arithmetic

4.4. How theories develop

4.5. Second-order logic

4.6.Well-foundedness and ordinals

4.7. Undecidability of the axiom of choice

4.8. Second-order arithmetic

4.9. The Incompleteness Theorem