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

0
votes
1answer
39 views

modeltheory, union

There's a row of models, namely $M_0 \subseteq M_1 \subseteq M_2 \subseteq \dotsb$ and there's a theory $T$ such: $\phi \in T \rightarrow \phi = \forall x\exists y\,\psi$ with $\psi$ quantor-free. ...
9
votes
2answers
324 views

Can a model of set theory think it is well-founded and in fact not be?

ZF's axiom of regularity implies that no infinite descending sequence of sets $x_1 \ni x_2 \ni x_3 \ni \cdots$ exists. Precisely this theorem asserts the non-existence of a map from $\mathbb{N}$ to ...
1
vote
1answer
109 views

Renaming the elements of a mathematical structure

One of the most basic insights about mathematical structures is that we can rename their elements without fundamentally changing the structure. Question. How do we actually formalize this observation ...
1
vote
2answers
71 views

Logic: some basic plane geometry

Suppose you've got the language of some basic plane geometry, i.e. two 1-place relation symbols $P$ and $L$ for point and line and one 2-place relation symbol $I$ for point $x$ lies on line $y$. Now, ...
1
vote
1answer
176 views

Logic: $\text{Mod } \Sigma$, the class of all models of $\Sigma$ and $\text{Th Mod }\Sigma$, how do these relate?

While reviewing a question I had asked earlier here: Proving and understanding the Fixed point lemma (Diagonal Lemma) in Logic - used in proof of Godel's incompleteness theorem I have the ...
2
votes
1answer
372 views

Logic: cardinality of the set of formulas

How can you proof that $||L||=|L|$ if $L$ is infinite (where $||L||$ stands for the cardinality of the set of all $L$-formulas and $|L|$ the number of all constants, function and relation symbols)? ...
0
votes
3answers
74 views

Logic: defining 2 in a certain structure

Let $L= \{ \leq \}$ be the language of the partial orders and $M$ the $L$-structure with $M=\{ 1,2,3,4,6,12\}$ and $\leq_M=\{(x,y)$: $x$ is a divisor of $y$$\}$. Now, give an $L$-formula $\phi(x)$ ...
2
votes
2answers
126 views

Logic: building a sentence

Let $L$ be a language with a 1-place function symbol $f$. Give an $L$-sentence $\phi$ that is true in every $L$-structure $M$ if the following holds: if $M \models \phi$, then $M$ is infinite. My ...
2
votes
0answers
121 views

What kind of logics satisfy the coincidence lemma?

Lets formulate the incidence lemma as follows. We have a possibly infinite set of variables X and the domain of discourse U. Lets define an interpretation of the variables X in the domain U as a ...
5
votes
1answer
104 views

Definability in exponential fields assuming quasiminimality

I've watched a lecture by Alex Wilkie on the MSRI website which covered the first order theory of exponential fields. He gave an exercise which looks very surprising. It should be solvable, however, ...
6
votes
2answers
296 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 ...
3
votes
1answer
161 views

Crashcourse Models in Set Theory

I am currently working through the lecture notes. In the end we had a short introduction to Models in Set Theory, but since it was quite to the end, we did not really go into details. So my ...
1
vote
2answers
91 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 ...
2
votes
3answers
154 views

Can we define 'model' to mean 'diagram' in the sense of mathematical logic? If so, how to define the satisfaction relation?

According to Wikipedia, every $\sigma$-structure $A$ is associated with a collection of atomic and negated atomic sentences called its diagram. Here's the precise definition. For each σ-structure ...
4
votes
1answer
103 views

$dcl(A)=\{x \in M : x$ definable from $A \}$, Show $dcl(dcl(A)=A$

Marker exercise 1.4.10c $dcl(A)=\{x \in M : x$ definable from $A \}$, Show $dcl(dcl(A)=A$ I assume "$x$ definable from $A$" means "$\{x\}$ is $A$-definable." Definition 1.3.1: Let $\mathcal{M} = ...
7
votes
1answer
165 views

Non-standard proofs of standard theorems

In Richard Kaye's book Models of Peano arithmetic, one can read (page 13): We have proved that any nonstandard $M \models \mathrm{Th}(\mathbb{N})$ has a nonstandard $a \in M \models \theta(a)$ iff ...
5
votes
2answers
133 views

Running programs in nonstandard models of PA

I came across the following problem in several places, to paraphrase: Let $T$ be a recursively axiomatizable, consistent extension of PA. Then there exists some $e$ such that the $e'$th program ...
2
votes
1answer
80 views

Back and forth and the axiom of choice

Is the axiom of choice a necessary condition for the application of "back and forth construction" in model theory?
1
vote
1answer
68 views

Type $\sim$ Minimal Polynomial & Orbit

In Model Theory by Wilfrid Hodges, he gives an intuition of what a type is in the following way: "One can think of types as a common generalisation of two well-known mathematical notions: the ...
0
votes
0answers
68 views

Getting Failure of Compactness from the Failure of Upward Lowenheim-Skolem in Omega logic.

(1)Given Omega-completeness, and assuming compactness implies upward Lowenheim-Skolem, can one get the failure of compactness by showing failure of upward l.s.? I ask because it would seem to take ...
5
votes
1answer
260 views

Quantifiers as Adjoints in Generalized Logics

It is a well known fact that the classical universal and existential quantifiers can be seen as adjoints in certain categories. In the continuous model theory of metric structures (see ...
2
votes
0answers
46 views

Concurrent relation and enlargement

The superstructure $V({}^{\ast}X)$ [with respect to a monomophism $\ast : V(X) \to V({}^{\ast}X)$] is called an enlargement of $V(X) $ if for each set $A \in V(X)$ there is a set $B \in {}^{\ast} ...
2
votes
2answers
107 views

Theory vs. Deductive Theory

Looking through some notes on model and computability theory, I noticed that the definition of the term 'theory' changed between them; in particular, the model theory (based on Hodges' text) defined a ...
0
votes
0answers
68 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')$$ ...
4
votes
1answer
111 views

Do we assert the existence of set theory when reasoning about L-structures?

In model theory, if L is a first order language, by the definition of a L-structure $\mathcal{M}$ it is partly given by a non-empty set $M$ called the universe or domain of $\mathcal{M}$. From where ...
4
votes
1answer
204 views

Ehrenfeucht–Fraïssé game, how can I understand it?

My course of "Formal Methods" deals with Ehrenfeucht–Fraïssé games, particularly regarding the inexpressibility in FO logic. At the moment I've fully understand what this games are and how they are ...
0
votes
1answer
101 views

Question on the ultrapower construction of superstructure

On page 83-85 (here, on googlebooks), An Introduction to Nonstandard Real Analysis, Albert E. Hurd, Peter A. Loeb, two steps are given to construct a monomorphism $\ast : V(X) \to V({}^{\ast} X)$. The ...
0
votes
1answer
38 views

Signatures and L-Structures

Consider the field of real numbers $\mathbb{R}$. This is an $L$-structure. Is there such a thing as an $S$-structure (i.e. a signature structure)? Or because we can recover a first order language from ...
7
votes
3answers
199 views

Is there any countable ordinal number which has a member undefinable?

Let $Q\colon=\{\alpha \in Ord \mid \exists \beta \in \alpha(\beta \text{ is undefinable in } \langle\alpha,<\rangle )\}$ denote the set of all ordinal numbers which has an undefinable member. ...
1
vote
3answers
72 views

Show $s(s(a))=s(b)$ implies $s(a)=b$

Let us have a first order language $L=\{0,s\}$, where $0$ is a constant, $s$ is a function symbol of arity $1$. The first-order theory $T$ is axiomatized as follows: $\forall x \neg( s(x) = 0)$ ...
4
votes
1answer
253 views

A sentence that has infinite models, finite model, but no finite model above certain cardinality

Let $T$ be a theory and $\sigma$ a sentence, such that there exists infinite $\mathfrak{A} \models T + \sigma$. there exists finite $\mathfrak{A} \models T + \sigma$. there exists $n \in ...
3
votes
1answer
95 views

What's the idea behind the proof of saturation of internal sets via ultrapower construction?

I'm trying to understand the proof of saturation of internal sets via ultrapower construction on Robert Goldblatt's Lectures on the Hyperreals: An Introduction to Nonstandard Analysis. Though, it's ...
2
votes
1answer
65 views

Can I express (only) the syntactical formulation of a set theory within another.

Motivated by this question on the SE philosophy board "Is there a one true set theory", I want to ask for a clarification: I've seen e.g. ZF being expressed in Grothendieck set theory. If I say ...
1
vote
1answer
69 views

Every connected $\omega$-stable group has a zero element?

Let $G$ be a connected $\omega$-stable group and $p$ its unique generic. Let $a$ be a realization of $p$, $G\prec G_1$ an elementary extension containing $a$ and $q$ the non forking extension of $p$ ...
5
votes
1answer
68 views

Point evaluation of a linear functional on an Ultrapower

Let $E$ be a Banach space and $(E)_{\mathcal U}$ be an ultrapower for some ultrafilter $\mathcal U$ on an index set $I$. It is remarked in a paper that $(E')_{\mathcal U}$ can be naturally embedded ...
5
votes
2answers
344 views

Do isomorphic structures always satisfy the same second-order sentences?

I know that if two mathematical structures are isomorphic, then they satisfy the same first-order sentences. The converse is false. This is probably a completely obvious question, but is it true that ...
10
votes
1answer
237 views

Is this a characterization of well-orders?

While grading some papers and thinking about a question related to well-orders (in particular, pointing a mistake in a solution), I came to think of a reasonable characterization for well-orders. I ...
6
votes
1answer
123 views

Model Theory (Hodges), Section 2.1, Exercise 13

Let $K$ be a field of characteristic 0, $n$ a positive integer, and $G$ the group $GL_n(K)$ of invertible linear transformations on $K^n$. Show that the following subsets of $G$ are ...
2
votes
1answer
119 views

Not Skolem's Paradox

Assume we have a countable, non-standard model of Peano Arithmetic (PA) in ZFC. http://en.wikipedia.org/wiki/Non-standard_model_of_arithmetic Let $N^*$ be the universe of this model and let $m \in ...
3
votes
0answers
150 views

Crankery: Is there a perfect inner model of ZFC?

In the book "Aspects of Vagueness", the article "The alternative set theory and its approach to Cantor's set theory" by A. Sochor proposes the following definition: We will say that a set universe ...
5
votes
1answer
55 views

Restrictions of automorphisms to elementary substructures

Suppose that I have structures $M \preceq M'$ (in some first-order language). I have a set $A$, with $M \subseteq A \subseteq M'$, and an automorphism $f$ of $M'$. Is it is always possible to find ...
141
votes
1answer
4k views

Is there a 0-1 law for the theory of groups?

For each first order sentence $\phi$ in the language of groups, define : $$p_N(\phi)=\frac{\text{number of nonisomorphic groups $G$ of order} \le N\text{ such that } \phi \text{ is valid in } ...
4
votes
1answer
123 views

Definiteness of omega

A homework(ish) problem from models of set theory: Define $\varphi(x) :\leftrightarrow Lim(x) \land \forall y\in x \, (Lim(y)\rightarrow y=0)$ where $Lim(x)$ means that $x$ is a limit ordinal. ...
0
votes
1answer
129 views

non-axiomatizable logics

Hope you're all doing well. My question is about non-axiomatizable logics. My understanding is that a "logic" (the mathematical structure) is just another word for a "propositional calculus" as in ...
5
votes
1answer
63 views

Omitting Types… recursively

I'm working on the following problem at the moment: Let $\mathcal{L} = \{R\}$, where $R$ is a binary relation symbol. Let $T$ be a consistent, decidable $\cal{L}$-theory, and let $p(x)$ be a ...
3
votes
1answer
62 views

Complexity of index sets in nonprincipal ultrafilters

Let $U$ be a nonprincipal ultrafilter on $\omega$. It can be shown that the set $I = \{e \mid W_e \in U\}$ (where $W_e$ is the $e$th r.e. set in some given enumeration) cannot be $\Delta_2^0$ (in ...
1
vote
1answer
127 views

Standard models being non-standard?

If there is a ''set'' W in V which is a standard model of ZF, and the ordinal κ is the set of ordinals which occur in W, then Lκ is the L of W. If there is a set which is a standard model of ...
3
votes
0answers
94 views

generating complete consistent theories

This is a model theoretic question. I was reading Kremer & Mints's Dynamic topological logic paper, and it mentioned that by a “standard argument”, every consistent formula is a member of some ...
3
votes
2answers
105 views

First order logic, finite partially ordered structure problem

The exercise below is part of an exam for a Logic course. There were other questions leading up to this, but I've included their "result" in the wording below. Suppose alphabet $\mathcal{L} = ...
1
vote
0answers
113 views

Is this first order version of the Collatz conjecture decidable in peano arithmetic?

Let $\phi(x)$ be a first order formula in the language of arithmetic with one free variable $x$. Consider the sentence $\psi_\phi$, defined as: $$\phi(0)\wedge \phi(1) \wedge (\forall x \phi(x) \to ...