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,152
questions
5
votes
0
answers
188
views
Reference-Request: Had this replacement principle been investigated before?
Replacement$^*$: If $\varphi$ is a formula with at least two variables occuring free, in which $``x,y"$ do not occur free, then:
$$\forall a \forall b \forall c \forall d \ ( \varphi(a,b) \land \...
- 9,256
6
votes
0
answers
101
views
Is PA interpretable in PRA + TI(<epsilon_0)?
By Gentzen's consistency proof, we know that PA has the same consistency strength as PRA + TI(<epsilon_0). Question: is PA interpretable in PRA + TI(<epsilon_0)?
For simplicity, let us assume ...
2
votes
0
answers
128
views
The strongest reflection principle that does not violate covering lemmas
#-generated reflection, or Indiscernible-generation, is considered to be the strongest reflection principle that does not violate the covering lemma in L. [1]
Is there a way to extend this success to ...
- 467
2
votes
0
answers
96
views
Which of these non-well founded set theories is synonymous with ZFC?
Lets add a constant $\mathcal A$ to the language of $\sf ZFC$.
Let "Foundation$_{\mathcal A}$" denote the following sentence:
$$ \forall x: \forall y \in x \exists z \in y \cap x \to \exists ...
- 9,256
17
votes
2
answers
1k
views
Axiom of Choice for collections of Equinumerous sets
Let ACE (Axiom of Choice for Equinumerous sets) be the following choice principal:
If $S$ is a set of non-empty sets such for any $X,Y\in S$ there is a bijection from $X$ to $Y$, then $S$ has a choice ...
- 488
5
votes
0
answers
131
views
What is known about propositional realizability for the second Kleene algebra and related PCAs?
Short version: Various things are known about realizability of propositional formulas for Kleene's “first algebra” (i.e., $\mathbb{N}$), like examples of realizable but unprovable formulas, and some ...
- 30.1k
4
votes
1
answer
235
views
What is the theory of statements with a provably *bounded* realizer (according to PA)?
$\let\T\mathrm\def\kr{\mathrel{\mathbf r}}$This is a follow up to Kleene realizability in Peano arithmetic.
We can summarize the results from Emil Jeřábek's answer as follows:
\begin{gather*}
T_1 = \{ ...
- 5,821
1
vote
0
answers
180
views
Can this Mereological system be synonymous with $\sf ZF(C)$?
This question is about synonymy of $\sf ZFC$ set theory with the following Mereological theory:
Language: first order logic with equality. Extra-logical primitives: $\subseteq$ standing for the binary ...
- 9,256
2
votes
0
answers
102
views
Existence of trees with height $\kappa$, every level has at most size $\lambda$ and has at least $\lambda^{+}$ maximal branches
Definitions A tree means a set-theoretic tree, that is a poset $(T,<)$ so that for each $x\in T$, the set $\{y\in T\mid y<x\}$ is well-ordered.
A $\kappa$-Kurepa tree is a tree of height $\kappa$...
2
votes
0
answers
480
views
Gödel's second incompleteness theorem [closed]
Apparently, see Feferman or Wikipedia, in a consistent system there are formulations of consistency that are demonstrable in the system itself while others are not. What distinguishes one from another?...
- 213
1
vote
1
answer
584
views
Can this kind of Mereology be synonymous with Set Theory?
This question is about synonymy of Morse-Kelley set theory "$\sf MK$" with the following Mereological theory:
Language: first order logic with equality. Extra-logical primitives: $\subseteq$ ...
- 9,256
6
votes
1
answer
302
views
Original motivations of Fraïssé's amalgamation construction
Roland Fraïssé introduced in the 50's his famous construction of Fraïssé limits, and then Ehud Hrushowski modified it in the early 90's to construct new structures.
The motivations for the latter was ...
- 995
2
votes
1
answer
118
views
Kripke frame, lattice and some intermediate logics
For a given finite and rooted intuitionistic Kripke frame $\mathcal{F}$, let $\log(\mathcal{F})=\{\phi : \mathcal{F}\vDash \phi\}$ and assume $S=\{\log(\mathcal{F}): \mathcal{F} \text{ is finite and ...
- 47
8
votes
0
answers
183
views
Reference request: choiceless cardinality quantifiers
There is a substantial literature on the logic of cardinality quantifiers. (E.g., the quantifier $Q_\alpha$ where $M \vDash Q_\alpha x \, \varphi (x)$ iff $\vert \{a \in M : M \vDash \varphi[a] \} \...
- 1,135
4
votes
1
answer
282
views
Is ZFGC, minimally modified to allow two Quine atoms instead of the empty set, synonymous\bi-interpretable with ZFGC?
Working in $\sf ZFGC$, remove Foundation, stipulate the existence of exactly two Quine atoms. Restrict Separation to fulfillable formulas, i.e. $\{x \in A \mid \phi \}$ exists as long as $\phi$ holds ...
- 9,256
14
votes
1
answer
769
views
Does completeness of the theory of a bijection without finite orbits depend on choice?
Consider the following sentences in a first-order language with one unary function symbol $f$:
$\forall x \exists y (fy=x)$
$\forall y\forall z(fy=fz\to y=z))$
$\forall x (\underbrace{f\dotsb f}_{n\...
- 143
3
votes
2
answers
226
views
Question regarding $W$ as not hyperarithmetic
Consider the indexes of all ordinary programs generating functions from $\mathbb{N}^2$ to $\{0,1\}$. If we let $W$ be the set of exactly of all those indexes $e$ such that $\phi_e$ computes a total ...
- 861
3
votes
1
answer
93
views
Is the filter generated by $A$-generic sets S1-prime?
Let $\mathfrak U$ be a monster model.
Let $A\subseteq\mathfrak U$ be a small set of parameters.
A set $\mathfrak D\subseteq\mathfrak U^{|x|}$ is $A$-generic if finitely many translations of $\mathfrak ...
3
votes
0
answers
98
views
Positive boolean satisfiability problem : finding minimal solutions
Consider, over a finite set of boolean variables $X$, a Boolean system in CNF (conjunctive normal form) whose clauses only contain non-negated literals.
For every assignment of the variables which ...
-2
votes
2
answers
479
views
Can Mereology be bi-interpretable with Set Theory, in absence of the bottom object?
This question is about synonymy between Set theory and Mereology.
David Lewis in Mathematics is Megethology tried to reduce Set Theory to Mereology augmented with a singleton function. The following ...
- 9,256
2
votes
1
answer
541
views
Logical content of Gauss's Lemma (arithmetic)
In the context where $a$, $b$, $c$ are integers we have $(a \mid bc, a\land b = 1) \Rightarrow a\mid c$. This result is called Gauss's Lemma in French Highschool.
It is well known that (Steve Awodey, ...
- 29
5
votes
1
answer
246
views
Why include $0$ and $1$ in the signature of Presburger arithmetic?
I recently became interested in some problems concerning decidability of extensions of Presburger arithmetic. However, being a number-theorist rather than a logician, I am confused by some notational ...
- 1,762
12
votes
1
answer
447
views
Why do we need the comparison lemma?
An inner model is a standard transitive (proper class) structure which satisfies all the axioms of ZFC and contains all the ordinals. The simplest and most well-known inner model is Gödel’s $L$, which ...
- 704
7
votes
1
answer
228
views
Is the set of ordinals in Double Extension Set Theory really a set?
We got stuck on the definition of ordinals when we built the DEST(Double Extension Set Theory) checker on Cubical Agda and ...
- 467
3
votes
0
answers
109
views
Do coproducts injections of Heyting algebras have left and right adjoints?
Given two Heyting algebras $A$ and $B$, let $A+B$ be their coproduct in the category of Heyting algebras. Is it true that the inclusion $A → A+B$ always has a left and a right adjoint ? (Actually, I ...
- 31
-2
votes
1
answer
206
views
Would this alteration safeguard the resulting theory from inconsistency?
If we replace "Emergence" axiom in the theory $T$ presented at posting "What is the set theory synonymous with this order-set theory?" with the following axiom, call the resulting ...
- 9,256
5
votes
0
answers
200
views
Classical first-order model theory via hyperdoctrines
I have been reading this discussion by John Baez and Michael Weiss and I find this approach to model theory using boolean hyper-doctrines very interesting. One of their goal was to arrive at a proof ...
- 3,024
8
votes
1
answer
1k
views
Why don't Zeilberger and Gosper's algorithms contradict Richardson's theorem?
Richardson's theorem proves that whether an expression A is equal to zero is undecidable. A is in this case an expression, constructed from $x,e^x,\sin(x)$ and the constant function $\pi$ and $\ln(2)$ ...
- 125
3
votes
1
answer
162
views
Would this alteration of $T$ affect its synonymy with PA?
If we replace the single axiom "Emergence" in the axiomatic system $T$ presented at posting [What is the set theory synonymous with this order-set theory], by the following schema. Would the ...
- 9,256
3
votes
0
answers
176
views
In constructive set theory, is it consistent for there to be a ring that models smooth infinitesimal analysis?
In a constructive set theory such as CZF, it is consistent to assume that every function $f : \mathbb R \to \mathbb R$ is continuous. However, it is not consistent to assume that every such function ...
- 5,821
4
votes
0
answers
143
views
Can this theory of dyadic rationals prove that multiplying by three is the same as summing thrice?
(This question arose from a discussion with Jade Vanadium about a theory of dyadic rationals.)
Let $T$ be the 2-sorted FOL theory with sorts $ℕ,ℚ$ and constant-symbols $0,1$ and binary function-...
- 2,733
1
vote
1
answer
299
views
What is the set theory synonymous with this order-set theory?
Let $ T$ be a theory written in Mono-sorted first order logic with equality, with extralogical primitives: $<, \in$.
Define: $x \leq y \iff x < y \lor x=y$
Axioms:
$\textbf{Well ordering: }\\\...
- 9,256
3
votes
0
answers
49
views
A new(?) kind of 2-adjunction for relating cartesian closed functors using dinatural hexagons
$\newcommand{\A}{\operatorname{A}}
\newcommand{\B}{\operatorname{B}}
\newcommand{\Cat}{\mathcal{Cat}}
\newcommand{\Cart}{\mathcal{Cart}}
\newcommand{\C}{\mathbf{C}}
\newcommand{\F}{\operatorname{F}}
\...
5
votes
1
answer
160
views
Electronic copy of Glivenko, ‘Sur quelque points de la logique de M. Brouwer’
Glivenko is cited i.a. in the SEP:
Glivenko, V., 1929, “Sur quelques points de la logique de M. Brouwer,” Académie Royale de Belgique, Bulletins de la classe des sciences, 5 (15): 183–188.
I’m ...
- 101
1
vote
0
answers
80
views
Is every set equinumerous to a well founded set in acyclic ZF?
If we replace the axiom of Regularity in $\sf ZF$ by the scheme of Acyclicity, which is:
$$\begin{align} n=2,3,\dots;\ & \neg \exists x_1,\dots , \exists x_n: \\ &x_1 \in x_2 \land \dots \...
- 9,256
10
votes
4
answers
1k
views
Is this theory synonymous with PA?
Language: Mono-sorted first order logic with equality.
Extralogical Primitives: $<, \in$
Define: $x \leq y \iff x < y \lor x=y$
$\textbf{Well ordering: }\\\textit{Transitive:} \ x < y \land ...
- 9,256
7
votes
0
answers
131
views
Logical properties of realizability (topoi or McCarty models) defined by alpha-recursion on admissible ordinals
Setup: Let $\alpha$ be an admissible ordinal (viꝫ., one such that $L_\alpha$ is a model of Kripke-Platek set theory), identified as usual with the set of ordinals $<\alpha$. Then there is a ...
- 30.1k
33
votes
3
answers
4k
views
Using Busy Beavers to prove conjectures
I've been pondering some stuff on Shtetl Optimized where Yedidia and Aaronson construct Turing machines that will only halt if (e.g.) the Riemann Hypothesis is false, or Goldbach's conjecture is false....
- 463
4
votes
1
answer
265
views
Bounded alternatives to powerset that interpret ZFC
In set theory, many properties/relations of interest can be expressed as $\Delta_0$ formulas (formulas with only bounded quantifiers):
\begin{align}
\text{empty}(a) &\equiv \forall x \in a . \...
- 1,793
14
votes
2
answers
1k
views
Church–Turing thesis for higher order functions
The Church–Turing thesis states that, simply speaking, any reasonable definition of "effectively computable functions" $\mathbb{N} \to \mathbb N$ agrees with the definition using Turing ...
- 1,031
2
votes
2
answers
255
views
Erdős–Sierpiński duality in locally compact Polish groups (e.g. $\mathbb{R}^n$)
Erdős–Sierpiński mapping for a locally compact Polish group $G$ is a bijection $f$ from $G$ to $G$ such that $A$ is a null set in $G$ with respect to the Haar measure if and only if $f(A)$ is a meager ...
- 131
1
vote
0
answers
272
views
Can the following definition of choice principle salvage the prior attempts?
In prior postings 1 , 2, I've presented a definition of choice principle as what is equivalent to a selection principle. However, it was proved that it is inadequate in the sense that it admits ...
- 9,256
6
votes
1
answer
279
views
A variation on pinned equivalence relations
Recall (see e.g. Zapletal, Pinned equivalence relations) that a Borel equivalence relation $E$ on $\omega^\omega$ is pinned iff for every forcing $\mathbb{P}$ and every $\mathbb{P}$-name $\nu$ we have ...
- 19k
1
vote
1
answer
212
views
Seeking clarification of ultrapower nonstandard model of arithmetic
I've read that one nonstandard model of arithmetic is:
take $\mathbb{N}^\mathbb{N}$, the set of countably infinite sequences of natural numbers
take a quotent that gives the ultrapower: identify ...
- 1,258
6
votes
0
answers
207
views
What are these non-classical versions of ZFC defined by realizability?
See Kleene realizability in Peano arithmetic for a similar question, but about PA instead of ZFC.
In the context of constructive set theory, consider two ways of defining realizability.
The first is $\...
- 5,821
6
votes
1
answer
278
views
Need help in trying to understand an argument by V. A. Yankov on the nonrealizability of Scott's axiom
(This is really long because I give a lot of context, but you can skip right to the end where the excerpt I'm trying to make sense of is copied and translated.)
Background: I'm trying to understand ...
- 30.1k
2
votes
1
answer
567
views
Is there a strict limit on choice principles in $\sf ZFC$?
Is there a principle $\sf P$ that $\sf ZFC$ [or some suitable extension of it] proves to be a strict limit on choice principles?
By a choice principle I mean a sentence (or scheme) that is equivalent ...
- 9,256
2
votes
0
answers
75
views
Is monotonicity redundant in this definition of Tarskian logics?
Given a logic over a language $L$, which has a consequence relation $\vdash$. This logic is Tarskian if for every $\Gamma \cup \Delta \cup {\alpha} \subseteq L$:
If $\alpha \in \Gamma$, then $\Gamma \...
- 21
3
votes
2
answers
514
views
Is the Ordering Principle equivalent to a selection principle?
Working in the context of set theory $\sf ZF$, selection may be defined as a function from nonempty sets to their elements. Formally:
$\operatorname {selective}(c) \iff \operatorname {function}(c) \...
- 9,256
7
votes
1
answer
860
views
Logical strength of a statement about vector spaces
[Apologies if this is a really trivial question, I know virtually nothing about set theory, and the following came up while preparing undergraduate linear algebra lectures.]
I'm asking about the ...
- 36.1k