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,449
questions
1
vote
0
answers
32
views
Invariance under $\operatorname{Aut}(N / \{M\})$
Let $M\preceq N$ where $N$ is $|M|^+$ saturated.
Let $p(x)$ be a partial type over $\le|M|$ parameters.
What do we know (if anything at all) about when $p(N)$ is invariant under the action of $\...
- 482
4
votes
1
answer
142
views
(When) are recursive "definitions" definitions?
This is a "soft" question, but I'm greatly interested in canvassing opinions on it. I don't know whether there is anything like a consensus on the answer. Under what conditions (if any) are ...
- 95
3
votes
1
answer
105
views
Is the class of linearly-orderable rings first order axiomatizable?
A linearly ordered ring is a commutative ring $R$ with unity equipped with a linear order $\leq$ that is compatible with addition, and such that the set of nonnegative elements are closed under ...
- 21.5k
3
votes
1
answer
396
views
Does Löwenheim-Skolem require Foundation in any way?
As title states, I'm curious whether Löwenheim-Skolem (in either of its upward or downward versions) necessitates some implicit use of Foundation. The usual presentation makes quite clear the reliance ...
- 512
0
votes
1
answer
74
views
Proving a simple consequence of the Compactness Theorem
I am self-learning logic, and trying to prove the following exercise using the Compactness Theorem:
Suppose $T$ is a theory for language $L$, and $\sigma$ is a sentence of $L$ such that $T \models \...
- 531
3
votes
1
answer
214
views
Is quantifying over natural numbers non first order?
I was reading here that
Note that ‘x is an infinitesimal’ is not first order, because it requires you to quantify over the naturals.
Whats's non first order about quantifying over natural numbers?
- 5,965
5
votes
1
answer
416
views
Is there a theory in which all types can be omitted?
Is there a natural example of a first order complete (consistent) theory $T$ in which every 1-type can be omitted? or is there always some isolated type? In that case, why?
Of course there are plenty ...
- 581
1
vote
1
answer
77
views
Proving that the set of sentences that are true using the symbols $+,<,=$ is the same over all ordered fields
I am interested in whether the set of formulas that one can prove true for a concrete ordered field using the symbols $+,<$ and $=$, depends on the field. In particular, I am interested in the set ...
- 5,965
-2
votes
2
answers
101
views
in definition of assigment, what's means 'except possibly a'?
in frist-order logic,
part of assignments practice represent like this
"if 𝜙is ∀𝛼𝜓, where 𝛼 is a variable, then ⊨vℳ 𝜙 iff for every assignment 𝑣' that agrees with 𝑣 on the values of every ...
- 33
3
votes
0
answers
62
views
Two families of isomorphic structures have isomorphic ultraproduct.
I am trying to prove the following result:
Let $(\underline{M}_i)_{i\in I}$, $(\underline{N}_i)_{i\in I}$ be two families of structures such that, for all $i\in I$, $\underline{M}_i \cong \underline{...
- 103
2
votes
1
answer
78
views
Condition for dense isolated types [closed]
I need some help with proving the following:
Theorem. Let $T$ be a complete theory in a countable language and let $M \models T$.
If $|\mathcal{S}_n^\mathcal{M}| < 2^{\aleph_0}$ then the isolated ...
- 41
6
votes
1
answer
226
views
Definability of acyclic graphs
I think you should be able to encode the axioms of a directed, acyclic graph by introducing a strict partial order. Say E(a, b) represents there is an edge from a to b. We introduce a strict partial ...
- 63
3
votes
1
answer
90
views
What are other examples of $\aleph_1$-categorical theories?
In model theory, $\aleph_1$-categorical (first order) theories (in a countable language) are very important, and I am studying them at the moment. However, it seems that the only examples I can find ...
- 581
2
votes
1
answer
88
views
Can equivalence relations have extra non-trivial properties?
The theory of equivalence relations can be axiomatized by 3 equality-free universal sentences, namely:
1.$xRx$
2.$xRy \rightarrow yRx$
3.$(xRy \land yRz) \rightarrow xRz$.
Now, certainly, we can add ...
- 21.5k
4
votes
1
answer
87
views
Why are extensions of countable models of ZFC better behaved than extensions of arbitrary models of ZFC?
This answer hints that certain kinds of extensions are only guaranteed to exist for countable models of ZFC. Why?
One intuitive reason i can think of is that the metatheory might not have enough new ...
- 457
7
votes
1
answer
436
views
Functional completeness over a structure
The set of propositional connectives $\{\wedge,\vee\}$ is of course not functionally complete; correspondingly, the logical vocabulary $\{\forall,\exists,=,\wedge,\vee\}$ is not sufficient for ...
- 249k
1
vote
1
answer
62
views
Need to check this proof that the class of models of ZC that fail replacement is not axiomatisable.
Here ZC is ZFC minus Axiom of Replacement.
My proof is as follows:
Suppose $M$ was axiomatized by a theory $H$.
For non-zero limit ordinal $\alpha$, let $T_\alpha$ be the set of the replacement axioms ...
- 335
1
vote
1
answer
48
views
Is the interpretation of a constant symbol an injective map?
The context
Im trying to show that the reduct to the luanguage $\frak{L}$ of any model of the complete diagram $D(\frak{M})$ of an $\frak{L}$-structure $\frak{M}$ is an elementary extension of some ...
- 535
-3
votes
1
answer
78
views
On pseudofiniteness and injective-surjective
In many literatures it is noted that “let M be pseudofinite and f a definable function, then f is injective if and only if it is surjective.” Let's break it down into parts, Let A --- M be a ...
0
votes
2
answers
135
views
Skolemization in Marker's Proof of Theorem 2.3.7 (Downward Löwenheim-Skolem)
For convenience, I'll re-state Lemma 2.3.6 and Theorem 2.3.7 in Marker's Model Theory:
$\textbf{Lemma 2.3.6}$: Let $T$ be an $\mathcal{L}$-theory. There are $\mathcal{L}^\ast \supseteq \mathcal{L}$ ...
- 17
2
votes
1
answer
113
views
In what sense is forcing "impossible" in $L$?
I just saw an interesting video from Hugh Woodin about Ultimate $L$. In it, he says one of the reasons $L$ is so interesting is because it not only settles many natural set theory questions, but is ...
- 8,000
2
votes
1
answer
54
views
Last Bits of Proof of the Compactness Theorem in Propositional Logic
I am reading the proof of compactness theorem for the propositional logic and the last part of the proof is left as exercise 2 of section 1.7 in the book by Enderton, A Mathematical Introduction to ...
- 15k
1
vote
1
answer
66
views
Linear disjointness of normal algebraic extension
In [Tent & Ziegler] "A Course in Model Theory" section B.3, it mentions that for ring $R,S$ contained in a common field extension with a common subfield $k$, if $S$ is an algebraic ...
- 403
3
votes
1
answer
62
views
Algorithm for Determining Truth of First-Order Sentences in Complex Numbers
Following my previous question Decidability in Natural Numbers with a Combined Function, I realized that there is a spectrum regarding the hardness of deciding whether a first-order sentence is true ...
- 87
-1
votes
1
answer
90
views
Decidability in Natural Numbers with a Combined Function [closed]
It is well known that there is no algorithm to determine whether a given first-order sentence is true in the structure of natural numbers with both addition and multiplication. In contrast, Presburger ...
- 87
0
votes
1
answer
177
views
Is there a set of all set-theoretical truths?
Does Tarski's undefinability theorem implies that there cannot be a set of all set-theoretical truths? Or can there be such a set (although undefinable)?
- 53
4
votes
1
answer
153
views
How does type theory deal with the lack of completeness, compactness, etc.?
As far as I understand, type theory (let's say Simple Type Theory or one of its extensions such as Homotopy Type Theory) is a computational view of $\omega$th-order logic.
See this question: Type ...
user1345451
1
vote
1
answer
49
views
For which cardinals $\kappa$ is the theory of a single bijection lacking cycles $\kappa$-categorical?
I'm currently stuck on Exercise 2.5.13 of David Marker's model theory text. The full statement of the exercise is as follows:
Let $\mathscr{L}$ be the language containing a single unary function ...
2
votes
1
answer
56
views
How to argue that Büchi arithmetic is more expressive than Presburger arithmetic
Büchi arithmetic is expressively equivalent to WS1S.
How can I show that WS1S is strictly more expressive than Presburger arithmetic?
Is there a simple argument for this?
- 5,965
2
votes
1
answer
50
views
Example of a global non-forking extension of a stationary type
I'm reading Bouscaren's Model Theory and Algebraic Geometry and I am having trouble understanding this example of a stationary type. Here $\mathfrak{C}$ is assumed to be a monster model, and a ...
