All Questions
1,458 questions with no upvoted or accepted answers
5
votes
0
answers
231
views
Is there a transfinite version of Post's Theorem?
Let $\emptyset^{(n)}$ denote the $n$th Turing jump of the empty set. Post's theorem states:
A set $B$ is $\Sigma^0_{n+1}$ if and only if $B$ is recursively enumerable by an oracle Turing machine with ...
- 271
5
votes
0
answers
146
views
Do presheaf toposes satisfy the full fan theorem?
Presheaf toposes satisfy LPO and (edit: if over categories with binary products) PAx and countable choice internally, so they automatically satisfy the stable fan theorem (every bar which is the ...
- 1,947
5
votes
0
answers
484
views
How to study formal logic without formally using the notion of a set?
I have recently begun curious in set theory, and when I researched this subject I saw that all axiomatizations of set theory, such as ZFC and NBG, are expressed in the language of first order logic. ...
- 331
5
votes
0
answers
95
views
Entailment in one-point extensions of standard-enough models
This is one of two questions about the power of "one-point extensions" in reverse mathematics. This one focuses on what separations can be achieved as one-point extensions of as-closed-as-...
- 20.5k
5
votes
0
answers
193
views
Product of nice proper forcing notions
Question Are there forcing notions $P$ and $Q$ such that $P$ is proper and $\aleph_2$-cc, $Q$ is proper and satisfies the $\aleph_2$-pic (pic=properness isomorphism condition) such that $P \times Q$ ...
- 32.2k
5
votes
0
answers
109
views
Comparing Mathias forcing notions relative to various filters
Let $\mathcal F$ be a (non-principle, non trivial, ...) filter on $\omega$. The Mathias Forcing relative to $\mathcal F$ is the forcing notion $\mathbb M(\mathcal F)$ consisting of pairs $(s, X)$ with ...
- 1,882
5
votes
0
answers
165
views
Formal and informal proofs: Is there any "bilingual corpus"?
There are extensive libraries of formalized mathematics like those of Lean, Coq or Isabelle/HOL. What I am interested in is documents of formalized mathematics that closely follow certain informal ...
- 1,228
5
votes
0
answers
120
views
Is an equilateral triangle constructible in a Tarski plane?
By a Tarski space I understand a mathematical structure $(X,\mathsf B,\equiv)$ consisting of set $X$, a betweenness relation $\mathsf B\subseteq X^3$ and a congruence relation ${\equiv}\subseteq X^2\...
- 42k
5
votes
0
answers
653
views
Bourbaki-Witt in a textbook, other than in logic?
The Bourbaki-Witt theorem states that, in a chain-complete poset, the subset $X$ generated by an inflationary monotone function $s$ from the least element and joins of chains satisfies
$$ \forall x,y\...
- 8,481
5
votes
0
answers
120
views
Can the equational theory of commutative rings be "unpacked" from the equational theory of exponentiation?
Below, I'll use "$\approx$" for the equality symbol in an equation, as opposed to "actual" equality.
Suppose $\mathcal{V}$ is a variety (in the sense of universal algebra) in the ...
- 20.5k
5
votes
0
answers
146
views
$2^{|V|}$ class cardinalities without global choice
Is it consistent with Morse-Kelley set theory without global choice (but with choice for sets) that there are $2^{|V|}$ proper classes of different cardinalities?
Alternative question: Is it ...
- 7,545
5
votes
0
answers
193
views
"Very $L$-like" models, part 1: large cardinals
(The original version of this question was much narrower and less natural; but see the edit history if interested.)
Say that a good logic is a regular logic $\mathcal{L}$ containing $\mathsf{FOL}$ ...
- 20.5k
5
votes
0
answers
266
views
How strong is this "modal definability principle"?
Throughout, we work in the class theory $\mathsf{MK}$ (although I'm open to tweaking this), "logic" means "set-sized logic whose semantics is definable over $V$," and "$\...
- 20.5k
5
votes
0
answers
302
views
Reference for countable and uncountable algebraic closures of $\mathbb{Q}$ in ZF
The following facts seem to be part of the folklore (where $\mathsf{ZF}$ means Zermelo-Fraenkel set theory with no axiom of choice):
it is consistent with $\mathsf{ZF}$ that there exists an ...
- 32.5k
5
votes
0
answers
138
views
Can we define partial group actions on (finite) sets via generators and relators?
Let $G = \langle Y | R \rangle$ be a finitely presented group. A partial group action on a set $X$ is a premorphism into the inverse semigroup
$$
\mathcal I (X) = \{ f: A \to B : A, B \subseteq X, f\...
- 639
5
votes
0
answers
2k
views
What is the most "Icarus" Icarus set axiom?
We call a set $X ⊆ V_{λ+1}$ an Icarus set if there is an elementary embedding $j : L(X, V_{λ+1}) ≺ L(X, V_{λ+1})$ with $\mathrm{crit}(j)< λ$.
But this raises the question: What is the most "...
- 695
5
votes
0
answers
235
views
Surreal numbers and the ultrafilter lemma
In this question, I asked how to interpret a historical claim made by Conway regarding the potential, if not ideal, use of the surreal numbers for nonstandard analysis. In the comments and answers it ...
- 4,907
5
votes
0
answers
191
views
Consistency strength about Ramsey M-rank and Mahlo-Ramsey cardinal
In the website "Cantor's attic", there are a long list of large cardinal axioms arranged by consistency strength.
In the list, "α-Mahlo Ramsey" is placed higher than "Ramsey M-...
- 1,490
5
votes
0
answers
96
views
Negation-quantifier-negation blocks in nonclassical logic: reference request
I'm looking for references to discussion of a certain question in the literature on non-classical first-order logics. I suspect it must have been investigated thoroughly, but I can't seem to find ...
- 1,155
5
votes
0
answers
197
views
Weak compactness is to trees as [?] is to lattices?
Let $\kappa$ be an inaccessible cardinal. Recall that $\kappa$ is weakly compact if every tree of height $\kappa$ has either a level of size $\kappa$ or a branch of size $\kappa$.
So if $\kappa$ is a ...
- 64k
5
votes
0
answers
112
views
Equivalent formulation of linear logic with more axioms and less inference rules
We can formulate classical (sequent) logic with only the structural inference rules including cut, and a collection of axioms like $A, B \vdash A \wedge B$. This is equivalent to the usual sequent ...
- 1,262
5
votes
0
answers
318
views
$\Sigma_n$-complete sets in the Levy hierarchy
Recall that a set $A \subseteq \mathbb N$ is (many-one, Turing) $\Sigma_n$-complete if it's $\Sigma_n$ and any other $\Sigma_n$ set (many-one, Turing) reduces to it. This definition actually makes ...
- 1,882
5
votes
0
answers
157
views
Axiomatizability of image of functor
Let $\sigma$ and $\tau$ be first-order languages and let $S$ resp. $T$ be theories (sets of sentences) for $\sigma$ resp. for $\tau$ ($S$ and $T$ possibly empty).
Let $\mathcal C$ resp. $\mathcal D$ ...
- 365
5
votes
0
answers
231
views
Schröder and graphical logic?
I was actually surprised by a comment by John Baez over at the n-Category Cafe about his surprise that Ernst Schröder, a mathematician of whom he had known through Schröder's work on mathematical ...
- 10.5k
5
votes
0
answers
225
views
The forgetful functor from Groups to Semigroups
While teaching this term I found myself reminded of the fact that the "usual" definition of a group homomorphism is really the definition of a semigroup homomorphism, applied to semigroups ...
- 25.8k
5
votes
0
answers
124
views
Is there an NSOP theory with FFSOP?
After talking to a couple of people, I have been unable to determine whether this is even known.
Recall that a first-order theory $T$ has the strict order property or SOP if there is a formula $\...
- 13k
5
votes
0
answers
100
views
How many parameters are needed to define strongly minimal sets in $\aleph_0$-categorical, $\aleph_0$-stable theories?
There's a well-known result of Cherlin, Harrington, and Lachlan that gives a very precise structural understanding of $\aleph_0$-categorical, $\aleph_0$-stable theories. One thing in particular is ...
- 13k
5
votes
0
answers
231
views
Which very large cardinals are preserved under Woodin's forcing for $\mathsf{AC}$?
Woodin showed that we can force $\mathsf{AC}$ if there is a proper class of supercompact cardinals while preserving supercompacts, by forcing Easton-support iteration of $\operatorname{Col}(\kappa,<...
- 3,042
5
votes
0
answers
154
views
Is there a Hausdorff space whose "covering problem" has intermediate complexity?
For a "reasonable" pointclass ${\bf \Gamma}$, say that a second-countable space $(X,\tau)$ is ${\bf \Gamma}$-describable iff for some (equivalently, every) enumerated subbase $B=(B_i)_{i\in\...
- 20.5k
5
votes
0
answers
190
views
Can an infinite abelian $p$-group be tall and thin?
Does there exist an abelian $p$-group $A$ with countable Ulm invariants and uncountable height?
Here by height, I mean the minimal ordinal $\rho$ such that $p^\rho A$ is divisible [1]. For an ordinal ...
- 64k
5
votes
0
answers
107
views
Heuristics for the word problem for monoids
The question is about a purely practical problem:
Given is a list of identities, as in http://www.findstat.org/MapsDatabase/Mp00069:
...
- 5,822
5
votes
0
answers
246
views
Does $\mathsf{Q}$ have any interesting provably recursive functions?
This question was asked and bountied at MSE without success.
For an appropriate theory $T$, say that an $n$-ary $T$-provably recursive function is a $\Sigma_1$ formula $\varphi$ with $n+1$ free ...
- 20.5k
5
votes
0
answers
262
views
Higher order arithmetic, hierarchies and proof theoretic ordinals
I asked this question on MSE some days ago but I have not received any answer so I have decided to post it here.
I would like to consider a generalization of the notation $\Pi$ and $\Sigma$ used for ...
- 161
5
votes
0
answers
278
views
Class theory of ZF-minus-Powerset as classical predicative system?
I've been thinking about some mathematics in weaker foundational systems a little bit, largely from a structural viewpoint, and with particular attention to classes.
Some categories I've been keeping ...
- 35.5k
5
votes
0
answers
276
views
Absoluteness and the scale property for $Π^2_2$ or $Σ^2_2$
Under the diamond principle $◊$ and large cardinal axioms, which of the two pointclasses $Π^2_2$ or $Σ^2_2$ is expected to have the scale property?
Because conditional $Σ^2_2$ absoluteness under $◊$ ...
- 7,545
5
votes
0
answers
265
views
$Π_2$ strength of KP
I am looking for a characterization of the $Π_2$ statements provable in KP.
Here, KP (often denoted KPω) is the Kripke-Platek set theory, including infinity and full induction on ordinals. Here is ...
- 7,545
5
votes
0
answers
218
views
Improving a Lindstrom-y fact about $\mathcal{L}_{\omega_1,\omega}$?
See e.g. the last section of Ebbinghaus/Flum/Thomas for the relevant background on abstract model theory. Below, all languages are finite for simplicity. "$HC$" is the set of hereditarily ...
- 20.5k
5
votes
0
answers
170
views
How much choice is required for a countably-infinite index subgroup of the real additive group?
The existence of such subgroups implies the existence of a non-measurable set; simply intersect each of the cosets with $[0,1]$. The results will all have equal outer measure, but their union will be ...
- 1,252
5
votes
0
answers
261
views
Generic properties of dominating/etc. reals with non-Cohen working parts
The first and foremost forcing that adds a real is the Cohen forcing which approximates a new real number by giving finite approximations to its characteristics function.
But very quickly after that, ...
- 39.8k
5
votes
0
answers
246
views
Forcing absoluteness in the setting of second-order arithmetic
There are some results about (set-size) forcing absoluteness for first-order properties in $L(\mathbb{R})$ and for $\mathbf{\Pi}^1_{\infty}$ properties when one works over $\mathsf{ZFC}$. My question ...
- 5,831
5
votes
0
answers
196
views
A slight extension of Sacks theorem
Sacks proves the following theorem first.
Theorem 1: If $\alpha$ is a countable admissible ordinal, then there is a real $x$ so that $\omega_1^x=\alpha$.
Anyone knows who proves the following ...
- 4,201
5
votes
0
answers
156
views
Consistency of monochromatic uniformization at an inaccessible cardinal
Let $\kappa$ be an inaccessible cardinal, is the following uniformization principle at $\kappa$ consistent (is it consistent with GCH?): there exists a ladder system $\langle A_\alpha\subset \alpha: \...
- 1,006
5
votes
0
answers
266
views
Finite axiomatizability and $\mathrm{PA^{top}}$
Is $\mathrm{PA^{top}}$ finitely axiomatizable? If not, does it have a finitely axiomatizable extension (allowing new predicates but not new variable types) that has arbitrarily large finite models?
$\...
- 7,545
5
votes
0
answers
336
views
Ultrapower of a field is purely transcendental
Let $F$ be a field, $I$ a set, and $U$ an ultrafilter on $I$. Is the ultrapower $\prod_U F$ a purely transcendental field extension of $F$?
According to Chapter VII, Exercise 3.6 from Barnes, Mack "...
- 2,663
5
votes
0
answers
177
views
Definable modal logics in first-order structures
The old version didn't ask the right question and was also terribly written; see the edit history if interested. Also: throughout, formulas are allowed parameters, and when I say "definable subset of $...
- 20.5k
5
votes
0
answers
175
views
Continuous open self maps on Cantor space
A continuous self map on the Cantor space $C = \{0,1\}^\mathbb{N}$ is a mapping $f = (f_i)_{i\in \mathbb{N}}$ such that each $f_i$ is a map from $C$ to $\{0,1\}$ that depends only on a finite number ...
- 2,772
5
votes
0
answers
304
views
Symmetry between V and HOD
Is it consistent that the set of ordinal definable real numbers is countable, but for every $y∈\mathrm{OD}∩ℝ$, every true $Σ_2^{V,y}$ statement holds in $\mathrm{HOD}$?
Note that $Σ_2^V$ is the best ...
- 7,545
5
votes
0
answers
177
views
Decomposition of forcing iterations
One of the great things about a finite support iteration $\Bbb P_\delta$, is that if $\alpha<\delta$, we can write $\Bbb P_\delta$ as the iteration of $\Bbb{P_\alpha\ast\dot Q_\alpha\ast P_\delta/...
- 39.8k
5
votes
0
answers
253
views
Bad forcing permutations
Let $P$ be the finite-support product of the Cohen forcing. It adjoins a sequence of Cohen-generic reals say $a_n$, $n<\omega$, which one naturally calls a $P$-generic sequence. Suppose that $\pi$ ...
- 2,281
5
votes
0
answers
143
views
Self-additive posets
We say that a partially ordered set $(P,<)$ is self-additive if the two natural embeddings of $P$ in $P\oplus P$ (the linear sum of $P$ and itself) are elementary.
We have the following.
...
- 1,338