# Tagged Questions

**120**

votes

**26**answers

14k 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 that every ...

**117**

votes

**0**answers

10k 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 ...

**92**

votes

**15**answers

17k 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 ...

**88**

votes

**11**answers

17k 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 ...

**81**

votes

**42**answers

17k 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 ...

**73**

votes

**16**answers

16k 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, ...

**73**

votes

**11**answers

7k 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 ...

**71**

votes

**9**answers

11k views

### Solutions to the Continuum Hypothesis

Related MO questions: What is the general opinion on the Generalized Continuum Hypothesis? Completion of ZFC )
Background
The Continuum Hypothesis (CH) posed by Cantor in 1890 asserts that $ ...

**64**

votes

**3**answers

6k 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 ...

**63**

votes

**16**answers

5k 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 ...

**60**

votes

**9**answers

4k 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 ...

**51**

votes

**28**answers

6k 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 ...

**51**

votes

**6**answers

11k 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 ...

**50**

votes

**3**answers

6k 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 ...

**49**

votes

**12**answers

9k 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 half of ...

**49**

votes

**2**answers

5k views

### Does Godel's incompleteness theorem admit a converse?

Let me set up a strawman:
One might entertain the following criticism of Godel's incompleteness theorem:
why did we ever expect completeness for the theory of PA or ZF in the first place?
Sure, one ...

**48**

votes

**26**answers

6k views

### Sexy vacuity …

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 ...

**48**

votes

**8**answers

5k 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 ...

**48**

votes

**3**answers

2k 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 ...

**46**

votes

**14**answers

4k 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 ...

**46**

votes

**5**answers

5k 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 ...

**45**

votes

**15**answers

11k 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 ...

**44**

votes

**34**answers

10k 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 ...

**44**

votes

**5**answers

4k 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 ...

**44**

votes

**2**answers

4k views

### How would you solve this tantalizing Halmos problem?

1-ab invertible => 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 series. In ...

**44**

votes

**2**answers

1k 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 ...

**43**

votes

**8**answers

4k 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 ...

**43**

votes

**9**answers

4k views

### How do they verify a verifier of formalized proofs?

In an unrelated thread Sam Nead intrigued me by mentioning a formalized proof of the Jordan curve theorem. I then found that there are at least two, made on two different systems. This is quite an ...

**42**

votes

**18**answers

4k 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 using model ...

**42**

votes

**3**answers

2k 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 ...

**40**

votes

**4**answers

4k views

### What was Gödel's real achievement?

When I first heard of the existence of Gödel's theorem, I was amazed not just at the theorem but at the fact that the question could be made precise enough to answer: how on earth, even in ...

**40**

votes

**2**answers

4k views

### A question about ordinal definable real numbers

If ZFC (Zermelo-Fraenkel set theory with the Axiom of Choice) is consistent, does it remain consistent
when the following statement is added to it as a new axiom?
"There exists a denumerably ...

**39**

votes

**5**answers

4k views

### Which graphs are Cayley graphs?

Every group presentation determines the corresponding Cayley graph, which has a node for each group element, and arrows labeled with the generators to get from one group element to another.
My main ...

**38**

votes

**2**answers

12k views

### Is the analysis as taught in universities in fact the analysis of definable numbers?

Ten years ago when I studied in the 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 ...

**37**

votes

**7**answers

2k views

### How would one even begin to try to prove that a simple number-theoretic statement is undecidable?

This question is closely related to this one: Knuth's intuition that Goldbach might be unprovable. It stems from my ignorance about non-standard models of arithmetic. In a comment on the other ...

**37**

votes

**8**answers

5k 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 ...

**37**

votes

**1**answer

1k views

### When does $A^A=2^A$ without the axiom of choice?

Assuming the axiom of choice the following argument is simple, for infinite $A$ it holds: $$2\lt A\leq2^A\implies 2^A\leq A^A\leq 2^{A\times A}=2^A.$$
However without the axiom of choice this doesn't ...

**36**

votes

**7**answers

7k 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 ...

**36**

votes

**5**answers

3k views

### What's wrong with the surreals?

Of all the constructions of the reals, the construction of the surreals seems the most elegant to me.
It seems to immediately capture the total ordering and precision of Dedekind cuts at a ...

**35**

votes

**4**answers

2k views

### The origin of sets?

The history of set theory from Cantor to modern times is well documented. However, the origin of the idea of sets is not so clear. A few years ago, I taught a set theory course and I did some digging ...

**34**

votes

**15**answers

6k views

### Strong induction without a base case

Strong induction proves a sequence of statements $P(0)$, $P(1)$, $\ldots$ by proving the implication
"If $P(m)$ is true for all nonnegative integers $m$ less than $n$, then $P(n)$ is true."
for ...

**34**

votes

**4**answers

2k views

### Which topological spaces admit a nonstandard metric?

My question is about the concept of nonstandard metric space that would arise from a use of the nonstandard reals R* in place of the usual R-valued metric.
That is, let us define that a topological ...

**34**

votes

**3**answers

2k views

### Inconsistent theory with long contradiction

What can one say about an inconsistent theory $T$ which has no contradictions (i.e. deductions of $P \wedge \neg P$) of length shorter than $n$, where $n$ is some huge number?
There have been some ...

**33**

votes

**5**answers

3k 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?
(This is mentioned in P. ...

**33**

votes

**1**answer

2k views

### Does $2^X=2^Y\Rightarrow |X|=|Y|$ imply the axiom of choice?

The Generalized Continuum Hypothesis can be stated as $2^{\aleph_\alpha}=\aleph_{\alpha+1}$. We know that GCH implies AC (Jech, The Axiom of Choice, Theorem 9.1 p.133).
In fact, a relatively weak ...

**32**

votes

**5**answers

3k views

### Does “compact iff projections are closed” require some form of choice?

There are many equivalent ways of defining the notion of compact space, but some require some kind of choice principle to prove their equivalence. For example, a classical result is that for $X$ to be ...

**32**

votes

**7**answers

2k views

### Is the ultraproduct concept fundamentally category-theoretic?

Once again, I would like to take advantage of the large number of knowledgable category theorists on this site for a question I have about category-theoretic aspects of a fundamental logic concept.
...

**31**

votes

**7**answers

5k 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 ...

**31**

votes

**10**answers

3k views

### Believing the Conjectures

In Believing the axioms (I and II), Penelope Maddy proposes five "rules of thumb" that she then uses to justify large cardinal axioms in set theory. These extrinsic rules are modeled after the ...

**31**

votes

**6**answers

2k views

### Is the non-triviality of the algebraic dual of an infinite-dimensional vector space equivalent to the axiom of choice?

If $V$ is given to be a vector space that is not finite-dimensional, it doesn't seem to be possible to exhibit an explicit non-zero linear functional on $V$ without further information about $V$. The ...