All Questions
6,026 questions
0
votes
1
answer
60
views
Is there a characterization of monoids that distribute over each other?
Let $(M, e_1, \times_1, e_2, \times_2)$ be an algebraic structure such that
$(M, e_1, \times_1)$ and $(M, e_2, \times_2)$ are monoids
$x \times_1 (y \times_2 z) = (x \times_1 y) \times_2 (x \times_1 ...
- 631
1
vote
0
answers
50
views
Construction of the smallest nucleus above a prenucleus: what does this proof tell us?
While reading Hyland's paper on the effective topos [retyped version here] in the L. E. J. Brouwer Centenary Symposium, specifically prop. 16.3, I realized that the following proposition is implicit:
...
- 32.5k
0
votes
0
answers
104
views
How near are a groupoid and its 'preorderification'?
As remarks, a groupoid is a category with only (categorical) isomorphisms as its morphisms and a preorder is a category only having one morphism between each object. If we choose one isomorphism by ...
4
votes
0
answers
147
views
Are the natural powers of two conservatively embedded in $\mathbb{C}$?
This is a followup to this question.
Consider $\mathbb{C}$ as a structure - in the sense of first-order logic - with the graphs of addition and multiplication. Let $\mathcal{X}$ be the substructure ...
- 20.5k
2
votes
0
answers
63
views
Consistency of Sigma-V-2 uniformization with AD
Is ZF + AD consistent with: For every real $r$, every true $Σ^V_2(r)$ statement has a $Δ^V_2(r)$ example?
DC is provable in ZF + every true $Σ^V_2$ statement has a $Δ^V_2$ example (i.e. witness). ...
- 7,545
3
votes
0
answers
52
views
Does there exist a multi-valued "monotone" and "compact" map from a Boolean algebra to the "free" part of $\mathcal{P}(\kappa)$?
This is a follow-up to my previous question, which has a negative answer. Here is the most general version that I'm interested:
Does there exist a Boolean algebra $A$, an infinite cardinal $\kappa$, ...
- 2,830
3
votes
1
answer
173
views
Can one say that there are equal numbers of sets satisfying formulas in Second Order Arithmetic?
Is there a way of saying in second order arithmetic that the number of sets $X$ such that $\phi$ equals the number of sets $X$ such that $\psi$, where $\phi$ and $\psi$ are formulas with $X$ free, and ...
- 2,555
5
votes
1
answer
149
views
Does there exist a section of $\mathcal{P}(\kappa)\to\mathcal{P}(\kappa)/(\text{fin})$ that is "nearly Boolean"?
The following might be a somewhat esoteric question:
Does there exist an infinite cardinal $\kappa$ and a section $f$ of the quotient map $\pi:\mathcal{P}(\kappa)\to\mathcal{P}(\kappa)/(\text{fin})$ (...
- 2,830
8
votes
0
answers
201
views
Can $\mathbb{C}$ have a "doppelganger" in $L(\mathbb{R})$ with countable automorphism group?
Working in $\mathsf{ZFC}$ + large cardinals (a proper class of Woodins, to be precise), is there a field $F\in L(\mathbb{R})$ such that $V\models F\cong\mathbb{C}$ and $L(\mathbb{R})\models\vert\...
- 20.5k
7
votes
0
answers
126
views
On the optimal strength of Goodstein's theorem
Goodstein's theorem is a famous example of an arithmetical statement that is unprovable in $\mathsf{PA}$ but provable in a stronger theory. It is well-known that Goodstein's theorem implies the ...
- 3,042
17
votes
1
answer
1k
views
Are integers conservatively embedded in the field of complex numbers?
I am looking for a reference to the fact that $\mathbb{Z}$ is conservatively embedded into the field $\mathbb{C}$ of complex numbers, that is anything in $\mathbb{Z}$ which is definable in $(\mathbb{C}...
- 301
3
votes
1
answer
102
views
Morphisms of the additive group of a field of finite Morley rank
It is well-known that a definable field of finite Morley rank has no proper definable group of automorphisms (a proof can be found for example in the book "Stable groups" of Poizat). My ...
1
vote
0
answers
81
views
How strong is separation + reflection without transitivity?
Consider a theory $T$ with a binary relation $\in$ and the following axiom schemas:
$\exists u \forall x (x \in u \leftrightarrow x \in a \land \phi)$ where $u$ is not free in $\phi$. This is the ...
- 2,203
1
vote
0
answers
99
views
Is this theory synonymous with ZF + Global Choice?
$\textbf{Logic:}$ Mono-sorted first order logic with equality.
$\textbf{Extralogical Primitives: } <, \in$
Define: $x > y \iff y < x \\ x \leq y \iff x < y \lor x=y \\ x \not > y \iff \...
- 11.3k
9
votes
2
answers
385
views
Iteration of $\aleph_2$-properness
Let us say a forcing $P$ is proper for a class of models $\mathcal C$, if for large enough regular $\theta$ and $M \prec H_\theta$ in $\mathcal C$ with $P \in M$, every $p \in P \cap M$ can be ...
- 18.6k
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
15
votes
1
answer
811
views
Are key theorems finitistically reducible?
Simpson writes on page 378 of his Subsystems of Second Order
Arithmetic:
"For example, all of the following key theorems of infinitistic
mathematics are provable in WKL$_0$ and therefore, by ...
- 16.6k
6
votes
1
answer
229
views
Can one define second-order equinumerosity in MSO via first-order cardinality quantifiers?
Let $L$ be MSO (Monadic Second Order Logic) extended with an $n$-ary second-order cardinality predicate (i.e., a first-order cardinality quantifier) $C_R$ for every $n$-ary relation $R$ on the ...
- 2,555
2
votes
0
answers
84
views
Is it a property when a cohesive type is a manifold?
Let $X : Type$ in a type theory $T$ interpreting synthetic differential geometry - I don't believe it should matter too much if we have smooth stuff on hand except maybe at the end of this line, but ...
- 433
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
-1
votes
0
answers
94
views
Relation between properties of functions/sets and Grzegorczyk's hierarchy
I know for example that the first level of the Grzegorczyk hierarchy contains the functions which enumerate the c.e sets and that it has an interesting relation to the provably total functions in ...
- 893
5
votes
1
answer
365
views
Are PA and Counting Theory synonymous\bi-interpretable?
The following question is whether $\sf PA$ is synonymous or even bi-interpretable with a theory about counting objects in finite sets.
Counting Theory:
$\textbf{Logic:}$ Bi-sorted first order logic ...
- 11.3k
1
vote
0
answers
89
views
About synonymy relationships around these two theories?
The following question is about patterns of synonymy relationships around two theories, $T^+$ and $\sf PA$.
For purposes of self inclusiveness I'll re-iterate $T$ and its extensions.
$\textbf{Logic:}$ ...
- 11.3k
8
votes
1
answer
437
views
Function $\phi$ such that $f(\phi(x,y)) = f(x) + f(y)$
I have a continuous function $f:\mathbb{R}^n\to\mathbb{R}$, and I am looking for a continuous (or at least measurable) function $\phi:\mathbb{R}^{2n}\to\mathbb{R}^n$ such that $f(\phi(x,y))=f(x)+f(y)$....
- 3,065
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
12
votes
1
answer
697
views
Does synonymy seep down to the fragments of theories?
IF we have a synonymous interpretation between two theories $T$ and $H$ that uses translation $\tau$ from the language of $T$ to the language of $H$. Then I'd expect that for a sentence $\mu$ in the ...
- 11.3k
17
votes
2
answers
2k
views
Do the surreal numbers enjoy the transfer principle in ZFC?
The surreal field $\newcommand\No{№}\No$ is definable in ZFC, and it is easy to see that the surreal order is $\kappa$-saturated for every cardinal $\kappa$, precisely because we fill any specified ...
- 236k
4
votes
0
answers
107
views
Partial uniformization under AD
Under ZF + AD, and especially $\text{AD}^+$, even if uniformization fails for reals, in some ways it must almost hold.
For a notion of small, we say that uniformization holds on a co-small set of ...
- 7,545
6
votes
1
answer
987
views
How many colors do we need?
How many different colors do we need so that the set of all possible colorings of $\mathbb{R}^3$ is greater than the powerset of $\mathbb{R}$.
Countably many doesn't seem to be enough and even $|\...
- 131
14
votes
0
answers
391
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
8
votes
1
answer
245
views
Is $\operatorname{non}(\mathcal{M}) < \mathfrak{a}$ consistent?
Let $\operatorname{non}(\mathcal{M})$ be the least cardinality of a non-meagre subset of the reals. Let $\mathfrak{a}$ be the least cardinality of an infinite maximal almost disjoint family (i.e. $\...
- 1,432
13
votes
2
answers
1k
views
What's the deal with De Morgan algebras and Kleene algebras?
The notion of Boolean algebras, and the corresponding classical propositional logic, is very standard, and it is easy to find information about them (for example, among many other such works, there is ...
- 32.5k
-4
votes
0
answers
133
views
Which arithmetic\set theory is synonymous with this theory?
$\textbf{Logic:}$ Mono-sorted first order logic with equality.
$\textbf{Extralogical Primitives: } <, \in$
Define: $x > y \iff y < x$
Define: $x \leq y \iff x < y \lor x=y$
$ \textbf{...
- 11.3k
-4
votes
1
answer
173
views
To which arithmetic\set theory this theory is bi-interpretable?
$\textbf{Logic:}$ Mono-sorted first order logic with equality.
$\textbf{Extralogical Primitives: } <, \in$
$ \textbf{Axioms:}$
$ \textbf{Order:} \ x < y < z \to x < z $
$ \textbf{...
- 11.3k
12
votes
1
answer
227
views
Is there a $\Pi_2$ sentence $A$ such that $\text{ZFC}^- + A$ proves powerset?
This is a follow-up to this question.
Let $\text{ZFC}^-$ be ZFC without powerset and with collection rather than replacement, as described here.
Is there a $\Pi_2$ (or perhaps $\Sigma_2$) sentence $A$ ...
- 2,203
-2
votes
1
answer
199
views
Can this theory interpret Peano arithmetic?
Logic: Bi-sorted first order logic with equality, first sort written in lower case range over natural numbers, the second sort written in upper case range over sets of naturals, "$=$" has no ...
- 11.3k
5
votes
0
answers
67
views
Definable pseudo-standard predicates in Internal Set Theory
Consider the usual language $\mathcal{L}=(\in, \mathrm{st})$ of Nelson's Internal Set Theory, and a unary $\mathcal{L}$-predicate $P$. For an $\mathcal{L}$-formula $\varphi$, let $\varphi^P$ denote ...
- 756
5
votes
0
answers
159
views
If $\omega_1$ is not inaccessible in $L$, how hard can it be to find a non-measurable $\Sigma^1_3$ set of reals?
In his wonderfully titled paper Can you take Solovay's inaccessible away? Shelah showed that if every $\mathbf{\Sigma}^1_3$ set of reals is Lebesgue measurable, then $\omega_1$ is an inaccessible ...
- 12.5k
2
votes
0
answers
92
views
Geometric interpretation of flags and the role of the rook monoid and Kazhdan–Lusztig theory in $M_n(\mathbb{C})$
Let $G = GL_n(\mathbb{C})$, $B$ be its Borel subgroup, and $P$ a parabolic subgroup. The space $G/B$ corresponds to complete flags in $ \mathbb{C}^n$, and $G/P$ corresponds to partial flags. The ...
- 141
3
votes
0
answers
120
views
References on P vs NP under various axiomatic systems
I am teaching algorithms and theory of computation this semester and had the opportunity to dig a bit into the details of one way functions and the P vs NP problem.
This problem has resisted attacks ...
- 31
-4
votes
0
answers
189
views
Can ZFC be interpreted in this infinitary logic theory?
Working in language $\mathcal L_{\Omega^+,\Omega^+}$ where $\Omega$ is the first strongly inaccessible cardinal. If we add a primitive partial $\Omega$-ary function $F$ and a primitive constant $\...
- 11.3k
2
votes
1
answer
162
views
Are Cohen Generics Minimal Covers?
Are Cohen generics (in $2^\omega$) minimal covers?
I'm ultimately interested in this question for some more effective notion of forcing but I realized I wasn't sure how to show this even assuming full ...
- 3,029
6
votes
1
answer
243
views
Is it possible that the number of $\mathcal{T}$-algebras is an arithmetic progression?
For a single-sorted algebraic theory $\mathcal{T}$ denote by $t_n$ the number of $\mathcal{T}$-algebras with $n$ elements (up to isomorphism). Is there an example for $\mathcal{T}$ such that ...
- 63.1k
-5
votes
0
answers
250
views
Can Cardinality Theory capture ZFC?
Cardinality Theory "CT" is a theory of sets of cardinals and links between them, only sets of cardinals can be assigned cardinalities. The links are unordered edges linking cardinals, they ...
- 11.3k
6
votes
0
answers
188
views
Is there a characterization of measurables in terms of indiscernibles?
There is a characterization of $\alpha$-Erdős cardinals in terms of sets of indiscernibles of order type $\alpha$. There is also a characterization of Ramsey cardinals in terms of sets of good ...
- 2,031
0
votes
0
answers
61
views
Defining rank of an abelian subgroup using the second centralizer
I recently posted this on MSE, but didn't receive any feedback; so I'm posting it on MO.
I recently came across this article which explored the maximal abelian subgroups of the symmetric group $S_n$. ...
- 195
5
votes
0
answers
137
views
Cone avoidance and $\Pi^0_1$-classes
Suppose $X \subseteq 2^{\omega}$ is nonempty and $\Pi^0_1$ relative to $a$. Assume $c_0 \nleq_T b_0 \oplus a$ and $c_1 \nleq_T b_1 \oplus a$. Must there exist some $y \in X$ such that $c_i \nleq_T ...
- 51
15
votes
5
answers
3k
views
Examples of mathematical theories that are naturally written in exotic logics
Zermelo's set theory (ZF), Peano's arithmetic (PA), Tarski's theory of closed real fields (RCF), Hilbert-Tarski's geometry, etc. are all naturally expressed in first-order logic (FOL) (with a single ...
- 259
8
votes
1
answer
196
views
Weakly compact cardinals in $L$: how long do branches take to appear?
Throughout, we work in $\mathsf{ZFC+V=L+}$ "There is a weakly compact cardinal," $\kappa$ is the first weakly compact cardinal and "tree" means "subtree of $2^{<\kappa}$ of ...
- 20.5k
4
votes
0
answers
100
views
Explicit superexponential growth for Presburger Arithmetic
Fischer and Rabin proved a superexponential bound $2^{2^{cn}}$ for the worst-case length of a proof of a proposition of length $n$ in Presburger arithmetic. The result is in
Michael J. Fischer and ...
- 16.6k