All Questions
1,460 questions with no upvoted or accepted answers
50
votes
0
answers
2k
views
How many algebraic closures can a field have?
Assuming the axiom of choice given a field $F$, there is an algebraic extension $\overline F$ of $F$ which is algebraically closed. Moreover, if $K$ is a different algebraic extension of $F$ which is ...
- 39.8k
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 ...
- 236k
33
votes
0
answers
2k
views
Is there a (discrete) monoid M injecting into its group completion G for which BM is not homotopy equivalent to BG?
For a (discrete) monoid $M$, the classifying space $BM$ is the
geometric realization of the nerve of the one object category whose
hom-set is $M$. (This definition gives the usual classfiying space
...
- 5,309
33
votes
0
answers
2k
views
Defining $\mathbb{Z}$ in $\mathbb{Q}$
It was proved by Poonen that $\mathbb{Z}$ is definable in the structure $(\mathbb{Q}, +, \cdot, 0, 1)$ using $\forall \exists$ formula. Koenigsmann has shown that $\mathbb{Z}$ is in fact definable by ...
user16974
32
votes
0
answers
2k
views
Peano Arithmetic and the Field of Rationals
In 1949 Julia Robinson showed the undecidability of the first order theory of the field of rationals by demonstrating that the set of natural numbers $\Bbb{N}$ is first order definable in $(\Bbb{Q}, +,...
- 17.7k
29
votes
0
answers
2k
views
Did Grothendieck overestimate topoi?
I was reading the Russian translation of Recoltes et Semailles and in the footnote where Grothendieck lists his 12 contributions (including schemes) we find the following lines:
Из этих тем ...
28
votes
0
answers
2k
views
Is Feferman's unlimited category theory dead?
In 2013 Solomon Feferman in Foundations of unlimited category theory: what remains to be done (The Review of Symbolic Logic, 6 (2013) pp 6-15, link) laid out three desirable axioms for "...
- 1,446
28
votes
0
answers
827
views
Can one divide by the cardinal of an amorphous set?
This question arose in a discussion with Peter Doyle.
It is provable in ZF that one can divide by any positive finite cardinal $k$: if $X \times \{1,\ldots,k\} \simeq Y \times \{1,\ldots,k\}$ then $X \...
- 44.4k
27
votes
0
answers
2k
views
Supercompact and Reinhardt cardinals without choice
A friend of mine and I ran into the following question while reading about proper forcing, and have been unable to resolve it:
Definition. A cardinal $\kappa$ is supercompact if for all ordinals $\...
- 20.9k
26
votes
0
answers
1k
views
Where do uncountable models collapse to?
Suppose $T$ is a complete first-order theory (in an finite, or at worst countable, language). Given any model $\mathcal{M}\models T$ of cardinality $\kappa$, we can ask whether $\mathcal{M}$ can be ...
- 20.9k
24
votes
0
answers
3k
views
What's the smallest $\lambda$-calculus term not known to have a normal form?
For Turing Machines, the question of halting behavior of small TMs has been well studied in the context of the Busy Beaver function, which maps n to the longest output or running time of any halting n ...
- 1,734
23
votes
0
answers
682
views
CH and automorphisms of ultrapowers of $\mathbb{Z}$ and $\mathbb{R}$
Notation and motivation. Given an algebraic structure $\mathbb{M}$ of cardinality at most the continuum and with countably many operations, and a nonprincipal ultrafilter $\cal{U}$ on a countably ...
- 17.7k
21
votes
0
answers
919
views
"Compactness for computability" - does it ever happen?
Throughout, "computable structure" means "first-order structure in a computable language with domain $\omega$ whose atomic diagram is computable."
Say that a computable structure $...
- 20.9k
21
votes
0
answers
578
views
Density of first-order definable sets in a directed union of finite groups
This is a generalization of the following question by John Wiltshire-Gordon.
Consider an inductive family of finite groups:
$$
G_0 \hookrightarrow G_1 \hookrightarrow \ldots \hookrightarrow G_i \...
- 2,200
20
votes
0
answers
408
views
Ado's theorem and the reduction to positive characteristic
The synopsis: proofs of Ado theorem in positive characteristic are simple, and in characteristic $0$ are difficult. Can one infer the characteristic $0$ case from the positive characteristic case?
The ...
- 2,934
20
votes
0
answers
407
views
Does the pointclass of universally Baire sets always have the uniformization property?
A set of reals, or binary relation on the reals, etc., is called universally Baire if and only if every continuous preimage of it in every topological space has the property of Baire. (There is also ...
- 5,471
19
votes
0
answers
563
views
What algebraic properties are preserved by $\mathbb{N}\leadsto\beta\mathbb{N}$?
Given a binary operation $\star$ on $\mathbb{N}$, we can naturally extend $\star$ to a semicontinuous operation $\widehat{\star}$ on the set $\beta\mathbb{N}$ of ultrafilters on $\mathbb{N}$ as ...
- 20.9k
19
votes
0
answers
905
views
What examples of existence forcing proofs are there?
Forcing proofs tend to be fairly constructive, in the sense that if I claim that there is a forcing that does something, I usually prove this by constructing that forcing.
There are only a handful of ...
- 39.8k
19
votes
0
answers
937
views
What is the Cantor-Bendixson rank of the space of first order theories?
Let $L$ be the language $\{R\}$ containing a single binary relation symbol. Consider the space $S_0(L)$ of complete, first-order $L$-theories. This is a seperable, compact Hausdorff space; what is its ...
- 2,146
19
votes
0
answers
590
views
Can Gentzen-style proofs give omega-consistency and beyond?
In 1936, Gentzen famously showed that Primitive Recursive Arithmetic, plus the assumption that the ordinal $\epsilon_0$ is well-founded, is able to prove Con(PA). But of course, Con(PA) doesn't yet ...
- 9,833
18
votes
0
answers
496
views
What is the logical complexity of the Hodge conjecture?
The Hodge conjecture seems to me the most mysterious among the Millennium problems
(and many others). In particular, I am not sure about its logical complexity. It is not difficult to see that the ...
- 6,891
18
votes
0
answers
855
views
Is this Variation of the Continuum Hypothesis Inconsistent with ZFC or ZF?
It is a well-known fact that the Generalized Continuum Hypothesis is undecidable from ZFC. For similar sentences $\phi$, this is simply equivalent to ZFC having a model $M$ for which $M\models\phi$.
...
- 1,252
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 ...
- 236k
17
votes
0
answers
540
views
Are there more true statements than false ones?
It is a nontrivial fact that half the primes are $\equiv 1 \pmod{4}$ and the other half are $\equiv 3\pmod{4}$. The Chebyshev bias suggests, however, that the latter class of primes is winning the ...
- 18.7k
17
votes
0
answers
368
views
Joyal's topos in which $[0,1]$ fails to be compact
Some time around 1977, André Joyal constructed a topos (actually a locale, i.e., a localic topos, necessarily non-spatial) in which the closed unit interval $[0,1]$ fails to be compact. There are ...
- 32.5k
17
votes
0
answers
1k
views
Non-rigid ultrapowers in $\mathsf{ZFC}$?
Originally asked and bountied at MSE:
Question: Can $\mathsf{ZFC}$ prove that for every countably infinite structure $\mathcal{A}$ in a countable language there is an ultrafilter $\mathcal{U}$ on $\...
- 20.9k
17
votes
0
answers
509
views
The free complete lattice on three generators, beyond ZF
This was originally asked at MSE; although it is still under bounty it seems unlikely to be answered there.
$\mathsf{ZF}$ proves that there is no free complete lattice on three generators since any ...
- 20.9k
17
votes
0
answers
558
views
Gitik's work on Shelah's weak hypothesis
It seems that Moti Gitik has recently refuted some variants of Shelah's weak hypothesis. For this see the title and abstract of his talk at the Set Theory, Model Theory and Applications conference.
I ...
- 32.1k
17
votes
0
answers
874
views
Ramsey's theorem for the first uncountable ordinal
Sierpiński proved that a version of Ramsey's theorem for colourings of pairs of countable ordinals fails miserably by comparing the ordering of $\omega_1$ with the linear ordering of (a subset of) the ...
- 11.3k
17
votes
0
answers
536
views
Question about combinatorics on words
Let $\{a_1,a_2,...,a_n\}$ be an alphabet and let $\{u_1,...,u_n\}$ be words in this alphabet, and $a_i\mapsto u_i$ be a substitution $\phi$.
Question: Is there an algorithm to check if for some $m,k$...
user6976
17
votes
0
answers
808
views
Decidability of $x^3+y^3+z^3 = c$
I wondering if it is known whether the following problem is algorithmically decidable or undecidable by Turing machines: given an integer c, determine if there are integers $(x,y,z)$ such that $x^3+y^...
- 171
17
votes
0
answers
674
views
The topos for forcing in computability theory
My understanding is that forcing (such as Cohen forcing) can be described via a topos. For example this nlab article on forcing describes forcing as a "the topos of sheaves on a suitable site."
My ...
- 6,287
17
votes
0
answers
908
views
Souslin trees and weakly compact cardinals
In Souslin trees on the first inaccessible cardinal it is asked if it is consistent that there are no $\kappa-$Souslin trees at the least inaccessible cardinal $\kappa$.
In this question I would like ...
- 32.1k
17
votes
0
answers
694
views
Antichains of Cardinals in ZF Without Choice...
With the Axiom of Choice, the cardinals form a nice linearly ordered "set". In the absence of the Axiom of Choice, the cardinals form a partially ordered "set". Broadly, I am wondering what ...
- 596
17
votes
1
answer
1k
views
How are the two natural ways to define “the category of models of a first-order theory $T$” related?
$\DeclareMathOperator\Mod{Mod}\DeclareMathOperator\Elem{Elem}$Background/Motivation: Inspired by an interesting question by Joel, I’ve been wondering about the relationship between two very natural ...
- 3,966
16
votes
0
answers
218
views
If a map between unital rings preserves multiplication and successor, does it preserve addition?
Welcome to my first MathOverflow posting!
This is a question about rings, all of them assumed to be both unital and associative.
Let $f\colon R\to S$ be a map between rings such that $f(xy)=f(x)f(y)$ ...
- 161
16
votes
0
answers
646
views
Consistency strength of $j:L_δ→L_δ$ for some δ
What is the consistency strength of existence of a nontrivial elementary embedding $j:L_δ→L_δ$ for some ordinal $δ$?
The consistency strength is strictly between totally ineffable and $ω$-Erdős ...
- 7,545
16
votes
0
answers
247
views
Gap two Sierpinski set?
Is it consistent to have a set of reals $X$ of size $\aleph_3$ such that for every $Y \subseteq X$, $Y$ has measure zero iff $|Y| \leq \aleph_1$?
- 9,631
16
votes
0
answers
772
views
Ideas behind Gitik's solution of PCF conjecture
Recently Moti Gitik has refuted Shelah's PCF conjecture (see Short extenders forcings II ) by proving the following theorem:
Theorem. Assuming the consistency of infinitely many strong cardinals, one ...
- 32.1k
16
votes
0
answers
373
views
What is the simplest known arithmetic definition of exponentiation?
For $n$ a natural number, let $E_n$ denote the set of bounded arithmetic formulas consisting of n alternating blocks of bounded quantifiers starting with an existential quantifier, followed by a ...
- 521
16
votes
0
answers
626
views
To what extent does (co)homology of groups made discrete depend on set theory?
There's a well-known paper by Milnor, "On the homology of Lie groups made discrete," that discusses the relation between the homology of a Lie group $G$ and the underlying discrete group $G^\delta$. ...
- 52.6k
16
votes
1
answer
2k
views
Axioms of Choice in constructive mathematics
There is a widely accepted opinion that the Axiom of Countable Choice (further, ACC)
$$ \forall n\in \mathbb{N} . \exists x \in X . \varphi [n, x] \implies \exists f: \mathbb{N} \longrightarrow X . \...
- 791
15
votes
0
answers
244
views
Natural examples of Borel surjections without right inverse
As discussed in this question, in general a Borel surjection $f:\mathbb{R}\rightarrow\mathbb{R}$ may not have a Borel right inverse, namely a $g$ such that $f\circ g=id$, although there is always a ...
- 623
15
votes
0
answers
1k
views
Condensed mathematics and independence results
I recently saw a paper on ``condensed mathematics'', in which I found the following quote interesting (see Condensed Mathematics: The internal Hom of condensed sets and condensed abelian groups and a ...
- 32.1k
15
votes
0
answers
587
views
Constructing a topos from a Heyting algebra
It is true that, given any topos $\mathcal{C}$ with a terminal object $1_\mathcal{C}$, $Sub(1_\mathcal{C})$ is a Heyting algebra.
Now suppose that we start with a Heyting algebra $H$. Is it always ...
- 171
15
votes
0
answers
425
views
Complexity classes for BSS machines
Given a first-order structure $\mathcal{S}$, a Blum-Shub-Smale machine on $\mathcal{S}$ is essentially a Turing machine where
Cells on the tape can hold arbitrary elements of $\mathcal{S}$.
The ...
- 20.9k
15
votes
0
answers
1k
views
Is the category of smooth manifolds equivalent to the opposite category of the category of commutative monoids of some additive symmetric monoidal category?
This is a followup to my previous question, which asked whether
the category of commutative or noncommutative C*-algebras or von Neumann algebras
is equivalent to the category of commutative or ...
- 37.8k
15
votes
0
answers
741
views
Minimal resources for Undecidability of First-Order Logic: the number of variables
It is well-known that First-Order Logic (FO) with a full vocabulary (i.e., a countable numbers of unary predicate symbols, a countable number of binary predicate symbols, etc.) is undecidable. And it ...
- 768
15
votes
1
answer
794
views
Are there any natural theories T for which P=NP implies T proves P=NP?
The qualifier "natural" is meant to exclude examples like "PA + P=NP" or "PA + True $\Pi_1$".
For concreteness, let's say that "natural" = sound, computably enumerable, with a feasible proof-checker.
...
- 333
14
votes
0
answers
390
views
Can the axiom of choice be expressed in 4 quantifiers?
This 2007 paper presents a 5-quantifier $(\in, =)$-expression that is ZF-equivalent to the axiom of choice, but leaves open the 4-quantifier case:
Thus the gap is reduced to the undecided case of a 4 ...
- 2,203