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.
Read more about this topic: Dedekind-infinite Set
Famous quotes containing the word sets:
“Wilson adventured for the whole of the human race. Not as a servant, but as a champion. So pure was this motive, so unflecked with anything that his worst enemies could find, except the mildest and most excusable, a personal vanity, practically the minimum to be human, that in a sense his adventure is that of humanity itself. In Wilson, the whole of mankind breaks camp, sets out from home and wrestles with the universe and its gods.”
—William Bolitho (1890–1930)