All Questions
1,460 questions with no upvoted or accepted answers
12
votes
0
answers
721
views
Diagonal lemma from recursion theorem?
Does Gödel's diagonal lemma follow from Kleene's recursion theorem? I believe the converse is true, by an argument like the following.
Let e ↦ θe be a bijection between ω and ...
- 1,081
11
votes
0
answers
237
views
+50
Is there a decidable theory of arithmetic with a non-collapsing quantifier hierarchy?
This question is very close to this old MSE question of mine, which is still unanswered.
Is there an (ideally reasonably-natural!) expansion of the structure $(\mathbb{N};+)$ in a finite language ...
- 20.5k
11
votes
0
answers
427
views
Is there a theory of completions of semirings similar to $I$-adic completions of rings?
Let $L = \text{Con } (\mathbb{N}, 0, +) \setminus \Delta$ be the lattice of monoid congruences on the naturals, excluding the trivial congruence. As it happens, every $\theta \in L$ is the meet of ...
- 631
11
votes
0
answers
430
views
Is $(\mathbb{R}, +)$ still injective as long as $(\mathbb{Q},+)$ is?
It is known that the existence of nontrivial injective abelian groups is independent of choice in ZF (or, rather, ZFA). In particular, $\mathbb{Q}$ is not provably injective, much less $\mathbb{R}$, ...
- 433
11
votes
0
answers
374
views
A game of harmonic series(s)
Given a set $A\subseteq\mathbb{R}_{>0}$, consider the following (two-player, perfect-information, length-$\omega$) game $H_A$:
Players $1$ and $2$ alternately play strictly increasing natural ...
- 20.5k
11
votes
0
answers
476
views
Which sentences are "irreducibly" self-referential over $\mathsf{PA}$?
Previously asked at MSE. Below, all sentences/formulas are in the language of arithmetic, and for simplicity we conflate numbers with numerals and sentences with Godel numbers.
Say that a sentence $\...
- 20.5k
11
votes
0
answers
300
views
Is ZF + "all sets of reals have the Ramsey property" + "there is a set without the Baire property" consistent?
A question which was mentioned in passing by Larson when discussing geometric set theory.
Are there models of set theory where all sets of reals have the Ramsey property but there is a set of reals ...
- 149
11
votes
0
answers
426
views
Theories of truth
Not knowing much about logic, I thought that in mathematics saying that a (closed) sentence $\varphi$ in a (formal) theory $T$ is "true" amounted to one of the following notions:
Syntactic ...
- 23.3k
11
votes
0
answers
314
views
Can we bound $2^{\aleph_\omega}$ without pcf theory?
One of the famous applications of pcf theory is that if $\aleph_\omega$ is a strong limit cardinal then $2^{\aleph_\omega}<\aleph_{\omega_4}$. I'm curious whether any weaker result with the same ...
- 20.5k
11
votes
0
answers
286
views
Does every finite poset have a rigid endomorphism?
Crossposted on Mathematics.
In this post, an order-preserving self-map of a poset $X$ will be called an endomorphism of $X$, and such an endomorphism $f$ will be called rigid if the only automorphism ...
- 4,416
11
votes
0
answers
266
views
Quantifier swap in Banach space theory
The uniform boundedness principle and its corollaries from a logical point of view are statements of when one can swap quantifiers in Banach spaces. Take for instance the principle of condensation of ...
- 301
11
votes
0
answers
623
views
Does Merkurjev's argument help Voevodsky's program?
In the talk
Unimath - its present and its future, July 10, 2017. Video and slides of a talk, Isaac Newton Institute for Mathematical Sciences, Cambridge. (abstract)
Voevodsky mentioned that he was ...
- 35.5k
11
votes
0
answers
564
views
Isomorphic free groups have bijective generating sets
Let $F(X)$ be the free group on a set $X$. Classically, we can prove the statement:
$F(X) \cong F(Y)$ if and only if $|X|=|Y|$.
The proofs (that I have seen) consist of turning the group ...
- 1,185
11
votes
0
answers
272
views
Preservation of chain condition under strategically closed forcing
It is well-known that $\kappa$-closed forcing preserves $\kappa$-c.c. posets. The same argument works for $\kappa$-strategically closed forcing. Here is the definition:
A poset $\mathbb P$ is $\...
- 18.6k
11
votes
0
answers
214
views
Is it decidable if a tree-presented semigroup contains an idempotent?
A semigroup presentation $\langle A | R\rangle$ is called tree-like if every relation has the form $ab=c$, $a,b,c$ are in $A$ and if two relations $ab=c, a'b'=c'$ belong to $R$, then $c=c'$ if and ...
user6976
11
votes
0
answers
438
views
Example of $\aleph_1$-categorical linear order
Is it possible to have an $L_{\omega_1,\omega}$-sentence $\phi$ in a vocabulary that includes $<$ that satisfies the following?
$<$ is a linear order on a definable subset;
$\phi$ is $\aleph_1$-...
- 2,882
11
votes
0
answers
442
views
c.c.c forcing notions and adding minimal generic reals
Is the following statement consistent:
``There is no non-trivial c.c.c forcing notion adding a minimal generic real''?
The question is related to Prikry's question: Is it consistent that any non-...
- 32.2k
11
votes
0
answers
514
views
Do all linear orders in this class have computable copies?
This is a question which has been bothering me now for quite some time. I've talked to a number of people about it, and we've shown that a few basic ideas can't work, but other than that haven't made ...
- 20.5k
11
votes
0
answers
223
views
Savings property: A transformation which turns nonnegative martingales into uniformly integrable ones
Background
I work in a subfield of computability theory called algorithmic randomness. We have been using martingales as long as probability theory (going back to work of von Mises). However, since ...
- 6,287
11
votes
0
answers
516
views
Using Lindstrom's theorem to prove Craig interpolation
[EDIT: The theorem I call "Beth definability" below is apparently not generally called that (wikipedia notwithstanding; see https://math.stackexchange.com/questions/288450/two-forms-of-beths-theorem). ...
- 20.5k
11
votes
0
answers
556
views
Various definitions of recursion from ordinal machines
Background: I'm trying to get an intuitive understanding of α-recursion and related concepts in higher recursion theory. Once nice book is Peter Hinman's Recursion-Theoretic Hierarchies, available ...
11
votes
0
answers
1k
views
Reverse mathematics strength of identically zero polynomials are the zero polynomial
According to wikipedia, the statement "every polynomial over a countable field that is not the zero polynomial has only finitely many roots" is equivalent to RCA0 over RCA0* (which is called ERCA-0 in ...
user5810
11
votes
0
answers
305
views
What are the logical morphisms from a topos E to Set?
If $E$ is a topos, is there a nice way to characterize the category of logical morphisms $E\to Set$? Is it complete and/or cocomplete?
The topos $Set$ geometrically represents a point; what does it ...
- 8,659
10
votes
0
answers
204
views
4-quantifier formula not decided by ZF
This interesting question asks the minimum number of quantifiers required to state the Axiom of Choice, and recalls that any sentence having three or fewer quantifiers is already decided by ZF. This ...
- 1,124
10
votes
0
answers
274
views
Open problems in complete theories
It is well-known that every complete recursively enumerable first-order theory is decidable. Does that mean that such theories are "trivial", or are there still interesting open problems ...
user507115
10
votes
0
answers
159
views
Closed sets versus closed sublocales in general topology in constructive math
This question is set in constructive mathematics (without Choice), such as in the internal logic of a topos with natural numbers object, or in IZF.
Short version of the question: if $X$ is a sober ...
- 32.5k
10
votes
0
answers
181
views
"Effective gaps" in the c.e. degrees
Below, $W_e$ is the $e$th c.e. set according to some appropriate list of such.
In a very loose analogy with Hausdorff gaps, say that an effective gap is a pair of computable sequences $(c_i)_{i\in\...
- 20.5k
10
votes
0
answers
248
views
What is the tiling semigroup for an einstein "hat" tiling?
My undergraduate dissertation was on inverse semigroups and the key text I used for it was Lawson's, "Inverse Semigroups: The Theory of Partial Symmetries". In said book, Lawson describes ...
- 379
10
votes
0
answers
323
views
Determinacy coincidence at $\omega_1$: is CH needed?
This is a follow-up to the last part of an old MSE answer of mine. Briefly, an analogue at $\omega_1$ of Steel's equivalence between clopen and open determinacy can be proved assuming $\mathsf{CH}$, ...
- 20.5k
10
votes
0
answers
366
views
Feferman's universes for proof assistants?
This question was prompted by a discussion from another MO question about the consistency of ZFC. There are some mathematicians who are comfortable with ZFC but uneasy with large cardinals. For them,...
- 82.7k
10
votes
0
answers
168
views
How nice can sets of reals be under $\mathsf{ZF} + \mathsf{BPI}$?
It's well known that the full axiom of choice is not needed to prove the existence of non-measurable subsets of $\mathbb{R}$. In particular, the Boolean prime ideal theorem ($\mathsf{BPI}$) is ...
- 12.5k
10
votes
0
answers
374
views
+400
Extending models of topological set theory
$\mathsf{GPK_\infty^+}$ is an alternative set theory in which we have comprehension for formulas which are positive in a certain sense; see the SEP article for more detail (or this MO post, which ...
- 20.5k
10
votes
0
answers
283
views
Martin's Maximum implies stationary/club Chang's conjecture?
Chang's Conjecture (CC) states: for any $f: [\omega_2]^{<\omega} \to \omega_1$, there exists a set $X\subset \omega_2$ of order type $\omega_1$ such that $|f''[X]^{<\omega}|\leq \aleph_0$.
...
- 3,038
10
votes
0
answers
334
views
Definability up to isomorphism versus definability of an isomorphic copy
Question: Is it provable in ZFC that every structure that is ordinal definable up to isomorphism has an ordinal definable isomorphic copy? If not, what are some counterexamples? All structures are ...
- 7,545
10
votes
0
answers
283
views
How does a theory give rise to a category with finite products?
In the paper Diagonal Arguments and Cartesian Closed Categories (here), Lawvere presents a fixed-point theorem that generalizes both Cantor's theorem and Gödel's (first) Incompleteness Theorem.
In ...
- 489
10
votes
0
answers
333
views
What kind of objects can code a universe?
Jensen proved that given $V\models\sf ZFC+GCH$, there is a class generic real $r$, such that $V[r]=L[r]$, and no cardinals are collapsed.
We know that this can be modified such that $r$ is minimal, i....
- 39.8k
10
votes
0
answers
205
views
Connection between second-order arithmetic and Hilbert-Bernays' Grundlagen
What is the exact (historical) connection between second-order arithmetic and Hilbert-Bernays' Grundlagen der Mathematik?
Some background: the literature on Reverse Mathematics contains a number of ...
- 4,359
10
votes
0
answers
169
views
Isomorphisms mod nonstationary
Suppose $G \subseteq \mathrm{Add}(\omega_1)$ is generic over $V$. Let $X_i = \{ \alpha : G(\alpha) = i \}$. Is it true that $P(X_0)/\mathrm{NS} \cong P(X_1)/\mathrm{NS}$?
- 18.6k
10
votes
0
answers
288
views
How wealthy are canonical inner models?
One of the way a person shows their wealth is by having many diamonds. The same can be said about models of $\sf ZFC$. We can add generic diamond sequences, while preserving the old ones, so in some ...
- 39.8k
10
votes
0
answers
293
views
Undetermined Banach-Mazur games: beyond DC
This question is a follow-up to this one; see that question for the definition of Banach-Mazur games. There James Hanson showed that ZF+DC proves that there is an undetermined Banach-Mazur game; ...
- 20.5k
10
votes
0
answers
416
views
Equational theory in the signature (+,*,0,1) of sedenions and beyond
Consider a Cayley-Dickson algebra $(X,+,∗,0,1)$, that is an algebra generated from the reals by the Cayley-Dickson construction. From complexes to quaternions, we lose commutativity of multiplication, ...
- 2,023
10
votes
0
answers
509
views
Sunflower / $\Delta$-system lemma in a more general poset?
The sunflower lemma (or $\Delta$-system lemma) may be viewed as a statement about the poset $P_\omega(\omega_1)$, and the generalized sunflower lemma may be viewed as a statement about the poset $P_\...
- 64k
10
votes
0
answers
356
views
Connection between Provability Logic (GL) and geometry?
In Provability Logic (aka GL) we have
The Beth definability theorem and
De Jong-Sambin Fixed Point Theorem
The former has a vague similarity to the implicit function theorem in that you can loosely ...
- 8,271
10
votes
0
answers
377
views
Model for "$\kappa$ limit cardinal iff $2^\kappa$ limit cardinal"
Is there a model of ${\sf (ZFC)}$ such that in the model we have that $\kappa$ is a limit cardinal if and only if $2^\kappa$ is a limit cardinal?
- 48.9k
10
votes
0
answers
561
views
stationary reflection in $[\kappa]^\omega$
It is well-known that the following reflection principle is consistent relative to a supercompact:
For all $\kappa \geq \omega_2$ and all stationary $S \subseteq [\kappa]^\omega$, there is $X \...
- 18.6k
10
votes
0
answers
236
views
Is there an expansion of $(\mathbb{N},+,<)$ by a pairing function that is still NIP?
I was told once that there is a theory consisting of just a pairing function that is stable, although I cannot find a reference for it. This motivated my question, which is essentially the title, ...
- 12.5k
10
votes
0
answers
438
views
On the Number of Parallel Automorphism Lines
Given a group $G$, one can define the transfinite line of iterative automorphisms of $G$ to be the following chain of the groups where $G_{\alpha+1}=Aut(G_{\alpha})$ for each ordinal $\alpha$ and the ...
10
votes
0
answers
367
views
A formula for Frobenius number of certain numerical semigroups
The old formula for the Frobenius number of a numerical semigroup generated by two elements can be stated as follows: assume $\gcd\{a+1,b+1\}=1$, then the Frobenius number of $S= \left<a+1,b+1\...
- 30.5k
10
votes
0
answers
635
views
Is the Banach game quantifier "intractable"? (Becker's guess)
(This is a revised version of the original question. Below I work in $\mathsf{ZF+DC+AD}$, but I would be happy to add further axioms if appropriate: $\mathsf{ZF+DC+AD_\mathbb{R}}$, for example, seems ...
- 20.5k
10
votes
0
answers
276
views
Strongly compact vs Shelah cardinals
Does Con(ZFC+there exists a strongly compact cardinal) imply the Con(ZFC+there exists a Shelah cardinal)?
- 32.2k