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*.

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 ℕ×ℕ.

∀*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.1. Morphisms of relational systems and concrete categories

3.2. Special morphisms

3.3. Algebras

3.4. Algebraic terms and term algebras

3.5. Integers and recursion

3.6. 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