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 ...

learn more… | top users | synonyms

32
votes
7answers
2k views

Do the axioms of set theory actually define the notion of a set?

In Henning Makholm's answer to the question, When does the set enter set theory?, he states: In axiomatic set theory, the axioms themselves are the definition of the notion of a set: A set is ...
3
votes
0answers
51 views

Cardinality of Galois groups

We know that no Galois group of a Galois extension is countable. The question is: which cardinalities are possible for a Galois group? (or also: for profinite groups?) I suspect that the theory of ...
0
votes
1answer
63 views

Is it circular to define the Von Neumann universe using “sets”?

I was just reading the Wikipedia page on the Von Neumann universe, where it is stated that this universe "is often used to provide an interpretation or motivation of the axioms of ZFC." However, later ...
1
vote
2answers
61 views

Explicit example of countable transitive model of $\sf ZF$

Do we know any explicit example of a countable transitive model for $\sf ZF$ or $\sf ZFC$?
1
vote
1answer
38 views

Tarski's schema T

On Wikipedia, Tarski schema T says: A sentence of the form "A and B" is true if and only if A is true and B is true A sentence of the form "A or B" is true if and only if A is true or B is true A ...
1
vote
1answer
48 views

Elimination of quantifiers for the theory of equivalence relations with two infinite classes by back-and-forth

As I said in an earlier question, I'm trying to understand how to obtain elimination sets by way of back-and-forth arguments. Since I'm not totally sure I understood how it works, I wanted to check my ...
2
votes
1answer
61 views

Generators of the Lindenbaum-Tarski algebra

I am a bit confused about the role of propositional variables in the construction of the free Lindenbaum-Tarski algebra. In the entry "Lindenbaum-Tarski algebra" on Wikipedia, in the section ...
2
votes
1answer
34 views

Graded back-and-forth systems and unnested Ehrenfeucht-Fraïssé games

I'm trying to work my way through back-and-forth systems and elimination sets by reading the relevant sections in Hodges' Model Theory and I'm a bit confused by one of his lemmas (specifically, it's ...
2
votes
1answer
59 views

Sum of measurable functions is measurable: countable choice required?

The standard proof that the sum of measurable functions is measurable uses countable choice, via the countable subadditivity of outer measure ($\implies$ measurable sets are closed under countable ...
1
vote
1answer
30 views

Inclusion in sequences of theories and models

Is this theorem true, and if so does it have a name and where can I reference it? "Let $T_1$ and $T_2$ be theories where $T_1 \subset T_2$. If $K_1$ and $K_2$ are the classes of all models of $T_1$ ...
2
votes
1answer
33 views

Finding Model Containing Commutative Diagram as Elementary Submodels

I'm looking at a justification for why we work inside a big model, but I'm having trouble proving a particular comment. Assume we're working with a complete theory $T$ and we have a commutative ...
1
vote
1answer
52 views

Quantifier elimination, $(\mathbb{R}, <)$

I have a general question about quantifier elimination. Which kinds of formulas do you have to observe? For example let T be the theory of $(\mathbb{R}, <)$ and I want to show, that this theory ...
2
votes
1answer
101 views

Is it possible that Gödel's completeness theorem could fail constructively?

Gödel's completeness theorem says that for any first order theory $F$, the statements derivable from $F$ are precisely those that hold in all models of $F$. Thus, it is not possible to have a theorem ...
2
votes
1answer
45 views

Characterizing coding with automorphisms

I am attempting the following exercise from chapter 5 of Van den Dries' notes "Introduction to Model-Theoretic Stability". I suspect the exercise shouldn't be too difficult but I've become pretty ...
0
votes
2answers
40 views

Why does a finite set having a model imply that the set is consistent [closed]

Assuming the soundness theorem to be true, can someone explain why if we assume $\Sigma$ has a model $M$. Then $\Sigma$ is consistent ?
0
votes
0answers
37 views

Definable over $(\mathbb{N},0,S)$, $A$ or $\mathbb{N}\setminus A$ is finite

Let $A\subseteq\mathbb{N}$ be defineable over $(\mathbb{N},0,S)$. Then is $A$ or $\mathbb{N}\setminus A$ finite. $S$ is here the successor-function $S(n)=n+1$. Hello, I have a question to this task. ...
0
votes
1answer
48 views

“finally cyclic”, definable over $(\mathbb{N},+)$

Let $A\subset\mathbb{N}$ "finally cyclic" (I give the definition below). Show, that $A$ is definable over $(\mathbb{N},+)$ Hello, I have a question to this task. I have to show, that the set $A$ is ...
7
votes
1answer
148 views

Gödel's ontological proof and “modal collapses”

Recent findings on Gödel's ontological argument allowed to ultimately establish a couple of things: Gödel's original axiomata are inconsistent Scott's variation instead is consistent Scott's axioms ...
3
votes
1answer
51 views

Does the theory of equivalence relations have quantifier elimination?

I am aware that the theory of equivalence relations with infinitely many classes, all of which infinite, has quantifier elimination, as can be seen from the answer to this question. However, does the ...
3
votes
3answers
138 views

In which order should I learn the foundations of mathematics? [closed]

I know from Wikipedia that those are the four pillars of the foundations of mathematics: Proof theory Aximatic Set theory Model Theory Recursion Theory and I want to learn all of them, the problem ...
1
vote
2answers
60 views

Prove that, for any sentence A of the predicate calculus with identity, at least one of spectrum(A) and spectrum(¬ A) is cofinite

I got the following exercise: Prove that, for any sentence A of the predicate calculus with identity, at least one of spectrum(A) and spectrum(¬ A) is cofinite. I already tried to prove this ...
1
vote
1answer
30 views

Why does the undefinability proof fail for $\mathbb{N}$ in $(\mathbb{Z}, 0, <)$?

An exercise asks to prove that: $\mathbb{N}$ is not definable in $(\mathbb{Z}, <)$, but definable in $(\mathbb{Z}, 0, <)$ (in the first-order logic). The solution to the former one relies ...
0
votes
1answer
50 views

What's the meaning this DOT notation?

I'm reading a chapter in a Model Checking book. I came across this chapter "Symbolic Model Checking", in which the author mentions Fixed Point representation. I don't know how to explain the context, ...
1
vote
1answer
47 views

For a compact logic, strong completeness follows from weak completeness

I have heard it said from reputable sources that one of the differences between a compact and a non-compact logic is that in a compact logic, strong completeness follows from weak completeness. ...
6
votes
1answer
43 views

Why does every complete theory have joint embedding property?

I came across a sentence in page 196 Chang & Keisler's model theory book that I don't understand. It says: Every complete theory has the joint embedding property. Def. A theory $T$ has joint ...
3
votes
1answer
80 views

Is $\mathbb{N}$ definable over $(\mathbb{R},<,+,\cdot,0,1)$

is it possible to define the set $\mathbb{N}$ over the modell $(\mathbb{R},<,+,\cdot,0,1)$? So, does a formula $\varphi$ exist which describes the natural numbers. Unfortunatly I have no clue how ...
1
vote
0answers
39 views

Definable over $(\mathbb{R}, <, +, \cdot, 0, 1)$

I have to solve the following task and got some problems with it: a) Be $n\in\mathbb{Z}$. Is $\{n\}$ definable over $(\mathbb{R}, <, +, \cdot, 0, 1)$ b) Be $q\in\mathbb{Q}$. Is $\{q\}$ definable ...
1
vote
0answers
24 views

Definable over $(\mathbb{R}, +, \cdot)$

I have the following task and I am not so sure about my solution: a) Is $\{0\}$ definable over $(\mathbb{R}, +, \cdot)$? b) Is $\{1\}$ definable over $(\mathbb{R}, +, \cdot)$? c) Is $<$ ...
0
votes
0answers
17 views

Showing that $(p(x)\rightarrow q(x)) \leftrightarrow (\neg q(x) \rightarrow \neg p(x))$ is a valid $\mathcal{L}$-formula

If $\mathcal{L}=\{p,q\}$ with $p,q \in \mathcal{P}_1$, would showing that $(p(x)\rightarrow q(x))$ and $(\neg q(x) \rightarrow \neg p(x))$ have the same truth table prove that $(p(x)\rightarrow q(x)) ...
1
vote
1answer
31 views

If a formula has a Morley Rank then it is less then $|T|^+$

We saw in class that given a complete theory $T$, then if $MR\varphi\ge (2^{|T|})^+$ then $MR\varphi=\infty$ And we ware told that Lachlan improved this result to $|T|^+$. To prove it, I assume ...
2
votes
1answer
20 views

How to prove: If $(\omega, <) \equiv \mathcal{M}$, then $(\omega, <) \prec_{f} \mathcal{M}$

To prove that If $(\omega, <) \equiv \mathcal{M}$, then there exists a function $f: \omega \to M$ (the domain of $\mathcal{M}$) such that $(\omega, <) \prec_{f} \mathcal{M}$. where, the ...
4
votes
2answers
79 views

Ultraproduct of a metric space

I am currently trying to understand "Curvature bounded below: a definition a la Berg--Nikolaev" by Nina Lebedeva and Anton Petrunin. They start with a complete, intrinsic metric and space $X$ and say ...
4
votes
1answer
140 views

$\vDash \varphi$ iff $\| \varphi \|_A =1$ for every boolean valued structure $A$

In the book Axiomatic Set Theory (Takeuti, G; Zaring, W.M. - 1973) the theorem 6.4 states that if $\varphi$ is a closed formula of a given language then it is satisfied in every boolean valued ...
2
votes
1answer
28 views

Spectrum of a set of first order formulas

Let ψ be a first order formula. Wikipedia defines the spectrum of the formula ψ as follows: The spectrum of ψ is the set of natural numbers n such that there is a finite model for ψ with n elements. ...
1
vote
2answers
42 views

How to define the functions and relations for a logical model?

In model theory one has to define functions and relations on a set for the function and relation symbols of the logical theory. My questions are: What kind of operations are allowed to define ...
0
votes
1answer
23 views

Equivalence infinite Spectrum problem and finite spectrum problem

Definitions: For a given first order sentence $\phi$ define $\text{spectrum}(\phi)$ to be the set of all cardinalities of the finite models of $\phi$. A set $S\subseteq\mathbb N_+$ is said to be a ...
4
votes
0answers
58 views

Completing ordered Fields

How do these two forms of completion behave (in NBG) when fields are authorized to be proper classes? $(i)$: Every ordered field has a real closed, algebraic extension. $(ii$): Every ordered field ...
7
votes
0answers
69 views

Definable subset of the additive theory of integers

I strongly suspect that the subset $\{ -1,1 \}$ of $(\mathbb{Z},+)$ is not definable, despite being fixed under all automorphisms of the structure. However, I can't seem to be able find a proof. Does ...
0
votes
1answer
42 views

Is T an infinity spectrum whenever T is a spectrum?

Definitions: For a given first order sentence $\phi$ define $\text{spectrum}(\phi)$ to be the set of all cardinalities of the finite models of $\phi$. A set $S\subseteq\mathbb N_+$ is said to be a ...
11
votes
1answer
120 views

Surjective exponentials for algebraically closed fields

The existence of the exponential on $\mathbb{C}$ has a very basic, yet very strong consequence : $(\mathbb{C}^*,\cdot)$ is a quotient of $(\mathbb{C},+)$. This question is concerned with fields $K$ ...
1
vote
1answer
47 views

Infinite Spectrum Problem

Let us work in a class theory like NBG. For a given first order sentence $\phi$ define $\infty\text{-spectrum}(\phi)$ to be the class of all cardinal numbers $\kappa$ for which there is a model $M$ ...
0
votes
1answer
24 views

List of primes and compactness

I'm working on the following problem: Let $p_0,p_1,...$ be a list of the prime numbers in increasing order. Show that for any set $X\subseteq\mathbb{N}$, there is a model of Th($\mathbb{N})$ which ...
3
votes
1answer
90 views

Ultraproduct with no long descending sequence

I have a countably infinite well-ordered structure $M$ (over a countable language if it helps), and an uncountable regular cardinal $κ$, and I wanted to construct an elementarily equivalent structure ...
4
votes
1answer
37 views

Ordinal pair $(α,β)$ such that $α<β$ and $Th(α,<) = Th(β,<)$

A number of weeks ago I was thinking of finding an example of a complete countable theory with only one binary predicate that is not $ω$-categorical. I later realized that $Th(\mathbb{Z},<)$ works, ...
1
vote
2answers
104 views

Do 'nice' first order logics have universal models?

A first-order logic is interpreted in a model where sentences of the logic can be said to be true or false. There may be more than one model, and we can identify morphisms between models. Do we have ...
0
votes
1answer
23 views

Are isomorphisms between finitely generated substructures determined on a set of generators?

Let $K$ be a structure, $\varphi: A \to B$ be an isomorphism of finitely generated substructures of $K$. Let $a_0,\dots,a_n$ be generators of $A$. Do the images $\varphi(a_i)$ of the generators $a_i$ ...
6
votes
2answers
439 views

Two definitions of strong homomorphism

We say that $f: A \to B$ is a homomorphism iff it preserves the operations and relations of the structure: $f(o^A(\bar{a})) = o^B(f(\bar{a}))$ where $a ∈ A^{ar(o)}$, $o$ any function symbol from the ...
0
votes
0answers
93 views

Medium-strong (graph) homomorphisms

Weak (graph) homomorphisms are mappings $f: V(G) \rightarrow V(G')$ such that the images of connected nodes $x,y$ (in the source graph) are connected: $$R(x,y) \rightarrow R(f(x),f(y)) = R(x',y')$$ ...
2
votes
1answer
58 views

why can't this proof of Löwenheim-Skolem Theorem be shorter?

An algebraic introduction to mathematical logic page 46 has the following: the proof continues on, but it seems to me we can stop here. Every consistent theory has a model, and we've just proven ...
1
vote
1answer
97 views

What are non-categorical theories about?

With theories that are categorical, it seems like you could say that the theory is about collections of objects (numbers, points, etc.) with a certain structure (the structure the standard models ...