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 languages. Not to be confused with mathematical modeling.
3,205
questions
6
votes
0answers
27 views
Is there a space of all finite models?
Let $\mathcal{L}=\{R_i\}_{i \in I}$ be a relational language. There is a natural construction of a compact space of countable $\mathcal{L}$-structures, namely, the space $$ \prod_{R_i \in \mathcal{L}} ...
0
votes
1answer
48 views
Set-up for the Paris-Harrington Theorem
In his book "Models of Peano Arithmetic" Kaye proves the Paris-Harrington Theorem. He starts off by introducing a "simplification" then proves the short Lemma 14.11 about it (see ...
0
votes
0answers
19 views
Motivation of indicator construction in Kaye
Kaye says the following in his book about models of $\textbf{PA}$ on p. 198:
I have no clue what motivates the definition of $f_n(x, y)$. The reference made to Propositions 14.1, 14.2 don't help me ...
0
votes
0answers
59 views
Is there a notion of “product” that fits this description?
So I want to take an algebraic structure $A$ (given as a set and a function, maybe some relations eventually) and I want to make sure it is (countably) infinite. If it's already infinite, we do ...
1
vote
2answers
68 views
strict order property
I wanted to prove that the theory of ordered abelian group has a strict order property.
I know by the theory of Kikyo and Shellah we have:
a theory is unstable iff it has SOP or NIP
and by the :
https:...
-1
votes
1answer
31 views
End extension example for complete theory
I elaborate my previous question about example of complete theory, that has two models, $\mathfrak{A}$ and $\mathfrak{B}$, that $\mathfrak{A} \le_{end} \mathfrak{B}$, but $\mathfrak{A} \npreceq \...
0
votes
1answer
44 views
End - extension in the complete theory that isn't elementary extension
Could you prompt me, example of complete theory, that has, say, two models, $\mathfrak{A}$ and $\mathfrak{B}$, that $\mathfrak{A} \le_{end} \mathfrak{B}$, but $\mathfrak{A} \npreceq \mathfrak{B}$?
...
1
vote
1answer
18 views
Conjunction/disjunction of types
Let $T$ be a theory. A type $p(x)$ is a set of formulas in variable $x$ such that $T\cup p(x)$ is finitely satisfiable.
Question. What does disjunction (or conjunction) of types mean? More precisely, ...
6
votes
1answer
36 views
Can the axioms for real closed fields be weakened in this way?
I am told that real closed fields $(F,+,-,*,0,1,<)$ can be axiomatized by the axioms for ordered fields and also an axiom stating that every positive element has a square root and an axiom schema ...
1
vote
2answers
36 views
Are the field reducts of real closed fields first-order axiomatizable?
We know that the class of real closed fields $(F,+,-,*,0,1,<)$ is first-order axiomatizable. Is the $\{+,-,*,0,1\}$ class of reducts of real closed fields axiomatizable? This is different from my ...
2
votes
2answers
113 views
Infinity in ZFC vs infinity in the metatheory
I was reading about different ways to formalize the notion of infinity in ZFC. The classic axiom is of course to have the existence of an inductive set, but you can also assert the existence of a ...
2
votes
2answers
50 views
Are the theories of betweenness the same in $\mathbb{R}^n$ for all $n\geq 2$?
Consider $\mathbb{R}^n$, for some $n$ greater than or equal to $2$. We can form a structure by adjoining to it the ternary betweenness relation $B(x,y,z)$. Are all those structures elementarily ...
0
votes
0answers
37 views
Power Set, Replacement or Infinity axioms unprovable in set theory
My question is related to the independence of the Power Set, Replacement, and Infinity Axioms. Can we show that Power Set, for example, is unprovable in $ZFC-P$? Is $\neg$Power Set unprovable in $...
0
votes
1answer
62 views
Example of a quantifier elimination procedure for a simple-but-nontrivial theory
Is there a simple-but-nontrivial example of a concrete quantifier elimination procedure with a concrete theory, especially one that's a standard example of what a constructive argument for quantifier ...
2
votes
1answer
36 views
Free models of infinitary essentially algebraic theories
Let $\mathbb{T}$ be an essentially algebraic theory in which the operations are allowed to have infinite arity. It is known that not every such theory has a free/initial model; for example, there is ...
0
votes
1answer
45 views
How can any sentence be valid?
I've just started working through C. Chang and H. Keisler's Model Theory independently right now, and I'm reading through the first chapter, but I'm a little confused by the nature of a valid sentence....
4
votes
1answer
86 views
Constructing a model of non-negative integers $\mathbb{N}$
I am attempting problem 3.43 of MIT's Discrete Mathematics text.
Let $\mathbf{\tilde0}$ be a constant symbol and next and prev be the successor ("+1") and predecessor("-1") total ...
2
votes
1answer
46 views
Quantifier elimination of valued fields.
I have been reading the quantifier elimination theorem for valued fields, Theorem 3.26 on page 35 of these lecture notes by Lou van den Dries: http://homepages.math.uic.edu/~freitag/valfields.pdf
I do ...
1
vote
1answer
43 views
Is there a way to represent the relation $<$ on the real numbers without using multiplication?
I know for $x,y\in\mathbb R$ we have $x<y$ iff there exists a $z\in\mathbb R$, so that $y=x+z^2$. Is there a similar way to āproveā $x<y$ using only $+$ and $=$? And if not, is there a more or ...
6
votes
1answer
96 views
Are there nonstandard $\mathsf{PA}$ models without $\Delta^1_1$ cuts?
My question is the following:
Is there a nonstandard model $\mathcal{M}\models\mathsf{PA}$ such that $\mathcal{M}$ has no $\Delta^1_1$-with-parameters-definable nonempty proper successor-closed ...
0
votes
1answer
49 views
Determine if $Ļ$ has a finite and infinite model or not.
Let $\sigma = \{E\}$ be a signature with a two-digit relation symbol
$E$. Determine for the following $FO-[\sigma]$ formula, whether it has
a finite model and whether it has an infinite model.
$$Ļ := ā...
5
votes
1answer
70 views
“$\Sigma_1^1$-Peano arithmetic” - does it pin down $\mathbb{N}$?
Let $\mathsf{PA}_{\Sigma^1_1}$ be the theory in second-order logic gotten by extending the usual first-order Peano axioms to include arbitrary $\Sigma^1_1$ formulas in the induction scheme. My ...
1
vote
1answer
29 views
An example of a class of structures whose axiomatizability depends on the axiom of choice
Is there an example of a specific class $K$ of structures (in the sense of first-order logic), such that $K$ is first-order axiomatizable if the axiom of choice is assumed, but that its ...
8
votes
1answer
127 views
Consistency of theories with circles
We define the circle with the center point - $(a,b)$ and his radius - $r>0$ as:
$$B(a,b,r)=\{\langle x,y \rangle\ \in \mathbb{R}^2:(x-a)^2+(y-b)^2\le r^2\}$$
Let $A$ be the set of the plane's ...
1
vote
2answers
62 views
Upward Löwenheim-Skolem Theorem for logics without equality
The usual proof of the upward Lƶwenheim-Skolem theorem rests on the use of the equality symbol as a primitive symbol, interpreted in every relevant structure as true equality. My question is on how ...
2
votes
0answers
51 views
Boolean topoi and classical logic
Let $T$ be a theory in classical (finitary) first-order logic over some language $L$. Then $T$ is equivalent over classical logic to its Morleyization $T^m$, i.e. the theory in the language $L^m$ ...
0
votes
0answers
69 views
Satisfaction of $\Delta_0$ formula for proper class
I'm reading Kanamori's book on large cardinals, and on page 6 he defines truth of $\Delta_0$ formula for transitive proper class M as follows,
$\vDash^0_M$ $\phi[x_1,...,x_k]$ iff $\phi(v_1,...,v_k)$ ...
1
vote
1answer
28 views
Theory of bijection with no finite cycle has trivial associated geometry
I am working through the following exercise in Tent and Ziegler's A Course in Model Theory.
Exercise 5.7.2. Show that the theory of an infinite set equipped with a
bijection without finite cycles is ...
1
vote
1answer
49 views
Proof that $\bigcup_{i \epsilon I} A_{i}$ is an elementary substructure of $\mathfrak{U}$
I'm currently studying model theory with the book "A Course in Model Theory" by Katrin Tent and Martin Ziegler. Currently I have written a proof for Exercise 2.1.1, and I would like to know ...
2
votes
2answers
64 views
Is there a precise way to state that a structure does not satisfy a theory because its signature is different?
A structure $\mathcal{S}$ is a triple $<\sigma, D, I>$ containing a signature $\sigma$, which determines what functions and relations the structure is able to interpret, a domain $D$, which ...
4
votes
1answer
26 views
Proving the existence of models with large cardinality
I'm reading through Marker's Model Theory: An Introduction, and I'm confused by the proof of Proposition 2.2.2. The result is as follows:
Let $T$ be an $\mathcal{L}$-theory with infinite models. If $\...
3
votes
1answer
79 views
Can a theory prove (schematically) its axioms relativized to a set?
In $\mathsf{ZFC}$, a somewhat cheating way to buy "transitive models" without cost in consistency is to add to the language a constant symbol $M$ and add to $\mathsf{ZFC}$ the axioms stating ...
6
votes
1answer
145 views
Is the empty set empty in all models of set theory?
In Timothy Bays' excellent article on Skolem's paradox, I have been stumped by the following lines:
Let's grant that the specific element which serves as āthe empty setā
will not remain constant as ...
1
vote
1answer
25 views
What does Skolem's paradox have to do with “unrelativized quantification”?
Timothy Bays' excellent essay on Skolem's paradox includes the following claim:
... Skolem's Paradox doesn't introduce contradictions into various forms of axiomatized set theory, even when these ...
0
votes
0answers
18 views
Question about the defination of the first order Language [duplicate]
I see the different definitions of $\mathcal{L}$ .
First one is in the book :A First Journey through Logic
it says the language consists two parts:logical symbols and non-logical symbols.
the non-...
1
vote
1answer
44 views
Quantifier Elimination Pure Identity Language in Chang
In Chang & Keisler's Model Theory, quantifier elimination on the theory of the pure identity language is shown. However, I'm confused about the notion of "basic formula" for which any ...
2
votes
1answer
50 views
Can the conjunction of any two $\exists\forall$-sentences be expressed equivalently as a $\exists \forall$-sentence?
We say that a sentence is a $\exists\forall$-sentence iff it is of the form $\exists w_1\cdots\exists w_m\forall v_1\cdots\forall v_n \theta(\bar{w},\bar{v})$ where $\theta$ is quantifier-free. My ...
2
votes
1answer
59 views
Definable vs Interpretable Order
This is probably a trivial question but I'll ask it nonetheless.
What is the difference between an order being definable, and an order being interpretable? All texts I've read make a distinction ...
-4
votes
0answers
49 views
$\phi\models \psi$ and $\psi$ divides imply $\phi$ divides.
How can I prove the following statement?
If $\phi(x,b)\models \psi(x,c)$ and $\psi(x,c)$ divides over $A$, then $\phi(x,b)$ divides over $A$.
Here is my attempt: Since $\psi(x,c)$ divides over $A$ ...
3
votes
2answers
109 views
Example of complete formula on constants.
I have question considering example of complete formula, that was presented in Keisler/Chang - Model Theory:
2.3.1. EXAMPLES
(1). Let $T$ be a complete theory and let $c_0,c_1,c_2,\ldots$ be constant ...
1
vote
1answer
37 views
Can we omit surjectivity of homomorphism between structures?
I know the following fact (it can be proved using induction on the length of $\Phi$):
Let $\mathfrak{A,B}$ be algebraic structures (their domains are $A,B$), let $f:\mathfrak A\rightarrow\mathfrak B$ ...
1
vote
0answers
79 views
How can we trust second-order logic?
Letās accept for the sake of argument the ontology of set theories without proper classes. Sets (improper classes) are the only things at all. This is perhaps silly, but it will hopefully illustrate a ...
5
votes
0answers
151 views
How to prove Craig's interpolation using amalgamation?
Notice: I have cross-posted this question into MathOverflow, here https://mathoverflow.net/questions/383999.
I am looking for a sketch of, or a reference to, a proof which I can't seem to find in the ...
6
votes
1answer
84 views
Dividing over $C$ with parameters in $acl(B)$
Let $M\models T$ and $C\subset B\subset M$ be finite sets. Let $tp(a/d)$ divides over $C$ and $d\in acl(B)$. Can we conclude that $tp(a/B)$ divides over $C$?
Here is my attempt: Let $\phi(x,d)\in tp(a/...
0
votes
1answer
52 views
$\text{Sat}_{\Delta_0}(x, y)$ is $\Delta_1(\textbf{PA})$ (Kaye's book)
In Kaye's "Models of Peano Arithmetic" in chapter 9 on satisfaction a lot of effort is expanded to prove that $\text{Sat}_{\Delta_0}(x, y)$, representing truth of $\Delta_0$-sentences, is a $...
1
vote
1answer
36 views
Building a model using the power set of $Ord$
I have a question where working in ZF I need to build a transitive model of Z containing $Ord$ (the class of all ordinals) s.t it does not model Zermelo definition of an infinite set:
$$\exists x\left(...
0
votes
0answers
13 views
FO- Definability of (Q,<) in (Q,+,x,1,0) [duplicate]
i know that exist polynomials formulas in the case of Integers and the Real which define their orders, my question is if such a formula exist in case of Rationals.
1
vote
1answer
58 views
What is a starfinite set?
In the book Field Arithmetic by Fried and Jarden, the following definition is given on p. 273:
Consider an enlargement of a higher order structure that contains both $P$ and $K$. Call the elements of ...
7
votes
1answer
50 views
Dividing over algebraic closure
Let $M\models T$ and $C\subset B\subset M$ be finite subsets. Let $a\in acl(C)$. How can we show that $tp(a/B)$ does not divide over $C$.
Here is my attempt: Suppose $tp(a/B)$ divides over $C$. Then ...
2
votes
1answer
34 views
Logical consequence using Replacement Axiom
Let $\mathfrak{A}=<A,E>$ be a countable model of $\mathrm{ZF}$. And $\mathfrak{A}_{A}=(\mathfrak{A},a)_{a\in A}$ is defined to be the model for the language $\{\in\}\cup \{c_{a}:a\in A\}$ by ...