All Questions
6,027 questions
1
vote
0
answers
62
views
Why do we require that all successors model this formula?
I'm reading Fitting's Intuitionistic Logic, Model Theory and Forcing. This occurs in Chapter 7.15.
The aim is to prove that a certain intuitionistic model is an intuitionistic model of ZF. I ...
- 149
0
votes
1
answer
70
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
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
1
vote
0
answers
67
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
122
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
160
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
5
votes
1
answer
153
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
3
votes
1
answer
181
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
8
votes
0
answers
207
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
10
votes
2
answers
388
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
2
votes
0
answers
66
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
7
votes
0
answers
133
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
3
votes
1
answer
107
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 ...
15
votes
1
answer
815
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
3
votes
0
answers
55
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
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
2
votes
0
answers
84
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,213
12
votes
0
answers
245
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
2
votes
0
answers
107
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
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
6
votes
1
answer
230
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
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
12
votes
1
answer
702
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
5
votes
1
answer
369
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
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
10
votes
0
answers
206
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
-2
votes
1
answer
205
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
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
6
votes
1
answer
988
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
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
19
votes
2
answers
2k
views
Can there exist a definable "ultrafilter" on the ordinals?
Can there exist a model $\textit M$ of $\textit{ZF}$ (or $\textit{ZFC}$) that contains a definable nontrivial "ultrafilter" on $\sf Ord^{\textit M}$? By this I mean that there is some ...
- 576
-1
votes
0
answers
95
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
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,213
8
votes
1
answer
246
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
14
votes
0
answers
392
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,213
1
vote
0
answers
90
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
6
votes
1
answer
244
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
-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
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
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 ...
- 16.6k
-4
votes
0
answers
135
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
6
votes
2
answers
324
views
Set theoretical foundations for derived categories
A modern approach to derived functors, that has been shown to be useful in a number of different circunstances is that of a derived category (see the book by Yakutieli, for example, here).
However, it ...
- 3,318
8
votes
1
answer
197
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
2
votes
2
answers
335
views
Are there models of ZF in which all uncountable sets are super/hyper/ultra-singular?
This question is a follow up to that posting.
Recall the definition of super/hyper/ultra-singular set given in the linked posting.
Is there a model of $\sf ZF$ in which every uncountable set is super-...
- 11.3k
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 ...
- 13.1k
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
5
votes
1
answer
423
views
What is the relationship between non-existence of those kinds of singular sets and AC?
Let's say a set $A$ is super-singular, if and only if, there exists a set $x$ such that $|A|=|\bigcup x|$ and $| A| > |x|$, and for each $y \in x$ we have: $ |y| \not > |x|$ .
A set $A$ is ...
- 11.3k
7
votes
1
answer
224
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
-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
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