# A countable subset of an infinite set and the axiom of choice.

According to a result of Paul Cohen in a mathematical model without the axiom of choice there exists an infinite set of real numbers without a countable subset. The proof that every infinite set has a countable subset (http://www.proofwiki.org/wiki/Infinite_Set_has_Countably_Infinite_Subset) is dependant on the axiom of choice and therefore cannot be proven in a model without the axiom of choice. Given that it cannot be proven does it imply there MUST be atleast one infinite set without a countable subset?

I realise this may seem like a stupid questions because it seems intuitive that if something can't be proven then there must be a counter example but I have learnt to be skeptical about any naievely intuitive conclusions so I was hopping somebody could just clarify.

Last edited:

pasmith
Homework Helper
The proof that every infinite set has a countable subset (http://www.proofwiki.org/wiki/Infinite_Set_has_Countably_Infinite_Subset) is dependant on the axiom of choice and therefore cannot be proven in a model without the axiom of choice. Given that it cannot be proven does it imply there MUST be atleast one infinite set without a countable subset?

No. "Cannot be proven" does not imply "is false".

The first sentence of your post conveys the impression that Cohen has actually established the existence of such a set, although you will have to look at his work to see whether his proof is constructive ("here's such a set") or not ("the non-existence of such a set is impossible").

The proof is at a level that I don't really understand but I'm pretty sure the proof wasn't constructive.

The proof is at a level that I don't really understand but I'm pretty sure the proof wasn't constructive.

His proof actually is rather constructive. He actually constructed a possible set theory in which your proposition holds false, and he showed it was (relative) consistent.

In mathematics, there are the following notions:
Proposition A is true
Proposition A is false
Proposition A can be proven
Proposition A cannot be proven

Do not confuse between these. There is a big difference between something being true and something which can be proven.

Roughly, if the axioms are true statements (which we certainly hope for), then Proposition A can be proven implies that Proposition A is true. But it doesn't mean that if Proposition A cannot be proven, then Proposition A is false!