Linked Questions
10 questions linked to/from Proofs of the uncountability of the reals
269
votes
16
answers
77k
views
Why worry about the axiom of choice?
As I understand it, it has been proven that the axiom of choice is independent of the other axioms of set theory. Yet I still see people fuss about whether or not theorem X depends on it, and I don't ...
63
votes
8
answers
10k
views
What does it mean to suspect that two conjectures are logically equivalent?
Here's a familiar conversation:
Me: Do you think Conjecture A and Conjecture B are equivalent?
Friend: Yes, because I think they're both true.
Me: [eye roll] You know what I mean...
Does there ...
- 8,100
53
votes
7
answers
8k
views
Are there any undecidability results that are not known to have a diagonal argument proof?
Is there a problem which is known to be undecidable (in the algorithmic sense), but for which the only known proofs of undecidability do not use some form of the Cantor diagonal argument in any ...
- 121k
34
votes
4
answers
4k
views
Why is it so difficult to define constructive cardinality?
Consider Frege's cardinality and HoTT set-truncation cardinality, both of which can be well-defined in constructive theory (as SetoidTT and CubicalTT, respectively). Why don’t we regard them as well ...
- 1,523
42
votes
7
answers
4k
views
Precise meaning of "picking a basis"?
Some years ago, Kevin Buzzard wrote a blog post asking whether the trace of a linear map $\phi \colon V \to V$ on a vector space $V$ can be defined "without picking a basis." He had some ...
- 91.7k
18
votes
4
answers
3k
views
Why is there no Borel function mapping every countable set of reals outside itself?
A choice function maps every set (in its domain) to an element of itself. This question concerns existence of an anti-choice function defined on the family of countable sets of reals. In an answer to ...
- 30.5k
12
votes
4
answers
2k
views
Are there non-diagonal proofs for Cantor's continuum and Godel's incompletness theorems?
There is a formal definition for the notion of a formal proof.
Question 1. Is there any formal definition for the notion of a diagonal formal proof?
Consider the following theorems both proved by ...
- 141
12
votes
4
answers
3k
views
Earliest diagonal proof of the uncountability of the reals.
I cited the diagonal proof of the uncountability of the reals as an example of a `common false belief' in mathematics, not because there is anything wrong with the proof but because it is commonly ...
- 13.7k
20
votes
2
answers
2k
views
Cantor's argument revisited
This was inspired by this recent question.
In my answer there, I pointed out that, given $F:{\mathcal P}(X)\to X$, an argument dating back to Zermelo allows us to define a pair $(A,B)$ of distinct ...
- 33.2k
7
votes
0
answers
293
views
When is a reduction not a reduction?
Every mathematician understands the concept of reducing a complicated problem to a simpler problem. "Without loss of generality, we may assume…" However, I've noticed that some kinds of "...
- 91.7k