Cantor's Diagonal Argument

Werg22

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?

Hurkyl

Staff Emeritus
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 $\mathcal{P}(X) \to X$), you construct some set that has a self-contradictory membership relation in pretty much the same manner.

Last edited:

robert Ihnot

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:

Hurkyl

Staff Emeritus
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.

Werg22

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?

CRGreathouse

Homework Helper
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?

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving