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)

8
votes
1answer
276 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
124 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
237 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
282 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
228 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
53 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
241 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
89 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
113 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
180 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
146 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
37 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
97 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
351 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
355 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
463 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
49 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
329 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
238 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
111 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
150 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
1answer
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
1answer
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
1answer
372 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
2answers
460 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
3answers
607 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
1answer
194 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
5answers
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
0answers
143 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
3answers
595 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
1answer
224 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
1answer
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
0answers
104 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
1answer
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
1answer
215 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
1answer
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
1answer
476 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
1answer
115 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
2answers
456 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
1answer
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
1answer
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
1answer
120 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
4answers
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
0answers
58 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
1answer
188 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
0answers
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
3answers
857 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
1answer
137 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
1answer
191 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
1answer
182 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 ...