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 ...
2,224 questions
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}, <) ...
