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

8
votes
2answers
138 views

Definability in a given structure

I want to prove the following statements: Is the function "sin" definable in the structure $(\Bbb{R},<,+,\cdot,0,1)$, that is does there exists a formula $\phi=\phi(x_0,x_1)$ such that for all ...
2
votes
1answer
190 views

Does elementary embedding exist between two elementary equivalent structures?

By previous question, if there is a elementary embedding from $\mathfrak A$ into $\mathfrak B$, then $\mathfrak A \equiv \mathfrak B$. Now it is naturally to ask conversely, if $\mathfrak A \equiv ...
1
vote
1answer
278 views

Is one structure elementary equivalent to its elementary extension?

Let $\mathfrak A,\mathfrak A^*$ be $\mathcal L$-structures and $\mathfrak A \preceq \mathfrak A^*$. That implies forall n-ary formula $\varphi(\bar{v})$ in $\mathcal L$ and $\bar{a} \in \mathfrak A^n$ ...
3
votes
1answer
258 views

Quantifier Elimination

I want to prove the following: The structure $(\mathbb{Z},\equiv,0)$ has QE (with $\equiv$ a relation such that for all $m,n\in\mathbb{Z}$: $m\equiv n$ iff $m-n$ is even). I thought hereover in the ...
3
votes
2answers
341 views

Automorphisms of saturated models

This is basically Exercise 10.1.5(c) in Hodges's Model theory. First, a reminder of some definitions: Let $\lambda$ be a cardinal, and let $\Sigma$ be a finitary first-order signature. A ...
3
votes
1answer
119 views

Feferman-Vaught theorem and Term Powers

In an example of usage of quantifier elimination in wikipedia, it briefly mentions Feferman-Vaught theorem and Term Powers, but I am finding little information on what these are. Can anyone explain ...
6
votes
1answer
214 views

Is Zermelo set theory finitely axiomatizable?

I know that ZF is not finitely axiomatizable, but what about Z (i.e. ZF without Replacement)?
2
votes
1answer
62 views

A formula that is upwards absolute but not downwards absolute

I know that any existential formula is upwards absolute (an any universal formula is downwards absolute) but I was looking for an example of a formula that is upwards absolute but not downwards ...
5
votes
2answers
149 views

Definable relations

I study model theory and I have questions about relations which are definable in a structure or not. I found three examples from exercises and i want to do them: Is the relation $<$ on $\Bbb{Q}$ ...
1
vote
1answer
149 views

Is $\mathbb N$ definable in $\mathbb C$?

$\mathbb C$ is an algebraic closed field with characteristic $0$, hence $Th(\mathbb C)$ is a recursive satisfiable complete theory, thus recursive axiomatizable. So if $\mathbb N$ is definable in ...
4
votes
1answer
135 views

Is this theory $\kappa$-categorical when $\kappa$ is infinite and not $\le \aleph_0$?

Let $\mathcal L$ be a language with only a binary predicate $E$, and let $T$ be a theory of structures in which $E$ is an equivalence relation which partitions the structure into two infinite ...
1
vote
2answers
218 views

Showing that the class of well ordered structures is not an elementary class

How I can prove that for the class $K$ of well-ordered structures there is no finite set of statements $T$ such that $\text{Mod} (T) = K$? Thanks
2
votes
2answers
209 views

Is the negation of Gödel's completeness theorem consistent with $ZF$ without AC?

The proof of compactness and completeness of $\mathscr{FOL}$ (with Hilbert system) used Zorn's lemma. And Zorn's lemma is equivalent to the Axiom of choice in $ZF$. So my question is can they be ...
1
vote
1answer
166 views

Finding the exactly number of countable models of a theory

I'm working for Modeltheory and i have the follwoing information: Define $T_0=Th((\mathbb{Q},<,0,1,2,\cdots))$ and ...
1
vote
1answer
51 views

Does one restrict oneself when leaving out the inversion in the signature of groups?

I feel a bit lazy, for I don't want to seek an answer myself in some textbook – because I fear it'd cost me too much time while someone here can easily just knock out the answer. I hope that's OK. (Do ...
5
votes
1answer
111 views

Proving that $\langle \omega, \in \rangle $ models empty set and extensionality

Let (A1) be the axiom of extensionality: $\forall x,y ( x = y \longleftrightarrow \forall z \in x \leftrightarrow z \in y))$ and let (A2) be the empty set axiom $\exists x \forall y (y \notin x)$. ...
1
vote
1answer
43 views

Model of a language $L$ vs. model of a theory $T$ in $L$

I am reading Just/Weese and they seem to use "model of a language $L$", for example, p. 90: and, more disturbingly, p. 91: Isn't this a "typo" (or perhaps sloppy writing)? If $L$ is any language ...
3
votes
1answer
51 views

Question about a proof that there is no formula $fin(x)$

Consider the following passage in Just/Weese: where $fin(x) \equiv $ "$x$ is a finite set". I'd like to confirm the following with you : requiring "ZFC $\vdash fin(n)$ if $n \in \omega$" is weaker ...
1
vote
0answers
70 views

Borel sets used in Model Theory

In Lemma 4.4.13 (page 161) of D.Marker- Model Theory book it is proved that $D(F,T)$ (the set of all possible F-diagrams of models of T) is a Borel set. Can someone explain to me the proof given a ...
3
votes
2answers
117 views

A theory $T$ is complete if and only if $Th(M) = T^\vdash$ for some model $M$

I'm trying to show that a theory $T$ is complete if and only if $Th(M) = T^\vdash$ for some model $M$ where $Th(M)$ denotes the set of all sentences that are true in $M$. What I have so far: ...
3
votes
2answers
69 views

Does $E$ in a model $\langle M, E\rangle$ of ZFC have to be wellfounded?

Consider the following exercise from Just/Weese: My first reaction was "Of course $E$ has to be strictly wellfounded otherwise it wouldn't model $\in$" but apparently I am missing something since I ...
2
votes
2answers
72 views

Confused about models of ZFC and passage of book

I have a question about a passage of Just/Weese. In the following, let $\mathcal M = \langle M, E \rangle$ be a model of ZFC. Here is the first half of what I'm about to ask a question: So I asked ...
0
votes
2answers
103 views

How to finish proof that $T$ has an infinite model?

I'm trying to prove the following: If $T$ is a first-order theory with the property that for every natural number $n$ there is a natural number $m>n$ such that $T$ has an $m$-element model then $T$ ...
2
votes
2answers
52 views

Equivalent characterisation of consistent

We call a set of formulas $\Sigma$ of a language $L$ consistent if there is no $\varphi$ in $L$ such that $\Sigma \vdash \varphi$ and $\Sigma \vdash \lnot \varphi$. Apparently, an equivalent ...
9
votes
1answer
1k views

Choosing a Master Thesis Topic: Logic - Model Theory

I am a first-year graduate student in maths. Around these days, I feel I must decide on which exact part of mathematics I shall go through. Infact, I have narrowed down the suitable options but still ...
6
votes
3answers
487 views

Complete first order theory with finite model is categorical

I am trying to prove that if $T$ is a complete first order theory that has a finite model then it has exactly one model up to isomorphism. To this end, I assumed that $T$ is complete with a finite ...
7
votes
1answer
194 views

The relation $<$ is not definable in the structure of the integers with successor function

I have to prove the following statement: Prove that there is no formula $\psi=\psi(x_0,x_1)$ in the language $\operatorname{Th}((\mathbb{Z},S))$ such that the relation ...
4
votes
2answers
232 views

Proof of compactness theorem

I wanted to prove the compactness theorem, p 79 Just/Weese: The (i) <= (ii) direction is not obvious to me. I thought I could prove it by showing not (i) implies not (ii) as follows: Assume ...
10
votes
1answer
304 views

Compactness Theorem Application

I am doing an exercise on the compactness theorem of first order logic. The task is to prove that there is no singe first order sentence which is satisfied in exactly the infinite graphs (thereby, a ...
0
votes
3answers
73 views

Understanding models and valuations

I'm thinking about part (a) of the following exercise in Just/Weese page 77: Here is the definition of valuation: For example, say we have a model of the language of group theory, $( \mathbb Z/ 2 ...
8
votes
2answers
310 views

Which sets are present in every model of ZF?

As in the title: the existence of which sets is implied by the axioms of $\mathsf{ZF}$? For example one such set would be the empty set whose existence is demanded by the Axiom of the Empty Set. But ...
1
vote
1answer
161 views

Property of finite structure inexpressibiliy in first-order logic

I want two show that a certain property $u$ of some finite structure is not definable in first-order logic. Is the following reasoning correct? Let $\mathcal{S}$ denote a finite structure. Further, ...
3
votes
1answer
119 views

Existence of elementary substructures of a uncountable structure over a countable language

Let $\kappa$ be an regular uncountable cardinal carrying a $\tau$-structure for some countable language $\tau$. What can be said regarding the existence of ordinals $\alpha <\kappa$ carrying ...
2
votes
1answer
67 views

Extend non-principal n-type

Is the following true? Let T be a complete theory in some elementary language. Let $n$ be a natural number and suppose $\Gamma$ is a non-principal $n$-type of T. Let $\Delta$ ne an $n+1$-type of T ...
1
vote
1answer
88 views

Prime Model and countable saturated model proof and types of a theory

I know that for the complete theory $Th((\mathbb{Q},+,0))$ we have the prime model $(\mathbb{Q},+,0)$ and the countable saturated model $(\mathbb{Q}^{\infty},+,0)$, but what should I do when I try to ...
1
vote
1answer
151 views

Examples of vaughtian pairs

Greets I just want to see examples of vaughtian pairs. Thanks
2
votes
2answers
82 views

Definability in FO($\mathbb{Q}, +, \leq$)

Is the set $\left\{(x, y) \in \mathbb{Q}_{>0}^2 \, : \, \frac{x}{y} \in 2\mathbb{N} - 1\right\}$ definable in FO($\mathbb{Q}, +, \leq$).
7
votes
3answers
230 views

Does the category framework permit new logics?

It appears to me that a topos permits a broader concept of subsets than the yes/no decission of a characteristic function in a set theory setting. Probably because the subobject classifier doesn't ...
9
votes
1answer
779 views

Show that binary < “less than” relation is not definable on set of Natural Numbers with successor function

After reading about the question, I've come to believe that it would suffice to exhibit and automorphism of that is not order preserving. However, I'm unsure of how to construct such an automorphism, ...
3
votes
1answer
75 views

Prime Model and boundary functions for n-types

Find a prime model and a countable $\omega$-saturated model of $Th((\mathbb{Q},+,0))$. Define a function from $\mathbb{N}$ to $\mathbb{N}$ such that, for each n, $Th((\mathbb{Q},<))$ has not more ...
2
votes
3answers
158 views

Number of types in a given complete Theory

Prove that $Th((\mathbb{Q},<,+,0,1))$ has uncountably many 1-types. Prove that $Th((\mathbb{Q},+,0,1))$ has countably many 1-types. Prove that $Th((\mathbb{Q},<,0,1))$ has five 1-types. Prove ...
2
votes
2answers
52 views

Definable orders

Let $(K, <)$ be an order field, can I define the order "<" in $K$ ? I know that $K \models 0<a \;$ if and only if there is $b$ in the real closure of $K$ such that $b*b = a$. Can I ...
2
votes
0answers
117 views

Realizing n-types of a complete theory

Let $\mathfrak{A}_0=(A_0,R_0)$ and $\mathfrak{A}_1=(A_1,R_1)$ be structures such that for each $i<2$, $A_i$ is a nonempty set and $R_i\subseteq A_i\times A_i$. We define the structure ...
3
votes
1answer
559 views

$2\mathbb Z$ is not a definable set in the structure $(\mathbb Z, 0, S,<)$

This is (a translation of) an excerpt from a model theory textbook that shows that $2\mathbb Z$ is not a definable set in the structure $(\mathbb Z, 0, S, <)$, where $S$ is the successor function. ...
2
votes
3answers
231 views

A theory with exactly $n$ countable models, for each $n>1$

For each $n>1$ we shall construct a first-order theory $T_n$ with exactly n countable models. Let $n>1$, consider the language $L_n=\left\{{R,c_1,...,c_n}\right\}$, where $R$ is a binary ...
1
vote
1answer
141 views

Problem with Morley's Theorem

Greets. Morley's theorem states that a theory which is categorical for an uncountable cardinal is categorical in all uncountable cardinals. My problem with the theorem is that I haven't found a ...
1
vote
2answers
164 views

Finite Set of Models

This is only directed towards logicians, model theorists etc.. I am reading "Model Theory" by Keisler and Chang and have encountered the following question. Let $\Psi = \{M_1,...,M_n \}$ be a finite ...
3
votes
2answers
109 views

First order sentence true in $\mathbb{Q}$ but not in $\mathbb{R}$.

I have the following assignment question: Find a first order sentence that is true in $\langle\mathbb{Q},+,\cdot ,0,1\rangle$ but not in $\langle \mathbb{R},+,\cdot,0,1\rangle$. Most of what I ...
1
vote
2answers
158 views

Boolean algebra spectrum

The first-order spectrum of a theory, is the set of cardinalities of its finite models. Finite models of Boolean algebras are informally n-dimensional cubes, therefore boolean algebra spectrum is the ...
3
votes
2answers
175 views

Does Löwenheim-Skolem fail for $\mathcal{L}_{\omega_1\omega}$?

Does descendant or ascendant Löwenheim-Skolem fail for $\mathcal{L}_{\omega_1\omega}$ -logic?