Cantor's Diagonal Argument

  • Thread starter Werg22
  • Start date
1,424
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?
 

Hurkyl

Staff Emeritus
Science Advisor
Gold Member
14,845
17
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:
1,056
0
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
Science Advisor
Gold Member
14,845
17
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.
 
1,424
1
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

Science Advisor
Homework Helper
2,817
0
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?
 

Related Threads for: Cantor's Diagonal Argument

Replies
36
Views
8K
Replies
12
Views
4K
  • Posted
Replies
1
Views
4K
Replies
19
Views
724
Replies
4
Views
2K
Replies
22
Views
1K
Replies
9
Views
2K
Replies
4
Views
2K

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

Hot Threads

Top