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

2
votes
2answers
61 views

What does “decidability” of a Model mean exactly?

I'm looking at the theorem concerning the Model of Arithmetic: M arith = (Integers, +, *, <) is undecidable. What does the "decidability" of a model mean exactly? Does that mean that "the ...
1
vote
0answers
42 views

Substructure of $\omega$-catogorical theory $T$.

I need some help understanding part of my Model Theory notes: "Given that $T$ is $\omega$-categorical and $\mathfrak{A} \vDash T$, for $S \subseteq A$, let $\langle S\rangle$ denote the smallest ...
5
votes
2answers
127 views

Set of odd integers is not definable in $(\mathbb{Z},+)$ by an existential formula

I would like some comments on how I approach this problem. The part right before this problem in my homework asks for an existential formula that defines the set of even integers. Please let me know ...
0
votes
1answer
118 views

What are the rules of inference used for syntactic consequence in Gödel's Completeness Theorem?

I am trying to understand the Completeness Theorem, and I was just looking at its explanation in the answer to this question: What is the difference between Gödel's Completeness and ...
3
votes
2answers
126 views

Definable Sets of ($\mathbb{Z};<$)

I came across this question "Prove that a subset $S$ of $\mathbb{Z}$ is definable in the structure $(\mathbb{Z};<)$ if and only if $S=\emptyset $ or $S=\mathbb{Z}$." I found something on the ...
1
vote
2answers
85 views

If $T \models \phi$ then there is a finite subtheory $T' \subset T$ such that $T' \models \phi$

Use the Compactness Theorem to show: if $T \models \varphi$ then there is a finite subtheory $T' \subset T$ such that $T' \models \varphi$. I don't see how I can use the compactness theorem here. ...
1
vote
1answer
30 views

Types and elementary extensions

Let $\mathcal{M}$ and $\mathcal{N}$ be two $\mathcal{L}$-structures and suppose that for n-tupls $\bar{a}\in M^n$ and $\bar{b}\in N^n$, $tp^\mathcal{M}(\bar{a})=tp^\mathcal{N}(\bar{b})$ where ...
3
votes
1answer
65 views

Definable subsets--theorem from A Shorter Model Theory

So this is a theorem [1] from A Shorter Model Theory and I'm being unable to prove this when it seems like proving this would be quite intuitive and straightforward. Does anyone know a proof? Let ...
4
votes
2answers
110 views

Joint Embedding Property

I want to show that any complete theory has JEP, And that JEP does not imply comleteness. I have trouble showing it, and I think I'm missing sometiong here. And another question: If $T$ is model ...
0
votes
1answer
74 views

A Model of Dense Linear Orders without Endpoints

Hopefully this question is well defined. Consider the following linear order in the language $\{<\}$: Step 0: Begin with $\mathbb{Q}$. Step 1: Create a new model $Q_1$ by realizing all the ...
1
vote
3answers
294 views

Elementary embeddings vs isomorphisms

I'm trying to get a better handle on the concepts of literal embeddings, elementary embeddings and isomorphisms, as the show up in logic. This is the problem: It seems to me, (and is, according to my ...
9
votes
1answer
205 views

Examples of Forcing in Model Theory

My question is exactly my title: What are some examples of (set theoretic) forcing in model theory? I have been studying (combinatorial) set theory and model theory (independently of one another) for ...
1
vote
1answer
82 views

o-minimal structures and definable functions

Consider the following definition of an o-minimal structure: An o-minimal structure $O=\{O_n\}$ is a sequence of Boolean algebras $O_n$ of subsets of $\mathbb{R}$ which satisfies the following ...
1
vote
1answer
121 views

Existence of nonstandard elementary extensions of $PA$?

My question follows from the 1958 result of MacDowell–Specker (located originally in Modelle der Arithmetik, J. Symbolic Logic Volume 38, Issue 4 (1973), 651-652) of the proof of the following ...
3
votes
1answer
118 views

Why separate the assignment function from the interpretation function?

The book I'm reading on model theory ('Model Theory' by Maria Manzano) offers no explanation for why we need an assignment function in addition to the interpretation function. The interpretation ...
2
votes
2answers
77 views

Robinson's Consistency Theorem for first order languages

Is there a simple proof for the case of first order languages for this theorem? Let $L_1$,$L_2$ be first order languages and $L$=$L_1$ $\cap$ $L_2$. Let $T_1$, $T_2$ be consistent ...
2
votes
1answer
73 views

“Adding constant symbols” in Model Theory.

What is going on when we "add constant symbols" to extend a language L. A new constant is not in the "alphabet" of L. C is, for example, just { 0, 1 } in many cases, but C could be an infinite set. ...
2
votes
1answer
135 views

Model complete theories without quantifier elimination

As we know, if a theory $T$ admits quantifier elimination, then $T$ is model complete. What are the simplest examples that show that the converse is not true?
2
votes
1answer
83 views

What does not having a first-order frame imply for models?

There are formulas in modal logic which which do not have a first-order frame condition, as stated here (Non-Sahlqvist formulas, Wikipedia). An example is the McKinsey formula for $p$: ...
2
votes
1answer
47 views

For any propostional sentences $a,b,c$, if $a\models (b\wedge c)$, then $a\models b$ and $a\models c$

I'm having a hard time dealing with the $\models$ symbol. I don't really know how to reason through or manipulate these equations to prove why or why not the result holds. Another similar question is: ...
3
votes
0answers
79 views

Motivation behind automorphism bases?

Given a model $\mathcal{M}$ with a domain $M$ and $B \subseteq M$, $B$ is an automorphism base for $\mathcal{M}$ iff $\forall f \in Aut(\mathcal{M}). (\forall b \in B. f(b)=b) \implies f = ...
3
votes
1answer
161 views

Model of Robinson Arithmetic but not Peano Arithmetic

I am curious how can structure of with linear successor function that do not admin induction looks like. In other words I would like to see structure of Peano Arithmetic without induction. I believe ...
3
votes
1answer
97 views

The Lowenheim-Skolem theorem does not hold for $\mathfrak{L}_{II}$.

In "Mathematical Logic" second edition written by H-D Ebbinghaus, J.Flum and W.Thomas, in chapter 9 "Extensions of First-Order Logic", page 140, in the prooof of theorem 1.5 (The Lowenheim-Skolem ...
3
votes
3answers
151 views

If $B$ is a model for the set of positive consequences of $\Gamma$, then there's $A \subseteq B$ such that $A \models \Gamma$

I'm working through Chang & Keisler again and got stuck on the following exercise (1.2.14) about propositional logic. First, consider a set $\mathscr{S}$ of sentence symbols of arbitrary ...
2
votes
1answer
42 views

Universal theory with relation symbol

Let $\mathcal{L}$ be a language containing a binary relation symbol $R$. I need to prove that if $T$ is a universal $\mathcal{L}$-theory (by which I mean that $T$ is a collection of universal ...
1
vote
1answer
73 views

Does theory have the smallest model

I have a language $L=\{P\}$ with equation, where $P$ is binary predicate symbol. Language's formulas are: $\varphi \equiv \forall x \forall y (\neg P(x,x) \land (P(x,y) \to P(y,x)))$, $\psi \equiv ...
0
votes
1answer
67 views

Does theory have uncountably many pairwise non-isomorphic models?

I have a language $L=\{P\}$ with equation, where $P$ is binary predicate symbol. Language's formulas are: $\varphi \equiv \forall x \forall y (\neg P(x,x) \land (P(x,y) \to P(y,x)))$, $\psi \equiv ...
1
vote
1answer
298 views

Equivalence vs equisatisfiability

Wikipedia page states that first order formula after skolemization is equisatisfiable but not equivalent to original one. I do not understand what the difference is. I know definition of ...
17
votes
5answers
6k views

In plain language, what's the difference between two things that are 'equivalent', 'equal', and 'identical'?

In plain language, what's the difference between two things that are 'equivalent', 'equal', 'identical', and isomorphic? If the answer depends on the area of mathematics, then please take the ...
0
votes
1answer
49 views

Find some complete theory $U \supseteq T$

I have a language $L=\{P\}$ with equation, where $P$ is binary predicate symbol. Language's formulas are: $\varphi \equiv \forall x \forall y (\neg P(x,x) \land (P(x,y) \to P(y,x)))$, $\psi \equiv ...
0
votes
1answer
59 views

Problem with forking

Let $A \subseteq \mathbb{U}$ be a small set, and $\bar{a}= (a_1, \dots, a_n)$, $\bar{b}=(b_1, \dots, b_k)$ be tuples of $\mathbb(U)$. Show that tp$(\bar{a}/A\cup (b_1, \dots, b_k)$ does not fork over ...
1
vote
1answer
68 views

Morley rank (with an unusual definition)

For a definable set $X \subseteq \mathbb{U}^n$, let us denote $\text{RM}(X)$ the Morley Rank $\text{RM}(\varphi(\bar{x}))$, with $\varphi(\bar{x})$ the formula defining $X$. Show that, for $X ...
1
vote
1answer
49 views

Does an interpretation of a structure by itself induce a bijection on the automorphism group of the structure?

Let $\Gamma$ be a model-theoretic interpretation of a structure $B$ in a structure $A$. Then $\Gamma$ induces a group homomorphism $\alpha_\Gamma:\mathrm{Aut}(A) \rightarrow \mathrm{Aut}(B)$. (See, ...
2
votes
2answers
133 views

Prove the Robinson arithmetic has infinite non-isomorphic models

I found this question: Can finite theory have only infinite models?, where is proved that Robinson's Arithmetic can have infinite models, but I've been unable to prove or find a proof of the existence ...
3
votes
0answers
73 views

Consequence in $\mathcal{L}_{\infty\lambda}$

Consider the infinitary first-order language $\mathcal{L}_{\infty\lambda^+}$ whose non-logical vocabulary consists of $\lambda \geq \omega$ individual constants and countably many predicate constants ...
1
vote
1answer
43 views

How would one prove that satisfaction of closed formulas is valuation-independent? (In FOL)

Consider this proposition in first-order logic: For any interpretation $I$, any closed formula $\phi$ and any two valuations $\rho$, $\sigma$. $I\rho \models \phi \iff I\sigma \models \phi$ This is ...
2
votes
1answer
60 views

Countable transitive model of ZFC and $\mathcal{P}(\omega)$

Let $\mathbb{M}$ be a countable transitive model of ZFC. I understand that $\omega^\mathbb{M} = \omega$ but $\mathcal{P}(\omega)^\mathbb{M} \neq \mathcal{P}(\omega)$, for ...
-2
votes
1answer
67 views

Model Theory - Equivalence of formulas using automorphisms

Let $\mathbf Q$ denote the additive group of rational numbers, i.e. the structure $\mathbf Q = (\mathbb Q;+,0)$. Let $L$ be the language of $\mathbf Q$ and let $T$ be the complete theory of $\mathbf ...
2
votes
1answer
60 views

Why are $n$-ary function symbols interpreted as $n$-ary operations and not general $n$-ary functions?

I would appreciate if someone here could check the correctness of my reasoning about the following. I'm new to logic. Let $\mathfrak{M} = \langle M,\mathfrak{I} \rangle$ be a structure for some ...
6
votes
2answers
81 views

Ultraproducts and Elementary Embeddings

Let $K= \{A_i: i\in \omega\}$ be a countable collection of $L-$structures. Suppose that for each $A_i, A_j$ in $K$, $\exists A_p \in K$ such that $i,j< p$ and $A_i \prec A_p $ and $A_j \prec ...
0
votes
0answers
59 views

Is this an accurate description of structures and interpretations.

I read about structures and interpretations today. I've described them below this paragraph. Have I accurately described them? If not, what have I incorrectly described? A structure, $\mathscr{A}$, ...
1
vote
1answer
56 views

Let $T$ be the theory of linear, dense order, without minimum or maximum. Is $T\cup\{c_{i}<c_{j}\mid i<j\}$ complete?

Let $T$ be the theory of linear, dense order, without minimum or maximum in the language $\mathscr{L}$ . Expend the language by adding it countable amount of constants: ...
0
votes
0answers
57 views

Quick question about the relation between elementary classes and pseudo-elementary classes

Let $\mathcal{L}$ be a logic and $\mathscr{K}$ a class of structures in the vocabulary of $\mathcal{L}$. We say that $\mathscr{K}$ is a (basic) elementary class iff there is $\phi \in \mathcal{L}$ ...
1
vote
1answer
82 views

$T$ be a theory that claims that both $P$ and $\neg P$ are infinite. Prove that $T$ is a complete theory

Let $\mathscr{L}=\{P\}$ a language with one unary predicate. Let $T$ be a theory that claims that both $P$ and $\neg P$ are infinite. Prove that $T$ is a complete theory. I tried to prove by ...
3
votes
2answers
196 views

Unexpressibility of a property in first order logic

We can give a very general notion of what is to iterate a function. Given a set $\mathcal U$ and a function $f:\mathcal U \rightarrow \mathcal U$, then, to iterate the function $f$ will mean to ...
2
votes
1answer
38 views

Models of $T_\exists$ are precisely the structures that contain a model of $T$

An usual exercise in introductions to model theory is to prove the following statement: Let $T$ be a theory, and let $T_\forall$ be the set of all universal sentences that are consequences of $T$. ...
3
votes
0answers
65 views

Ordering of $\mathbb{R}$ not quantifier-free definable in $L_{R}$

I'm reading David Marker's book "Model Theory: An Introduction" and I'm trying to solve Exercise 3.4.24 which is stated as follows: Let $x$ and $y$ be algebraically independent over $\mathbb{R}$. a) ...
5
votes
2answers
149 views

Formula for perfect squares spectrum.

I have been working on exercises from "A first Course in Logic" by S. Hedman. Exercise 2.3 (d) asks to find a first-order sentence $\varphi$ having the set of perfect squares as a finite spectrum. But ...
2
votes
2answers
40 views

Models of $T$ in cardinallity $\kappa$ are isomorphic

Assume that $T$ is a consistent set in a countable language $\mathscr{L}$ with no finite models. There is a cardinal $\kappa$ such that every two models of $T$ with cardinallity of $\kappa$ are ...
19
votes
2answers
1k views

Are there number systems corresponding to higher cardinalities than the real numbers?

As most of you know, the set $\omega$ with cardinality $\aleph_0$ corresponds to what we normally know as the natural numbers $\mathbb{N}$, and the set $\mathcal{P}(\omega)$ with cardinality ...