Tagged Questions

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)

14
votes
6answers
2k views

What “forces” us to accept large cardinal axioms?

Large cardinal axioms are not provable using usual mathematical tools (developed in $\text{ZFC}$). Their non-existence is consistent with axioms of usual mathematics. It is provable that some of ...
3
votes
2answers
212 views

Sufficient Condition for Defining $\in$

Consider the first order language $\mathcal{L}=\{\in,\in'\}$ with two binary relational symbols $\in , \in'$ and $ZFC$ as a $\{\in\}$-theory. If we define $\in'$ using $\{\in\}$-formula $\varphi(x,y)$ ...
1
vote
1answer
220 views

A Special Pair of Formulas

Consider the first order language ‎$‎‎‎\mathcal{L}=\{\in,\subseteq\}‎$ and ‎$‎‎\{\in\}$-theory ‎$\text{ZFC}$.‎ ‎Is ‎the‎re a formula ‎$‎‎\psi ‎(x,y)‎ \in \{\subseteq\}-Form‎$ ‎with ‎the ‎following ...
27
votes
1answer
822 views

Is there a computable ordinal encoding the proof strength of ZF? Is it knowable?

In comments on Quora (see, for example, here, here, here), Ron Maimon has repeatedly expressed the strong opinion that Hilbert's program was not killed by Gödel's results in the way typically ...
10
votes
2answers
597 views

Questions about Prikry forcing and Cohen forcing

I have some questions. The first one is about the product of Prikry's forcing. Let $\kappa$ be a measurable cardinal, $U_1, U_2$ be normal measures on $\kappa$ and let $\mathbb{P}_{U_1}, ...
6
votes
1answer
217 views

Sets of cardinalities of bases without choice

For a vector space $V$, let $BS(V)$ be the set of cardinalities (not necessarily $\aleph$s) of bases of $V$. Of course, in ZFC each $BS(V)$ is a singleton, but supposing the axiom of choice fails, it ...
9
votes
1answer
293 views

Inner model in which every uncountable cardinal is large

The following is known: $(*)$ If $0^\sharp$ exists, then any uncountable cardinal is is an inaccessible cardinal (and even more) in $L$. My question is that: Are there any large cardinal ...
3
votes
1answer
157 views

Proof of existence of recursively inaccessible and Mahlo ordinals

As in title - I'm looking for a proof of the existence of a countable recursively inaccessible or recursively Mahlo ordinals, especially the first one. When looking for it in all the papers I stumbled ...
4
votes
0answers
186 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 ...
10
votes
0answers
250 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 ...
1
vote
2answers
172 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 ...
10
votes
1answer
339 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 ...
12
votes
0answers
563 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 ...
14
votes
2answers
475 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
3answers
367 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 ...
3
votes
1answer
369 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 ...
3
votes
2answers
188 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 ...
2
votes
1answer
227 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 ...
5
votes
1answer
224 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
441 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, +, ...
5
votes
4answers
252 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
147 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?
4
votes
2answers
291 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 ...
13
votes
0answers
568 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 ...
1
vote
0answers
194 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 ...
4
votes
0answers
76 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 ...
2
votes
0answers
68 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 ...
5
votes
6answers
692 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 ...
8
votes
2answers
311 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, ...
8
votes
1answer
282 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 ...
3
votes
1answer
129 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 ...
6
votes
1answer
246 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 ...
12
votes
0answers
286 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 ...
6
votes
2answers
231 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 ...
1
vote
0answers
56 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
246 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
97 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: ...
2
votes
0answers
115 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 ...
6
votes
1answer
184 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 ...
4
votes
1answer
149 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, ...
1
vote
0answers
39 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 ...
4
votes
0answers
100 views

Relation between fundamental theorem of Ehrenfeucht-Fraisse games and notions of bisimulation and simulation

Vijay D alluded to the relation between the fundamental theorem of Ehrenfeucht-Fraisse games and notions of bisimulation and simulation in response to the whats-a-magical-theorem-in-logic question. ...
9
votes
3answers
352 views

Is a model of arithmetic contained in a model of arithmetic an initial segment?

It's easy enough to show that if $\mathbb{N}_1$ is a non-standard model of the Peano axioms, then there is a canonical embedding $\mathbb{N} \to \mathbb{N}_1$, and we have a theorem that if $x \in ...
7
votes
3answers
371 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 ...
16
votes
2answers
470 views

Is the notion of fixed point property for topological spaces an absolute notion?

Recall that a topological space $X$ has the fixed point property (FPP) if any continuous function $f: X\to X$ has a fixed point. Is the notion of FPP for topological spaces an absolute notion? More ...
3
votes
0answers
51 views

A question on the incompleteness of quantified K.2 and S4.2 with the Barcan formula

I have been attempting to come to grips with Max Cresswell's account of this in Journal of Philosophical Logic 24 (4):379 - 403 (1995) where he presents proofs of the incompleteness of QK.2BF as well ...
7
votes
0answers
339 views

Is there a theory of abuse of notation? [closed]

Is there any theory about the different ways notation can be abused and which abuses are ineliminable without complicating the notation in some essential way? We can define "abuse of notation" as any ...
1
vote
2answers
240 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 ...
2
votes
1answer
122 views

A question on the modal logic S4.2

The modal logic S4.2 with the characteristic axioms 4: $\square \alpha \rightarrow \square \square \alpha$ and .2: $\lozenge \square \alpha \rightarrow \square \lozenge \alpha$ and T: ...
10
votes
0answers
156 views

Maximality of linear orders in the Keisler order on theories

Recently Malliaris and Shelah (see their preprint http://math.uchicago.edu/~mem/Malliaris-Shelah-CST.pdf) have shown that theories with $SOP_2$ are maximal in the Keisler order. A preceding result of ...