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

Cantor's Diagonal Argument

  1. Feb 1, 2009 #1
    What allows us to do the construction found in Cantor's diagonal argument? Is there an axiom we must adopt to allow for such infinite constructions?
     
  2. jcsd
  3. Feb 1, 2009 #2

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    It doesn't take all that much set-theoretic structure for Cantor's argument to be valid. (It even works in the universe of finite sets)

    In what sense are you using the phrase "infinite construction"? And why should that be relevant to anything?

    The argument is pretty much the same as Russell's paradox; assuming the problematic function exists (an injection [itex]\mathcal{P}(X) \to X[/itex]), you construct some set that has a self-contradictory membership relation in pretty much the same manner.
     
    Last edited: Feb 2, 2009
  4. Feb 2, 2009 #3
    There does not seem to be any need beyond mathematical induction, and the use of the excluded middle, (i.e. A or not A). We set things up in a countable way, and then rely upon proof by contradiction.

    In fact, Euclid depends upon both of these principals in proving that the number of primes is infinite.
     
    Last edited: Feb 2, 2009
  5. Feb 2, 2009 #4

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Actually, the Diagonal argument doesn't even use the law of the excluded middle -- the law of noncontradiction is enough. The diagonal argument works in intuitionistic set theory, where the law of the excluded middle is invalid.
     
  6. Feb 2, 2009 #5
    What I mean by "infinite" construction is that we are allowed to select the next digit of the number ad infinitum - we allow ourselves to say that the construction "ends". Is this notion independent of others in mathematics; i.e. if we conduct mathematics without its use, do we get contradictions?
     
  7. Feb 2, 2009 #6

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    Are you asking about math without induction, like Robinson arithmetic?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?