Equivalent Conditions for Dedekind-Infinite Set

From ProofWiki
Jump to navigation Jump to search

Theorem

For a set $S$, the following conditions are equivalent:

$(1): \quad$ $S$ is Dedekind-infinite.
$(2): \quad$ $S$ has a countably infinite subset.

The above equivalence can be proven in Zermelo-Fraenkel set theory.

If the axiom of countable choice is accepted, then it can be proven that the following condition is also equivalent to the above two:

$(3): \quad$ $S$ is infinite.


Proof





(1) implies (2)

Let S be a Dedekind-infinite set.

This means that S is equilvant to a proper subset of itself.

That means there exists a map F from S to a proper subset of itself.

Let A be an element of S not in the image of F.

Also let A_n be a sequence such that A_0 = A and A_(n+1) = F(A_n).

The elements of A_n form a countably infinite set.

(2) implies (1)

Let S be a set with a countably infinite subset A.

We can define F such that if x is an element of A, then f(x) = f(A_n) = f(A_(n+1)) (and f(x) = x otherwise)

Thus F is a bijection between S and a subset of S (S minus A_0).

This means it is equilvant to that subset.