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

Give an example of a structure of cardinality $\omega_2$ that has a substructure of $\omega$ but no substructure of $\omega_1$

Give an example of a structure of cardinality $\omega_2$ that has a substructure of $\omega$ but no substructure of $\omega_1$ This is from Hodges' A Shorter Model Theory. My idea is to take ...
0
votes
1answer
42 views

Sentence $\phi_n$ is true in $S$ iff $S$ has at most $n$ elements

I'm trying to prove this result: For any natural number $n \geq 1$ there is a sentence $\phi_n$ such that $\phi_n$ is true in $S$ iff $S$ has at most $n$ elements. My attempt: By induction ...
0
votes
0answers
18 views

Definition of prime model extension over a set

Standard definition of prime model over a set is that: $M\vDash T$ is said to be a prime model extension of a set $A$ if $A\subset M$ and any partial elementary map $A\rightarrow N$ ($N\vDash$) extend ...
2
votes
2answers
70 views

How does the Soundness Theorem follow from this lemma?

The soundness theorem is a famous theorem in logic that goes like this: If $\Gamma \vdash \phi$, then $\Gamma \vDash \phi$. It's supposed to follow readily from Lemma 3.2.3 from Moerdijk/Van ...
0
votes
1answer
28 views

Is the theory of real closed fields expanded by restricted analytic functions decidable?

Is the theory of real closed fields expanded by restricted analytic functions decidable? I have been doing a lot of reading on the subject, but I can't quite find a straight answer on this one. The ...
0
votes
1answer
37 views

Winning strategy for graphs (Ehrenfeucht-Fraïssé games)

I'm stuck with a question: Proof that you can't express if a graph is cyclic in first-order logic. The definition of cyclic is that for every node there is a ...
0
votes
1answer
30 views

Doubt about the proof on uniqueness of saturated model

A standard proof for the fact that any 2 saturated models of the same cardinality are isomorphic can be found here But I have doubt about this. Specifically, the construction of the next partial ...
2
votes
1answer
83 views

Why are algebras classified as being of a certain type?

In Grätzer's, Universal Algebra, page 33, Grätzer defines the concept of an algebra of type $\tau$, as follows: An algebra $\mathfrak{A} = \langle A ; F \rangle$ of type $\tau$ is a pair, where ...
1
vote
0answers
33 views

How can a structure for a formal language be defined? [duplicate]

I'm learning some stuff about formal languages and structures for them. However there's this thing I don't understand. How can we ever define/specify a structure for a language, if we do not yet have ...
0
votes
0answers
58 views

“there are infinitely many” with finitely many variables

I vaguely recall reading somewhere that one cannot say "there are infinitely may" using a formula with only finitely many variables. A bit more precisely, let $\mathcal L$ be the result of extending ...
1
vote
1answer
32 views

Finite set of formulas from $L(A)$ is realized iff it is consistent with $Th(\mathfrak{A})$

Let $\mathfrak{A}$ be an $L$-structure with domain $A$. If $\Sigma$ is a finite set of formulas in $L(A)$, how can I prove that $\Sigma$ is realized in $\mathfrak{A}$ iff it is consistent with ...
3
votes
1answer
63 views

Are the hyper-reals countably transitive?

A hyper-real field is $ R^*=(R^N)_{/U}$ where $U$ is a free ultrafilter on $N$. If A and B are any countable order-isomorphic subsets of $R^*$, is there an order-automorphism of $R^*$ that maps $A$ ...
6
votes
2answers
94 views

Defining the existence of a non algebraic element in the language $L:= \{0,1,+,\cdot\}$

I raise following question after reading this post. Is it possible in the language $L:= \{0,1,+,\cdot\}$ to write sentences for which a model will necessarily contain a copy of $\mathbb Q$ and a non ...
5
votes
1answer
41 views

Can this sequence be a hyperreal number? What would be its real part?

Consider the sequence $\{a_n\} = \{\sin(n) \mid n\in \mathbb N \}$. Can this sequence be viewed as a hyperreal number? What could be its real part? Any intuition would be highly appreciated :) ...
0
votes
1answer
40 views

(Sphere Lemma) Hanf locality Lemma and locally threshold testability

I am reading the proof of Hanf's Sphere Locality lemma for (finite or infinite structures but with bounded degree), and I'm trying to understand the details of the proof! I'm confused with the ...
2
votes
1answer
52 views

Local isomorphism question in logics

The definition of a local isomorphism between structures: a local isomorphism between structures $\mathcal{A}$ and $\mathcal{B}$ over an alphabet $L$ is a finite relation $$\{ ...
5
votes
1answer
69 views

Given any set of consistent axioms, is it always possible to find a model for these axioms in ZFC set theory?

If not, are there any conditions under which there must be a model under ZFC theory? Alternatively, is there any set of axioms for which this does hold true? If so, can we drop some of the axioms and ...
0
votes
1answer
27 views

Properties of transitive modal frames

I am working through Fitting and Mendelsohn's First Order Modal Logic and have come across the following exercise: Prove that a frame $\langle \mathcal{G}, \mathcal{R} \rangle$ is transitive if ...
3
votes
0answers
36 views

Model-theoretic characterization of local modal correspondence

I've been reading van Benthem's dissertation (available on ILLC's website) on modal correspondence theory. In Section I.3, he develops a model-theoretic characterization of modal formulas having ...
2
votes
1answer
75 views

What is the definition of a definable set of statements, and what is a constructive way to think of this regarding Tarski's Undefinability Theorem?

Logic and model theory are not my area so my thinking is probably off, but I am curious about this so please go ahead and set me straight. A definable set is one for which there is a formula that is ...
2
votes
1answer
39 views

Real Closed Fields with Predicate for a Dense Subfield

Consider $M = (\mathbb{R};+,<, \times, 0, 1, K)$ where $K$ is a unary predicate which holds on $\mathbb{Q}$ (or any dense subfield of $\mathbb{R}$). Question: Is it true that the parametrically ...
3
votes
1answer
36 views

Proving the Downward Löwenheim-Skolem using monotonic operators

This is another exercise from Kees Doets Basic Model Theory. Here's the idea. It's well known that the downward Löwenheim-Skolem theorem follows as an easy corollary of the following lemma using ...
3
votes
2answers
68 views

Proving that $\langle \omega+1, \leq \rangle$ and $\langle \omega + \omega^*, \leq \rangle$ are not elementarily equivalent

This is an exercise from Kees Doet's Basic Model Theory. The basic idea is to show that an ordering of type $\omega + 1$ is not isomorphic to an ordering of type of $\omega + \omega^*$, where ...
2
votes
1answer
40 views

number of types if isolated types are dense

Let $T$ be a countable, complete theory, $M\models T$ and $A\subset M$. Now, Theorem 5.12.16 in Srivastava's book "A Course on Mathematical Logic, 2nd Edition" says that $S_{n}^M(A)$ must be countable ...
5
votes
1answer
76 views

Completeness for Infinitary Logic?

I have heard a rumor that there is a proof system for certain infinitary logics, given by Carol Karp (?) in her thesis, but I can't find a copy. The result that I'm told exists is the following: A ...
3
votes
2answers
96 views

Is there an embedding of $\langle \mathbb{N} \setminus \{0\}, \leq, \times, 1 \rangle$ into $\langle \mathbb{N}, \leq, +, 0 \rangle$?

This appears to be a common beginning exercise in model theory (I found it both in Chang & Keisler and also in Manzano's Model Theory). It's not difficult to see that there is an embedding of ...
0
votes
1answer
38 views

Model theory exam question:Show that if $M$ is isomorphic to $N$, then there is an extention to signature $S*$ so that $M*$ isomorphic to $N*$

So I had an exam today, and this question was really difficult for me: Let $S$ be a signature with $S=\{<,f\}$, $n_f=2$. $M=(\mathbb R;<,+)$ and $N=(\mathbb R_{>0};<,\cdot)$, $+, \cdot$ ...
2
votes
3answers
59 views

Quantifier elimination over rationals.

My question is concerned with a statement in Marker's Model Theory. The statement is that for formula $\phi(a,b,c)=\exists x(ax^2+bx+c=0)$, we cannot have a quantifier free formula $\phi'$ such that ...
3
votes
1answer
33 views

Elementary substructure and elementary equivalence

So the subject I'm stumbling around a bit is elementary equivalence and elementary substructures. So maybe you could help me sort things out. So the definitions as I know them. Structures $M, N$ ...
1
vote
1answer
27 views

Over signature $S= \{f \}$, $n_f=1$, find a formula $\phi$ so that for every structure, $M \vDash \phi \implies|M|$ is infinite

Over signature $S= \{f \}$, $n_f=1$, find a formula $\phi$ so that for every structure, $M \vDash \phi \implies |M|$ is infinite I'm trying to solve this for a really long time. I tried to perhaps ...
2
votes
2answers
66 views

Proving that for structure $M=(\mathbb R; +,<,0)$, the function $f(x,y)=x \cdot y$ is not a definable set in $M$

Proving that for structure $M=(\mathbb R; +,<,0)$, the function $f(x,y)=x \cdot y$ is not a definable set in $M$. Note: A function is called a definable set, if its graph, meaning the set ...
3
votes
2answers
30 views

Let $T$ be a theory over $S$, prove that $T \vdash \{\phi \rightarrow \psi \} \iff (T \cup \phi) \vdash \psi$

Let $T$ be a theory over $S$, prove that $T \vdash \{\phi \rightarrow \psi \} \iff (T \cup \phi) \vdash \psi$. So this seems very obvious intuitively. I'm just not sure what is the 'technique' to ...
3
votes
0answers
113 views

Application of the reflection theorem in ZFC

In a proof that a certain theory $T$ in conservative over $\textsf{ZFC}$, the author makes the following step: (Here $\Delta$ is a finite set of formulas such that $\textsf{ZFC}\vdash\Delta$.) ...
2
votes
0answers
41 views

For signature $s= \{ f\}, n_f=1$, show that if for structures $M, N$, $f^N, f^M$ have only one orbit, of infinite order, then $M,N$ are isomorphic

For signature $s= \{ f\}, n_f=1$, show that if for structures $M, N$, $f^N, f^M$ have only one orbit, of infinite order, then $M,N$ are isomorphic. So we know that for some $m \in M$, the set ...
1
vote
1answer
24 views

A substructure that is elementary equivalent to its structure, isn't an elementary substructure example mistake?

So we were given this example to show that substructure that is elementary equivalent to its structure, isn't necessarily an elementary substructure. Just so I'll be clear on the definition: A ...
1
vote
0answers
35 views

Questions concerning a specific given theory.

Let $L$ be the a language containing countably many unary predicates $\{P_i : i\in \mathbb{N} \}$ and countable many constants $\{a_{i,j} : (i,j)\in \mathbb{N}^2 \}$. Let $T$ be the theory which says ...
3
votes
1answer
55 views

Ultraproducts explicit example

so I'm studying for my exam in the Model Theory course I take. I just can't really wrap my head around ultraproducts. It's so abstract and complex. Is there a place where I can be shown with an ...
1
vote
1answer
39 views

$\kappa$-categoricity in the language of identity

I have the following exercise from Dirk Van Dalen's Logic and Structure: Here with language of identity we mean the language with no extralogical symbols (i.e. no symbols of predicates, functions ...
2
votes
1answer
75 views

Number of non-isomorphic models

Let $C$ be the class of cardinals. Define by recursion $C_0 = C$, $C_\alpha = C_\beta\cup P(C_\beta)$ if $\alpha=\beta+1$ and $C_\alpha = \bigcup_{\beta<\alpha}{C_\beta}$ for limit $\alpha$ (Here ...
2
votes
4answers
87 views

Non-standard model of $Th(\mathbb{R})$ with the same cardinality of $\mathbb{R}$

Let $\mathfrak{R}= ⟨\mathbb{R},<,+,-,\cdot,0,1⟩$ be the standard model of $Th(\mathbb{R})$ in the language of ordered fields. I need to show that there exists a (non standard) model of ...
8
votes
2answers
175 views

Why do we know that Gödel sentences are true in the standard model of set theory, but do not know if the continuum hypothesis is?

By what methods can we identify sentences that are true in the standard model of set theory, but not in other models? In particular, how do we prove that Gödel sentences are true in the standard ...
6
votes
1answer
61 views

General notions of “basis” in algebra/model theory

Free groups, free abelian groups, and vector spaces all have a notion of 'basis': a subset $B$ of the structure such that everything in the structure can be written uniquely as a finite combination of ...
0
votes
1answer
33 views

Hardness of index sets for computable structures

Suppose we have a computable structure $M$ and we want to show that its index set $I(M)$ is (many-one) $\Gamma$-hard for some complexity class $\Gamma$ (like $\Sigma^0_2$). To do this, we need to show ...
-2
votes
1answer
40 views

Question concerning types, partial elementary maps and universality.

Show that the following are equivalent: $M$ realizes all $\lambda$-types of $M$ over $\emptyset$ for any $\lambda<\kappa$. For any $N\equiv M$ and any $A \subseteq N$ with $|A|<\kappa$ there ...
1
vote
1answer
35 views

On some equivalences of $\omega$-categoricity.

Let $T$ be a complete theory without finite models. Prove that the following are equivalent: $T$ is $\omega$-categorical. $T$ has a countable model which is both atomic and saturated. All models of ...
2
votes
0answers
27 views

Whether certain reducts of relational structures are themselves elementary classes?

Suppose I have a theory consisting of binary relation symbols $R$ and $S$. The theory is divided into a set of formulas involving only $R$ and equality, and also a single formula of the form ...
1
vote
1answer
38 views

Are A. Malcev's conditions first order?

There is a Russian paper by A. Malcev written in 1939 that give infinitely many jointly necessary and sufficient conditions for a (not necessarily commutative) monoid to be embeddable. Are those ...
2
votes
1answer
52 views

Simple examples of non-isomorphic but elementarily equivalent structures.

An uncountable example is obtained by considering dense linear orders without endpoints. Any two dense linear orders without endpoints are elemenatarily equivalent. But $\langle\mathbb{R},<\rangle$ ...
3
votes
1answer
22 views

Is the class of group-embeddable monoids an axiomatizable class?

Is the class of monoids which can be embedded in a group a first-order axiomatizable class? And if it is, is it finitely axiomatizable?
1
vote
1answer
36 views

Calculate rank of Morley in $ACF_{0}$

How I can calculate the Morley rank of the type $x = x$ in the theory $ACF_{0}$?