Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Aug 8, 2013 #1
    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: Aug 8, 2013
  2. jcsd
  3. Aug 8, 2013 #2


    User Avatar
    Homework Helper

    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").
  4. Aug 8, 2013 #3
    The proof is at a level that I don't really understand but I'm pretty sure the proof wasn't constructive.
  5. Aug 8, 2013 #4
    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!
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook