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

0
votes
0answers
21 views

Definable sets, substructures and unions

Ok so my question is as follows; Let A be a substructure of B and S $\subset$ B be a definable set define by a universal formula $\phi(x)$, I need to show that in A $\phi$ defines $A \cap S$ My ...
0
votes
1answer
51 views

L-sentence which expresses bijective function

I've stumbled upon this exercise from "Sets, Models, Proofs" and can't seem to find a solution. It goes like this: Let $L$ be a language with just one 1-place function symbol $F$. Give an ...
1
vote
2answers
65 views

Possible not countable extension of the natural numbers?

This question comes from:Is $1234567891011121314151617181920212223......$ an integer? We define $\mathcal{A}$ as the set of infinite strings of digits $$ \bar a_i=a_0 a_1a_2a_3\cdots a_i \cdots ...
1
vote
0answers
31 views

What is an omega model?

I went to a seminar and a side question was if a theory had an omega model, however from the context I could not deduce the exact meaning. Does an omega model have a general meaning in mathematical ...
0
votes
2answers
39 views

Show this language structure models this sentence.

In an effort to educate myself, I am attempting the second problem in first chapter of the book "Model Theory" by Marker. The problem is reproduced below: Let $\mathcal{L} = \{\cdot, e\}$ be the ...
0
votes
1answer
22 views

Show every boolean combination of $\mathcal{L}$-formula is equivalent one with quantifiers.

This is part 2 of a question I asked here: Prove this claim about language and structures. The setting is that suppose $\phi_1,\ldots,\phi_n$ are $\mathcal{L}$-formulas and $\psi$ is a Boolean ...
1
vote
1answer
65 views

Prove this claim about language and structures.

I have a very thin background in logic and I am attempting the first problem in first chapter of the book "Model Theory" by Marker. The problem is reproduced below: Suppose $\phi_1,\ldots,\phi_n$ are ...
5
votes
2answers
64 views

Are there elementarily equivalent models $\mathcal{M}, \mathcal{N}$ of the same cardinality s.t. neither can be elementarily embedded into the other?

Do there exist elementarily equivalent models $\mathcal{M}, \mathcal{N}$ of the cardinality $\kappa=\omega$ such that neither can be elementarily embedded into the other? If the models were not ...
1
vote
2answers
75 views

What are some applications of model theory?

In an attempt to "broaden my horizons", I am taking a class on model theory, which follows this book: http://u.math.biu.ac.il/~dahari/download/Mathematical%20Logic/Elad%2022.pdf Skimming through the ...
1
vote
1answer
41 views

Is it possible to characterize the theory of Integral domains with first-order logic alone ?

Is it possible to characterize general ring theory with first-order logic alone ? Is it possible to do so for the theory of Integral domains ?
1
vote
0answers
28 views

Principal Ultrafilter implies Isomorphic Ultraproduct

Let $\mathfrak{F}=\{X\subseteq \mathbb {N} \mid 17\in X \}$ (Note that $\mathfrak {F}$ is principal ultrafilter) and: Let $\mathfrak{N}$ be the standard model for arithmatic and ...
0
votes
0answers
18 views

Least finite linear orders with same theory in monadic second order logic.

Today I want to ask a relaxed version of my last question. So if somebody finds a solution to that question he will immediately get a solution for this question here. Question. Let $m<\omega$ ...
2
votes
0answers
32 views

When do finite linear orders have the same theory in MSO?

Let $\mathfrak A$ and $\mathfrak B$ be finite linears orders and $m<\omega$. Then we have $$\mathfrak A \equiv^m_{FO}\mathfrak B \quad\text{iff}\quad |A|=|B| \,\, \text{or}\,\, |A|,|B|\ge 2^m-1.$$ ...
2
votes
0answers
62 views

$\overline{\mathbb Q}$ and $\mathbb C$ same first order theory

How do you show that $\overline{\mathbb Q}$ (the algebraic closure of $\mathbb Q$) and $\mathbb C$ have the same first order theory over the signature $(0,1,+,\cdot)$?
0
votes
1answer
64 views

First Order Logic prove there exists a Model that has an infinite member

I'm doing some extra self-exercises on first order logic (I'm taking the course through open university) and I've come across this question: Let there be a language $L = \{ +, \cdot, 0, 1, < ...
10
votes
1answer
218 views

First Order Logic: Prove that the infinitely many twin primes conjecture is equivalent to existence of infinite primes

I'm learning First Order Logic independently using a college textbook. I've been doing some self exercise question in it and came across this one, which I can't seem to figure out how to do: Let ...
1
vote
1answer
92 views

Prove that for an arbitrary (possibly infinite) language, that for a finite L-structure $M$, if $M \equiv N$ then $ M \cong N$ [duplicate]

Prove that for an arbitrary (possibly infinite) language, that for a finite L-structure $M$, if $M \equiv N$ then $ M \cong N$ I'm struggling to think of what to do, I presume the best thing is ...
2
votes
1answer
49 views

Let $M$ and $N$ be $L$-Structures, $h\colon M \cong N$ an isomorphism. Show $h$ is an elementary map.

Let $M$ and $N$ be $L$-Structures, $h\colon M \cong N$ an isomorphism. Show $h$ is an elementary map. I'm not even sure where to begin at the moment. I was informed of "induction on the ...
1
vote
0answers
35 views

Formula for automorphism between sequence of real numbers

Here's the question: "Suppose that $r_1<r_2<\ldots<r_n$ and $s_1<s_2<\ldots<s_n$ are two increasing sequence of real numbers. Let $\mathfrak{R} = (\mathbb{R};<)$. Write down a ...
3
votes
2answers
48 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
38 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
98 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
87 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
62 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
52 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
25 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
54 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 ...
3
votes
2answers
57 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
56 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
118 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 ...
8
votes
1answer
115 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
54 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
86 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 ...
2
votes
1answer
63 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
50 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
40 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
54 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
48 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
43 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
72 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
52 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
83 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
129 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
37 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
65 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
46 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
70 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 ...
15
votes
5answers
1k 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
45 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
48 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 ...