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

  • Thread starter gottfried
  • Start date
  • #1
119
0
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:

Answers and Replies

  • #2
pasmith
Homework Helper
2,038
663
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").
 
  • #3
119
0
The proof is at a level that I don't really understand but I'm pretty sure the proof wasn't constructive.
 
  • #4
22,129
3,297
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!
 

Related Threads on A countable subset of an infinite set and the axiom of choice.

Replies
3
Views
1K
  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
1
Views
512
  • Last Post
Replies
3
Views
2K
Replies
3
Views
4K
Replies
4
Views
2K
Replies
3
Views
4K
Replies
4
Views
6K
Replies
8
Views
8K
Top