**4**

votes

**0**answers

95 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

322 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

**2**answers

237 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

**1**answer

93 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

**0**answers

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

**5**

votes

**1**answer

116 views

### Attribution of an equivalence of the existence of omega-models of RCA0

There are many well-known equivalences in reverse mathematics between statements of the form "Every set is contained a countable coded $\omega$-model of $T$" and $S$, where $S, T$ are subsystems of ...

**6**

votes

**1**answer

161 views

### Is (Z,+,0,1,P2,P3) decidable?

Is Presburger arithmetic, augmented with two unary predicates P2, P3, for powers of 2 and powers of 3 respectively, decidable?
I know that adding just one of P2, P3 to Presburger keeps it decidable, ...

**1**

vote

**1**answer

365 views

### Compactness and completeness in Gödel logic

The standard proof of the completeness theorem in first-order Gödel logic is based
on a first-order countable language. I want to know that is there any proof of the completeness theorem in ...

**16**

votes

**2**answers

452 views

### Internal logic of the topos of simplicial sets

I am looking for a closed statement (i.e. not depending on any parameter objects) which is true in the internal logic of the topos of simplicial sets, but is not an intuitionistic tautology. Ideally, ...

**8**

votes

**3**answers

604 views

### What set theoretical questions could never be answered by Turing machines of arbitrary cardinality?

Let us assume that there are Turing machines of arbitrary cardinality, by that I mean they can have input tapes of any arbitrarily high cardinality and compute for a number of steps also of ...

**12**

votes

**1**answer

189 views

### Nontrivial upper bounds on proof-theoretic ordinals of strong theories: do we have any?

Motivated by Consistency of Analysis (second order arithmetic) and Proof-Theoretic Ordinal of ZFC or Consistent ZFC Extensions?, I have the following question:
Are there any examples of strong ...

**8**

votes

**5**answers

2k views

### Interesting meta-meta-mathematical theorems?

The Goedel incompleteness theorems can be considered meta-mathematical theorems, as they are "written" in a meta-theory and "talk" about properties of a class of formal theories.
The following may be ...

**3**

votes

**0**answers

142 views

### Equational theories determined by “identities without variables”

How to characterize equational theories $T$ which have the following property: for any two terms $t(x_1,...,x_n)$ and $t'(x_1,...,x_n)$ in the signature of $T$, if for any closed terms (i. e. terms ...

**8**

votes

**3**answers

585 views

### Consistency of Analysis (second order arithmetic)

Is there a proof of the consistency of Analysis (second order arithmetic), which is similar to Gentzen's proof of the consistency of arithmetic?
Update:
Which (different) methods can be used to ...

**3**

votes

**1**answer

218 views

### Colorful model theory

There are a number of concepts in model theory - often situated around Hrushovski's amalgamation method (see for instance http://math.univ-lyon1.fr/~wagner/nijmegen.pdf) - which are colorfully named:
...

**4**

votes

**1**answer

217 views

### Perfect set property implies $\omega_1$ is a limit cardinal in $L$

Specker proved in 1957 that if in $V$ every set of real numbers has the perfect set property, than in $L$, $\omega_1^V$ is actually a limit cardinal.
The original proof is in German, and I've been ...

**2**

votes

**0**answers

102 views

### Does the Lévy collapse obey this nice characterization? [duplicate]

This question is related to an issue in my answer to Monroe Eskew's question on the failure of Cantor-Bernstein for the Lévy collapse.
Question. Is the Lévy collapse $\text{Coll}(\omega,\lt\kappa)$ ...

**6**

votes

**1**answer

170 views

### Failure of Cantor-Bernstein for the Levy Collapse

Related to this question, is it possible to give an example of the failure of Cantor-Bernstein for complete embeddings of forcing notions involving the Levy Collapse $Col(\omega,<\kappa)$? Suppose ...

**5**

votes

**1**answer

214 views

### A model of Krivine

In a paper by J.-L. Krivine, Modèles de ZF+AC dans lesquels tout ensemble de réels définissable en termes d'ordinaux est mesurable-Lebesgue [C. R. Acad. Sci. Paris Sér. A-B 269 (1969), A549–A552, ...

**5**

votes

**1**answer

157 views

### What do algebraic theories with strictly terminal trivial models look like?

By algebraic theory I mean one in the sense of Lawvere, i.e. a collection of finitary operations, including projections, together with a multi-composition satisfying the obvious axioms. (I believe ...

**7**

votes

**1**answer

475 views

### Starting Hilbert's Program on the other end

The idea of Hilbert's program was to start with a simple finitary logic and proof the consistency of more complex systems in this system. Of course, this turned out to be problematic. Even when ...

**4**

votes

**1**answer

112 views

### Replace Morley sequence over some set by one over a finite set, s.t. they both satiesfy a certain formula

Let $T$ be a stable $L$-theory with elimination of imaginaries. We work in the monster model $\mathfrak C$ of $T$. Let $A$ be a small (infinite) set of the monster, $\phi(x,y)$ be a $L(A)$-formula and ...

**7**

votes

**2**answers

454 views

### What is the name of this type of groups?

Suppose $A$ is a finite set and $\Sigma=A\cup A^{-1}$. Let $L\subseteq \Sigma^{\ast}$ be a regular language on the alphabet $\Sigma$. Is there a common name for the group $G$ presented as:
$$G=\langle ...

**4**

votes

**1**answer

194 views

### Is Van der Waerden's function elementary

Van der Waerden's function was proved to have elementary upper bound on growth rate.
Is the Van der Waerden's function itself elementary in the sense of Kalmar?

**2**

votes

**1**answer

242 views

### Expressive power of first-order category theory

Given the signature $\lbrace \mathsf{dom}, \mathsf{cod}, \mathsf{id},\circ \rbrace$ and the axioms of category theory – which are expressible in the signature's first-order (FO) language – ...

**2**

votes

**1**answer

119 views

### How many elementary equivalent models are unifiable by ultrapower?

Definition. A class $\mathcal{C}$ of pairwise elementary equivalent $\mathcal{L}$-structures is unifiable by ultrapower if there is an index set $I$ and an ultrafilter $F$ on it such that $\forall ...

**9**

votes

**4**answers

1k views

### Are there non-diagonal proofs for Cantor's continuum and Godel's incompletness theorems?

There is a formal definition for the notion of a formal proof.
Question 1. Is there any formal definition for the notion of a diagonal formal proof?
Consider the following theorems both proved by ...

**1**

vote

**0**answers

57 views

### First-order Peano Axioms and order-completeness of $\mathbb{N}$ [closed]

Definition: An ordered set is order-complete if any nonempty subset with an upper bound, has a lowest upper bound or supremo.
Notation: We denote the system of first-order Peano Axioms (along with ...

**9**

votes

**1**answer

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

**9**

votes

**0**answers

161 views

### Reverse mathematics of meromorphic functions on Riemann surfaces

Various sources touch briefly on the reverse mathematics of measure theory and complex analysis. But I have found none on the uniformization theorem for Riemann surfaces or the existence of ...

**10**

votes

**3**answers

850 views

### Is it ever a good idea to use Keisler-Shelah to show elementary equivalence?

The most useful way I know to show that two structures are elementarily equivalent is Ehrenfeucht-Fraisse games. These are quite nice and intuitive, and even when I can't use them to solve my problem ...

**4**

votes

**1**answer

136 views

### Finite generation of vector identities

This question is partially motivated by Looking for a comprehensive referece for vector identities, although that question may not be appropriate for MO.
Consider the set $\mathcal{E}$ of all valid ...

**5**

votes

**1**answer

189 views

### A ZFC construction to get a proper extension which is a $\omega_1$-model

In $V$, let me call a set theory structure A is a $\omega_1$ model if the $\omega_1$ of $A$ is the same as the $\omega_1$ in $V$ (up to isomorphism). The question I would like to ask is the following: ...

**6**

votes

**1**answer

176 views

### Skolem Hulls in $H_{\omega_2}$

I put this on stack exchange over a week ago with no answer, so let's try here.
Consider a model of the form $\mathfrak{A} = (H_{\omega_2}, \in, \lhd, f_0, f_1, ...)$, some expansion of ...

**-2**

votes

**1**answer

183 views

### Natural constructions (not depending on parameters) [closed]

Consider graph clusterings as a prototypical example of (logical) constructions.
Let a clustering of a graph $(V,E)$ be any covering of $V$, i.e. a set $C$ with $\bigcup C = V$.
I am looking for a ...

**8**

votes

**2**answers

232 views

### Vaught's conjecture for partial orders

In
``Steel, John R. On Vaught's conjecture. Cabal Seminar 76–77, pp. 193–208''
the following is proved:
Theorem. Let $\phi\in L_{\omega_1,\omega}.$ If every model of $\phi$ is a tree, then $\phi$ has ...

**9**

votes

**3**answers

331 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

**3**answers

344 views

### Can a Decidable Theory Have Non-recursive Models?

Tennenbaums' theorem proves neither addition nor multiplication can be recursive in any countable non-standard model of arithmetic. Tennenbaum's proof applies to theories much weaker than PA.
...

**4**

votes

**2**answers

289 views

### Forcing for Arbitrary First Order Theories

Forcing is a relative model construction method for models of $ZF$ as a particular first order theory using models of another first order theory (forcing companion) that in this case is the theory of ...

**6**

votes

**2**answers

1k views

### Is Turing degree actually useful in real life? [closed]

In theoretical computer science, we classify problems according to their Turing degree. Is there any practical application of this?
Edit: Given that we cannot explicitly and mechanically understand ...

**5**

votes

**1**answer

141 views

### Intermediate submodels which do not satisfy AC

The following is known:
Theorem. Suppose $V[G]$ is a generic extension of $V$ by a set forcing, and let $N$ be a model of $ZFC$ with $V\subseteq N\subseteq V[G].$ Then $N$ is a generic extension of ...

**9**

votes

**4**answers

469 views

### Are there two computable binary trees such that each has a branch not computing any branch through the other?

It is a well-known elementary classical result in computability theory that there are computable infinite binary trees $T\subset 2^{<\omega}$ having no computable infinite branch. (One can build ...

**6**

votes

**0**answers

166 views

### When is a reduction not a reduction?

Every mathematician understands the concept of reducing a complicated problem to a simpler problem. "Without loss of generality, we may assume…" However, I've noticed that some kinds of ...

**4**

votes

**1**answer

203 views

### Computational approach deciding whether a set of Wang Tile could tile the space up to some size

As an applied person, I'm facing one practical problem deciding whether a set of Wang tile could tile the plane periodically or aperiodically. Although both problems seem undecidable, but I'm on a ...

**3**

votes

**3**answers

297 views

### Godel's Second Incompleteness theorem and Models

As I understand it, Godel's completeness theorem essentially says that if a sentence $\phi$ can be proven in a first order theory $\Gamma$, then $\phi$ is satisfied in all models $\mathcal{U}$ of ...

**2**

votes

**0**answers

167 views

### How many Dedekind-finite sets can $\mathbb{R}$ be partitioned into?

Building off Asaf Karagila's answer to my previous question (Can $\mathbb{R}$ be partitioned into dedekind-finite sets?) on partitioning $\mathbb{R}$ into strictly Dedekind-finite sets:
(1) What ...