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

5
votes
2answers
102 views

Explicit countable elementary extension of $\mathbb{N}$

I would like to see an explicit example of a non-trivial elementary extension of the structure $(\mathbb{N}, +, \cdot, 0, 1)$ where $\mathbb{N}$ includes zero. Most of all I am interested in countable ...
1
vote
2answers
83 views

How does Gödel's second incompleteness apply to any theory containing arithmetic?

If I understand correctly, there are two facts proven by Gödel's second incompleteness theorem, for a formal theory containing arithmetic 1) It is possible to express the consistency of the theory ...
2
votes
2answers
38 views

To build a tree in a countable theory with uncountable many types in finite variables

I'm trying to prove that if $T$ is a countable consistent theory that has no binary trees, then $T$ is small. i.e $|S_n (T)|=\aleph _0$ In order to do this i assume toward contradiction that $S_n ...
4
votes
1answer
50 views

If $\mathcal{T}_1$ and $\mathcal{T}_2$ admit quantifier elimination, does $\mathcal{T}$ admit quantifier elimination?

Let $\mathcal{T}_1$ and $\mathcal{T}_2$ be theories with disjoint signatures $\mathcal{L}_1, \mathcal{L}_2$. Form a new language $\mathcal{L} = \mathcal{L}_1 \cup \mathcal{L}_2 \cup \{P_1, P_2\}$, ...
4
votes
2answers
134 views

A structural view to the power set axiom: Is this axiom really justifiable?

The power set axiom in set theory states that the collection of the subsets of a set is a set itself. I wonder if this is a "natural" axiom in the sense that if we consider sets as the simplest ...
1
vote
1answer
82 views

How do we know $\mathbb{N}$ is a model of Peano Arithmetic?

The induction axiom in the theory of Peano Arithmetic (PA) is actually an axiom scheme such that for every formula $\phi(x,\bar{y})$ with free variables $x,\bar{y}$ ($\bar{y}$ being a string of ...
3
votes
1answer
43 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
36 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 ...
4
votes
2answers
92 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
140 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
58 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
86 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
51 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
61 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
55 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
49 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
181 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
42 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
48 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
208 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
63 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
71 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
25 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
67 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
107 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
28 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
61 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
87 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
48 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
34 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
47 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
159 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
45 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
46 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
40 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
174 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
36 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
48 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
20 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
165 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
34 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
38 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
65 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
115 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
52 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
54 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 ...