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.
0
votes
1answer
13 views
Finding the probability of a joint density
Given the joint density of two random variables $X$ and $Y$,
$f_{XY}(x,y)=2e^{-(x+y)}$ for $0<x<y$
How do I compute $P(Y<1|X=1)$?
I know the conditional probability formula is:
$P(Y<1|...
2
votes
1answer
48 views
Arithmetic - linear order of $\mathbb{Z}$-copies
Let $\mathcal{M} \equiv (\mathbb{N}, 0, S, <, +)$ and consider the equivalence relation $\sim$ defined in $M$ by: $a \sim b$ if and only if $d(a, b) < \infty$, i.e. the distance is finite.
It ...
0
votes
0answers
40 views
Finding a model for a set of axioms
Suppose $V$ is a vector space, preferably real or complex, with an additional operation $\wedge$ that sends two vectors to another vector space and obeys the following axiom:
$$a \wedge (a+b) = (a+b) ...
1
vote
1answer
39 views
$\mathbb{Z}+\mathbb{Z}$ is a model of $Th(\mathbb{Z}, <, =)$
$Th(\mathbb{Z})$ is the set of all closed formulas which are true in the model $\mathbb{Z}$ of the signature $\{<, =\}$
I need to prove that $Th(\mathbb{Z})$ is not countably categorical.
...
0
votes
0answers
26 views
Is the standard model of the reals the only model up to isomorphism of cardinality $\beth_1$? [duplicate]
TL;DR: I'm trying to figure out what you need to do to pin down the standard model of the reals without explicitly constructing such a model and then defining the standard model $W$ of the reals up to ...
2
votes
1answer
65 views
Are the integers definable in $\mathbb{Z}_{(p)}$?
I am familiar with the statement (not the proof) of Robinson's definition of $\mathbb{Z}$ in $\mathbb{Q}$ in the language of rings. I would like to ask the same question for $\mathbb{Z}_{(p)}$ in ...
-2
votes
1answer
57 views
Adding a new unary function to Morse–Kelley set theory [on hold]
Suppose we take MK and add a new unary function symbol α, with a countable set of extra axioms
α(1) ∈ α(0)
α(2) ∈ α(1)
α(3) ∈ α(2)
(i) Show that the resulting theory is consistent.For all n ∈ N $\...
2
votes
1answer
53 views
Mekler’s construction!
I was looking at this slides by Artem Chernikov. But I did not understad what Mekler’s construction is exactly.
Can one explain the idea of Mekler’s construction (in model theory) in a simple words? ...
2
votes
1answer
34 views
David Marker Model Theory Cor 5.2.10
This Corollary states that a complete theory $T$ in a countable language with infinite models is $\omega$-stable when it is $\lambda$-categorical for some $\lambda\geq\aleph_1$.
I am confused why ...
1
vote
1answer
93 views
Axiomatisable Groups
Let A be a set of sentences (“proper axioms”) in a first-order language L with equality. Let us write Mod(A) for the class of all models of A which respect equality. We say that a class of L-...
0
votes
1answer
25 views
Questions regarding the proof of quantifier elimination of DLO
So this is the proof in David Marker's Model theory book, Theorem 3.1.3.
I am a bit confused over the first line of the proof. It reads :
"First suppose $\phi$ is a sentence. If $\mathbb{Q}\models\...
1
vote
1answer
47 views
A (First-Order) theory T such that every embedding between T-models is elementary
I was wondering, is there a characterization for such a theory? It seems like a pretty handy property so there must be something. Would really appreciate any insight.
1
vote
1answer
35 views
Ways to show two structures are elementary equivalent
Let $\mathcal{L}$ be a finite first-order language. When we say structure we mean $\mathcal{L}$-structure.
Question. Can someone lists different ways which we may use to show two given structures ...
1
vote
0answers
12 views
Using Ehrenfeucht-Fraisse games to prove elementary equivalent [duplicate]
The following theorem is Theorem 2.4.6 of Marker’s model theory book.
Theorem. Let $\mathscr{L}$ be a finite a finite language without function symbols and let $\mathcal{M}$ and $\mathcal{N}$ be $\...
0
votes
0answers
22 views
Reference for elementary substructures of the standard model of analysis
Is there was any resource discussing or categorizing elementary substructures of the intended model of analysis?
Analysis in this context is also known as second-order arithmetic. They will of course ...
0
votes
1answer
27 views
Proof of the Tarski-Vaught test
The Tarski-Vaught test is a way to determine if a substructure is elementary. To my understanding, here is the theorem:
Tarski-Vaught Test Let $N$ be a substructure of $M$. Then the following two ...
1
vote
0answers
89 views
Why not consider the model of $ZFC_2 + 0-inaccessibility$ as the standard model of ZFC?
Let's take $ZFC_2 + 0$-inaccessibility; That is, ZFC written in full second order logic and add to it absence of existence of any inaccessible set. So this defines a unique model of all hereditarily ...
1
vote
1answer
40 views
Function that maps strings from one formal language into string of another formal language?
Is there branch of mathematics and mathematical theories, that considers mappings from strings of one language into strings of another formal language?
Example. Let's consider two languages that can ...
0
votes
2answers
47 views
Syntax of one language as the semantics of another language?
Can formal language serve as the semantic model of another language/logic? Grammatical Framework system is example where such direction is taken: abstract grammar can serve as the model of concrete ...
0
votes
1answer
56 views
What is the lowest layer of the Constructible Universe which is a model of $ZFC-P$?
This answer says that the smallest ordinal $\lambda$ such that $L_\lambda$ is a model of $ZFC$ isn’t easy to describe, other than to say that $\omega_1^{CK}<\lambda<\omega_1$. But my question ...
3
votes
1answer
38 views
Is NIP closed under $\exists$?
Definition. Let $\mathscr{L}$ be a first-order language. An $\mathscr{L}$-formula $\phi(x,y)$ has independence property (IP) if there are two sequences $(a_i)_{i<\omega}$ and $(b_I)_{i\subset \...
-1
votes
1answer
18 views
If Y is a subset of X, is always true that then Y inherits (always) a total order from X?
If Y is a subset of X, then Y inherits a total order from X. The set Y therefore has an order topology, the induced order topology
What does it mean "inherits" ? Is this a a Kripke model M ...
1
vote
2answers
66 views
Quantifier elimination exercise
Let $L$ be the language $\{c_n : n \in \mathbb{N} \}$, and $T$ the theory $\{c_i \neq c_j : i < j < \omega \}$. I want to show that $T$ has quantifier elimination (QE).
It suffices to show QE ...
1
vote
2answers
27 views
Can a model $\mathcal M$ be $|\mathcal M|^+$-saturated?
If $\kappa$ is an infinite cardinal, we say a model $\mathcal M$ is $\kappa$-saturated when for all $A\subset M$ with $|A|<\kappa$ all complete $1$-types $p(x)$ in $\mathcal L_A$ are realised in $\...
1
vote
1answer
54 views
What exactly is meant by “true in all interpretations”?
Wikipedia defines a valid formula as:
A formula of a formal language is a valid formula if and only if it is true under every possible interpretation of the language.
I'm trying to understand what ...
0
votes
1answer
32 views
Terminology: arithmetic vs. expressible vs. represented
A function $f:\mathbb{N}^k\rightarrow\mathbb{N}$ is arithmetic iff its graph is arithmetic, i.e., there is a formula $\psi(\vec{x},y)$ in the language of Peano arithmetic such that for all $\vec{a}$ ...
0
votes
1answer
49 views
Marker - Why is this compactness argument allowed?
The argument is made here at the start of section 4, on types. From what I understand, he didn't really show that delta was finitely satisfiable because delta must hold for all v, not just a ...
0
votes
2answers
103 views
Is Skolem arithmetic effectively axiomatizable?
Skolem arithmetic
I found nothing via Google about its
axioms. Wikipedia says nothing about whether it has ever been effectively axiomatized. If it has, then what do its effective axioms look like?
3
votes
1answer
54 views
Given all possible k-ary relations over an n-element set, which sentences converge to a non-zero percentage as n goes to infinity?
For each relation, the sentence is either true or false.
Is there a taxonomy of sentences in this regard? Many seem to converge to 0 or 1, are there some that converge to values in between?
2
votes
1answer
22 views
An $\omega$-categorical theory $T$ with no finite models is complete.
I'm trying to understand the following proof of this result, but I don't understand:
where the assumption that $T$ has no finite models is used;
why the final step is valid.
Take two models $\...
1
vote
1answer
22 views
A problem from Model Theory of Chang and Keisler.
I'm trying to solve the exercise 2.3.1 of Chang-Keisler book "Model Theory".
If $\phi(x_1, \cdots, x_n)$ is a complete formula in a theory $T$ with respect to $x_1,\cdots, x_n$, then $\exists x_n \...
2
votes
1answer
46 views
How to show a theory eliminates quantifiers?
Definition(1). Let $\mathscr{L}$ be a first-order language. An $\mathscr{L}$-theory $T$ is said to have quantifier-elimination whenever if for all $\mathscr{L}$-formula $\phi(\bar{x})$ there exists a ...
2
votes
1answer
33 views
What property is captured by this third statement defining a structure?
I am currently reading a book, Tame Topology and O-minimal Structures by van den Dries. He defines a structure on a nonempty set $R$ to be a sequence $\mathcal{S}=(\mathcal{S}_m)_{m\in\mathbb{N}}$ ...
0
votes
0answers
39 views
Making the algebraic similarities of groups and Lie algebras precise.
There is a correspondence between Lie algebras and groups on the level of their "algebra", in that many "purely algebraic" theorems in group theory correspond exactly to "purely algebraic" theorems in ...
0
votes
2answers
30 views
Why is the additive group of an ordered division ring divisible, with a dense underlying set?
I'm reading tame topology and o minimality by Van Den Dries.
He defines an ordered ring as follows:
a ring with 1 st:
$0<1$
$x<y \implies x+z<y+z$ for any $z$
$x<y$ and $0<z \implies ...
1
vote
0answers
69 views
Simple examples of the diagonal lemma
According to Boolos' Computability and Logic, the diagonal lemma states:
Let $T$ be a theory containing $\mathbf{Q}$. Then for any formula $B(y)$ there is a sentence $G$ such that $\vdash_T\,G\...
1
vote
2answers
104 views
Showing that all semirecursive sets are semidefinable
I'm working on this problem from Boolos' Computability and Logic:
A set $P$ is (positively) semidefinable in a theory $T$ by a formula $\phi(x)$ if for every $n$, $\phi(\mathbf{n})$ is a theorem of ...
2
votes
1answer
44 views
How to prove symmetry of forking?
Where can I find a detailed proof for symmetry of forking (page 235 in Marker)? It may be easy but I really can't understand it. For example I don't know why we take $M$ as an $\omega$-saturated model?...
0
votes
2answers
89 views
Is it consistent for $P(\mathbb{N})$ to be present in a low layer of the Constructible Universe?
$ZF+V=L$ implies that $P(\mathbb{N})$, the power set of the set of natural numbers, is a subset of $L_{\omega_1}$. But my question is, is it consistent with $ZF$ if $P(\mathbb{N})$ is a subset of $L_{...
0
votes
1answer
38 views
How to construct a decidable-yet-incomplete theory?
An exercise from Boolos' Computability and Logic asks the reader to give an example of a theory which is decidable but not complete. I am wondering if the following suffices.
Let $T$ be a theory ...
5
votes
0answers
97 views
Can there be a sentence that is true in every model of an effective theory and yet not provable in that theory?
Formally this is:
$\exists S [\forall \mathcal M (\mathcal (\mathcal M\models T) \to (\mathcal M \models S)) \wedge \neg (T \vdash S)]$
In English: there is a sentence in the language of an ...
2
votes
1answer
27 views
Hyperfinite intervals are uncountable but nonstandard models of Peano arithmetic can be countable?
My understanding is, by Lowenheim-Skolem I can find a countable nonstandard model of Peano Arithmetic. On the other hand, I have just encountered the following argument:
For $\alpha \in {}^*\mathbb{N}...
1
vote
1answer
26 views
Are generically stable types stationary?
Is every type that is generically stable over a model $M$, stationary over $M$? (Without any assumption on $T$.)
Some definitions:
A global type $p(x)$ is generically stable over $M$ if 1 and 2 ...
1
vote
1answer
34 views
Is a theory with a prime model necessarily complete?
Based on what I see in available sources it seems that the answer to my question is "no". But I fail to see why. Here is my line of reasoning:
Consider a theory $T$ which has some prime model $\...
2
votes
1answer
49 views
Exam question: Show that each infinite L-structure has a countable, elementary substructure
I've had the following question in a midterm exam about first order logic, and didn't manage to solve it:
Let $\mathcal{L}$ be a language and $\mathcal{A}, \mathcal{B}$ structures over $\mathcal{L}$...
0
votes
1answer
52 views
Exercise 3.4.3 in David Marker's “Model Theory”
While studying Model Theory for my exam, I came across the following question:
a) Show that the theory of $(\mathbb{Z}, s)$ has quantifier elimination where $s(x) = x + 1.$
b) Show that the ...
3
votes
2answers
258 views
Undefinable classes?
Note: this question has been changed substantially from its original form.
Originally I had asked whether or not it is possible to prove that all classes whose elements are 'truly arbitrary' are ...
1
vote
1answer
56 views
Countable countable models
I have a proof of the following:
[*] Let $A$ be a countable $\omega$-saturated model of a complete,
countable theory $T$ (with infinite models). There is a bijection
between the orbits under ...
4
votes
1answer
41 views
$\mathbb{Q}^{alg}[[a,b]] $ is not elementary equivalent to $\mathbb{C}[[a,b]]$, and the same for $\mathbb{Q}^{alg}[a]$ and $\mathbb{C}[a]$?
Since ACF is complete, $\mathbb{Q}^{\text{alg}}$ is elementary equivalent to $\mathbb{C}$, and by Ax-Kochen $\mathbb{Q}^{\text{alg}}[[a]]$ is elementary equivalent to $\mathbb{C}[[a]]$.
But how should ...
0
votes
1answer
56 views
An incomplete yet decidable theory
I am working on the following exercise from Boolos' Computability and Logic:
Problem. Suppose an axiomatizable theory $T$ has only infinite models. Suppose $T$ is not complete, [yet has] two ...
