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

1
vote
1answer
61 views

Trying to construct a model for this algebraic specification

I'm studying for an exam on lambda-calculus and algebraic specifications, and I'm having trouble figuring out this problem. I was wondering if anyone here could help?? The given specification: S: ...
1
vote
2answers
172 views

How to prove exact number of congruences over $\mathbb {R}$?

I have to prove that there are exactly 2 congruences over $\mathbb {R}$ seen as a model/structure $\tau = (\varnothing, {+,*}, \varnothing, \operatorname{arity}(+) = \operatorname{arity}(*)=2)$ where ...
30
votes
6answers
1k views

What is an efficient nesting of mathematical theorems?

Various mathematical areas of research evolved from a wide and diverse range of questions. Many are physical in nature or come from informatics/computer science, some are procedural or optimization ...
6
votes
0answers
248 views

Using the compactness theorem to show a set of first-order formula is equivalent to a set of quantifier-free formula

I am going through some theorems in Hodges' ``A shorter model theory'' and I have realized that I do not understand a certain argument regarding compactness. My question has two forms, I am sure that ...
3
votes
1answer
320 views

Model Theory: Homomorphism preserves positive L-formulas

A formula $\varphi$ of a language $L$ is positive iff it can be obtained from atomic formulas by using $\vee, \wedge$. Let $M,N$ be $L$-structures and $f: M \rightarrow N$ be an $L$-homomorphism. How ...
8
votes
2answers
236 views

Fraïssé limits and groups

I was recently reading up on Fraïssé limits in Hodges' "A shorter model theory." I was trying to think of some examples and wanted to see if I could take the Fraïssé limit on the category of finite ...
1
vote
1answer
230 views

Gluing together mathematical structures, how?

By structure, I mean that which is defined here: http://en.wikipedia.org/wiki/Structure_%28mathematical_logic%29 What I'm looking for is a way of gluing together structures so that each structure ...
4
votes
1answer
273 views

How many countable models of ZFC are there?

If we were looking at just an arbitrary binary relation on a countable set then I guess we would be looking at infinite graphs and those are uncountable. However, ZFC places an extra structure on our ...
1
vote
1answer
101 views

Another question on saturated models of ZFC

Let $M$ be a saturated model of ZFC and let $\kappa$ be any cardinal in $M$. Now let $$\begin{align*} p_\kappa(f) &= \{ “f \text{ 1-1 function”} \wedge \operatorname{dom}(f) \subseteq \omega ...
3
votes
2answers
97 views

$\Sigma_1 \cup \Sigma_2$ has a model

Let $\Sigma_1$ and $\Sigma_2$ be sets of $L$-sentences such that no symbol of $L$ occurs in both $\Sigma_1$ and $\Sigma_2$. Suppose $\Sigma_1$ and $\Sigma_2$ have infinite models. Then $\Sigma_1 \cup ...
0
votes
1answer
83 views

Poizat's definition of $p$-equivalent $k$-tuples

Maybe this is too trivial a question to be posted anywhere, but anyway. I am reading Poizat's "A Course in Model Theory". In page 4 he defines the notion of two $k$-tuples, each in the universe of ...
2
votes
1answer
128 views

What is a model of a formal system?

Please give the most illuminating example of a model for a formal system, and a simple example of its use. I also wish an example of an interpretation, and what its useful for.
5
votes
2answers
282 views

Primes in nonstandard models of PA

What is known about prime numbers in nonstandard models of PA? Restricted to true natural numbers the sets are identical, but does there always exist nonstandard primes? Can we explicitly define one ...
4
votes
2answers
181 views

What does a nonstandard proof of Con(PA) look like?

As in Godel's incompleteness theorem natural numbers encode proofs of theorems. Due to Godel's completeness theorem there is a natural number (in some nonstandard model) that proves $Con(PA)$. What ...
0
votes
1answer
193 views

Non-triviality of a semigroup and a semiring

Assume we are given an additive semigroup $M$ which we know it is non-trivial i.e. $M\neq \lbrace 0 \rbrace$. Let $R$ be the semiring obtained from adding a multiplication law to the semigroup. Under ...
0
votes
0answers
77 views

Definable measure preserving isomorphisms of $p$-adic semialgebraic sets

Consider a $p$-adic field $K$ (finite extension $\DeclareMathOperator{\bQ}{\mathbb{Q}}$of $\bQ_p$) in Macintyre language $\DeclareMathOperator{\cL}{\mathcal{L}}$ $\cL_{\rm Mac}$. Let $Z$ be a ...
14
votes
2answers
405 views

Comparing countable models of ZFC

Let us consider the class $\cal C$ of countable models of ZFC. For ${\mathfrak A}=(A,{\in}_A)$ and ${\mathfrak B}=(B,{\in}_B)$ in $\cal C$ I say that ${\mathfrak A}<{\mathfrak B}$ iff there is a ...
4
votes
1answer
132 views

Computing square roots and calculus

If one were to verify that $$ \sqrt{2} < 3 $$ would the underlying formalisation require a logic more expressive than first-order? Or, is FOL sufficient since real numbers can be formalised in ...
1
vote
2answers
260 views

The structure $(\mathbb{Q}, <)$ is O-minimal

I am trying to prove that the DLO $(\mathbb{Q}, <)$ is an $O$-minimal structure, but I am trying to prove this without using the fact that the complete theory of dense linear orderings without ...
1
vote
1answer
219 views

Structure and Formula encoding for Turing Machine

During my study of Finite Model Theory I found that usually purely relational structure say $\mathcal{M} = \langle A, R_1,\ldots,R_k \rangle$ are encoded as ...
2
votes
1answer
128 views

A problem about complete theory

I'm working on the following problem which is exercise 3.5.1 in Rothmaler's Model Theory book. Show that theory $T$ is complete iff $\phi \vee \psi \in T$ implies $\phi \in T$ or $\psi \in T$ (keep in ...
2
votes
1answer
356 views

Formalising real numbers in set theory

If I understand correctly, the real numbers can be formalised in a first-order, like in ZF. However, such a formalisation is not strong enough to ensure that all models of the reals are isomorphic. ...
0
votes
2answers
132 views

Some questions concerning set-theoretic models of first-order theories

Consider a finitely axiomatized theory $T$ with axioms $\phi_1,...,\phi_n$ over a first-order language with relation symbols $R_1,...,R_k$ of arities $\alpha_1,...,\alpha_k$. Consider the atomic ...
2
votes
1answer
240 views

How can i prove that the theory of random graph has a vaughtian pair?

I'm searching for theories that have a vaughtian pair. I've been given a hint, that $T_{RG}$ has at least one. I have also found many theorems stating in which cases a theory has no vaughtian pair, ...
10
votes
4answers
935 views

How can there be genuine models of set theory?

I know that this a beginner's question asked too many times, but I still didn't get an answer which lets me quit asking: Given that a model/interpretation of a theory (in the Tarskian sense) is a ...
5
votes
1answer
417 views

A logic that can distinguish between two structures

it's known that there are non-isomorphic structures that satisfy the same first-order sentences. Likewise it's known (by cardinality arguments) that there are non-isomorphic structures that satisfy ...
7
votes
1answer
191 views

A compactness problem for model theory

I'm working on the following problem: Assume that every model of a sentence $\varphi$ satisfies a sentence from $\Sigma$. Show that there is a finite $\Delta \subseteq \Sigma$ such that every model ...
1
vote
0answers
182 views

Can the reduced product construction generate boolean-valued models?

In model theory, the reduced product construction contains a collection of structures or models, a set I that indexes the collection, and a filter U on I. Ultraproducts are a special case of reduced ...
6
votes
1answer
250 views

Infinite field of characteristic p elementary equivalent to field with transcendental element over prime subfield

I'm trying to show that if F is an infinite field of characteristic p then it's elementary equivalent to a field F' of char p which contains an element transcendental over its prime subfield (the ...
6
votes
2answers
161 views

Axioms for atomless Boolean algebras

I'm embarrassed to be asking, but: "Write down a set of axioms for the theory of atomless Boolean algebras." This is Exercise 1.14 in Chapter 9 of "Models and Ultraproducts" by Bell and Slomson. I'm ...
3
votes
3answers
266 views

Interpretation of a formula and truth

I just started self-studying Mathematical Logic by Ebbinghaus. I already knew something about formal languages, but nothing about model theory. There is something I don't understand: Exercise 3.3, ...
3
votes
1answer
197 views

Can somebody explain to me how we define an isomorphism between structures?

I was reading this definition from journal article 'fixed-point logics with nondeterministic choice' by Anuj Dawar and David Richerby. On page 505 it says 'Classes of structures are assumed to be ...
14
votes
3answers
615 views

Comparing Category Theory and Model Theory (with examples from Group Theory).

The following question eats my brain: The standard definition of a "category" and a list of examples following this definition confuses me. My question is simple: (Q1)If someone write "the category ...
1
vote
0answers
192 views

Same same but different: Coextensive relations in model and set theory

The definition of a structure in model theory can be summed up like this (for simplicity's sake without individual constants and functions): Def. 1 A structure is a triple of sets $\langle A, ...
1
vote
1answer
174 views

Interpretation of relational symbols

Is it too pedantic to ask, why in the definition of a structure in model theory sets are assigned to the relational symbols $P, R, ...$ of a language and not to corresponding formulas $Px, Rxy, ...$ ...
8
votes
2answers
266 views

Why is the class of topological spaces not axiomatizable?

This is a follow-up question to this one, where in the answer it is explained how topological spaces may very well be described in a purely first-order manner. Furthermore, the set of first-order ...
12
votes
1answer
695 views

(Why) is topology nonfirstorderizable?

Is it the right point of view to say, that topology is nonfirstorderizable (only) because the union of arbitrarily many open sets has to be open? And if "arbitrarily many" was relaxed to "finitely ...
3
votes
2answers
144 views

Gap the lemma: satisfiable theory implies contradiction-free theory

I have a question about a gap in lemma. First how things were defined in the course I'm taking (I'm sorry to be making the readers going through this list of definitions, but I don't know how to make ...
4
votes
2answers
412 views

Model existence theorem in set theory

From the FOM newsgroup I learned: It's a theorem of (first-order) set theory that every consistent first-order theory has a model. What's the exact formulation of this theorem in purely ...
7
votes
2answers
327 views

The first-order theory of linear orders given by closed subsets

[ This question can be seen as a second part to my question A question on linear orders and elementary equivalence ] The question is whether the following conjecture is true or false. I am interested ...
10
votes
2answers
472 views

A question on linear orders and elementary equivalence

Does anybody know whether the following statement is true or false? Conjecture: For every linear order $\langle A, \leq \rangle$ there is a (topologically) closed subset $X$ of $\mathbb{R}$ (the real ...
1
vote
1answer
94 views

Idea for a proof involving an identity of term functions on $\sigma$-structures [x]

I have some problems with the following theorem: Fix an signature $\sigma$ and a set of variables $\mathbb{V}$. We call $t$ and $t_1$ "equivalent", if for every $\sigma$-structure $S$ and every term ...
2
votes
1answer
127 views

Find a first order sentence in $\mathcal{L}=\{0,+\}$ which is satisfied by exactly one of $\mathbb{Z}\oplus \mathbb{Z}$ and $\mathbb{Z}$

I'm re-reading some material and came to a question, paraphrased below: Find a first order sentence in $\mathcal{L}=\{0,+\}$ which is satisfied by exactly one of the structures $(\mathbb{Z}\oplus ...
2
votes
3answers
258 views

logic question: enumerating propositions

Is it possible to enumerate all propositions (ie, sentences containing no quantified or free variables) that are true given a set of formulas in higher-order logic? (ie, those propositions entailed by ...
4
votes
4answers
153 views

**symbol** of a mapping vs. mapping itself /understand the definition of “structure”

I am having problems understanding the definition of a "structure" in universal algebra. In my course in was introduced in the following way: "A structure $S$ consists of an underlying set ...
11
votes
0answers
338 views

Non-axiomatisability and ultraproducts

Let $T$ be a first-order theory over a language $L$, and let $\mathcal{M}$ be a subclass of the class of models of $T$. As I understand it, if there is no theory $\hat{T}$ over $L$ whose class of ...
7
votes
1answer
136 views

Are there any strongly axiomatizable logics that are not compact?

I mean here a logic in the sense of a language and semantics. By strongly axiomatizable I mean strongly sound and strongly complete. So I'm basically asking if there is a particular deductive system ...
21
votes
1answer
334 views

FO-definability of the integers in (Q, +, <)

With $Q$ the set of rational numbers, I'm wondering: Is the predicate "Int($x$) $\equiv$ $x$ is an integer" first-order definable in $(Q, +, <)$ where there is one additional constant symbol ...
6
votes
2answers
198 views

Boolean algebras without atoms

Why is the theory of Boolean algebras without atoms $\omega$-categoric?
5
votes
2answers
261 views

$\omega$-saturation of $(\mathbb{R},<)$

Could anyone of you explain me why $(\mathbb{R},<)$ is $\omega$-saturated? EDIT: do you know also why the theory of Boole algebras without atoms is $\omega$-categoric? Added: The added question ...