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

7
votes
2answers
160 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 ...
1
vote
2answers
55 views

Algebraic closure vs Real closure

I have proved that the surreal numbers have the properties of a real closed field. Now I should be able to explain what the importance of this real closure is. unfortunately I do not have a background ...
4
votes
0answers
80 views

O-minimal spectrum is a spectral space

I'm trying to understand a proof on "Sheaves of Continuous Definable Functions" (Pillay, Anand. "Sheaves of continuous definable functions." The Journal of symbolic logic 53.04 (1988): 1165-1169.) ...
0
votes
0answers
20 views

Robinson Arithmetic, $\Sigma_1$-theorem

Use How can I show that every $\Pi_1$ sentence consistent with Robinson Arithmetic is true in the standard model? to show, that $Q\vdash\varphi$ for every true $\Sigma_1$-theorem $\varphi$. Hello, ...
0
votes
1answer
33 views

How can I show that every $\Pi_1$ sentence consistent with Robinson Arithmetic is true in the standard model?

Let $\mathcal{N}=(\mathbb{N}, ...)$ be the standard model of Q (Robinson Arithmetic), and let $\mathcal{N}^{\ast}=(N, ...)$ be an arbitrary model. Let $\varphi$ be a $\Sigma_1$-theorem, and let $\...
-2
votes
1answer
49 views

How to show that Peano axioms prove that if $\varphi$ defines a non-empty set, then it has a least element? [on hold]

Show the following statement in PA $\forall v_1\dotso\forall v_k\,(\exists v_0\,\varphi\to\exists v_0(\varphi\wedge\forall v_{k+1}<v_0\,\neg\varphi^{v_0}_{v_{k+1}}))$ With $v_0, v_1, \...
1
vote
1answer
54 views

Adding witnesses to prove Gödel's completeness theorem

I am currently working with "The Foundations of Mathematics" by Kunen to understand the proof for Gödel's completeness theorem due to Henkin. When adding the witnessing terms, there is one thing I ...
1
vote
1answer
47 views

Relation and Function in a language

At the very beginning of David Marker's book Model Theory, it defines a language to be given by a set of function symbols $F$ and a set of relation symbols R. I am just wondering isn't a relation a ...
6
votes
2answers
62 views

Does the following set of formulas have a finite model?

So this is the problem: Do the following 3 formulas have a finite model: 1. $\forall x \forall y (p(x,y) \Rightarrow \neg p(y,x))$ 2. $\forall x \forall y (p(x,y) \Rightarrow \exists z (p(x,z) ...
1
vote
0answers
76 views

easy proof of the completeness theorem [closed]

The completeness theorem of first-order logic states: If $\Phi\models\phi$, then $\Phi\vdash\phi$. Assume that I have a calculus $\vdash$ in mind for which I want to prove this completeness theorem. ...
1
vote
0answers
36 views

Isomorphism, Model-Theorie, “beginning”

Let $\mathcal{N}^{\ast}=(N, <_{\mathcal{N}^{\ast}},...)$ be a model of $Q$ (the Robinson arithmetic). Show, that it exists a "beginning" (definition below) of $\mathcal{N}^{\ast}$ which is ...
2
votes
2answers
71 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 ...
0
votes
1answer
52 views

Peano Arithmetic, proof

Show in PA: $\forall v_0\forall v_1 (v_0<v_1\rightarrow \exists v_2\quad v_0+v_2=v_1)$ Hello, I have a question to this task, because I do not know, how to proof this. I give the definition ...
4
votes
1answer
58 views

Simple model of (propositional) intuitionistic logic to recognize valid formulas

I noticed that when I want to know (or rather see/understand) whether some classical tautology is valid intuitionistically, I first try to replace each propositional variable by a finite union of open ...
2
votes
1answer
81 views

Elementary suborders of Cohen forcing

My question is basically whether being a Cohen poset is a first-order statement within the order itself. More specifically, let $\mathbb{P}$ be an elementary suborder of $\mathrm{Add}(\omega,\lambda)...
8
votes
1answer
735 views

What is an example of a non standard model of Peano Arithmetic?

According to here, there is the "standard" model of Peano Arithmetic. This is defined as $0,1,2,...$ in the usual sense. What would be an example of a nonstandard model of Peano Arithmetic? What would ...
2
votes
0answers
42 views

Modell-Theory, Isomorphism

Let $\mathcal{L}$ be a language of the first-order logic with a binary relationsymbol $\stackrel{\cdot}{<}$ (and no other symbols). Observe the following set $T$ of theorems: $T:=\{\forall v_0\...
0
votes
3answers
125 views

Would a theory with model $\{\}$ be consistent?

I don't know much about model theory, but it was suggested in another math forum that a theory with model $\{ \}$ would be consistent. Is this correct?
4
votes
0answers
29 views

Weak elimination of imaginaries in the theory of the random graph

Let ${\cal U}$ be a countable random graph. Prove that for every formula $\varphi(x)\in L({\cal U})$, where $x$ has arbitrary finite arity, there are a positive integer $n$ and finite $C\subseteq{\cal ...
4
votes
1answer
98 views

Complete calculus of first-order logic working for empty structures too

Usually, in model theory, one presupposes that structures (models) are non-empty. I don't like this (related: What's the deal with empty models in first-order logic?). So let us explicitly permit ...
-1
votes
0answers
40 views

model-theory, at most countable language

Let $\mathcal{M}$ be a model of an at most countable language. Show: It exists a model $\mathcal{M}'$ with: a) The carrier set $|\mathcal{M}'|$ of $\mathcal{M}'$ is at most countable, and ...
2
votes
1answer
30 views

In a stable theory a Indiscernible sequences are Indiscernible sets

Let $T$ be a stable theory. Every Indiscernible sequences is a Indiscernible sets. (Where Indiscernible set is a Indiscernible sequence where every permutation on the order keeps it Indiscernible ...
2
votes
1answer
38 views

Suppose a model $A$ is $\aleph_0$-saturated. Show every n-type over T is realized in $A$

We define: $A$ is $\aleph_0$-saturated if for any expanision $A_{c_1,...,c_m}$ of $A$ by finitely many constant symbols $c_1,...,c_m$, every 1-type consistent with $Th(A_{c_1,...,c_m})$ is realised ...
1
vote
1answer
31 views

Model-Theory, construction of a model with certain properties

Let $\mathcal{M}$ be an arbitrarily large infinite model. Let $X$ be a random set. Show: It exists a model $\mathcal{M}'$, such that a) $\mathcal{M}'\models\varphi\Leftrightarrow\mathcal{M}\...
2
votes
1answer
63 views

Compactness theorem

Let $\Sigma$ be a set of theorems, such that for every $\varphi\in\Sigma$ exists an arbitrarily large (<--- edited) finite modell $\mathcal{M}$, with $\mathcal{M}\models\varphi$. Show: It ...
33
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
58 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 ...
1
vote
1answer
90 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 ...
3
votes
2answers
87 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
42 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
59 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
68 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
35 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 ...
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
57 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
104 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
46 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
42 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
39 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
49 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 ...
3
votes
1answer
64 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
152 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
62 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
34 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
51 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
55 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. ...
7
votes
1answer
53 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
82 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 ...