A set is called

A set is called

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

1.⇒3. by restricting the order, once condensed ground {0,

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

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

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.

Let us abbreviate in binders

Assume given a set

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

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

In fact, such an

Still another justification of recursion, working for any term algebra, will later come using minimal subalgebras in products.

Another generalization of recursion, easy to insert in the above proof (or deducible by changing

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

This sequence can be defined recursively by

Then a bijection

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

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. Infinity and the axiom of choice

4.5. How theories develop

4.6. Second-order logic

4.7. The Incompleteness Theorem