Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [model-theory]

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 ...

1
vote
1answer
25 views

What does the word “extend” mean in the context of model theory?

Consider the following two problems: (1) Let $L=\{E\}$ be a language consisting one binary relation symbol. Let $T$ be the $L$-theory saying that $E$ is an equivalence relation with infinitely many ...
1
vote
1answer
30 views

Elementary substructure in the ring of polynomials

Let $K$ be a commutative ring and $u, t$ be infinite sets of formal variables such that $u \subset t$. Prove that $K[u]$ is an elementary substructure of $K[t]$ with signature $\sigma = \{+, \cdot ,1, ...
1
vote
0answers
40 views
+50

$\exists^\infty$-elimination and model companion.

In the book Ziegler, Tent: A course in model theory it states Exercise 5.5.7. Let $T_1$ and $T_2$ be two model complete theories in disjoint languages $L_1$ and $L_2$. Assume that both theories ...
2
votes
1answer
51 views

Class Absoluteness on $V$ with ZF-Models

There's a bit about models and absoluteness in particular that confuses me (I think my question is related to Noah Schweber's answer to Why cumulative hierarchy of Sets is not model of ZF). In Kunen's ...
2
votes
1answer
50 views

Showing two sets of formulas are logically equivalent using induction.

Can someone let me know if my proof is okay for showing the following two sets are logically equivalent (in propositional logic)? I asked this a day or so ago but the post was very long, disorganized, ...
2
votes
1answer
47 views

Choicelike consequence of compactness

Could someone please elaborate on the proof of Corollary 3.2.? Why does one need a total order *on $F$* if one is just interested in well-ordering each $F_x$ (in order to choose one element)? Also, a ...
1
vote
0answers
15 views

Definable subsets of a cartesian product of two structures

Below I reproduce a consequence of the Feferman-Vaught theorem, taken from Wilfrid Hodges' book Model Theory: Corollary 9.6.4: Let $L$ be a first-order language, let $A$ and $B$ be $L$-structures ...
0
votes
0answers
20 views

Criterion for $\mathcal L$-structure to be a model of universal theory

Let $T$ be a universal (universally axiomatizable) theory of signature $\mathcal L$ without functional symbols. Let also $M$ to be an $\mathcal L$-structure. Prove that if every finite substructure of ...
3
votes
2answers
51 views

Understanding the proof of $V=L \rightarrow \Diamond$

I am trying to understand the proof that $\Diamond$ holds in the constructible universe. I am following Kunen's Set Theory, where the proof is on pages 230-231 (the more recent, 2011 edition). I am ...
1
vote
0answers
22 views

Elementary substructure and existentially closed

Definition. We say that $\mathcal{M} \models T$ is existentially closed if whenever $\mathcal{N} \models T$, $\mathcal{M}\subseteq \mathcal{N}$, and $\mathcal{N}\models \exists x \phi(x, a)$, where $a ...
2
votes
2answers
85 views

Löwenheim-Skolem and proper class models of ZFC. [duplicate]

Let $N$ be a proper class model of ZFC and $x \subset N$ a set. Show that there is a set $y \in N$ such that $x \subset y$. If $x \subset N$, I think that by the downward's part of Löwenheim-Skolem, ...
0
votes
0answers
10 views

How is the realization of Ehrenfeucht-Mostiwski type defind?

For two (maybe different) linear orders $(I,<)$ and $(J,<)$ let $(a_j)_{j<J}$ and $(b_i)_{i<I}$ be two sequences. Let A be a parameter set and $\mathcal{EM}\big((a_j)_{j<J}/A\big)$ the ...
-2
votes
1answer
23 views

Existence of total order for every set

please prove it from Compactness theorem for propositional logic. Don't assume AC in any form. I mean relation $<$ is total order for $X$ iff trichotomy transitivity irreflexivity are true about $...
0
votes
1answer
37 views

Class of rings with all nilpotent elements is not axiomatizable

Prove that class of rings with all elements being nilpotent is not first order axiomatizable in signature $\{+, \cdot, 0, 1, = \}.$ I need some hints how to approach this problem. All similar ...
2
votes
1answer
29 views

Show that there are exactly $\aleph_0$-many countable $L$-structure if $L$ consists of one unary relation symbol.

$\textbf{First question:}$ Let $L=\{R\}$ be a language consisting of one unary relation symbol. Show that there are exactly $\aleph_0$-many countable $L$-structures up to isomorphism. My (attempted) ...
0
votes
1answer
37 views

Special formula, term, structure and assignment

I am trying to find (in a suitable language) a (simple) formula $\phi$, a term t, a structure $\mathcal{M}$ and an assignment b so that for $b':=b_{x/\overline{b}(t)}$ we get a different value for $\...
2
votes
3answers
68 views

Formula so that $(\forall x \ \phi \rightarrow \forall x \ \psi) \rightarrow \forall x (\phi \rightarrow \psi)$ is not valid

I am looking for an example of a formula of the form in the title of this post which is not valid. I am very much looking forward to your replies!
0
votes
1answer
60 views

Models of extensionality and comprehension without union

I want to find a model that satisfy comprehension and extensionality axiom but that it does not satisfy union axiom. I think that $M:=\{a,b,c,d,e,g\}$ with $\in^M=\{(a,b),(a,c),(b,e),(c,d),(e,g),(d,g)\...
2
votes
1answer
29 views

Tent & Ziegler, Lemma 7.2.11

I try to understand the proof of Lemma 7.2.11 in Tent&Ziegler book: "If $(a_i)_{i\in I}$ is independet over A and $J<K$ are subsets of I, then $tp((a_k)_{k\in K}/A\cup\{a_j|j\in J\})$ does not ...
17
votes
4answers
2k views

Why can't we prove consistency of ZFC like we can for PA?

this might be a silly question, but I was wondering: PA cannot prove its consistency by the incompleteness theorems, but we can "step outside" and exhibit a model of it, namely $\mathbb{N}$, so we ...
3
votes
1answer
44 views

$\vDash (\forall x \forall y \forall z (R(x,y) \land R(y,z)\rightarrow R(x,z)))\land (\forall x \exists y R(x,y)) \rightarrow \exists x R(x,x) $

Prove that the following formula is true in every structure or construct a structure as a counterexample where the formula is not true: $(\forall x \forall y \forall z (R(x,y) \land R(y,z)\...
2
votes
1answer
19 views

Uper-bound on length of paths in graph

Let $T_g$ be the theory of simple graphs (no loop, undirected) in the language $\mathcal{L}=\{R\}$ where $R$ is a binary relation. Let $T$ be an $\mathcal{L}$-theory such that $T\models T_g$ and ...
-1
votes
1answer
36 views

What is the relation between these two meanings of “theory”?

In this introduction on Satisfiability modulo theories, it is explained that by a "theory" $T$, it is meant a tuple $(\Sigma, I)$ where $\Sigma$ is a signature (i.e. a set of non-logical symbols), and ...
0
votes
0answers
34 views

Why do finite restrictions of members of back and forth system are also back and forth systems and not just any restriction?

I was trying to show the following (from these notes pg 65): Define a finite restriction of a bijection γ : X → Y to be a map γ|E : E → γ(E) with finite E ⊆ X. If Γ is a back-and-forth system ...
1
vote
1answer
48 views

Spectrum of a sentence $\varphi$ with no equality sign

Assume $\varphi$ is a sentence without the equality relation. Show that if $k \in Sp(\varphi)$ and $n > k$ then $n \in Sp(\varphi)$. $Sp(\varphi)$ is the spectrum of $\varphi$, so it is the set of ...
1
vote
1answer
38 views

Model of ordered plane with the negation of Pasch's axiom

I am interested in finding the model of particular set of geometry axioms in which Pasch's axiom fails. First I'll give the definitions. By ordered line I mean the set $L$ (line) with one three-...
1
vote
0answers
21 views

Show that any complete consistent witnessing set of sentences has a closed term

Let $L$ be a first-order language. A set $\Sigma$ of $L$-sentences is witnessing if for every sentence in $\Sigma$ of the form $(\exists v) \xi(v)$, there exists a closed $L$-term $\lambda$ with $\xi(\...
0
votes
1answer
31 views

Transitive classes and $\Delta_0$- absoluteness.

I want to show that in $L_{\epsilon}$, formulas in $\Delta_0$ are absolute, that is $$\phi \leftrightarrow \phi^M$$ where $M$ is a transitive class and $\phi^M$ denotes the relativization of $\phi$ ...
1
vote
2answers
28 views

Satisfaction of a sentence in a model

I'm a little confused about satisfaction of formulas (in particular of sentences). Consider a concrete example. Let $L=(\cdot, ^{-1},e)$ be the language of groups and consider its model $M$ with ...
2
votes
1answer
55 views

Reconstructing a non-$\omega$-categorical countable structure from its automorphism group

Let $M$ and $N$ be countable structures. If $M$ and $N$ are both $\omega$-categorical, then we know that $M$ and $N$ are bi-interpretable iff $\mathrm{Aut}(M) \cong \mathrm{Aut}(N)$ as topological ...
1
vote
1answer
97 views

Almost universal class

I so stuck with a problem of set theory. But first a recursive definition: Define $R_0=\emptyset$ If $R_\alpha$ is defined, then $R_{\alpha+1}=\mathcal{P}(R_\alpha)$ (the power set). For a limit ...
1
vote
1answer
34 views

Is the value group of an algebraically closed valued field divisible?

Is the value group of an algebraically closed valued field divisible? Since Every existentially closed abelian group is divisible, I'm trying to show the value group is existentially closed but I don'...
0
votes
1answer
70 views

What’s the relation between definability of a class of structure and the completeness of a set of axioms?

Please help me with confusions of following terms: 1.Incompleteness 2.undefinable 3.non-standard model If a structure has non-standard counterpart under a certain set of axioms, does that mean such ...
4
votes
2answers
69 views

How is “interpretation” used differently in propositional vs. first-order logic?

I am confused on the usage of the word "interpretation" and/or "model" when it comes to propositional logic versus first-order logic because there are so many conflicting / unclear notions that I ...
0
votes
0answers
27 views

Algebraic independence with a first order fornula

Is it possible to express the algebraic indipendence of a finite number of elements with a first order language?
0
votes
2answers
42 views

How does one show a set of sentences are models of infinite vectors spaces over F?

I was going through these notes and had the following: where $F$ is a field and $V$ is a group. Note that $\Sigma_{F}$ is the set of sentences whose models are exactly the vector spaces over $F$ (I ...
0
votes
1answer
92 views

Confusion over the definition of “model”

In my question yesterday I asked about the definition and usage of the word "model", for which I was told the following definition: A formula of propositional logic is true under an interpretation ...
1
vote
1answer
51 views

Definable sets in a $\kappa$-saturated structure.

Exercise 5.2.4. in Ziegler, Tent: A Course in Model Theory states: If (the $L$-structure) $\mathfrak{A}$ is $\kappa$-saturated, then all definable subsets are either finite or have cardinality at ...
14
votes
1answer
96 views

Exponentiation and a weak fragment of arithmetic

The title is slightly misleading, since the theory I'm looking at is an extension of PA; however, the question is "morally" about very weak arithmetic. Specifically, consider the following theory PA':...
0
votes
1answer
63 views

Back-n-Forth or a Direct Isomorphism Between A Countable DLO Without Endpoints and $U = \{ \frac{m}{2^n} \}$

Note: I changed this question and deleted my answer, bringing it into the question for quick review. The proof now has the same brevity as the back-and-forth method found in wikipedia. Let $P$ be a ...
0
votes
1answer
31 views

Hodges' definition of the Robinson Diagram

Thanks to the answer here, I think I understood what are elementary/atomic diagrams. I'm reading Hodges' textbook now, and he defines a diagram a bit differently: for $A$ an $L$-structure and a ...
1
vote
0answers
25 views

Homomorphisms of structures preserve terms

Suppose $A,B$ are $L$-structures and $f:A\to B$ is a homomorphism. I'm trying to show that if $t(x)$ is a term, then $f(t^A(a))=t^B(f(a))$. Suppose $t(x)=x_i$. Then $f(t^A(a))=f(a_i)$ and $t^B(f(a))=...
0
votes
0answers
28 views

Constructing embeddings (Lemma 2.3.3 from Marker)

Lemma 2.3.3 from Marker: Suppose $\mathcal N$ is an $\mathcal L_M$-structure and $\mathcal N\models \operatorname{Diag}( \mathcal M)$; then, viewing $\mathcal N$ as an $\mathcal N$-structure, there ...
-1
votes
1answer
40 views

Atomic and elementary diagram of an $\mathcal L$-structure

Definition. Suppose that $\mathcal M$ is an $\mathcal L$-structure. Let $\mathcal L_M$ be the language where we add to $\mathcal L$ constant symbols $m$ for each element of $M$. The atomic ...
0
votes
1answer
52 views

Understanding definable sets

enter image description here This is part of Marker's book on Model theory. I have a hard time understanding the example given there. First of all, he says "Let $\mathcal M$ be a ring", which is ...
3
votes
2answers
54 views

Are there exist any aleph-one categorical theories which are not strongly minimal? [closed]

Is every aleph-one categorical theory strongly minimal?Are there exist any aleph-one categorical theories which are not strongly minimal?
8
votes
0answers
48 views

Simpler way to build large $\omega$-models

Consider the following statement: $(*)\quad$ There are $\omega$-models of ZFC of arbitrarily large cardinality. This is provable in ZFC + "There is an $\omega$-model of ZFC" alone. The proof I ...
4
votes
1answer
41 views

Completeness and homomorphisms between models

Suppose that $T$ is the first-order theory of a given class of models $C$ over some signature. Suppose $M$ is an arbitrary model of $T$. Does it follow that there is always a model $M'\in C$ and ...
5
votes
0answers
174 views

Is many sorted logic really a unifying logic?

I am reading "Extensions of First Order Logic" by Maria Manzano (1996). It develops the thesis that "[M]ost reasonable logical systems can be naturally translated into many-sorted first order ...
1
vote
1answer
58 views

Is $Th(\mathbb{Z}, <) \cup Diag (\mathbb{Q}, <)$ satisfiable?

I want to show that there exist $\mathcal{M} \equiv (\mathbb{Z}, <)$ and an order-preserving embedding $\sigma :\mathbb{Q} \rightarrow \mathcal{M}$. It's enough to see that $ Th(\mathbb{Z}, <) ...