A set

T_{0}=0

∀*n*∈ℕ, T_{n+1}=T_{n}+*n*+1

This corresponds to giving ℕ×ℕ the following stucture of ground term (0,

- 0=(0,0)
- S(0,
*y*)=(*y*+1,0) - S(
*x*+1,*y*)=(*x*,*y*+1)

Fixing a bijection *b*_{2} from ℕ^{2} to ℕ,
for any integer *n*>0 we can recursively define a
bijection *b _{n}*:ℕ

∀

(which gives back

Also the set ℕ

- A sequence of bijections
*h*: ℕ↔_{n}*E*, gives a surjection ∐_{n}_{n∈ℕ}*h*_{i}ℕ×ℕ →*U*=⋃_{n∈ℕ}*E*so that taking_{n}*E*=ℕ_{n}^{n}we find that*U*=ℕ^{(ℕ)}is countable. - With the decomposition in prime numbers
- As the binary representation maps ℕ to the set 2
^{(ℕ)}of finite subsets of ℕ, it also maps ℕ^{(ℕ)}to the set 2^{(ℕ×ℕ)}of finite subsets of ℕ×ℕ.

In set theory with the powerset,
for any language *L*, the existence of a ground term *L*-algebra
is deducible from that of an injective *L*-algebra, by taking its
minimal subalgebra. Then, the following statements are
equivalent, forms of the **axiom of infinity** which
means the existence of an infinite set:

- There exists an injective algebra whose language has at least a constant and a non-constant.
- There exists a set with a non-surjective injection into itself.
- There exists an injective {0,
*S*}-algebra. - There exists an infinite set.
- For any countable algebraic language there is a countable injective algebra
- Any consistent first-order theory with a countable language has a countable model

1. ⇒ 2. : given such an algebra *E* with a non-constant *s*, the function
(*E*∋*x*↦*s*_{E}(*k*↦*x*))
is a non-surjective injection of *E* into itself.

2. ⇔ 3. is obvious.

Let us show an easy converse :

If a language *L* is included in some universe *U*, even a
"small" one only containing finite sets (model of a weak version of set theory,
without axiom of infinity or even without powerset), then there
exists an injective *L*-algebra.

Assuming the axiom of infinity, the above definition of finiteness
can be rephrased as follows : a set *E* is *finite*
if there exists an integer *n*∈ℕ and a bijection from
V_{n} = {*x*∈ℕ | *x*<*n*} to
*E*.

For any set

Let ≈ be the equivalence relation of

The quotient structure on

Now denoting

- If
*E*is finite,*e*∈ Min*Q*, and*Q*is a ground term with root*e*representing the number of elements of*E*; - If
*E*is infinite,*e*∉ Min*Q*, and Min*Q*is a ground term algebra (thus a model of arithmetic), whose preimage is the set of all finite subsets of*E*.

∀*n*∈ℕ, ∀*u*∈*H*, ∀*x*∈ *E*, ∃*v*∈ *H*,
*v _{n}*=

∀*n*∈ℕ, ∀*x*∈ *E*, *x* = *u _{n}* ⇔ ∃

We can still generalize recursion by taking recursive conditions of the form

∀*n*∈ℕ, *u*_{n} =
*f*((*u*_{k})_{k<n}).

Back to homepage : Set theory and foundations of mathematics

1. First foundations of mathematics

2. Set theory (continued)

3. Algebra 1

...

3.6. Algebraic terms and term algebras

3.7. Integers and recursion

3.8. Arithmetic with addition

4.1.Finiteness and countability

4.2. The Completeness Theorem

4.3. Infinity and the axiom of choice

4.4. Non-standard models of Arithmetic

4.5. How theories develop

4.6. The Incompleteness Theorem