All Questions
6,026 questions
298
votes
34
answers
53k
views
What are some reasonable-sounding statements that are independent of ZFC?
Every now and then, somebody will tell me about a question. When I start thinking about it, they say, "actually, it's undecidable in ZFC."
For example, suppose $A$ is an abelian group such ...
256
votes
16
answers
71k
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 ...
185
votes
11
answers
52k
views
Knuth's intuition that Goldbach might be unprovable
Knuth's intuition that Goldbach's conjecture (every even number greater than 2 can be written as a sum of two primes) might be one of the statements that can neither be proved nor disproved really ...
- 2,745
169
votes
1
answer
17k
views
Ultrafilters and automorphisms of the complex field
It is well-known that it is consistent with $ZF$ that the only automorphisms of the complex field $\mathbb{C}$ are the identity map and complex conjugation. For example, we have that $\vert\...
- 8,298
150
votes
45
answers
30k
views
Nontrivial theorems with trivial proofs
A while back I saw posted on someone's office door a statement attributed to some famous person, saying that it is an instance of the callousness of youth to think that a theorem is trivial because ...
143
votes
12
answers
30k
views
Solutions to the Continuum Hypothesis
Related MO questions: What is the general opinion on the Generalized Continuum Hypothesis? ; Completion of ZFC ; Complete resolutions of GCH How far wrong could the Continuum Hypothesis be? When was ...
- 24.7k
135
votes
43
answers
38k
views
What are the most attractive Turing undecidable problems in mathematics?
What are the most attractive Turing undecidable problems in mathematics?
There are thousands of examples, so please post here only the most attractive, best examples. Some examples already appear on ...
128
votes
13
answers
24k
views
Checkmate in $\omega$ moves?
Is there a chess position with a finite number of pieces on the infinite chess board $\mathbb{Z}^2$ such that White to move has a forced win, but Black can stave off mate for at least $n$ moves for ...
- 5,492
124
votes
17
answers
18k
views
Pressure to defend the relevance of one's area of mathematics
I am a set theorist. Since I began to study this subject, I became increasingly aware of negative attitudes about it. These were expressed both from an internal and an external perspective. By the “...
122
votes
4
answers
39k
views
Is the analysis as taught in universities in fact the analysis of definable numbers?
Ten years ago, when I studied in university, I had no idea about definable numbers, but I came to this concept myself. My thoughts were as follows:
All numbers are divided into two classes: those ...
- 10.1k
114
votes
2
answers
12k
views
How would you solve this tantalizing Halmos problem?
$1-ab$ invertible $\implies$ $1-ba$ invertible has a slick power series "proof" as below, where Halmos asks for an explanation of why this tantalizing derivation succeeds. Do you know one?
Geometric ...
- 4,736
113
votes
2
answers
16k
views
Does every non-empty set admit a group structure (in ZF)?
It is easy to see that in ZFC, any non-empty set $S$ admits a group structure: for finite $S$ identify $S$ with a cyclic group, and for infinite $S$, the set of finite subsets of $S$ with the binary ...
- 3,511
113
votes
11
answers
18k
views
On mathematical arguments against Quantum computing
Quantum computing is a very active and rapidly expanding field of research. Many companies and research institutes are spending a lot on this futuristic and potentially game-changing technology. Some ...
110
votes
10
answers
26k
views
Set theories without "junk" theorems?
Clearly I first need to formally define what I mean by "junk" theorem. In the usual construction of natural numbers in set theory, a side-effect of that construction is that we get such theorems as $...
- 11.8k
107
votes
36
answers
21k
views
Interesting examples of vacuous / void entities
I included this footnote in a paper in which I mentioned that the number of partitions of the empty set is 1 (every member of any partition is a non-empty set, and of course every member of the empty ...
106
votes
19
answers
12k
views
When are two proofs of the same theorem really different proofs
Many well-known theorems have lots of "different" proofs. Often new proofs of a theorem arise surprisingly from other branches of mathematics than the theorem itself.
When are two proofs really the ...
- 1,069
100
votes
16
answers
29k
views
What if Current Foundations of Mathematics are Inconsistent? [closed]
The title of the question is also the title of a talk by Vladimir Voevodsky, available here.
Had this kind of opinion been expressed before?
EDIT. Thanks to all answerers, commentators, voters, ...
96
votes
16
answers
34k
views
Most 'unintuitive' application of the Axiom of Choice?
It is well-known that the axiom of choice is equivalent to many other assumptions, such as the well-ordering principle, Tychonoff's theorem, and the fact that every vector space has a basis. Even ...
89
votes
10
answers
17k
views
Is there any formal foundation to ultrafinitism?
Ultrafinitism is (I believe) a philosophy of mathematics that is not only constructive, but does not admit the existence of arbitrarily large natural numbers. According to Wikipedia, it has been ...
- 1,001
86
votes
10
answers
11k
views
What's wrong with the surreals?
Of all the constructions of the reals, the construction via the surreals seems the most elegant to me.
It seems to immediately capture the total ordering and precision of Dedekind cuts at a ...
- 1,843
86
votes
7
answers
21k
views
How many orders of infinity are there?
Define a growth function to be a monotone increasing function $F: {\bf N} \to {\bf N}$, thus for instance $n \mapsto n^2$, $n \mapsto 2^n$, $n \mapsto 2^{2^n}$ are examples of growth functions. Let's ...
- 114k
84
votes
3
answers
6k
views
How do I verify the Coq proof of Feit-Thompson?
I probably don't have the appropriate background to even ask this question. I know next to nothing about formal or computer-aided proof, and very little even about group theory. And this question is ...
- 29.8k
82
votes
3
answers
20k
views
Czelakowski's claimed proof of the Twin Prime Conjecture
It seems like the article "The Twin Primes Conjecture is True in the Standard Model of Peano Arithmetic: Applications of Rasiowa–Sikorski Lemma in Arithmetic (I)" by Janusz Czelakowski ...
- 1,083
80
votes
4
answers
9k
views
Who first characterized the real numbers as the unique complete ordered field?
Nearly every mathematician nowadays is familiar with the fact that
there is up to isomorphism only one complete ordered field, the
real numbers.
Theorem. Any two complete ordered fields are isomorphic....
- 236k
78
votes
12
answers
12k
views
Why aren't representations of monoids studied so much?
It seems to me like every book on representation theory leaps into groups right away, even though the underlying ideas, such as representations, convolution algebras, etc. don't really make explicit ...
- 2,392
77
votes
8
answers
12k
views
Succinctly naming big numbers: ZFC versus Busy-Beaver
Years ago, I wrote an essay called Who Can Name the Bigger Number?, which posed the following challenge:
You have fifteen seconds. Using standard math notation, English words, or both, name a single ...
- 9,833
76
votes
6
answers
8k
views
A better way to explain forcing?
Let me begin by formulating a concrete (if not 100% precise) question, and then I'll explain what my real agenda is.
Two key facts about forcing are (1) the definability of forcing; i.e., the ...
- 82.7k
76
votes
9
answers
6k
views
Can we unify addition and multiplication into one binary operation? To what extent can we find universal binary operations?
The question is the extent to which we can unify addition
and multiplication, realizing them as terms in a single
underlying binary operation. I have a number of questions.
Is there a binary ...
- 236k
74
votes
8
answers
14k
views
Category theory and set theory: just a different language, or different foundation of mathematics?
This is a question to research mathematicians, as well as to those concerned with the history and philosophy of mathematics.
I am asking for a reference. In order to make the reference request as ...
- 6,937
73
votes
9
answers
29k
views
What are some important but still unsolved problems in mathematical logic?
In the past, first-order logic and its completeness and whether arithmetic is complete was a major unsolved issues in logic . All of these problems were solved by Godel. Later on, independence of ...
72
votes
31
answers
9k
views
Can infinity shorten proofs a lot?
I've just been asked for a good example of a situation in maths where using infinity can greatly shorten an argument. The person who wants the example wants it as part of a presentation to the general ...
- 29k
72
votes
13
answers
19k
views
Logic in mathematics and philosophy
What are the relations between logic as an area of (modern) philosophy and mathematical logic.
The world "modern" refers to 20th century and later, and I am curious mainly about the second ...
- 24.7k
71
votes
5
answers
9k
views
Does anyone know a polynomial whose lack of roots can't be proved?
In Ebbinghaus-Flum-Thomas's Introduction to Mathematical Logic, the following assertion is made:
If ZFC is consistent, then one can obtain a polynomial $P(x_1, ..., x_n)$ which has no roots in the ...
- 25.6k
70
votes
6
answers
8k
views
The logic of Buddha: a formal approach
Buddhist logic is a branch of Indian logic (see also Nyaya), one of the three original traditions of logic, alongside the Greek and the Chinese logic. It seems Buddha himself used some of the features ...
69
votes
19
answers
9k
views
What are some results in mathematics that have snappy proofs using model theory?
I am preparing to teach a short course on "applied model theory" at UGA this summer. To draw people in, I am looking to create a BIG LIST of results in mathematics that have nice proofs ...
- 65.4k
69
votes
5
answers
10k
views
What was Hilbert's view of Gödel's Incompleteness Theorems?
According to Solomon Feferman, in his slide presentation "Three Problems for Mathematics", Hilbert wrote (in regards to Gödel's second incompleteness theorem):
...the end goal [is] to establish as ...
- 6,132
68
votes
9
answers
8k
views
Is all ordinary mathematics contained in high school mathematics?
By high school mathematics I mean Elementary Function Arithmetic (EFA), where one is allowed +, ×, xy, and a weak form of induction for formulas with bounded quantifiers. This is much weaker than ...
- 20.7k
68
votes
4
answers
12k
views
Nelson's program to show inconsistency of ZF
At the end of the paper Division by three by Peter G. Doyle and John H. Conway, the authors say:
Not that we believe there really are any such things as infinite sets, or that the Zermelo-Fraenkel ...
- 25.5k
67
votes
10
answers
14k
views
Arguments against large cardinals
I started to learn about large cardinals a while ago, and I read that the existence, and even the consistency of the existence of an inaccessible cardinal, i.e. a limit cardinal which is additionally ...
- 825
67
votes
5
answers
10k
views
Decidability of chess on an infinite board
The recent question Do there exist chess positions that require exponentially many moves to reach? of Tim Chow reminds me of a problem I have been interested in. Is chess with finitely many men on an ...
- 50.8k
66
votes
9
answers
14k
views
Axiom of choice, Banach-Tarski and reality
The following is not a proper mathematical question but more of a metamathematical one. I hope it is nonetheless appropriate for this site.
One of the non-obvious consequences of the axiom of choice ...
- 10.4k
66
votes
3
answers
4k
views
Reasons to prefer one large prime over another to approximate characteristic zero
Background:
In running algebraic geometry computations using software such as Macaulay2, it is often easier and faster to work over $\mathbb F_p = \mathbb Z / p\mathbb Z$ for a large prime $p$, rather ...
- 7,338
65
votes
16
answers
8k
views
What is the high-concept explanation on why real numbers are useful in number theory?
The utopian situation in mathematics would be that the statement and the proof of every result would live "in the same world", at the same level of mathematical complexity (in a broad sense), unless ...
65
votes
7
answers
23k
views
Can the Riemann hypothesis be undecidable?
The question is contained in the title; I mean the standard axioms ZFC. The wiki link: Riemann hypothesis. There are finite algorithms allowing one to decide if there are non-trivial zeroes of the $\...
- 659
65
votes
3
answers
6k
views
Forcing as a new chapter of Galois Theory?
There is a (very) long essay by Grothendieck with the ominous title La Longue Marche à travers la théorie de Galois (The Long March through Galois Theory). As usual, Grothendieck knew what he was ...
- 7,853
64
votes
15
answers
7k
views
Unnecessary uses of the axiom of choice
What examples are there of habitual but unnecessary uses of the axiom of
choice, in any area of mathematics except topology?
I'm interested in standard proofs that use the axiom of choice, but where
...
63
votes
8
answers
16k
views
Reductio ad absurdum or the contrapositive?
From time to time, when I write proofs, I'll begin with a claim and then prove the contradiction. However, when I look over the proof afterwards, it appears that my proof was essentially a proof of ...
63
votes
5
answers
9k
views
Bourbaki's definition of the number 1
According to a polemical article by Adrian Mathias, Robert Solovay showed that Bourbaki's definition of the number 1, written out using the formalism in the 1970 edition of Théorie des Ensembles, ...
- 22.3k
61
votes
8
answers
9k
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 ...
- 7,633
61
votes
5
answers
12k
views
Is the Riemann Hypothesis equivalent to a $\Pi_1$ sentence?
1) Can the Riemann Hypothesis (RH) be expressed as a $\Pi_1$ sentence?
More formally,
2) Is there a $\Pi_1$ sentence which is provably equivalent to RH in PA?
Update (July 2010):
So we have two ...
- 5,502