Skip to main content

All Questions

Filter by
Sorted by
Tagged with
0 votes
1 answer
45 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 ...
Keith's user avatar
  • 621
1 vote
0 answers
49 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: ...
Gro-Tsen's user avatar
  • 32.5k
0 votes
0 answers
97 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 ...
categoricalequivalent's user avatar
4 votes
0 answers
142 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 ...
Noah Schweber's user avatar
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). ...
Dmytro Taranovsky's user avatar
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$, ...
David Gao's user avatar
  • 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 ...
Alexander Pruss's user avatar
5 votes
1 answer
148 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})$ (...
David Gao's user avatar
  • 2,830
8 votes
0 answers
199 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\...
Noah Schweber's user avatar
7 votes
0 answers
125 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 ...
Hanul Jeon's user avatar
  • 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}...
Boris Z's user avatar
  • 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 ...
Moreno Invitti's user avatar
1 vote
0 answers
80 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 ...
user76284's user avatar
  • 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 \...
Zuhair Al-Johar's user avatar
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 ...
Monroe Eskew's user avatar
  • 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 ...
Pedro Sánchez Terraf's user avatar
15 votes
1 answer
810 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 ...
Mikhail Katz's user avatar
  • 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 ...
Alexander Pruss's user avatar
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 ...
Garrett Figueroa's user avatar
11 votes
0 answers
235 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 ...
Noah Schweber's user avatar
-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 ...
H.C Manu's user avatar
  • 893
5 votes
1 answer
364 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 ...
Zuhair Al-Johar's user avatar
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:}$ ...
Zuhair Al-Johar's user avatar
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)$....
gmvh's user avatar
  • 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 ...
Keith's user avatar
  • 621
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 ...
Zuhair Al-Johar's user avatar
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 ...
Joel David Hamkins's user avatar
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 ...
Dmytro Taranovsky's user avatar
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 $|\...
Arianit's user avatar
  • 131
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 ...
user76284's user avatar
  • 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. $\...
Clement Yung's user avatar
  • 1,412
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 ...
Gro-Tsen's user avatar
  • 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{...
Zuhair Al-Johar's user avatar
-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{...
Zuhair Al-Johar's user avatar
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$ ...
user76284's user avatar
  • 2,203
-2 votes
1 answer
197 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 ...
Zuhair Al-Johar's user avatar
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 ...
Z. A. K.'s user avatar
  • 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 ...
James E Hanson's user avatar
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 ...
Learner's user avatar
  • 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 ...
ode's user avatar
  • 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 $\...
Zuhair Al-Johar's user avatar
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 ...
Peter Gerdes's user avatar
  • 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 ...
Martin Brandenburg's user avatar
-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 ...
Zuhair Al-Johar's user avatar
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 ...
C7X's user avatar
  • 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$. ...
dbossaller's user avatar
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 ...
Hello World's user avatar
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 ...
Miguel's user avatar
  • 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 ...
Noah Schweber's user avatar
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 ...
Mikhail Katz's user avatar
  • 16.6k

1
2 3 4 5
121