Let us start with a technical result:

For any subset

(proof : to be developed...)

It is easy to check that any condensed ground {0,

A set is called

A set is called

- It has an injection to a condensed ground {0,
*S*}-draft - It has a bijection with a condensed ground {0,
*S*}-draft - A condensed ground {0,
*S*}-draft has a surjection to it

2.⇒(1.∧ 3.) ; 3.⇒1. without AC, by picking the smallest element of each preimage.

So, countable sets are either finite or in bijection with ℕ. The latter, on which there exists a
possible structure of ground term {0,*S*}-algebra, will be called countably infinite.
However we still need to prove that they are indeed infinite.

- There exists an injective algebra whose language has at least a constant and a non-constant.
- There exists a non-surjective injection of a set to itself; equivalently an
injective {0,
*S*}-algebra, or a set ℕ. - 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

4. ⇒ 2. ⇒ 1.; for 1. ⇒ 2. : from a non-constant operation *s* there,
*x*↦*s*(*k*↦*x*)
is an injective, non-surjective transformation.

We may regard 5. ⇒ 4. as relative to the natural assumption that the concept of injective
algebra forms a consistent theory. This theory is essentially the part of set theory which describes
tuples. So, if a language *L* is
included in a model of that simple part of set theory, then there
exists an injective *L*-algebra. If such a model *U* is standard, this takes the form
*L*⋆*U* ⊂ *U*, making (*U*, Id_{L⋆U})
an injective *L*-algebra. ∎

The infinity of ℕ easily implies the uniqueness of the
number of elements of a finite set, as its non-uniqueness would give that set a strict injection
into itself, and thus an injection of ℕ into it.

For 3. ⇒ 2. we shall pick a different set, as the existence of an injective {0,

For any set

Let ≈ be the equivalence relation of

The quotient structure on

Indeed:

- ∀(
*A*,*B*),(*A*',*B*') ∈*S*,_{P}*A*≈*A*' ⇔*B*≈*B*'. The converse for*x*∈*B*\*A*,*x*'∈*B*'\*A*' and*f*:*B*↔*B*' is by*A*∋*y*↦ (*f*(*y*)=*x*' ?*f*(*x*):*f*(*y*)) ∈*A*'. - ∀
*A*∈*P*,*A*≈∅ ⇔*A*=∅ ⇔*A*∉ Im*S*._{P}

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

Assuming the axiom of infinity, the finiteness of a set *E* is equivalent to the existence of a
number *n*∈ℕ and a bijection from
V_{n} = {*x*∈ℕ | *x*<*n*} to
*E*; or a surjection from V_{n} to
*E*, which is then bijective precisely when *n* takes its smallest value
(the number of elements of *E*).

Without ℕ, either ℘(℘(*E*)) or (with more
work) *E ^{E}* can be used to express the
finiteness of a set

Any left cancellative element of a finite monoid is invertible.
Thus any finite cancellative monoid is a group.

Proof: it acts as an injective transformation of
a finite set, thus a permutation, by which the preimage of *e* is a right inverse, thus an inverse.

x\y |
0 |
1 |
2 |
3 |

0 |
0 |
1 |
4 |
9 |

1 |
2 |
3 |
5 |
10 |

2 |
6 |
7 |
8 |
11 |

3 |
12 |
13 |
14 |
15 |

The sequence (

*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∈ℕ}*E*_{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 ℕ×ℕ.

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