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
39 views

What can we conclude if $\mathcal{N}$ is an elementary extension of $\mathcal{M}$?

In particular, if $\mathcal{N}$ is an elementary extension of $\mathcal{M}$, can we immediately conclude that if $\mathcal{M} \models T$, then $\mathcal{N} \models T$? Why or why not? My line of ...
2
votes
2answers
88 views

Check my proof of “overspill” in non-standard models of Peano arithmetic.

Proposition Let $\mathcal{M}$ be a nonstandard model of Peano arithmetic, $\phi(v,\bar{w})$ a formula in the language of arithmetic, and $\bar{a} \in \mathbb{M}$. Show that if $\mathcal{M} \models ...
1
vote
0answers
81 views

Definitions of isomorphism and elementary substructures

Let us define -all the definitions are from V. Manca, Logica matematica, 2001, 'mathematical logic'- a $\Sigma$-morphism as a function $f:D_1\to D_2$ between models $\mathscr{M}_1$ and ...
2
votes
1answer
62 views

Show that the subset of a real ordered field defined by a ring formula has a least upper bound.

So currently trying to get well practiced in model theory, and i have come across the following question which i need some help with. Esentially let $S \subseteq \mathbb{R}$ be a non empty set, ...
1
vote
1answer
40 views

Show that any model of $\Delta$ is a Nonstandard Model of Arithmetic

I was hoping that someone could help check my proof. I originally thought I was spot of with my proof, but my professor suggested that my method was wrong. So, I went to check the hint in the back of ...
0
votes
1answer
51 views

Two Place Position and Model Question

! i get trouble in one multiple choice question in logic course: any one could help me with some description ? if we have Two-place position predicate, like : 1) all models of $\varphi$ is ...
2
votes
1answer
39 views

Find a formula that separate between structure

I have language $ L = \{ < \} $. I have the following structures: $|M| = \{ 1-\frac{1}{m} |m\in Z, m >1\} $ $|N| = \{ 1-\frac{1}{m} - \frac{1}{n} |m,n\in Z, m,n >1\} $ I need to find a ...
0
votes
1answer
41 views

Could someone give a concrete example of an amalgamation from model theory?

The theorem I have in mind can be found in page 135 of this book: ...
0
votes
2answers
66 views

If $\nu : \mathcal{M} \rightarrow \mathcal{N}$ is an elementary embedding, then is it true that $\mathbb{M} \subseteq \mathbb{N}$?

Exactly as the title suggests: If $\nu : \mathcal{M} \rightarrow \mathcal{N}$ is an elementary embedding, then is it true that $\mathbb{M} \subseteq \mathbb{N}$?
0
votes
2answers
54 views

what does the “fixed point” in fixpoint algorithms refer to?

I was reading the following powerpoint here to remember something I studied a long time ago. http://www.cs.cmu.edu/~emc/15-820A/reading/lecture_1.pdf the 12th slide is labeled fixpoint algorithms, ...
3
votes
0answers
52 views

Proving amalgamation property in model theory

Restate the proposition Suppose $\mathcal{M}_0$, $\mathcal{M}_1$, and $\mathcal{M}_2$ are $\mathcal{L}$-structures and $j_i ~:~ \mathcal{M}_0 \rightarrow \mathcal{M}_i, ~(i = 1,2)$ is an elementary ...
1
vote
1answer
55 views

Using first order sentences, how would you write down the axioms of finite field?

Suppose my language is $\mathcal{L} = \{+,-,\cdot,0,1\}$. My attempt is as follows: $$ \forall x \forall y \forall z (x - y = z \leftrightarrow x = y + z)\\ \forall x x \cdot 0 = 0\\ ...
2
votes
1answer
92 views

Prove elementary amalgamation theorem in model theory.

Restate the proposition Suppose $\mathcal{M}_0$, $\mathcal{M}_1$, and $\mathcal{M}_2$ are $\mathcal{L}$-structures and $j_i ~:~ \mathcal{M}_0 \rightarrow \mathcal{M}_i, ~(i = 1,2)$ is an elementary ...
2
votes
0answers
71 views

Examples of forcings which add no “definable” Aronjain tree

Maybe a bit board question but: Fixing a regular cardinal $\kappa$ in the ground model, I am looking for examples of set forcing notions which preserve regularity of $\kappa$ and add no new $\kappa$ ...
4
votes
1answer
85 views

Suppose some theory T has countably many axioms, how many models of $T$ are there of cardinality $\aleph_1$,$\aleph_2$,$\aleph_{\omega_1}$?

Setting Let $\mathcal{L} = \{E\}$ where $E$ is a binary relation symbol. Let $T$ be the $\mathcal{L}$-theory of an equivalence relation with infinitely many infinite classes. So we see $T$ has ...
2
votes
1answer
84 views

Using first order sentences, axiomize the $\mathcal{L}$-theory of an equivalence relation with infinitely many infinite classes.

Problem Let $\mathcal{L} = \{E\}$ where $E$ is a binary relation symbol. Let $T$ be the $\mathcal{L}$-theory of an equivalence relation with infinitely many infinite classes. Current Solution ...
4
votes
3answers
88 views

How would you define the set of even numbers in $\mathbb{Z}$ using a first order sentence?

Given a language $\mathcal{L} = \{+,0\}$ and structure $\mathcal{M}$ with underlying universe $\mathbb{Z}$, I would like to write a formula or sentence $\phi$ so that the set $$\Big\{ \bar{a} ~:~ ...
0
votes
2answers
33 views

Domain of functions interpretated in model

I read (V. Manca, Logica matematica, 2011) that the set $T_\Sigma(V)$ of the terms on a signature $\Sigma$ and variables $V$ is inductively defined letting, for any generic variable $x$, ...
7
votes
1answer
104 views

Is $\mathbb{N}$ definable in $(\mathbb{Z},0,S)$?

Is the subset of natural numbers (first-order) definable in the structure $(\mathbb{Z},0,S)$ ($S$ is the successor function)? I believe that it cannot, since $\mathbb{N}$ is exactly the set of ...
2
votes
2answers
101 views

Examine my argument that $\mathbb{Z} \oplus \mathbb{Z} \not\equiv \mathbb{Z}$

Setting Let $\mathcal{L} = \{+,0\}$. I want to show that $$\mathbb{Z} \oplus \mathbb{Z} \not\equiv \mathbb{Z}$$. Note $\equiv$ means elementary equivalence in this question. Updated Problem My issue ...
0
votes
2answers
94 views

A proof of the Löwenheim-Skolem-Tarski theorem

The Löwenheim-Skolem-Tarski theorem, which says that If a theory has a model of a given infinite cardinality, then it has models of any greater infinite cardinality is proved by my textbook in the ...
0
votes
2answers
83 views

A first order sentence such that the finite spectrum of that sentence is the following subsets of $\mathbb{N}^+$.

I would like to find a language $\mathcal{L}$ and first order sentence $\phi$ of $\mathcal{L}$ so that its finite spectrum is $\{p^n ~:~ n > 0, \text{ p is prime}\}$ $\{ p ~:~ p \text{ is ...
0
votes
1answer
49 views

Show some $\mathbb{X} \subseteq \mathbb{N}^+$ occurs as the finite spectrum of a sentence for this language.

Setting Define the finite spectrum of an $\mathcal{L}$-sentence $\phi$ as $$\{ n \in \mathbb{N}^+ ~:~ there ~ is~ \mathcal{M} \models \phi ~with~ |\mathbb{M}| = n\}$$ And let $$\mathbb{X} = \{ 2^n ...
2
votes
1answer
30 views

Walk me through the proof that the class of graphs is elementary.

I am attempting problem 1.4.5 in "Model Theory" by Marker, but I am very lost in terms of how to get started. So to help me with the process I would like someone to show me that the class of graphs is ...
0
votes
1answer
114 views

Distinguish between substructure, submodel, elementary substructure, and elementary submodel.

I can see (although I must not really understand) the definition of these terms, but could someone please explain the difference between these concepts, and whether any one of them imply the other? ...
0
votes
1answer
60 views

How to calculate the cardinality of a model

I know, thanks to some clarifications received from a user of this site, the definition of a model. When evaluating the cardinality of a model by taking the interpretations of all the constants, ...
2
votes
1answer
70 views

What is finite in a finite model

I am studying some theorems of model theory in an introductory text of mathematical logic. I know that a model is a way of associating the relationary symbols of a signature $\Sigma$ to $k$-ary ...
5
votes
2answers
97 views

No proposition $\chi$ such that $\mathscr{M}\models\chi\iff\mathscr{M}$ is infinite

Let notation "$\models$" be used for the two following case: let $\mathscr{M}\models\varphi$, where $\mathscr{M}$ is an interpretation model and $\varphi$ is a proposition, mean that $\varphi$ holds ...
0
votes
0answers
54 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
80 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 ...
2
votes
3answers
95 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
1answer
50 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
62 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 ...
1
vote
1answer
58 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
91 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 ...
4
votes
2answers
85 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
1answer
74 views

Expressing continuity and differentiability in a given language

Let $f,g$ be binary function symbols, $P$ a binary predicate symbol, $c,d$ constant symbols and let $\mathcal{L} := \{f,g;P;c,d\}$. Consider ...
1
vote
2answers
134 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
60 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
1answer
74 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
19 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
47 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
81 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
81 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
326 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
97 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
52 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
39 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
55 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
40 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 ...