Skip to main content

All Questions

Filter by
Sorted by
Tagged with
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 ...
32 votes
2 answers
4k 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 4/...
Benjamin Dickman's user avatar
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 ...
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 ...
Konrad Swanepoel's user avatar
9 votes
1 answer
889 views

Combinatorics for the action of Virasoro / Kac–Schwarz operators: partition polynomials of free probability theory

In the background sections below, I establish the relations among characterizations of the action of Virasoro / Kac–Schwarz operators of 2D gravity models presented in terms of Laurent series by ...
Tom Copeland's user avatar
  • 10.5k
56 votes
7 answers
8k views

What is the smallest unsolved Diophantine equation?

If $P=\sum_{\bf i} a_{\bf i}x^{\bf i}\in {\mathbb Z}[x_1,\dots,x_d]$, let $|P|=\sum_{\bf i}|a_{\bf i}|x^{\bf i}$ and $h(P)=|P|(2,\dots,2)$, so that there is only a finite number of $P$ with $h(P)\leq ...
Zidane's user avatar
  • 937
23 votes
1 answer
3k 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 ...
user avatar
32 votes
5 answers
4k views

How many of the true sentences are provable?

Is there a natural measure on the set of statements which are true in the usual model (i.e. $\mathbb{N}$) of Peano arithmetic which enables one to enquire if 'most' true sentences are provable or ...
pinaki's user avatar
  • 5,339
23 votes
5 answers
4k views

Morse-Kelley set theory consistency strength

I've come across several references to MK (Morse-Kelley set theory), which includes the idea of a proper class, a limitation of size, includes the axiom schema of comprehension across class variables (...
Richard Rast's user avatar
  • 1,979
18 votes
0 answers
895 views

Is the universality of the surreal number line a weak global choice principle?

I'd like to consider the principle asserting that the surreal number line is universal for all class linear orders, or in other words, that every linear order (including proper-class-sized) linear ...
Joel David Hamkins's user avatar
17 votes
2 answers
3k 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 ...
Asaf Karagila's user avatar
  • 39.8k
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 $...
Jacques Carette's user avatar
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 ...
57 votes
6 answers
6k 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 ...
Konrad Swanepoel's user avatar
49 votes
0 answers
3k views

Concerning proofs from the axiom of choice that ℝ³ admits surprising geometrical decompositions: Can we prove there is no Borel decomposition?

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 ...
Joel David Hamkins's user avatar
40 votes
3 answers
5k 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 ...
skeptical scientist's user avatar
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 ...
Gil Kalai's user avatar
  • 24.7k
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 ...
Anixx's user avatar
  • 10.1k
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 ...
Martyguy's user avatar
  • 1,069
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 ...
Richard Stanley's user avatar
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 ...
user8996's user avatar
  • 825
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 ...
Kaveh's user avatar
  • 5,502
49 votes
5 answers
5k views

Are the two meanings of "undecidable" related?

I am usually confused by questions of the type "could such and such a problem be undecidable", because as far as I know there are two distinct possible meanings of "undecidable". ...
John Pardon's user avatar
  • 18.7k
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 ...
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 ...
Terry Tao's user avatar
  • 114k
60 votes
6 answers
7k views

Has decidability got something to do with primes?

Note: I have modified the question to make it clearer and more relevant. That makes some of references to the old version no longer hold. I hope the victims won't be furious over this. Motivation: ...
abcdxyz's user avatar
  • 2,824
53 votes
1 answer
6k 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 ...
Asaf Karagila's user avatar
  • 39.8k
48 votes
5 answers
7k views

What axioms are used to prove Gödel's Incompleteness Theorems?

I understand Gödel's Incompleteness Theorems to be statements about effectively generated formal systems, which basically makes them theorems about algorithms. This is cool, because despite being ...
Andrew Critch's user avatar
39 votes
6 answers
7k views

A remark of Connes on non-standard analysis

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 is ...
Robert Haraway's user avatar
36 votes
3 answers
2k views

Internal logic of the topos of simplicial sets

I am looking for a closed statement (i.e. not depending on any parameter objects) which is true in the internal logic of the topos of simplicial sets, but is not an intuitionistic tautology. Ideally, ...
Mike Shulman's user avatar
  • 66.8k
29 votes
1 answer
1k views

Is the Golomb countable connected space topologically rigid?

The Golomb space $\mathbb G$ is the set of positive integers endowed with the topology generated by the base consisting of the arithmetic progressions $a+b\mathbb N_0$ with relatively prime $a,b$ and $...
Taras Banakh's user avatar
  • 41.9k
23 votes
2 answers
3k views

Is there any research on set theory without extensionality axiom?

In practice (say, in computer science), collections with many "labels" ("identities"), or collections which occur in many copies, are more frequently used than sets. Such collections do not satisfy ...
Ioachim Drugus's user avatar
23 votes
1 answer
2k views

Can we axiomatize Omnific Integers without the Surreal Number system?

Omnific integers are the counterpart in the Surreal numbers of the integers. The surreal numbers are usually defined using set theory, and then the omnific integers are defined as a particular subset (...
Keshav Srinivasan's user avatar
20 votes
7 answers
2k 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 well-...
Joel David Hamkins's user avatar
20 votes
3 answers
5k 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α ...
Scott Aaronson's user avatar
10 votes
2 answers
803 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: ...
user40780's user avatar
  • 867
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 ...
AgCl's user avatar
  • 2,745
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 ...
Johan Wästlund's user avatar
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 ...
Scott Aaronson's user avatar
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 ...
Andreas Thom's user avatar
  • 25.5k
60 votes
8 answers
10k views

Why should we believe in the axiom of regularity?

Today I started reading Maddy's Believing the axioms. As I knew beforehand, it includes some discussion of ZFC axioms. However, I really hoped for a more extensive discussion of axiom of foundation/...
Wojowu's user avatar
  • 28.2k
54 votes
5 answers
15k views

The unification of Mathematics via Topos Theory

In her paper The unification of Mathematics via Topos Theory, Olivia Caramello says "one can generate a huge number of new results in any mathematical field without any creative effort". Is ...
Roy Maclean's user avatar
  • 1,190
47 votes
3 answers
7k views

Clearing misconceptions: Defining "is a model of ZFC" in ZFC

There is often a lot of confusion surrounding the differences between relativizing individual formulas to models and the expression of "is a model of" through coding the satisfaction relation with ...
Jason's user avatar
  • 2,762
46 votes
8 answers
12k views

What are some proofs of Godel's Theorem which are *essentially different* from the original proof?

I am looking for examples of proofs of Godel's (First) Incompleteness Theorem which are essentially different from (Rosser's improvement of) Godel's original proof. This is partly inspired by ...
37 votes
6 answers
6k 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 \...
David Roberts's user avatar
  • 35.5k
34 votes
8 answers
8k 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 ...
Martin Brandenburg's user avatar
32 votes
3 answers
7k views

Is the statement that every field has an algebraic closure known to be equivalent to the ultrafilter lemma?

The existence and uniqueness of algebraic closures is generally proven using Zorn's lemma. A quick Google search leads to a 1992 paper of Banaschewski, which I don't have access to, asserting that ...
Qiaochu Yuan's user avatar
30 votes
3 answers
3k views

Can there be an embedding j:V → L, from the set-theoretic universe V to the constructible universe L, when V ≠ L?

Main Question. Can there be an embedding $j:V\to L$ of the set-theoretic universe $V$ to the constructible universe $L$, if $V\neq L$? By embedding here, I mean merely a proper class isomorphism from $...
Joel David Hamkins's user avatar
28 votes
2 answers
7k 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 ...
algori's user avatar
  • 23.5k

1
2 3 4 5
23