# 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, ...

3,178 questions

**1**

vote

**0**answers

13 views

### On a combinatorial set covering property

Let $\kappa < \lambda < \mu$ be infinite cardinals. Is there a collection ${\cal U}\subseteq {\cal P}(\mu)$ of subsets of $\mu$ with the following properties?
for all $U\in {\cal U}$ we have $|...

**0**

votes

**0**answers

59 views

### Can reflection in $V$ and reflection out of $V$ principles be used in the same theory?

I've noticed that most of the work in Ackermann set theory is primarily concerned with constructing sets in $V$, the rest of the classes are just excess material, carrying no comprehension over them. ...

**1**

vote

**0**answers

44 views

### Can this reflective class theory interpret ZFC?

Reflective Set Theory $\mathsf{RfST}$ is formulated in first order predicate logic with extra-logical primitives of equality $``="$, membership $``\in"$, and a single primitive constant symbol $V$ ...

**0**

votes

**1**answer

65 views

### Superintuitionistic logics which are not hereditary/monotonic: impossible or possible?

An intuitionistic Kripke model is a triple $\langle W,\leq, \Vdash \rangle$, where $\langle W,\leq \rangle$ is a preordered Kripke frame, and
$\Vdash$ satisfies the following condition of ...

**7**

votes

**1**answer

141 views

### Effective set= ordinal definable set

I just today realized that the concept of ordinal definability is defined in a different way by vopenka-Balcar-Hajek ``The notion of effective sets and a new proof of the consistency
of the axiom of ...

**0**

votes

**0**answers

40 views

### What is the limit to iterating class comprehension, reflection and limitation of size?

In posting about a reflection principle coupled with a limitation of size axiom over Ackermann set theory, the answer is that the theory is blown up to a Mahlo cardinal.
I'm here just wondering if ...

**21**

votes

**1**answer

310 views

### Is there a short proof of the decidability of Kepler's Conjecture?

I've believed that the answer is "yes" for years, as suggested in various sources with reference to Tóth's work. For example, the Wikipedia article for Kepler Conjecture says:
The next step toward ...

**3**

votes

**1**answer

130 views

### What is the strength of adding limitation of size and a simple version of reflection to Ackermann set theory?

The following theory is formulated in first order predicate logic with extra-logical primitives of equality $``="$, membership $``\in"$, and a single primitive constant symbol $V$ denoting the class ...

**6**

votes

**0**answers

222 views

### measure of generic reals in forcing extensions

It is well-known that if $V[G]$ is a generic extension by adding a Cohen real, then
the set $\{r \in V[G]: r$ is Cohen generic over $V\}$ has measure zero.
On the other hand, if $V[G]$ is a generic ...

**0**

votes

**0**answers

101 views

### What is the consistency strength of this kind of reflection principle?

If $\psi$ is a predicate that is definable in $FOL(\in,=)$ by a formula from parameters in $V$, then if $\psi$ hold of the class $\small ORD$ of all ordinals in $V$, then the class of all cardinals in ...

**4**

votes

**0**answers

243 views

+200

### A strong plus-one hypothesis

To make this more easily readable, I'll start with the question and then give the explanation/motivation.
Question. Is the following principle (or its weakening, with "for every real $r$" replaced ...

**0**

votes

**0**answers

77 views

### Prove that the following formula is valid in LTL (linear temporal logic): □(p→ q) → (◊ p → ◊ q) [closed]

Can someone help me solve this? Don't know how to solve LTL question.

**1**

vote

**1**answer

105 views

### Semantics/Syntax distinction vs. Meta/Object language distinction

Distinguishing the semantics of a language from its syntax means (at least) distinguishing the meaning of the expressions (what is being represented) from the grammatical structure and formation rules ...

**1**

vote

**2**answers

218 views

### Can we have a theory $T$ that is complete for simple sentences in the language of $T$ that are weaker than $ Con(T)$?

Let's denote a sentence $P$ as "weak Godel sentence of theory $T$", if and only if
$$[\neg (T \vdash P) \wedge \neg (T\vdash \neg P)] \wedge [Con(T)=Con(T+P) \wedge Con(T)=Con(T+ \neg P)] $$
In ...

**15**

votes

**0**answers

562 views

### What is the smallest unsolved diophantine equation?

If $P=\sum_{\bf i} a_{\bf i}x^{\bf i}\in {\mathbb Z}[x_1,\dots,x_d]$, let $|P|=\sum_{\bf i}|a_{\bf i}|x^{\bf i}$ and $h(P)=|P|(2,\dots,2)$, so that there is only a finite number of $P$ with $h(P)\leq ...

**8**

votes

**3**answers

640 views

### Differences between logic with and without equality

By logic without equality I mean those kind of logics where equality is treated as a binary relation satisfying some axioms, as opposed to a logics where equality is a logical symbol satisfying some ...

**7**

votes

**1**answer

380 views

### Destroying Suslin, nothing special

Recall that a tree on $\omega_1$ is called Suslin if every chain and antichain are countable. If every level is countable and there are no cofinal branches, then it is called Aronszajn (in particular ...

**0**

votes

**0**answers

129 views

### Is “ZF+ V=L” an upper limit theory for cardinal decidability (per its strength)?

{EDIT: this posting has been edited, the additional text is in italics}
If $\varphi, \psi$ are two parameter free formulas in the language of set theory $T$ such that there is a theorem of $T$ that ...

**3**

votes

**2**answers

223 views

### What are the definable sets in Skolem arithmetic?

Definable subsets of $\mathbb N$ in the language of Presburger arithmetic are exactly the eventually periodic sets and quantifier free part corresponds to Integer Programming with linear inequalities ...

**2**

votes

**1**answer

178 views

### Meta-incomputability

Is there a set $B$ about which it provably cannot be decided whether it is computable in $\mathsf{ZFC}$?

**3**

votes

**0**answers

183 views

### Formal foundations done properly [closed]

I would want to do mathematics properly, so that the proofs of results can be trusted on instead of them being just suggestions on which results could perhaps apply. This means formulating the math in ...

**5**

votes

**1**answer

282 views

### van der Waerden's theorem in Reverse Mathematics

What is known about weak systems of axiomata that allow one to prove van der Waerden's theorem ?
van der Waerden's theorem can be used to show that there are infinitely many primes (see below). Is ...

**7**

votes

**1**answer

139 views

### Does $\mathsf{MA}^+(\sigma-{\rm closed})$ imply there are no Kurepa Trees?

The question in the title is somewhat self contained but let me make some definitions and remarks to clarify.
Recall that $\mathsf{MA}^+(\sigma-{\rm closed})$ is the statement that if $\mathbb P$ is ...

**1**

vote

**1**answer

140 views

### What is the strength of this strict constructible iterative hierarchy?

Begin with the empty set then construct the set of the empty set, then construct the set of all subsets of the latter set, then at each level of construction construct the next level as the set all ...

**2**

votes

**1**answer

109 views

### Conservativity of language extension

It is folklore that extending a language of classical first-order logic is conservative. That is, given two languages $L \subseteq L'$, a set of $L$-sentences $\Gamma$ and an $L$-sentence $\varphi$, ...

**1**

vote

**1**answer

178 views

### Is Replacement motivated by ranked iterative conception of sets?

When one reads the Wikipedia article on the Von Neumann Universe, one gets the impression that the idea of "the cumulative hierarchy" serves as a motivation for $ZFC$. I don't see really how this is ...

**12**

votes

**1**answer

481 views

### A peculiarity of Henkin's 1950 proof of completeness for higher order logic

My question concerns Henkin's original (1950) completeness proof https://projecteuclid.org/euclid.jsl/1183730860 for classical higher order logic and type theory relative to so-called general models.
...

**16**

votes

**1**answer

468 views

### Is there a pair of non-isomorphic structures each of which is isomorphic to an ultrapower of the other?

Does there exist a pair of non-isomorphic structures $\mathfrak{A}$ and $\mathfrak{B}$ as well as sets $I$ and $J$ and ultrafilters $\mathcal{U}$ on $I$ and $\mathcal{F}$ on $J$ such that $\mathfrak{A}...

**4**

votes

**0**answers

127 views

### Reference request: destroying saturation at an inaccessible?

An ideal $I$ on $P(\kappa)$ is said to be $\kappa^+$-saturated if there is no sequence $\langle S_\alpha \mid \alpha<\kappa^+\rangle$ of $I^+$ sets such that $\alpha<\beta<\kappa^+\implies S_\...

**8**

votes

**0**answers

131 views

### Primitive recursive and feasible presentations for nonstandard models of arithmetic

Let us define a countable model $\cal{M}$ = $(M,+_M ,\cdot_M, <_M)$ of $Q$ (Robinson arithmetic) to have a (primitive) recursive presentation if $\cal{M}$ is isomorphic to $(\omega, \oplus, \...

**0**

votes

**0**answers

54 views

### Can MK be interpreted in a class theory about an abstract hierarchy principle + an accessibility principle?

The following is a first order MONOSORTED class theory, that is primarily motivated by an abstract hierarchy principle. It extends first order logic
with equality, its language has only two extra-...

**6**

votes

**1**answer

334 views

### Action of infinite symmetric groups on iterated power sets

Let $X$ be an infinite set, and $k \ge 1$ be a natural number. We work without the axiom of choice.
Let $G_0$ be the full symmetric group on $X$, and let $G_1$ be the
full symmetric group on ${\cal ...

**2**

votes

**2**answers

684 views

### If Goldbach's Conjecture is eventually true, is it necessarily true?

We have all heard that if Goldbach's conjecture is independent, then it is true. This is because if GC is false then there is an even number which is not the sum of two primes, and hence a finite ...

**31**

votes

**1**answer

1k views

### Probably true, but provably unprovable

I'm wondering if anyone has found, or can find, a sequence of statements $P(n)$ ($n \in \mathbb{N}$) such that:
Heuristic arguments using probability theory suggest that all the statements $P(n)$ are ...

**9**

votes

**0**answers

319 views

### What happens when you iterate Cohen reals?

There are a few classical theorems in set theory:
The finite support iteration of ccc forcing is ccc.
The countable support iteration of proper forcing is proper.
The finite support iteration of ...

**8**

votes

**1**answer

169 views

### Is there a version of the “infinitary” disjunctive normal form theorem for topoi and slice categories?

According to nLab
Proposition 2.3. A complete Boolean algebra is completely distributive iff it is atomic (a CABA), i.e., is a power set as a Boolean algebra.
This is basically an infinitary ...

**10**

votes

**1**answer

316 views

### Looking for “Set theory for a small universe” by Ketonen

In the paper Partition theorems for systems of finite subsets of integers, Pudlák and Rödl show a Ramsey-type result. The main feature of this result is that the sizes of sets in such systems are not ...

**0**

votes

**0**answers

80 views

### Formula orderings in infinite propositional logic and existence of minimum

Let $PS$ be a countable set of propositional variables and $L_{PS}$ be the standard propositional language on $PS$.
Let $E \subseteq L_{PS}$. Let us call $E$ a pseudo-cover iff (i) all formulas of $E$ ...

**13**

votes

**1**answer

353 views

### reverse mathematics of the Lebesgue measurability of analytic sets

Can the fact that all analytic sets are Lebesgue measurable be proven in $Z_2$, or in some weak subsystem such as $\Pi^1_1\text{-CA}_0$? Conversely, can certain set existence axioms be derived from ...

**10**

votes

**0**answers

143 views

### stationary reflection in $[\kappa]^\omega$

It is well-known that the following reflection principle is consistent relative to a supercompact:
For all $\kappa \geq \omega_2$ and all stationary $S \subseteq [\kappa]^\omega$, there is $X \...

**6**

votes

**0**answers

142 views

### Singular strong generator

Let $V$ be a model of $\mathrm{ZFC}$ and let $j\colon V \to M$ be an elementary embedding with a critical point $\kappa$ ($M$ is transitive). A strong generator of $j$ is an ordinal $\zeta \geq \kappa$...

**3**

votes

**1**answer

101 views

### Function $f:\kappa\to\alpha$ with small fibers where $\alpha\in\kappa$

Is it consistent in $\mathsf{ZF}$ that there is an infinite cardinal $\kappa$, cardinals $\alpha, \beta\in\kappa$ and a function $f:\kappa\to \alpha$ such that for each $x\in\alpha$ there is an ...

**3**

votes

**1**answer

127 views

### What is the dual of generating Boolean subalgebra by subexpressions of a modal formula?

I am supposed to be answering this question rather than asking it but I really cannot figure out.
There is a variation on Stone duality linking algebraic and (descriptive) Kripke semantics for (...

**14**

votes

**0**answers

276 views

### O-minimality and forcing

It is well-known that the structure $(\mathbb{R}, +, \cdot, <, 0, 1)$ is an o-minimal structure and hence the set of integers $\mathbb{Z}$ is not definable in it.
In an ongoing project with Will ...

**4**

votes

**1**answer

106 views

### Characterizing “bounded” distributivity in terms of dense open sets

Prikry forcing is a well-known example of a forcing which adds an $\omega$-sequence to some cardinal $\kappa$, but does not add bounded subsets to $\kappa$.
There are other examples of forcings which ...

**4**

votes

**1**answer

251 views

### bijections and order types

Suppose $\kappa$ is an infinite cardinal and $\alpha$ is an ordinal of cardinality $\kappa$. Is it possible to find a bijection $f : \kappa \to \alpha$ such that for all $x \subseteq\kappa$, $\mathrm{...

**1**

vote

**2**answers

160 views

### Does Regularity schema imply $\in$-induction when added to first order Zermelo set theory?

That $\in$-induction fails to be a theorem schema of first order Zermelo + Foundation (see here), then it appears that it is more eligible to replace axiom of Regularity (Foundation) by a Regularity ...

**8**

votes

**0**answers

129 views

### Is there an expansion of $(\mathbb{N},+,<)$ by a pairing function that is still NIP?

I was told once that there is a theory consisting of just a pairing function that is stable, although I cannot find a reference for it. This motivated my question, which is essentially the title, ...

**1**

vote

**1**answer

154 views

### The continuum hypothesis and the diamond principle for $\aleph_1$

In [S. Shelah. Uncountable constructions for B.A. e.c. groups and Banach spaces. Israel J. Math. 51 (1985), 273-297], the existence of a special Banach space is proved, assuming the diamond principle ...

**2**

votes

**1**answer

239 views

### Is $\in$-induction provable in first order Zermelo set theory?

Are there models of first order Zermelo set theory (axiomatized by: Extensionaity, Foundation, empty set, pairing, set union, power, Separation, infinity) in which $\in$-induction fail?
I asked this ...