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
2answers
212 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
64 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
74 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
72 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
117 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
62 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
111 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
48 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
164 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
48 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 on....
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
37 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
51 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
22 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
166 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
40 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
66 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 $f^{-1}[C]\...
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
56 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
55 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
125 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
104 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
95 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
79 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 meta-...
0
votes
1answer
45 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?
2
votes
1answer
60 views

Why isn't $\leq$ definable in $(\mathbb{R};0,+,-)$?

Are there any simple and straightforward proofs of this fact? I'm not really sure how to begin to approach the problem.
1
vote
0answers
42 views

Automorphisms and Definable subsets?

I'm trying to show that if we have a structure $\textbf{A}$ and $C\subseteq A$, with an $\mathcal{L}_C$ formula $\varphi(x)$ defining the set $S$ in $\textbf{A}$, then for any given automorphism $h\...
0
votes
1answer
35 views

Is logical implication examining only the syntatical component?

As my title asks, is logical implication only examining the syntatical compinent of the formal language? I am using Enderton's book on Mathematical Logic in my class and after some work I am ...
3
votes
1answer
52 views

Show the inequality $x <y$ is definable in the language $\langle \mathbb{R}; +, \times ; 0,1 \rangle $

My initial idea is that I need to find a sentence that expresses 'x is positive' and then I can say: for any $a, b$, $a>b$ iff there is a positive x s.t. $b+x=a$, but can't figure out how, any ...
3
votes
1answer
56 views

A simple proof that elementary equivalence and isomorphism coincide for finite structures?

I'm wondering if there's a straightforward proof of this result I've seen mentioned in quite a few places. If $\mathcal{L}$ is finite, of course, this is trivial since there's a single formula that ...
1
vote
1answer
54 views

First-order definition of “$f$ is continuous at $x$” using just $<$

I need to show that the set $\{ a\in \mathbb{R}\ |\ f\ \text {is continuous at a}\}$ is definable in the structure $(\mathbb{R};<,\ f)$, where $f$ is just some function $f:\mathbb{R}\rightarrow\...
1
vote
1answer
37 views

Prove that this theory is incomplete

Given $\Sigma = \{\forall x \forall y \forall z(x \circ (y \circ z) = (x \circ y) \circ z), \forall x (x \circ e = x), \forall x \exists y (x \circ y = e)\}$ (eg. group theory axioms), I need to prove ...
1
vote
0answers
77 views

Prove that there exists a non-standard model of arithmetic

Specifically, I need to show there exists a structure $\mathcal{Z}'$ that is elementarily equivalent to $ \langle \mathbb{N} ; <; \cdot ; 0,1 \rangle $ (the standard model of arithmetic) but is not ...
1
vote
1answer
43 views

Relation between homogeneity and categoricity

Define a structure $\mathcal{A}$ as homogeneous if, for every two substructures $\mathcal{B}, \mathcal{C}$ of $\mathcal{A}$, if $f: B \to C$ is an isomorphism, then $f$ extends to an automorphism of $\...
3
votes
1answer
65 views

Is a theory elementary iff it is categorical? [closed]

If an elementary class is the set of structures satisfying a theory, and a theory is categorical if it determines a structure up to an isomorphism, it would seem that the two concepts are related, no?
5
votes
0answers
62 views

bi-interpretability and automorphism groups

Let $M$ and $N$ be two first order structures, say they are countable and $\aleph_0$-categorical. Then $M$ and $N$ are bi-interpretable if and only if their automorphism groups $Aut(M)$ and $Aut(N)$ ...
2
votes
1answer
62 views

Show the only definable subsets of $ \langle \mathbb{Q} , < \rangle $are the empty set and $ \mathbb{Q} $

I'm trying to show the above, and I know it should be quite simple, but I'm struggling to get my head around how you show subsets are not definable using automorphisms- so a detailed explanation would ...
2
votes
1answer
53 views

DOP, Shelah, Clarifying the definition

I'm trying to understand Shelah's prototypical example of DOP here on page 26, item (c). It would be a very nice example if correctly understood.However, there is some strange mixture in the ...
6
votes
1answer
107 views

Integer parts isomorphic?

Let $F$ be a real closed field. It is known$^{[1]}$ that $F$ has an integer part, that is, a subring $A$ such that $\forall x \in F, \exists ! a \in A, a \leq x < a+1$. Are all integer parts over ...