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.

Filter by
Sorted by
Tagged with
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 ...
Zuhair Al-Johar's user avatar
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 (...
Christopher King's user avatar
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 ...
Student's user avatar
  • 5,008
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 ...
Speltzu's user avatar
  • 169
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$ ...
C7X's user avatar
  • 1,176
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 ...
Christopher King's user avatar
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 ...
Greg Nisbet's user avatar
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 $...
new account's user avatar
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^{\...
Dominic van der Zypen's user avatar
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{...
Noah Schweber's user avatar
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 ...
Tim Campion's user avatar
  • 60.5k
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 ...
Amiren's user avatar
  • 1
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. $\...
Zuhair Al-Johar's user avatar
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 ...
Christopher King's user avatar
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)$$ ...
Christopher King's user avatar
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 ...
Joshua Grochow's user avatar
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 ...
Noah Schweber's user avatar
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 $\...
Zuhair Al-Johar's user avatar
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 (...
Dominic van der Zypen's user avatar
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 ...
Lorenzo's user avatar
  • 2,134
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 ...
Noah Schweber's user avatar
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 \...
Zuhair Al-Johar's user avatar
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 ...
Stephen Mackereth's user avatar
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 ...
Ember Edison's user avatar
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 ...
Zuhair Al-Johar's user avatar
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 ...
Brian Pinsky's user avatar
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 ...
Gro-Tsen's user avatar
  • 29.8k
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 = \{ ...
Christopher King's user avatar
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 ...
Zuhair Al-Johar's user avatar
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$...
George Marangelis's user avatar
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?...
Speltzu's user avatar
  • 169
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$ ...
Zuhair Al-Johar's user avatar
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 ...
huurd's user avatar
  • 995
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 ...
4869's user avatar
  • 47
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] \} \...
Beau Madison Mount's user avatar
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 ...
Zuhair Al-Johar's user avatar
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\...
George Hayduke's user avatar
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 ...
SSequence's user avatar
  • 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 ...
Domenico Zambella's user avatar
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 ...
Christopher-Lloyd Simon's user avatar
-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 ...
Zuhair Al-Johar's user avatar
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, ...
smed's user avatar
  • 29
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 ...
Jakub Konieczny's user avatar
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 ...
Binary198's user avatar
  • 704
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 ...
Ember Edison's user avatar
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 ...
user713327's user avatar
-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 ...
Zuhair Al-Johar's user avatar
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 ...
Antoine Labelle's user avatar
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)$ ...
Martin Clever's user avatar
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 ...
Zuhair Al-Johar's user avatar