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

4
votes
1answer
93 views

Show that the theory of the $Th(\mathbb N)$ in first order logic with the finiteness quantifier is categorical

Suppose that a finiteness quantifier $\mathbf Fx$ is added to first order logic. Its semantics are: $\mathbf Fx\Phi(x)$ is true in a model just in case there a finitely many things in the domain of ...
4
votes
3answers
205 views

$\langle \Bbb Q,<\rangle$ is an elementary submodel of $ \langle \Bbb R,< \rangle$

I am trying to show that $\langle\Bbb Q,<\rangle$ is an elementary submodel of $\langle\Bbb R,<\rangle$. I first believed that this problem is quite trivial $-$ I thought all I needed to do was ...
3
votes
1answer
144 views

Automorphism of an elementary extension of a structure that moves an undefinable element

I know that the easiest way to show a point is not definable is to find an automorphism of the structure that moves the given point. I've also seen many examples undefinable points that couldn't be ...
4
votes
1answer
230 views

Types and Algebraicity

Let $\Phi(\bar x)$ be a type over a set $X$ with respect to a structure $A$. Show that if $\Phi$ is algebraic, then $\Phi$ contains a formula $\phi$ s.t. $A\models\exists\ _{<n}\bar x\phi(\bar x)$ ...
3
votes
1answer
238 views

Consequences of axioms of Dense linear order without endpoints is complete

I've been musing over this problem over the past few days, and believe I have an answer. However, I am still a bit shaky with some of the definitions I am using, and would appreciate if anyone could ...
22
votes
1answer
563 views

Model existence for infinitary logics

One of the problems of infinitary logic is that it is possible for compactness to fail in a spectacular way: for example, one can concoct an inconsistent set of axioms whose proper subsets are all ...
8
votes
2answers
152 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
221 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
340 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
306 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
382 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
139 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 ...
7
votes
1answer
228 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
72 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
165 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
153 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
141 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
257 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
219 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
191 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
53 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
112 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
44 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
126 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
70 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
75 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
121 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
53 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
2k 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
539 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
240 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
242 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
322 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
74 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
326 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
185 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
130 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
72 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
99 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
162 views

Examples of vaughtian pairs

Greets I just want to see examples of vaughtian pairs. Thanks
2
votes
2answers
88 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$).
8
votes
3answers
235 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
972 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
76 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
170 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
53 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
129 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
629 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. ...