Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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

1
vote
0answers
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
0answers
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
0answers
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
1answer
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
1answer
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
0answers
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
1answer
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
1answer
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
0answers
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
0answers
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
0answers
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
0answers
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
1answer
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
2answers
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
0answers
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
3answers
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
1answer
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
0answers
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
2answers
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
1answer
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
0answers
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
0answers
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
0answers
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
0answers
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
1answer
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
2answers
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
1answer
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
0answers
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
1answer
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
1answer
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
0answers
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
1answer
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
0answers
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
0answers
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
1answer
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
1answer
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
0answers
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
1answer
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
1answer
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
2answers
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
0answers
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
1answer
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
1answer
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 ...