**23**

votes

**2**answers

2k views

### Similarities between Post's Problem and Cohen's Forcing

Remark: I have since learned that G.H. Moore addresses this question in the third reference listed at the end of this post, beginning on p. 157 in which he cites a letter from Kreisel to Gödel dated ...

**52**

votes

**2**answers

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

**119**

votes

**15**answers

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

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

**4**

votes

**0**answers

321 views

### Reference for Wang Tile

I am working on projects in solving ground state of generalized ising models. One recent work involves tiling with basic tiles that filled the whole lattice. For example, we could obtain results:
...

**34**

votes

**7**answers

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

**34**

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

**70**

votes

**3**answers

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

**47**

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

**28**

votes

**0**answers

1k views

### Concerning the various proofs from the axiom of choice that R^3 admits of surprising geometrical decompositions into circles, skew lines and so on: can we prove in any instance that there are no Borel such decompositions? Or that AC is required?

This question follows up on a comment I made on Joseph O'Rourke's
recent question, one of several questions here on mathoverflow
concerning surprising geometric partitions of space using the axiom
of ...

**-2**

votes

**2**answers

1k views

### Is metatheory, providing proof of the incompleteness theorem, consistent?

Is metatheory, considered as a formal system, that used to prove the First Incompleteness Theorem, consistent?

**88**

votes

**42**answers

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

**83**

votes

**9**answers

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

**50**

votes

**15**answers

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

**51**

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

**46**

votes

**14**answers

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

**39**

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

**17**

votes

**2**answers

3k views

### Large cardinal axioms and Grothendieck universes

A cardinal $\lambda$ is weakly inaccessible, iff a. it is regular (i.e. a set of cardinality $\lambda$ can't be represented as a union of sets of cardinality $<\lambda$ indexed by a set of ...

**27**

votes

**6**answers

4k views

### A remark of Connes

In an interview (at http://www.alainconnes.org/docs/Inteng.pdf) Connes remarks that
I had been working on non-standard analysis, but after a while I had found a catch in the theory.... The point ...

**20**

votes

**3**answers

2k views

### Who needs Replacement anyway?

The set theory ETCS famously comes without the Replacement axiom schema (or an equivalent) that is part of ZFC. One (to me, not apparently useful) set that one cannot build in ETCS is $\coprod_{n\in ...

**10**

votes

**5**answers

2k views

### Interesting meta-meta-mathematical theorems?

The Goedel incompleteness theorems can be considered meta-mathematical theorems, as they are "written" in a meta-theory and "talk" about properties of a class of formal theories.
The following may be ...

**13**

votes

**5**answers

2k views

### Hahn-Banach without Choice

The standard proof of the Hahn-Banach theorem makes use of Zorn's lemma. I hear that, however, Hahn-Banach is strictly weaker than Choice. A quick search leads to many sources stating that Hahn-Banach ...

**19**

votes

**7**answers

1k views

### Does every set admit a rigid binary relation? (and how is this related to the Axiom of Choice?)

Let us say that a set B admits a rigid binary relation, if there is a binary relation R such that the structure (B,R) has no nontrivial automorphisms.
Under the Axiom of Choice, every set is ...

**9**

votes

**4**answers

3k views

### Pi1-sentence independent of ZF, ZF+Con(ZF), ZF+Con(ZF)+Con(ZF+Con(ZF)), etc.?

Let
ZF1 = ZF,
ZFk+1 = ZF + the assumption that ZF1,...,ZFk are consistent,
ZFω = ZF + the assumption that ZFk is consistent for every positive integer k,
... and similarly define ZFα ...

**14**

votes

**2**answers

1k views

### Does ZFC prove the universe is linearly orderable?

It is consistent with ZFC that the universe is well-ordered, e.g. in $V=L$ where global choice holds. I also know that it is consistent that global choice fails (although I have no immediate example ...

**16**

votes

**1**answer

1k views

### Gödel's Constructible Universe in Infinitary Logics (A Possible Approach to HOD Problem)

Gödel's constructible universe ($L$) is defined using definable power set operator in first order logic ($\mathcal{L}_{\omega ,\omega}$). One can produce such a universe in infinitary logics in ...

**12**

votes

**1**answer

310 views

### What metatheory proves $\mathsf{ACA}_0$ conservative over PA?

Simpson's book shows $\mathsf{ACA}_0$ is conservative over $\mathsf{PA}$ in the natural way by model theory using definable subsets. Of course, $\mathsf{ACA}_0$ being conservative over PA is ...

**12**

votes

**1**answer

874 views

### finite dimensional real division algebras

A celebrated theorem of Milnor and Kervaire asserts that any finite dimensional division algebra over the real numbers has dimension 1,2,4 or 8. This result is established using methods from algebraic ...

**17**

votes

**2**answers

852 views

### If ZFC has a transitive model, does it have one of arbitrary size?

It is known that the consistency strength of $\sf ZFC+\rm Con(\sf ZFC)$ is greater than that of $\sf ZFC$ itself, but still weaker than asserting that $\sf ZFC$ has a transitive model. Let us denote ...

**7**

votes

**2**answers

734 views

### Can formal logic give a precise notion of “canonical”?

Coming off of this discussion, I'm wondering what the term "canonical" really means. In that thread, many suggested category theory as a way to formalize the concept of what "canonical" means, using ...

**6**

votes

**2**answers

667 views

### Is there one binary operation foundational for set theory?

The membership relationship "$\epsilon$" is foundational for set theory, in the sense that the axioms of any set theory are formulated in the language of "$\epsilon$". Naturally, the question arises ...

**4**

votes

**1**answer

310 views

### Can the Burgess-Hazen analysis of Predicative Arithmetic be extended to Transfinite Types?

Around page 300 of his book "Mathematical Thought and its Objects", Charles Parsons discusses the work of Edward Nelson, who believes that mathematical induction is impredicative, because it can be ...

**4**

votes

**1**answer

228 views

### Computational approach deciding whether a set of Wang Tile could tile the space up to some size

As an applied person, I'm facing one practical problem deciding whether a set of Wang tile could tile the plane periodically or aperiodically. Although both problems seem undecidable, but I'm on a ...

**3**

votes

**5**answers

999 views

### Defining 'free monoid' without Nat?

Is there a definition of what is a 'free monoid' which does not pre-suppose that the natural numbers has already been defined? The definitions that I have been able to track down all use the natural ...

**2**

votes

**1**answer

467 views

### Compactness and completeness in Gödel logic

The standard proof of the completeness theorem in first-order Gödel logic is based
on a first-order countable language. I want to know that is there any proof of the completeness theorem in ...

**142**

votes

**27**answers

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

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

**31**

votes

**15**answers

5k views

### Abstract Thought vs Calculation

Jeremy Avigad and Erich Reck in their remarkable historical paper "Clarifying the nature of the infinite: the development of metamathematics and proof theory" claim that one of the factors of becoming ...

**80**

votes

**11**answers

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

**57**

votes

**6**answers

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

**41**

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

**56**

votes

**4**answers

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

**27**

votes

**8**answers

4k views

### Arithmetic fixed point theorem

I want to understand the idea of the proof of the artihmetic fixed point theorem. The theorem is crucial in the proof of Gödel's first Incompletness theorem.
First some notation: We work in $NT$, the ...

**30**

votes

**3**answers

2k views

### Why do stacked quantifiers in PA correspond to ordinals up to $\epsilon_0$?

I am trying to understand why induction up to exactly $\epsilon_0$ is necessary to prove the cut-elimination theorem for first-order Peano Arithmetic; or, as I understand, equivalently, why the length ...

**27**

votes

**9**answers

3k views

### How many groups of size at most n are there? What is the asymptotic growth rate? And what of rings, fields, graphs, partial orders, etc.?

Question. How many (isomorphism types of) finite groups of size at most n are there? What is the asymptotic growth rate? And the same question for rings,
fields, graphs, partial orders, etc.
...

**15**

votes

**2**answers

3k views

### Question arising from Voevodsky's talk on inconsistency

This question arises from the talk by Voevodsky mentioned in
this recent MO question. On one of his slides, Voevodsky says that
a general formula even with one free variable describes a subset of ...

**14**

votes

**12**answers

3k views

### Excellent uses of induction and recursion

Can you make an example of a great proof by induction or construction by recursion?
Given that you already have your own idea of what "great" means, here it can also be taken to mean that the chosen ...

**16**

votes

**3**answers

2k views

### Is there a computable model of ZFC?

Background
Assuming ZFC is consistent, then by downward Löwenheim–Skolem, there is a countable model (M,$\in$) of ZFC. Since the universe M is countable, we may as well think of it as actually being ...

**27**

votes

**1**answer

1k views

### Is there a computable ordinal encoding the proof strength of ZF? Is it knowable?

In comments on Quora (see, for example, here, here, here), Ron Maimon has repeatedly expressed the strong opinion that Hilbert's program was not killed by Gödel's results in the way typically ...

**21**

votes

**2**answers

1k views

### What is the theory of local rings and local ring homomorphisms?

It is well-known that the category of local rings and ring homomorphisms admits an axiomatisation in coherent logic. Explicitly, it is the coherent theory over the signature $0, 1, -, +, \times$ with ...