What Enables Cantor's Diagonal Argument Construction?

[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]

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.

 

[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.

 

[Hurkyl]

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]

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?

Are you asking about math without induction, like Robinson arithmetic?