Model theory is the study of (classes of) mathematical structures (e.g. groups, fields, graphs, universes of set theory) using tools from mathematical logic. Objects of study in model theory are models for formal languages which are structures that give meaning to the sentences of these formal ...

learn more… | top users | synonyms

3
votes
1answer
36 views

Hodges exercise 2.7.1: Quantifier elimination in dense linear orderings

In Hodges' A Shorter Model Theory, exercise 2.7.1 tells you to prove theorem 2.7.1, which says that the following five formulas are an elimination $\Phi$ set for the class of all dense linear ...
3
votes
1answer
34 views

two different realization of one type

Im having trouble solving this problem: Let $M$ be a saturated structure of cardinality $\kappa$. Let $A\subseteq |M|$ with $|A|<\kappa$. Then there is a type $p\in S_1(A)$ with two different ...
3
votes
2answers
82 views

What does the theory of the empty set look like?

I know next to nothing about logic, but I was wondering what first order axioms would give rise to the theory of the empty set (that is to a theory whose only model is the empty set)? The problem I ...
6
votes
1answer
138 views

Detecting incomparability in countable elementary submodel

This might be just an easy exercise in model theory but I can't seem to wrap my head around right now. Let $\theta$ be large enough regular cardinal and $\kappa < \theta$. $(\kappa, \prec)$ is ...
3
votes
2answers
55 views

Quantifier elimination in infinitary languages

Let $L$ be a first order relational language with identity. Let $E$ be an $L$-structure. Let $L_{\alpha\beta}$ be the usual infinitary extension of $L$. Thus, $E$ is an $L_{\alpha\beta}$-structure ...
3
votes
1answer
22 views

satisfaction of a set in the expanded language

Consider a set $\Gamma$ of formula which is satisfiable in language $\mathcal{L}$. let $\mathcal{L'} \supseteq \mathcal{L}$ be any expansion. then is $\Gamma$ satisfiable in $\mathcal{L'}$? I can ...
4
votes
1answer
80 views

Elimination of quantifiers

What does it mean that a theory admits constructive elimination of quantifiers? A theory admits elimination of quantifiers when each formula of the theory is equivalent to a quanifier-free formula, ...
1
vote
2answers
37 views

bound and free variables

I have a question that has been bothering me for quite some time. In second order logic sometimes there is an indication that a variable can be both bound and free. The simplest example I can give is ...
7
votes
1answer
47 views

Why can't an $\omega$-stable theory have finitely many countable models?

This is a "well-known fact," but I'm at a loss to finding a proof. I could swear I've read it somewhere, but checking the handful of places I'm used to checking doesn't help. Google gives nothing, ...
0
votes
1answer
53 views

Prove that $K$ is finitely definable iff $K$ has finite support

Hi guys I need to prove a Finite Support Theorem which states that $K$ is finitely definable iff $K$ has finite support. Unfortunately I succeeded in proving only the first part of if and only if. ...
2
votes
1answer
46 views

Different models of complete theory modeled by ($\mathbb{N}$, $\leq$)

This is a homework excercise. I have a FO language $\mathcal{L}$ without identity ($"="$) with a binary predicate symbol $P$, an $\mathcal{L}$-structure $\mathcal{N}$ with ground set $ \mathbb{N}$ ...
9
votes
1answer
153 views

Models in set theory and continuum hypothesis

Some days ago I had the opportunity to listen to the talk about model theory and connections with algebra and geometry. I'm not at all specialist in this field so my question probably will be naive ...
1
vote
1answer
34 views

Prove that any countably incomplete ultraproduct of a collection of models is $\aleph_1$-saturated

I'm using this article for the proof. everything sounds well, but I don't think I have a proper comprehension on some (especially the final) parts. For example, what is the function $f$ doing at the ...
4
votes
1answer
44 views

Discussion on AC and countable unions of countable sets

My question stems from the comments following Asaf Karagila's answer here : Why can't you pick socks using coin flips? At some point there was a discussion about whether or not a countable union ...
3
votes
2answers
190 views

Is the number of orbits of the automorphism group of infinite field with a finite characteristic acting of the field is finite?

I am trying to solve some statement in Model theory. And if i can show that given an infinite field $\mathbb{F}$ with a finite character, then the number of orbits of $Aut(\mathbb{F})$ acting on ...
2
votes
1answer
49 views

What's wrong with my proof on “any countably incomplete ultraproduct of a collection of models is $\aleph_1$-saturated”?

I'm using this article for the proof. I thought some parts are extra and tried to make a new shorter proof. Here goes: Let $\Delta(x)$ be a set of formulas (with one free-variable $x$) in the ...
-1
votes
1answer
68 views

Why is there a need for ordinal analysis?

Consider the Peano axioms. There exists a model for them (namely, the natural numbers with a ordering relation $<$, binary function $+$, and constant term $0$). Therefore, by the model existence ...
3
votes
1answer
24 views

End Extension models of $I\Delta_0$

Recently I'm thinking about below question, but I can not prove or disprove it. Is it true that for every model $M\models I\Delta_0$ there exists a model $M'\models PA$ such that $M'$ is end ...
0
votes
1answer
43 views

Tarski-Vaught Test - why only one variable tested at a time?

The book Model Theory: An Introduction by David Marker states the Tarski-Vaught test for elementary substructures (p45, 2002 edition) as : Suppose that M is a substructure of N. Then M is an ...
8
votes
1answer
96 views

Is there a “computable” countable model of ZFC?

Question Assuming ZFC is consistent (has a model), does there exist a set $S$ and a binary relation $\in_S$ on $S$ that satisfy the following? $S \subseteq \{0,1\}^*$ (this is the Kleene star, and ...
0
votes
0answers
26 views

Model-finding: negated quantifiers

I want to find a model and a countermodel for the following formula: $¬∀a¬∃b((P(a)∧P(f(b)))→Q(f(f(b))))$ I tried: Model 1: $A = \{x, y\}, P^M = \{x,y\}, Q^M = \{x\}, f(b) = b$ which satisfies the ...
1
vote
1answer
55 views

Simplifying theories with quantifier elimination

Let $\Sigma$ be a theory that has quantifier elimination. I'm trying to show that there is then an equivalent theory $\Sigma^*$, with each $\sigma\in\Sigma^*$ of the form $\forall x\psi(x)$ or ...
3
votes
2answers
75 views

Was more information that necessary given in this exercise?

I had the following exercise in an exam: Question Let $L$ be a first order language with equality, a binary function symbol, and a binary predicate symbol. Let $I=(\Bbb Z, +, \leq), J=(\Bbb ...
4
votes
1answer
59 views

Quantifier elimination for theory of equivalence relations

Let $\mathcal{L}=\{\sim\}$ and $\Sigma_\infty$ be the set of axioms stating that: (i) $\sim$ is an equivalence relation (ii) Every equivalence class is infinite (iii) there are infinitely many ...
2
votes
1answer
45 views

Regarding the theory $REI_{\alpha}$

The theory $REI_{\alpha}$ has as its language $L=\{E_{\beta}|\beta\leq\alpha\}\cup{\{E_{-1}\}}$, and each $E_{\beta}$ and $E_{-1}$ are binary relation symbols. Let $T$ (=$REI_{\alpha}$) be the theory ...
0
votes
0answers
29 views

Prove that formule is true in every realisation of language [duplicate]

I have language $\mathcal L$= $\{$P,Q,R$\}$, arity of $P,Q,R$ is $1,1,2$. And I have two formulas: 1) ($\forall x$ $P(x)$ $ \land $ $\forall x$ $Q(x)$) $\leftrightarrow$ $\forall x$ ($P(x)$ $ \land $ ...
3
votes
0answers
61 views

Positive existential theory of an extension of the ring

When we know that the positive existential theory of a ring $R[x]$ in a language $L$ is undecidable, does it follow that the positive existential theory of $R[x,y]$ in the same language $L$ is also ...
3
votes
1answer
29 views

Parameters and strongly minimal sets

Suppose $T$ is a countable complete theory, with monster model $\mathbb{C}$. A definable set $D := \phi(\mathbb{C}, \overline a)$ is strongly minimal if given any other formula $\psi(x, \overline b)$ ...
2
votes
1answer
32 views

How to show $T=\{\forall x(x\neq S^{n}x)|1\leq n\}\cup\{\sigma\}$ in $\mathcal{L}=\{S\}$ is $\kappa$-categorical

Problem saying: Let $T=\{\forall x(x\neq S^{n}x)|1\leq n\}\cup\{\sigma\}$ in $\mathcal{L}=\{S\}$ , where $S$ is a unary function and $S^{n}$ abbreviates $\underbrace{S\dots S}_{n}$ , and ...
5
votes
1answer
154 views

Can there be a countable transitive model satisfying the same $MK$ theory as $V$?

A little while ago, I asked whether or not there could be a countable transitive model satisfying the same $ZFC$ theory as $V$ (assuming that we're working within some $V$, or (if you like) that there ...
1
vote
1answer
43 views

Defining a formula using FO+TC

Define a signature Σ and an FO+TC formula ϕ over Σ, such that: there is no infinite structure satisfying ϕ for every even natural number n>0 there is a structure of size n satisfying ϕ for every ...
3
votes
0answers
44 views

model theory & algebraically closed field

recently I'm taking mathematical logic course, and the class covers some basic model theoretical ideas. Since I have not taken any abstract algebra course, It is so hard to understand what is going ...
1
vote
1answer
35 views

How should one read the s*(t) function in Mendelson's Introduction to Mathematical Logic?

I'm self-teaching logic and doing it by means of following Elliot Mendelson's Introduction to Mathematical Logic (6th edition). In p.56 he defines a a function s* which, in his words, 'assigns to each ...
6
votes
1answer
160 views

Countable elementary submodels

I'm having some trouble understanding elementary submodels. Let $H_\chi$ be the set of all sets which are hereditarily of cardinality $<\chi$. Let $\textbf{N}=(N,\in)$ be a countable elementary ...
4
votes
1answer
33 views

Why in countably saturated models, types that are consistent with $TH(\mathcal{M_a})$ are finitely realizable?

I'm learning about countably saturated ($\alpha$-saturated) models. There is a hidden presupposition everywhere used: The type $\Gamma(x)$ is consistent with $TH(\mathcal{M_a})$ iff $\Gamma(x)$ is ...
0
votes
1answer
40 views

Is model theory needed to understand ordinal logic?

By ordinal logic, I mean turing's ordinal logic. I'm going to learn first order logic, elementary set theory, basic computability, and godelian incompleteness as prerequisites for ordinal logic. But, ...
1
vote
0answers
18 views

Let $L$ be a first order language with equality and two binary function symbols…

$\bf Question$ Let $L=(F=\{f^2,g^2\}, P=\{=\}, C=\{c\})$ be a first order language. Let $I = (\Bbb R^{2\times 2}, f^2(x,y)=(x+y)^t,g^2(x,y)=x+y,0) $ be an interpretation of $L$. Exhibit ...
4
votes
1answer
155 views

Can't EF game theory be applied to finite languages WITH function symbols?

Let $\mathcal{M}$ and $\mathcal{N}$ be two structures in a language $\mathcal{L}$. We define the finite determined game $G_n(\mathcal{M},\mathcal{N})$ as a game with $n$ rounds where in each round ...
2
votes
1answer
31 views

non-isomorphic countable models of $Th(\mathbb{N})$

I'm proving there are exactly $2^\omega$ non-isomorphic countable models of standard natural numbers. I got cardinality of them $\geq 2^\omega$from prime arguments. but I don't get how to prove other ...
2
votes
1answer
35 views

Is this an axiomatization of real closed fields?

I know that real closed fields are defined as ordered fields where every positive element is a square and every odd polynomial has a root. But can they also be axiomatized as totally ordered fields ...
3
votes
1answer
61 views

The analogy between two Rudin-Keisler orders

Given a set $X$, an ultrafilter $U$ on $X$, and a function $f\colon X\to Y$, we can push forward $U$ along $f$ to obtain an ultrafilter $f_*U$ on $Y$, defined by $C\in f_*U$ if and only if ...
5
votes
1answer
111 views

Equivalence of the theories $\operatorname{Th}(\Bbb{R}, 0,1,+, \le)$ and $\operatorname{Th}(\Bbb{Q}, 0,1,+, \le) $

So I was working on showing that $$\operatorname{Th}(\Bbb{R}, 0,1,+, \le) = \operatorname{Th}(\Bbb{Q}, 0,1,+, \le) $$ My initial idea for working on this problem was to systematically start by ...
3
votes
1answer
43 views

Axioms for $\mathbb Z$-groups without named one?

The theory of $(\mathbb Z,+,0,1)$ has been studied as the theory of $\mathbb Z$-groups, and it has been examined as a series of exercises (and I'm sure other places) in David Marker's Model Theory ...
2
votes
1answer
48 views

The Amalgamation Property in AECs

I am new to abstract elementary classes (AEC) and am reading the early chapters of Baldwin's Categoricity text. I have shown that the disjoint amalgamation property holds for an AEC obtained by ...
1
vote
1answer
41 views

Is a tautology substitution instance with first order formulas valid?

I wonder how to show the following: Let $P_1,...,P_n$ be propositional symbols occurring in a tautology $\alpha$. Assume that $\varphi_1,...,\varphi_n$ are first order formulas and that $\alpha'$ ...
4
votes
1answer
116 views

Using Compactness to find a non-constructible set

$\newcommand{\ZFC}{\mathit{ZFC}}$I was trying to explain the first ideas of forcing to a friend and I recalled the construction of a model of non-standard arithmetic by using compactness. It is clear ...
6
votes
1answer
89 views

How do inconsistent arithmetics get around Gödel incompleteness?

Gödel theorems imply that arithmetic can not be complete under recursive axiomatization and consistency assumptions. Unexpectedly, consistency can be dropped in a meaningful way by switching to a ...
2
votes
1answer
72 views

Understanding countable elementary submodels

So I'm having some trouble understanding the existence of countable elementary submodels. I have read and understand the Löwenheim–Skolem theorem, so given a model I understand how to build a ...
2
votes
1answer
73 views

Is the use of the meta-meta-theory allowed in proving an independence result?

I am wondering about the use of a meta-meta-theory in proving statements of the form "$\phi$ is independent of $\mathcal{T}$" in mathematical logic. Short question: Is using a result from the ...
0
votes
1answer
38 views

Simple proof that Automorphisms preserve definable subsets?

I've been looking all over for a proof of this result, but I haven't really found anything. Is anyone aware of a particularly simple or elegant one?