All Questions
6,026 questions
44
votes
2
answers
4k
views
Is multiplication implicitly definable from successor?
A relation $R$ is implicitly definable in a structure $M$ if there is a formula $\varphi(\dot R)$ in the first-order language of $M$ expanded to include relation $R$, such that $M\models\varphi(\dot R)...
- 236k
44
votes
5
answers
5k
views
Several Topos theory questions
Hey. I have a few off the wall questions about topos theory and algebraic geometry.
Do the following few sentences make sense?
Every scheme X is pinned down by its Hom functor Hom(-,X) by the ...
- 12.1k
44
votes
3
answers
5k
views
"Simpler" statements equivalent to Con(PA) or Con(ZFC)?
Given any reasonable formal system F (e.g., Peano Arithmetic or ZFC), we all know that one can construct a Turing machine that runs forever iff F is consistent, by enumerating the theorems of F and ...
- 9,833
43
votes
16
answers
9k
views
Essential reads in the philosophy of mathematics and set theory
I am graduate student and have a decent understanding of logic and set theory.
Recently I have got interested in the philosophy of mathematics and set theory. I have read a number of papers by ...
43
votes
6
answers
5k
views
Hilbert's (cancelled) 24th problem
Hilbert's 23 problems, ten of which were presented at the 1900 ICM in Paris, are too famous for any mathematician to not know. If one reads the descriptions of the problems in Hilbert's paper, one ...
- 4,265
43
votes
2
answers
3k
views
Do vector spaces without choice satisfy Cantor-Schroeder-Bernstein?
If $V \hookrightarrow W$ and $W \hookrightarrow V$ are injective linear maps, then is there an isomorphism $V \cong W$?
If we assume the axiom of choice, the answer is yes: use the fact that every ...
- 64k
43
votes
9
answers
5k
views
The sets in mathematical logic
It is well known that intuitive set theory (or naive set theory) is characterized by having paradoxes, e.g. Russell's paradox, Cantor's paradox, etc. To avoid these and any other discovered or ...
- 764
43
votes
4
answers
5k
views
Lists as a foundation of mathematics
I am wondering if there is a foundation of mathematics where not sets or "set-like objects" (such as objects of a suitable topos as in ETCS) are the primitive notion, but rather lists. These ...
- 63.1k
43
votes
1
answer
2k
views
Do the analogies between metamathematics of set theory and arithmetic have some deeper meaning?
By "formal analogies" between the metamathematics of $\mathsf{ZFC}$/set theory and $\mathsf{PA}$(=Peano Arithmetic)/first order arithmetic, I mean facts such as the following:
We are considering a ...
- 32.5k
42
votes
7
answers
3k
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 ...
- 29k
42
votes
5
answers
4k
views
What are the main structure theorems on finitely generated commutative monoids?
I should read J. C. Rosales and P. A. García-Sánchez's book Finitely Generated Commutative Monoids and L. Redei's book The Theory of Finitely Generated Commutative Semigroups. I haven't. But here's ...
- 22.3k
42
votes
1
answer
4k
views
Mathematicians wearing hats on arbitrary total orders
I've been pondering the following generalisation of a famous problem (the special case where $T = \mathbb{N})$:
Question: We have some totally-ordered set $T$ of mathematicians, each wearing a hat ...
- 12.4k
42
votes
4
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 ...
- 3,475
42
votes
2
answers
6k
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 ...
- 6,215
41
votes
6
answers
13k
views
Can we prove set theory is consistent?
Disclaimer
Of course not, I'm aware of Gödel's second incompleteness theorem. Still there is something which does not persuade me, maybe it's just that I've taken my logic class too long ago. On the ...
- 14.7k
41
votes
3
answers
2k
views
What is the minimal size of a partial order that is universal for all partial orders of size n?
A partial order $\mathbb{B}$ is universal for a class $\cal{P}$ of partial orders if every order in $\cal{P}$ embeds
order-preservingly into $\mathbb{B}$.
For example, every partial order
$\langle\...
- 236k
41
votes
4
answers
2k
views
What is the probability two random maps on n symbols commute?
It is well known that two randomly chosen permutations of $n$ symbols commute with probability $p_n/n!$ where $p_n$ is the number of partitions of $n$. This is a special case of the fact that in a ...
- 38.6k
41
votes
2
answers
2k
views
On the difference between two concepts of even cardinalities: Is there a model of ZF set theory in which every infinite set can be split into pairs, but not every infinite set can be cut in half?
An interesting question has arisen over at this
math.stackexchange
question
about two concepts of even in the context of infinite
cardinalities, which are equivalent under the axiom of
choice, but ...
- 236k
40
votes
7
answers
8k
views
What is the general opinion on the Generalized Continuum Hypothesis?
I'm community wikiing this, since although I don't want it to be a discussion thread, I don't think that there is really a right answer to this.
From what I've seen, model theorists and logicians ...
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 ...
40
votes
3
answers
5k
views
How much of mathematical General Relativity depends on the Axiom of Choice?
One of the cornerstones of the mathematical formulation of General Relativity (GR) is the result (due to Choquet-Bruhat and others) that the initial value problem for the Einstein field equations is ...
- 655
40
votes
2
answers
3k
views
Ultrafilters as a double dual
Given a set $X$, let $\beta X$ denote the set of ultrafilters. The following theorems are known:
$X$ canonically embeds into $\beta X$ (by taking principal ultrafilters);
If $X$ is finite, then there ...
- 12.4k
40
votes
2
answers
4k
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 ...
- 9,833
40
votes
1
answer
2k
views
Rigid non-archimedean real closed fields
Update. The question has been recently answered in the positive by David Marker and Charles Steinhorn (as in indicated in Marker's answer). Note that Remark 3 below is now expanded by reference to a ...
- 17.7k
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 ...
- 1,131
39
votes
6
answers
7k
views
Why can't proofs have infinitely many steps?
I recently saw the proof of the finite axiom of choice from the ZF axioms. The basic idea of the proof is as follows (I'll cover the case where we're choosing from three sets, but the general idea is ...
- 15.4k
39
votes
10
answers
4k
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 ...
39
votes
8
answers
6k
views
Learning roadmap for Foundations of Mathematics (for the working mathematician)
(At the risk of being vapulated and downvoted, I'll ask this here.)
Suppose you work in a field that has nothing to do with the foundations of mathematics, but thanks to MO, you are becoming more and ...
39
votes
4
answers
6k
views
On critical reviews of Hawking's lecture "Gödel and the end of the universe"
The search for a neat Theory of Everything (ToE) which unifies the entire set of fundamental forces of the universe (as well as the rules which govern dark energy, dark matter and anti-matter realms) ...
39
votes
5
answers
4k
views
A “mother of all groups”? What kind of structures have "mother of all"s?
For ordered fields, we have a “mother of all ordered fields”, the surreal numbers $\mathbf{No}$, a proper-class “field” which includes (an isomorphic copy of) every other ordered field as a subfield. ...
- 1,687
39
votes
5
answers
8k
views
Is there a constructive proof of Cantor–Bernstein–Schroeder theorem ?
An important feature of the Cantor-Schroeder-Bernstein theorem is that it does not rely on the axiom of choice. However, its various proofs are non-constructive, as they depend on the law of excluded ...
- 775
39
votes
7
answers
6k
views
Is V, the Universe of Sets, a fixed object?
When I first read Set Theory by Jech, I came under the impression that the Universe of Sets, $V$ was a fixed, well defined object like $\pi$ or the Klein four group. However as I have read on, I am ...
- 750
39
votes
3
answers
3k
views
Can one show that the real field is not interpretable in the complex field without the axiom of choice?
We all know that the complex field structure $\langle\mathbb{C},+,\cdot,0,1\rangle$ is interpretable in the real field $\langle\mathbb{R},+,\cdot,0,1\rangle$, by encoding $a+bi$ with the real-number ...
- 236k
39
votes
4
answers
6k
views
Completion of a category
For a poset $P$ there exists an embedding $y$ into a complete and cocomplet poset $\hat{P}$ of downward closed subsets of $P$. It is easy to verify that the embedding preserves all existing limits and ...
- 4,096
39
votes
8
answers
14k
views
Good introductory book to type theory?
I don't know anything about type theory and I would like to learn it.
I'm interested to know how we can found mathematics on it.
So, I would be interested by any text about type theory whose angle ...
39
votes
2
answers
5k
views
Why is this new result such a big deal?
This popular article reports a recent result in reverse mathematics, showing that a certain theorem in Ramsey theory is provable from RCA$_0$, the base theory in SOSOA. Then there are a bunch of ...
- 391
39
votes
3
answers
5k
views
For which Millennium Problems does undecidable -> true?
Three good answers were received — by Alex Gavrilov, Bjørn Kjos-Hanssen, and Terry Tao — and the bounty has been awarded (somewhat arbitrarily) to Alex Gavrilov.
The answers ...
39
votes
4
answers
4k
views
The symmetric group theory of natural numbers
Sometimes it is not easy to formulate a correct question. Here is a better version of this question (I still do not know if it is optimal, but it is better than the previous one).
We say that a set $...
user6976
39
votes
3
answers
3k
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 ...
38
votes
4
answers
4k
views
Illustrating Edward Nelson's Worldview with Nonstandard Models of Arithmetic
Mathematician Edward Nelson is known for his extreme views on the foundations of mathematics, variously described as "ultrafintism" or "strict finitism" (Nelson's preferred term), which came into the ...
- 4,597
38
votes
5
answers
5k
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 ...
- 53.3k
38
votes
4
answers
6k
views
Could groups be used instead of sets as a foundation of mathematics?
Sets are the only fundamental objects in the theory $\sf ZFC$. But we can use $\sf ZFC$ as a foundation for all of mathematics by encoding the various other objects we care about in terms of sets. The ...
- 3,137
38
votes
6
answers
3k
views
What are the advantages of the more abstract approaches to nonstandard analysis?
This question does not concern the comparative merits of standard (SA) and nonstandard (NSA) analysis but rather a comparison of different approaches to NSA. What are the concrete advantages of the ...
- 16.6k
38
votes
4
answers
2k
views
On sentences true in all finite groups
Let $w$ be a group word with two variables $x$ and $y$.
Is the sentence $(\forall x)(\exists y)w=1$
true in every group if it is true
in every finite group?
The same question about the sentence $(\...
- 893
38
votes
4
answers
3k
views
Is there research on human-oriented theorem proving?
I know there is already a research community that is working on automatic theorem proving mostly using logic (and things like Coq and ACL2). However, I came across a lecture from a fields medalist W.T....
- 524
38
votes
1
answer
3k
views
Is the area of the Mandelbrot provably computable?
Recall the Mandelbrot set $M$ is the set of points $c$ in the complex plane such that the sequence $z_0 = 0, z_{n+1} = z_n^2 + c$ is bounded. It is well-known that $M$ is a compact set of positive ...
- 6,287
37
votes
4
answers
2k
views
Is the field of constructible numbers known to be decidable?
By the field of constructible numbers I mean the union of all finite towers of real quadratic extensions beginning with $\mathbb{Q}$. By decidable I mean the set of first order truths in this field, ...
- 11.1k
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 \...
- 35.5k
37
votes
6
answers
5k
views
What do we gain with higher order logics?
Gödel's speed up theorems seem to say that higher order logics offer shorter shortest proofs of various propositions in number theory. Explicitly, he gave the following
Theorem.
Let $n>0$ be ...
- 10.1k
37
votes
7
answers
8k
views
Model theoretic applications to algebra and number theory(Iwasawa Theory)
One of my favorite results in algebraic geometry is a classical result of AX (see http://terrytao.wordpress.com/2009/03/07/infinite-fields-finite-fields-and-the-ax-grothendieck-theorem/) I'll recall ...
- 2,396