All Questions
6,026 questions
4
votes
0
answers
224
views
Is there a ${\bf 0'}$-computable linear order with "all intervals wild"?
Say that a linear order $L$ is a thicket iff $L$ is infinite, and for all elements $a,b,c_1,...,c_n\in L$ with $a<_Lb$ and $[a,b]_L$ infinite the following are equivalent:
$\{a,b\}\subseteq \...
- 20.5k
10
votes
0
answers
377
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
0
votes
1
answer
63
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
8
votes
2
answers
537
views
A continuous notion of realizability
I have been interested in non-classical logics, off and on, for quite a while. This question is probably very basic, and I hope it is not too low-level for MO. My question stems from an attempt to ...
CommunityBot
- 1
1
vote
0
answers
52
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 ...
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
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 ...
- 10.1k
-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 ...
- 228
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}...
- 20.5k
3
votes
1
answer
103
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 ...
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 ...
- 12.9k
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})$ (...
- 18.6k
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\...
- 3,065
10
votes
1
answer
499
views
What is the least $\alpha$ such that $L_\alpha$ contains a non-measurable set
What is the least level of the constructable hierarchy that contains a non-measurable (Lebesgue) subset of $2^\omega$. If it makes a difference assume we are working inside L (V=L).
I'm pretty sure it ...
- 50.6k
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
9
votes
2
answers
698
views
Partitioning a set of cardinality $\kappa$ into more than $\kappa$ disjoint subsets
There is an old result due to Mycielski and Sierpiński, and popularized in a Monthly article by Taylor and Wagon (A Paradox Arising from the Elimination of a Paradox; see also this MO answer), that ...
- 39.8k
1
vote
0
answers
82
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
10
votes
2
answers
387
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 ...
- 1,291
2
votes
0
answers
102
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
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 ...
- 1,094
4
votes
2
answers
195
views
Modal logics which have an algebraic semantics but not a Kripke semantics
A colleague told me that there are modal logics which have an algebraic semantics of some kind but which do not have a Kripke semantics and in which both $\Box$ is not monotonic with respect to $\to$, ...
- 31
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 ...
- 47.3k
20
votes
3
answers
4k
views
Propositions equivalent to the completeness of the real numbers
Can anyone point me to a reasonably comprehensive article (or book chapter) explaining which basic theorems of calculus are equivalent to the completeness axiom of the reals and which ones aren't?
...
- 16.6k
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
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
23
votes
10
answers
5k
views
Completeness vs Compactness in logic
One standard approach to showing compactness of first-order logic is to show completeness, of which compactness is an easy corollary. I am told this approach is deprecated nowadays, as Compactness is ...
- 17.7k
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
29
votes
3
answers
3k
views
Is there a probability theory developed in intuitionistic logic?
Since Boole it is known that probability theory is closely related to logic.
According to the axioms of Kolmogorov, probability theory is formulated with a (normalized)
probability measure $\mbox{...
CommunityBot
- 1
-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
45
votes
6
answers
8k
views
Situation with Artemov's paper?
Artemov's paper on Goedel's theorem has been on the arxiv since 2019. There was a (less than fully friendly) discussion of this on FoM. At stackexchange, I found only a brief mention at this MSE ...
- 82.7k
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)$....
- 716
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
43
votes
16
answers
9k
views
Essential reads in the philosophy of mathematics and set theory
I am graduate student and have a decent understanding of logic and set theory.
Recently I have got interested in the philosophy of mathematics and set theory. I have read a number of papers by ...
- 236k
8
votes
2
answers
1k
views
Surreals and NSA: some foundational issues
Surreals and NSA: some foundational issues.
A.
Leaving aside the whole internal machinery of surreals (with funny questions like is $\omega$ an entire number and if yes is it odd or even, simple, a ...
- 4,316
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 ...
- 12.5k
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 ...
- 236k
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
7
votes
1
answer
222
views
Finitistic interpretation of Nelson's internal set theory
What does “standard” in internal set theory really mean?
Is it secretly a way of reconciling conventional mathematics with (ultra)finitism?
Until recently I thought “standard” was just a way of ...
- 15.9k
7
votes
1
answer
508
views
Realizability for constructive Zermelo-Fraenkel set theory
$ \def \CZF {\mathbf {CZF}}
\def \IZF {\mathbf {IZF}}
\def \A {\mathcal A}
\def \then {\mathrel \rightarrow}
\def \r {\mathrel \Vdash}
\DeclareMathOperator \V V $
In "Realizability for ...
- 21.3k
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 ...
- 47.3k
82
votes
3
answers
20k
views
Czelakowski's claimed proof of the Twin Prime Conjecture
It seems like the article "The Twin Primes Conjecture is True in the Standard Model of Peano Arithmetic: Applications of Rasiowa–Sikorski Lemma in Arithmetic (I)" by Janusz Czelakowski ...
- 105k
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 ...
- 2,203
4
votes
0
answers
225
views
Complexity of $Σ_n$ theory of $H(ω_2)$ under MM$^{++}$
Complexity of $Σ_n$ theory of $H(ω_2)$ under MM$^{++}$
Under Woodin's $\mathbb{P}_\text{max}$ axiom (which is implied by MM$^{++}$), what is the complexity of the $Σ_n$ theory of $H(ω_2)$? Same ...
- 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 $|\...
- 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
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,442