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

learn more… | top users | synonyms (1)

4
votes
0answers
62 views

$\infty$-Borel Determinacy?

An $\infty$-Borel set is a set $X\subseteq\mathbb{R}$ which has an $\infty$-Borel code - a set $r$ coding the construction of $X$ via open sets, complementation, and well-ordered unions (see ...
13
votes
1answer
335 views

Random reals and strongly meager sets

Adding a single Cohen real makes the set of reals from the ground model strong measure zero (see this question). The notion of strong measure zero sets has its dual concept in the category branch -- ...
8
votes
0answers
184 views

cardinals below the critical point of a generic embedding

This may be an easy question. Are the cardinals below the critical point of a precipitous ideal embedding always absolute between the generic ultrapower and the generic extension? To focus on the ...
27
votes
3answers
2k views
+100

For which Millennium Problems does undecidable -> true?

Bounty  This question having gone unanswered for (more than) one year, and in the light-hearted spirit of this week Dick Lipton and Ken Regan Gödel's Lost Letter weblog "Multiple-Credit ...
5
votes
0answers
332 views

Different approaches to the multiverse of sets

There are some different approaches to the multiverse of sets, in particular: 1) The approach by Woodin, 2) The approach by Sy Friedman, ..., 3) The approach by Hamkins. I wonder to know if ...
1
vote
2answers
125 views

Is there an intuitionistic generalized boolean algebra (of Stone)?

A "boolean algebra without the greatest element" was called by Stone "generalized boolean algebra" and he axiomatized it. Is there any publication about "preudo-boolean algebras without the greatest ...
2
votes
1answer
216 views

A variant of Kruskal's theorem

For $X$ and $Y$ finite sequences of finite trees, let us say that $X$ is everywhere contained in $Y$ ($X\subseteq_{ec}Y$) iff, for every $y\in Y$, there is some $x\in X$ such that $x$ is a minor of ...
46
votes
12answers
8k views

Logic in mathematics and philosophy

What are the relations between logic as an area of (modern) philosophy and mathematical logic. The world "modern" refers to 20th century and later, and I am curious mainly about the second half of ...
9
votes
1answer
288 views

Applications of SCH outside of set theory

Recall that the Singular Cardinals Hypothesis (SCH) says that if $\kappa$ is a singular cardinal and $2^{cf(\kappa)}<\kappa,$ then $\kappa^{cf(\kappa)}=\kappa^+.$ Clearly it has many applications ...
-4
votes
0answers
88 views

Logic and mathematics [closed]

If we have two persons, the first's length = 8, and the second 's length = 2, now if the first looked to the second , then the perception of the first to the second should be that the second is more ...
1
vote
2answers
217 views

Infinite play with tape, or covering the integers with prime arithmetic progressions

It is possible that a more technical version of this question has been asked and answered in the literature. If so, then a reference is much appreciated. I will phrase it in terms of colored tapes ...
11
votes
0answers
289 views

Does every Aronszajn tree has a Suslin or a Special subtree?

Question: Does every $\omega_1$-Aronszajn tree contains a Suslin sub-tree or a special Aronszajn sub-tree? Recall that Suslin trees are $\omega_1$-trees (trees of height $\omega_1$, and countable ...
6
votes
3answers
251 views

Decidability of the winning-position problem in an infinity chess with a finite number of short-range pieces only

Definitions Long-range pieces: queens, rooks, bishops. Short-range pieces: pawns, knights, kings. We can extend the definition of short-range pieces to include also fairy pieces like: Berolina ...
0
votes
0answers
120 views

Standard satisfiability for sentences in the language of ordered Abelian groups! [closed]

Consider $\mathcal{L}$ as the language of ordered Abelian groups. Let $\varphi$ be an $\mathcal{L}$-sentence in first-order logic. (According to comments I modify the question. The original one is ...
4
votes
3answers
320 views

Systematic brute-force searches for counterexamples

This is getting nowhere on math.stackexchange.com, so I'm putting it here. Gödel's completeness theorem says that for every statement in first-order predicate calculus with equality, there is either ...
14
votes
2answers
381 views

Pathological behavior of Borel sets?

Usually in set theory, Borel sets are much more nicely behaved than arbitrary sets of reals. One reason for this is Borel determinacy, which immediately yields measurability, Baireness, and the ...
4
votes
1answer
288 views

Application of Combinatorics, Logic and computability theory in physical science: Tiling of Wang Tile with proportionality

The original problem of Domino Tiling and Wang Tile has great theoretical interest on computability theory... However, the great emerging problem on application of Wang Tile in material science and ...
6
votes
2answers
337 views

How big $|Aut(M)|$ can be, given $|\partial Aut(M)|$?

My apologies: There were a couple of typos in the original question. Hope I got them all. Let $\kappa$ be an uncountable cardinal of cofinality $\omega$ and $M$ a model of size $\kappa$. We equip ...
18
votes
8answers
2k views

Connections between ultrafilters in topology and logic

I have a some-what vague question. It seems to me that there are two main ways in which ultrafilters (on a set) can be used. One is in topology. The notion of an ultrafilter converging to a point is ...
0
votes
0answers
12 views

the lexicographix order [migrated]

If it is given ordinals $\alpha$ and $\beta$, the lexicographix order on $\alpha \times \beta$,$\leq_{lex}$ is given by: $(\gamma_0,\delta_0)<_lex(\gamma_1,\delta_1)$ if and only if either ...
8
votes
3answers
296 views

Conjecture on NP-completeness of tesselation of Wang Tile up to finite size

Motivated by these following questions on tessellation: coloring in lattice Reference for Wang Tile Computational approach deciding whether a set of Wang Tile could tile the space up to some size ...
2
votes
1answer
95 views

Conjecture of a subset of Wang tile which might be decidable

From the two papers proving the undecidability of Wang tile in 1966 by Berger and in 1971 by RM Robinson, the tiles used in proving undecidability has a general common feature: The left color and ...
5
votes
1answer
188 views

Interaction between Turing and many-one reducibility

This is a question about two reducibility notions in computability theory. I suspect the answer is a fairly simple construction, and I'm just not seeing it. For sets $X, Y\subseteq\omega$, we say $X$ ...
9
votes
2answers
373 views

What is the precise notion of “enough arithmetic” in Godel's first Incompleteness theorem?

I'm trying to reconstruct the proof of Godel's first theorem (Rosser's strong version) from the uncomputability of the Halting function. If we just started with the language $\mathcal{L}=\{0, S, +, ...
1
vote
1answer
130 views

Bondarchuk, Kaluznin, Kotov, Romov’s Theorem on inclusion of Polymorphism ($Pol \rho \subseteq Pol \sigma$)

Bondarchuk, Kaluznin, Kotov, Romov’s paper [1] is well-known. Anne Fearnley [2] infered from it the following theroem and used it to prove the inclusion of polymorphisms. Theorem (Bondarchuk, ...
5
votes
4answers
182 views

Is every Heyting algebra the Lindenbaum algebra of an intuitionistic first order theory?

This question comes after the comments in the recent related question Sigma-complete Lindenbaum algebras?, but in its current form is sufficiently different in my opinion, and so I decided to follow ...
2
votes
1answer
131 views

Sigma-complete Lindenbaum algebras? [closed]

Is there any calculus whose algebraization is a sigma-complete Lindenbaum algebra, i.e., a sigma-complete Boolean algebra after identification of equivalent formulas?
9
votes
0answers
207 views

Souslin trees and weakly compact cardinals

In Souslin trees on the first inaccessible cardinal it is asked if it is consistent that there are no $\kappa-$Souslin trees at the least inaccessible cardinal $\kappa$. In this question I would like ...
23
votes
3answers
728 views

Does every set of reals contain a measure-zero set of the same cardinality? Does it contain a meager set of the same cardinality?

This question arises from an issue in my post on Ashutosh's excellent question on Restrictions of the null/meager ideal. Question 1. Does every set of reals contain a measure-zero subset of the same ...
3
votes
1answer
125 views

On a modal correspondence

Is there an intuitive characterization of the correspondence for the modal logical formula $\square (\alpha \rightarrow \square \alpha) \rightarrow (\square \alpha \vee \square \lnot \alpha)$? In ...
1
vote
0answers
91 views

On directedness, transitivity and ancestral directedness

Let $\textit{C}$ be the modal logical schema $(\square (\square \alpha \rightarrow \alpha) \wedge \square (\square \lnot\alpha \rightarrow \lnot \alpha))\rightarrow (\square \alpha \vee \square \lnot ...
8
votes
2answers
244 views

The (non-)absoluteness of second-order elementary equivalence

Elementary equivalence is set-theoretically absolute between any two transitive models of set theory; this is also true for the infinitary logics - e.g., $\mathcal{L}_{\omega_1\omega}$ - at least, ...
4
votes
0answers
64 views

$n$th order arithmetic with predicates for orders

Two papers I have looked at lately axiomatize $n$-th order arithmetic in a single sorted language with predicates $Z_1,\dots,Z_n$ and axioms like $\forall x(Z_1(x)\vee\dots\vee Z_n(x))$ to say ...
6
votes
5answers
514 views

practical algorithms for np complete problems

Inspired by: Conjecture on NP-completeness of tesselation of Wang Tile up to finite size And the practicality of this topic (solving tessellation on a lattice): coloring in lattice Computational ...
9
votes
1answer
172 views

Obtaining a lightface pointclass from a boldface one

Define a pointclass to be: boldface inductive-like if it is $\mathbb{R}$-parameterized, has the scale property, and is closed under $\wedge$, $\vee$, $\forall^\mathbb{R}$, $\exists^\mathbb{R}$, and ...
2
votes
0answers
58 views

Algorithmic quantifier elimination over p-adic fields

It is known that the first-order theory of p-adic fields is decidable, and that the p-adics admit elimination of quantifiers. What is the state of the art in algorithmic aspects of quantifier ...
6
votes
0answers
131 views

Canonical model for $\neg\mathsf{CH}$ and $\Omega$-logic

Recently I found this book by Woodin. In the introduction of it the author writes the following: The main result of this book is the identification of a canonical model in which the Continuum ...
11
votes
0answers
256 views

Do all linear orders in this class have computable copies?

This is a question which has been bothering me now for quite some time. I've talked to a number of people about it, and we've shown that a few basic ideas can't work, but other than that haven't made ...
3
votes
1answer
107 views

How do you prove that Q+Con(PA) can't be interpreted in ACA_0?

The theory $\mathrm{ACA}_0$ is not reflexive (because it is finitely axiomatisable and cannot prove its own consistency). So how, if at all, is it possible to prove that $\mathrm{Q+Con(PA)}$ cannot be ...
13
votes
4answers
994 views

Decidability of tiling R^2

Does there exist a closed curve, with finite area and finite circumference, of which it is undecidable (in an axiomatic system where it is constructable) whether it can tile the plane? I know the ...
2
votes
1answer
118 views

On the Combinatorial Classification of Modal Kripke Frames

We have that S5 modal logic is characterized by the modal axioms $K$, $M$ (reflexive), $4$ (transitive), and $B$ (symmetric). That is, an equivalence relation on a set of possible world (which can be ...
6
votes
0answers
128 views

Does the totality of Ackermann's function prove the consistency of $\Sigma_1$-induction?

It is well known that Ackermann's function is not primitive recursive. Therefore, the theories of primitive recursive arithmetic (PRA) and of $\Sigma_1$-induction ($I\Sigma_1$) cannot prove the ...
6
votes
2answers
196 views

Is every non-recursive set in $\Sigma_1$ complete in $\Sigma_1$ (relatively to many-to-one reductions)?

Most well known sets in $\Sigma_1 \setminus\Delta_0$, such as the Halting problem, are complete in $\Sigma_1$, relatively to the many-to-one reduction. In fact I don't know any example of a (non ...
0
votes
0answers
35 views

A question on completeness for quantified temporal logics

Quantified temporal logics have the Barcan formulas and its converses for both G (it will always be the case that) and H (it has always been the case that), so that both $\forall x G \alpha ...
5
votes
1answer
227 views

Woodin Cardinals and Inner Models

I have a few questions I have been thinking about that I could definitely use some insights on: Question 1. Since a Woodin cardinal is a "local" notion, defined with respect to some rank-initial ...
0
votes
1answer
48 views

Preserving Predimension Functions under Functional Convergences

Definition 1. If ‎$‎‎‎\mathcal{L}‎$ ‎is a‎ ‎countable relational ‎language, ‎a ‎predimension ‎class ‎‎‎‎‎$‎C‎$ is a class ‎of $‎‎\mathcal{L}$-structures with ‎the ‎following ‎properties:‎ ‎C1: ...
4
votes
1answer
121 views

Stable examples from Algebra such that the model theoretic algebraic closure of a substructre is no model

Let $T$ be a stable theory. Let $A$ be a subset or substructure of a model $M$ of $T$. Now in some theories the (model theoretic) algebraic closure of $A$ is already a (sub)model of $T$. For example, ...
2
votes
0answers
99 views

Preimages of accessible full subcategories

My question is ultimately about the model theory of $L_{\infty, \omega}$, but it is more convenient to phrase it in terms of category theory. Suppose I have finitely accessible categories ...
5
votes
1answer
155 views

Is a computer program for correspondence theory available?

In the 1990s I some times used a computer program with the Max Planck Institute which helped with calculating complicated correspondences for modal logical formulas. Is some program like that ...
1
vote
0answers
23 views

Completeness results for quantified tense logics with BF?

Modal tense logics or temporal logics are important in that they correspond with partial orders and their extensions. Are there completeness results for quantified temporal logics with the Barcan ...