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, theories of truth, truth revision, consistency.

0
votes
0answers
110 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
264 views

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 ...
1
vote
1answer
117 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
225 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
594 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 ...
9
votes
3answers
673 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
401 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
133 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
233 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
2answers
228 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
189 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
294 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
146 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
141 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
111 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
180 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
495 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
503 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
128 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
135 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
56 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
370 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
695 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
334 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
195 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
332 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
84 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
362 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
150 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
132 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
288 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 ...
5
votes
2answers
202 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
257 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
161 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
135 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
155 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
244 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 ...
5
votes
0answers
115 views

Natural examples of recursive pseudowellorderings

Question: What are some natural examples of recursive pseudowellorderings? By natural, I mean in the style of reasonable ordinal notation systems as opposed to dependent on a Gödel numbering or an ...
4
votes
0answers
141 views

Ordinal analysis and nonrecursive ordinals

Ordinal analysis is typically described as characterizing recursive ordinals in a theory $T$, but there is a sense in which it can characterize all $T$-ordinals, even those that are nonrecursive. ...
5
votes
1answer
257 views

Progress towards a computational interpretation of the univalence axiom?

I will preface this by saying that I am not an expert on type theory. I am just a curious outsider slowly making my way through the HoTT book when I (rarely) have some spare time. I am just curious ...
10
votes
1answer
789 views

Relation between the Axiom of Choice and a the existence of a hyperplane not containing a vector

In a lot of problems in linear algebra one uses the existence, for each $E$ vector space over a field $k$, and each $x\in E$, of a Hyperplane $H$ such that $E=k\cdot x \oplus H$ (Let us denote $\...
0
votes
0answers
226 views

Is there a known shorter axiomatization of NF than this?

Is there an already known axiomtization of $NF$ that is shorter than the following axiomatic system in first order logic with equality $``="$ and membership $``\in"$? And what is exactly meant by ...
1
vote
1answer
83 views

Reduction of the predicate calculus to the propositional calculus in the case of one sigle object in the universe? [closed]

To what extent is it possible to formally susbstantiate the following affirmation that: "In a classical first order logical universe with exactly one unique and single object, the predicate calculus ...
3
votes
0answers
117 views

If any satisfiable $\mathcal{L}_{κ,κ}(Q_{=κ})$-theory remains satisfiable when replacing $Q_{=κ}$ with $Q_{=μ}$, is $κ$ huge?

Recently, I have asked a model-theoretic question concerning a weakening of different forms of compactness. I now present another model-theoretic question as a weakening of hugeness. If any ...
7
votes
1answer
234 views

Can we inductively define Wadge-well-foundedness?

For a topological space $X$ (which I'll identify with its underlying set of points), we define the Wadge preorder $Wadge(X)$: elements of the preorder are subsets of $X$, and the ordering is given by $...
0
votes
0answers
74 views

Functoriality of indiscernible sequences

Let $T$ be a first order theory of, say, some type of combinatorial geometries which contain indiscernible sequences of points. Let $(\Gamma,\mathcal{O})$ be a model of $T$, where $\Gamma$ is the ...
2
votes
0answers
95 views

Lengths of proofs and quasilinear time

Length of proofs depends not only on the theory but also on its axiomatization. Once an axiomatization is fixed, typical proof systems are equivalent up to a polynomial factor. But what if we care ...