Dedekind-infinite Set - Dedekind-infinite Sets in ZF

Dedekind-infinite Sets in ZF

The following conditions are equivalent in ZF. In particular, note that all these conditions can be proved to be equivalent without using the AC.

• A is Dedekind-infinite.
• There is a function f: A → A which is injective but not surjective.
• There is an injective function f : N → A, where N denotes the set of all natural numbers.
• A has a countably infinite subset.

Every Dedekind-infinite set A also satisfies the following condition:

• There is a function f: A → A which is surjective but not injective.

This is sometimes written as "A is dually Dedekind-infinite". It is not provable (in ZF without the AC) that dual Dedekind-infinity implies that A is Dedekind-infinite. (For example, if B is an infinite but Dedekind-finite set, and A is the set of finite one-to-one sequences from B, then "drop the last element" is a surjective but not injective function from A to A, yet A is Dedekind finite.)

It can be proved in ZF that every dually Dedekind infinite set satisfies the following (equivalent) conditions:

• There exists a surjective map from A onto a countably infinite set.
• The powerset of A is Dedekind infinite

(Sets satisfying these properties are sometimes called weakly Dedekind infinite.)

It can be shown in ZF that weakly Dedekind infinite sets are infinite.

ZF also shows that every well-ordered infinite set is Dedekind infinite.