# Tagged Questions

**2**

votes

**0**answers

101 views

### Graph theoretical representation of Wang Tile

We note that for one dimensional tiling problem of Wang Tile could be represented by a graph. Each cycle on the graph represents a periodic solution.
However, is there a well established counter-part ...

**10**

votes

**1**answer

322 views

### Does small forcing preserve CH?

Suppose CH holds and $\mathbb{P}$ is a poset of size $\omega_1$, such that forcing with $\mathbb{P}$ preserves $\omega_1$. Does forcing with $\mathbb{P}$ preserve CH? If $\mathbb{P}$ is proper then ...

**10**

votes

**0**answers

143 views

### Can Gentzen-style proofs give omega-consistency and beyond?

In 1936, Gentzen famously showed that Primitive Recursive Arithmetic, plus the assumption that the ordinal $\epsilon_0$ is well-founded, is able to prove Con(PA). But of course, Con(PA) doesn't yet ...

**14**

votes

**6**answers

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

**2**answers

209 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

**1**answer

220 views

### A Special Pair of Formulas

Consider the first order language $\mathcal{L}=\{\in,\subseteq\}$ and $\{\in\}$-theory $\text{ZFC}$. Is there a formula $\psi (x,y) \in \{\subseteq\}-Form$ with the following ...

**26**

votes

**1**answer

771 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

**2**answers

579 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

**1**answer

212 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

**1**answer

282 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

**1**answer

151 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

**0**answers

173 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

**0**answers

245 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

**2**answers

166 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

**1**answer

332 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

**0**answers

533 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

**2**answers

455 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

**3**answers

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

**4**

votes

**1**answer

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

**4**

votes

**2**answers

186 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

**1**answer

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

**1**answer

215 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

**2**answers

429 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

**4**answers

233 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

**1**answer

144 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?

**3**

votes

**1**answer

143 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

**0**answers

562 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

**0**answers

99 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

**0**answers

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

**0**answers

64 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

**6**answers

641 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

**2**answers

294 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

**1**answer

275 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

**1**answer

122 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

**1**answer

236 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

**0**answers

281 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

**2**answers

227 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

**0**answers

44 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

**1**answer

239 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

**1**answer

87 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

**0**answers

112 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

**1**answer

165 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

**1**answer

142 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

**0**answers

27 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

**0**answers

94 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

**3**answers

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

**6**

votes

**3**answers

345 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

**2**answers

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

**1**

vote

**0**answers

42 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

**0**answers

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