Questions tagged [lo.logic]
first-order and higher-order logic, model theory, set theory, proof theory, computability theory, formal languages, definability, interplay of syntax and semantics, constructive logic, intuitionism, philosophical logic, modal logic, completeness, Gödel incompleteness, decidability, undecidability, theories of truth, truth revision, consistency.
5,432 questions
0
votes
0
answers
27
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 ...
- 139
1
vote
0
answers
66
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
116
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
158
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
65
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
54
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
180
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
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
8
votes
0
answers
206
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
132
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
106
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
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
2
votes
0
answers
105
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
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 ...
- 18.6k
10
votes
0
answers
205
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
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
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
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
12
votes
0
answers
242
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
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
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
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
12
votes
1
answer
701
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
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
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,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
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
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
-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,213
-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
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 ...
- 13k
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
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
-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
5
votes
0
answers
138
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
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
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
6
votes
2
answers
323
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
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
1
answer
422
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
1
vote
0
answers
96
views
Determine equivalences in the generated collection of subgroups and quotients
Let $A$ be an abelian group, and $B_1, B_2, \dots, B_m$ be subgroups of $A$. Define the family of subgroups $\mathcal{D}_0 = \{ \{0\}, A, B_1, B_2, \dots, B_m \}$.
Let $\mathcal{C}_1$ be the ...
- 807