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,126
questions
1
vote
0
answers
62
views
Can the proper/whole domain relationship in bi-interpretations be reversed for non-synonymous theories?
Suppose we have theories $T$ and $H$ that are bi-interpretable, now suppose that the relevant interpretations achieving that bi-interpretability are: $\tau: T \to H$, and $\pi: H \to T$. Now suppose ...
9
votes
0
answers
116
views
What are these generalizations of the principles of omniscience called?
I will give some principles that are slightly stronger versions of the principles of omniscience. Despite being about the natural numbers, they imply their analytic versions! Under countable choice (...
9
votes
2
answers
1k
views
Truth in a different universe of sets?
I understand that provability and truth as different concepts.
Provability is syntactic, it only concerns whether the given
sentence can be derived by reiterating the inference rules over a
collection ...
1
vote
0
answers
111
views
Provability predicates
We know that there are provability predicates, that is, predicates derived from the recursive relation "x is a demonstration of y", with which Godel's second incompleteness theorem would not ...
10
votes
1
answer
340
views
1970 question of Reinhardt - how large is this ordinal?
On page 241 of William Reinhardt's paper "Ackermann's set theory equals ZF" (Annals of Math. Logic vol. 2, 1970), question 4.15 is the following:
How large is the first ordinal $\gamma$ ...
10
votes
5
answers
923
views
When can a function defined on $[a, b] \cup [b, c]$ be constructively extended to a function defined on $[a, c]$?
Let $a, b, c \in \mathbb R$ such that $a \le b \le c$. Let $S$ be some set and $f : [a, b] \cup [b, c] \to S$ be a function. When can we find a function $g : [a, c] \to S$ that meets the following ...
7
votes
0
answers
170
views
Is the positive fragment of second-order logic compact?
This is a crosspost of this question that I posted on the math stack exchange a year and a half ago.
There are two slightly different versions of compactness in the FOL setting:
If $\Delta$ is ...
11
votes
2
answers
775
views
Undefinable inner model
What are some examples of a pair $M\subseteq N$ of transitive set models of $\mathsf{ZFC}$ with the same ordinals, such that $M$ is not a definable class (with parameters) in $N$? Is it possible that $...
0
votes
1
answer
210
views
Is it consistent that $2^{(\cdot)}$ is "surjective" on the class of uncountable ordinals?
$\newcommand{\Z}{{\sf (ZFC)}}$
It is consistent in $\Z$ that there is an uncountable cardinal $\kappa$ such that for no cardinal $\lambda$ we have $2^\lambda = \kappa$: Take any model in which $2^{\...
4
votes
0
answers
272
views
Which countable sets don't drastically change the definable topologies on $\mathbb{R}$?
For $\mathcal{M}$ an expansion of $\mathcal{R}=(\mathbb{R};+,\times)$ and $A\subseteq\mathbb{R}$, let $\tau^\mathcal{M}_A$ be the topology on $\mathbb{R}$ generated by the sets definable in $\mathcal{...
11
votes
1
answer
556
views
On the classification of second-countable Stone spaces
Let $X$ be a Stone space (i.e. totally disconnected compact Hausdorff). Then the following are equivalent:
$X$ is second countable
$X$ is metrizable
$X$ has countably many clopen subsets
$X$ is an ...
4
votes
1
answer
453
views
Truth Values of Statements in non-standard models
Excuse me, if the question sounds too naive.
Non-standard models of PA will have statements of non-standard lengths, basically infinite. And it is also true that every statement of a theory will have ...
2
votes
0
answers
142
views
Is it consistent to have these kinds of acyclic hereditarily size sets?
Working in $\sf ZFC-Reg. {}+ Acyclicity$. Where :
Acyclicity: $\neg \exists x_1, \cdots, \exists x_n: x_1 \in x_2 \in\cdots\in x_n \in x_1$
We add the following kind of weird non-well founded sets.
$\...
3
votes
0
answers
73
views
What does the computation of irrationality and transcendentality via a fancy implementation of analytic Markov's property look like?
Proofs that various real numbers are not rational or not algebraic tend to be constructively valid as is. Examples include the proofs that $\sqrt 2$ and $\log_2(3)$ are not rational and that $e$ is ...
13
votes
1
answer
472
views
Is there a theory between HA and PA that doesn't have Markov's rule?
A theory $T$ admits Markov's rule when
For every formula $\phi(n)$, if $$T \vdash \forall n \in \mathbb N. \phi(n) \lor \lnot \phi(n)$$ and $$T \vdash \lnot \lnot \exists n \in \mathbb N. \phi(n)$$ ...
3
votes
0
answers
156
views
Are all "reasonable" Gödel encodings isomorphic in some sense?
It is clear that many different Gödel numberings can work in Gödel's proof. Yet for the proof one just needs a few properties of how the numberings of related sentences are related, and I'm wondering ...
3
votes
0
answers
133
views
Lindström's theorem part 2 for non-relativizing logics
By "logic" I mean the definition gotten by removing the relativization property from "regular logic" — see e.g. Ebbinghaus/Flum/Thomas — and adding the condition that for every ...
4
votes
1
answer
156
views
Which of the known variants of Replacement can survive DeExtensionality?
Starting with $\sf ZF$. If we replace the power set axiom by the axiom stating that for any set $A$ there exists a set $x$ such that for every $y \subseteq A$ we have a set $y' \in x$ such that $\...
13
votes
1
answer
911
views
Cantor-Bernstein with "weakly injective" functions
Let us call a map $f: X \to Y$ between non-empty sets a "weak injection" if $f^{-1}(\{y\})\subseteq X$ is finite for every $y \in Y$.
Recall that the (Schroeder-)Cantor-Bernstein-Theorem (...
5
votes
2
answers
402
views
Models of second-order arithmetic closed under relative constructibility
I know little to nothing about second-order arithmetic and its subsystems. However, I would like to understand when a model of (a subsystem of) second-order arithmetic ($\mathsf{Z}_2$) is downward ...
1
vote
0
answers
62
views
EF-games with scrambling
This question is motivated both by the notion of zero-knowledge proofs and by general curiosity about versions of the infinitely-long Ehrenfeucht-Fraisse game which don't trivialize (= Duplicator win ...
5
votes
0
answers
187
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 \...
6
votes
0
answers
99
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
123
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 ...
2
votes
0
answers
94
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 ...
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 ...
5
votes
0
answers
130
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 ...
4
votes
1
answer
228
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 = \{ ...
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 ...
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
471
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?...
1
vote
1
answer
583
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$ ...
6
votes
1
answer
299
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 ...
2
votes
1
answer
111
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 ...
8
votes
0
answers
178
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] \} \...
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 ...
14
votes
1
answer
765
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\...
3
votes
2
answers
222
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 ...
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
95
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
477
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 ...
2
votes
1
answer
535
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, ...
5
votes
1
answer
242
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 ...
12
votes
1
answer
443
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 ...
6
votes
1
answer
213
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 ...
3
votes
0
answers
108
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 ...
-3
votes
1
answer
202
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 ...
5
votes
0
answers
196
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 ...
8
votes
1
answer
994
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)$ ...
3
votes
1
answer
161
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 ...