What Enables Cantor's Diagonal Argument Construction?

  • Context: Graduate 
  • Thread starter Thread starter Werg22
  • Start date Start date
  • Tags Tags
    Argument
Click For Summary

Discussion Overview

The discussion centers around the foundations of Cantor's diagonal argument, specifically exploring what axioms or principles enable its construction, particularly in the context of infinite sets and mathematical reasoning. Participants examine the implications of infinite constructions and their relationship to set theory and logic.

Discussion Character

  • Exploratory
  • Debate/contested
  • Technical explanation

Main Points Raised

  • Some participants suggest that Cantor's argument requires minimal set-theoretic structure, noting its validity even within finite sets.
  • One participant questions the relevance of "infinite construction" and its implications for mathematical reasoning.
  • Another participant argues that mathematical induction and the law of excluded middle are sufficient for the argument, citing Euclid's proof of the infinitude of primes as an example.
  • Contrarily, a participant claims that the diagonal argument does not require the law of excluded middle, asserting its validity in intuitionistic set theory where this law is not accepted.
  • A participant elaborates on the concept of "infinite construction," discussing the selection of digits in a number and questioning whether mathematics without this notion leads to contradictions.
  • There is a follow-up inquiry about conducting mathematics without induction, referencing Robinson arithmetic as a possible framework.

Areas of Agreement / Disagreement

The discussion features multiple competing views regarding the necessity of certain axioms or principles for Cantor's diagonal argument, with no consensus reached on the foundational requirements for infinite constructions.

Contextual Notes

Participants express varying assumptions about the role of induction and the law of excluded middle in mathematical reasoning, indicating potential limitations in their arguments based on differing interpretations of these principles.

Werg22
Messages
1,431
Reaction score
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?
 
Physics news on Phys.org
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:
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:
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.
 
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?
 
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?
 

Similar threads

High School I have an issue with Cantor's diagonal argument
  • · Replies 6 ·
Replies
6
Views
2K
High School Another consequence of Cantor's diagonal argument
  • · Replies 43 ·
2
Replies
43
Views
6K
High School One thing I don't understand about Cantor's diagonal argument
  • · Replies 55 ·
2
Replies
55
Views
9K
Undergrad Proof of a fact about real numbers - transcendental and algebraic
  • · Replies 7 ·
Replies
7
Views
2K
Graduate Does Cantor's Diagonal Argument Apply to the Rationals?
  • · Replies 4 ·
Replies
4
Views
3K
Undergrad Question about Cantor's Diagonal Proof
  • · Replies 22 ·
Replies
22
Views
4K
Undergrad Countability of binary Strings
  • · Replies 18 ·
Replies
18
Views
4K
Undergrad Understanding Cantor's Diagonalization Proof: A Brief Explanation
  • · Replies 17 ·
Replies
17
Views
3K
Undergrad Maybe all reals can be listed?
  • · Replies 32 ·
2
Replies
32
Views
3K
Undergrad Regarding Cantor's diagonal proof
  • · Replies 86 ·
3
Replies
86
Views
10K