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.
4,739 questions
0
votes
1
answer
39
views
a complete theory in a countable language with countably many types but uncountably many countable models [duplicate]
I am trying to find such a theory.
I have a nice example of a complete theory with an $\aleph_0$-saturated countable model. Namely, consider the theory in the graph language with the graph axioms that ...
1
vote
1
answer
117
views
Complexity of $Th(\langle \mathbb{Z}; + , 1 \rangle)$ same as $Th(\langle \mathbb{Z}; + \rangle)$?
I want to know a lower bound for the complexity of the decision problem for $\langle \mathbb{Z}; + \rangle$. The below paper notes that Presburger arithmetic, originally $\langle \mathbb{N}; +\rangle$,...
- 287
0
votes
1
answer
60
views
Necessary and sufficient conditions for the theory of a quotient model to be equal to the theory of the main model
Given a language $\mathcal{L}$ and a model $\mathcal{M}$ in the language $\mathcal{L}$, what are the necessary and sufficient conditions that a congruence relation $\equiv$ must have such that $Th(\...
- 355
1
vote
1
answer
129
views
Complete theory where we cannot omit all non-isolated types
The exercise is to give an example of a complete theory in a countable language such that no model of the theory omits all non-isolated types.
I'm having trouble, especially since parameters are not ...
5
votes
2
answers
164
views
Construction of a dense linear order with $2^\kappa$ cuts
The question is the following:
Given a cardinal $\kappa$, is there a dense linear order of size $\leq \kappa$ such that there are $2^\kappa$ cuts (a cut is a downward closed subset)?
The question is a ...
- 115
6
votes
3
answers
739
views
Does truth not exist in ZFC, or is it merely not definable?
I am having a lot of trouble with the concept of Tarski's undefinability theorem as it relates to set theory.
Tarski's undefinability theorem says that there is no formula $Tr$ on the natural numbers ...
- 1,262
2
votes
0
answers
83
views
QE of $(\mathbb{N}, 0, 1, +, <, (\equiv_k)_{k \geq 2})$
I'm stuck on the proof for this. $(\equiv_k)$ is the binary relation for congruence modulo $k$.
I began my proof by looking at a primitive formula $\eta(\bar{x}, y)$ and am attempting to find a finite ...
0
votes
1
answer
149
views
Relation between Tarski's conception of truth and (implicit) Axioms
I am trying to understand the original paper of Tarski Concept of Truth in the formalized languages, as printed in his collected works.
I have read introductory texts from Shoenfield Mathematical ...
2
votes
1
answer
116
views
What real numbers correspond to second order logic definable Dekekind cuts?
This question spurred from a thought I had: does every (lower) Dedekind cut have a (finite) second order logic formula that defines it?
Fix the usual setting: the domain is $\mathbb{Q}$ with the order ...
- 2,584
1
vote
1
answer
56
views
two connected countable graphs elementarily equivalent but not isomorphic
I have been trying without avail. The theory of connected graphs is not definable of course.
However, the theory of connected graphs with fixed diameter is definable, so I was thinking to somehow ...
0
votes
1
answer
43
views
elementarily equivalence implying isomorphism for countable
My professor proved Robinson's Joint Consistency Theorem and in one of the steps, took a theory in an expanded language with unary relations for structures and $W_n$ for $n \in \mathbb{N}$. He encoded ...
10
votes
0
answers
367
views
When is the iterated ultrapower innocuous?
Suppose $U$ is an ultrafilter over $I$. When does the isomorphism
$$
\prod_U \Big(\prod_U \mathfrak A_i\Big) \cong \prod_U \mathfrak A_i
$$
occur?
I think I saw somewhere that if $U$ is a uniform $\...
- 729
-2
votes
1
answer
99
views
Get to know: The Tarski-Vaught Test [closed]
I want to understand the Tarski-Vaught Test and how to apply it.
It is stated as follows.
Let $\mathcal{M}$ ben an $\mathcal{L}$-structure and $A\subseteq M$. Then $A$ is the base set of an elementary ...
- 49
1
vote
2
answers
74
views
Finite Ehrenfeucht-Fraisse games with infinite constants
Suppose we have some theory $T$ on a language $L$ containing some (let's just say 1) relational symbol and a countably infinite number of constants. If we let $M,N$ be two models of $T$, define $G_n(M,...
- 147
4
votes
1
answer
135
views
Why is the transfer principle embedding in nonstandard universes bounded?
I am trying to read Model Theory by Chang and Keisler. Given a set $A$, let $V(A)$ be
$$
\begin{align*}
V_0 &= A \\
V_1 &= V_0 \cup \mathcal{P}(V_0) \\
\dots \\
V_n &= V_{n-1} \cup \...
- 947