Cantor's Diagonal Argument

  • Thread starter Werg22
  • Start date
  • Tags
    Argument
In summary, Cantor's diagonal argument relies on mathematical induction and the law of excluded middle to construct a set with a self-contradictory membership relation, similar to Russell's paradox. This argument also works in intuitionistic set theory, where the law of excluded middle is invalid. The construction is considered "infinite" because it allows for selecting the next digit of a number ad infinitum. Whether or not this notion is independent of other concepts in mathematics and whether contradictions arise without its use is still being debated.
  • #1
Werg22
1,431
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?
 
Mathematics news on Phys.org
  • #2
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:
  • #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:
  • #4
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.
 
  • #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?
 
  • #6
Werg22 said:
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?
 

What is Cantor's Diagonal Argument?

Cantor's Diagonal Argument is a proof developed by mathematician Georg Cantor in 1891. It is used to show that there are different sizes of infinity, and that the set of real numbers is uncountable.

How does Cantor's Diagonal Argument work?

Cantor's Diagonal Argument starts with a hypothetical list of all the real numbers, and then constructs a new number that is not on the list. This shows that the list is incomplete and there must be more real numbers than can be counted.

Why is Cantor's Diagonal Argument important?

Cantor's Diagonal Argument revolutionized the field of mathematics by showing that there are different levels of infinity, challenging the commonly held belief that infinity is a single concept. It has also had important implications in other areas of mathematics, such as set theory and logic.

How does Cantor's Diagonal Argument relate to the concept of uncountability?

Cantor's Diagonal Argument is used to prove that the set of real numbers is uncountable. This means that there is no way to put the set of real numbers in a one-to-one correspondence with the set of natural numbers, or any other countable set.

Can Cantor's Diagonal Argument be applied to other sets besides real numbers?

Yes, Cantor's Diagonal Argument can be used to show that any set larger than the set of natural numbers is uncountable. This includes sets such as the set of all irrational numbers, the set of all functions from the natural numbers to themselves, and the set of all subsets of the natural numbers.

Similar threads

Replies
3
Views
865
  • Set Theory, Logic, Probability, Statistics
Replies
6
Views
1K
  • General Math
Replies
22
Views
2K
  • General Math
Replies
32
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
25
Views
2K
Replies
11
Views
1K
  • Set Theory, Logic, Probability, Statistics
2
Replies
43
Views
3K
  • Set Theory, Logic, Probability, Statistics
2
Replies
55
Views
4K
  • General Math
Replies
19
Views
1K
Replies
4
Views
1K
Back
Top