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

14
votes
3answers
603 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
188 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
173 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
263 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
688 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
143 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
399 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
471 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
93 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 ...
1
vote
3answers
249 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
152 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
331 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
331 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
195 views

Boolean algebras without atoms

Why is the theory of Boolean algebras without atoms $\omega$-categoric?
5
votes
2answers
259 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 ...
3
votes
1answer
508 views

Non-standard models of arithmetic for Dummies (2)

I've learned that there are (at least) three types of countable non-standard models of arithmetic, depending on the primitive operations: successor only → $\mathbb{N}$ followed by a copy of ...
15
votes
1answer
1k views

Non-standard models of arithmetic for Dummies

Why is (1) a copy of $\mathbb{N}$ "followed by" a copy of $\mathbb{Z}$ not a (non-standard) model of arithmetic, neither (2) a copy of $\mathbb{N}$ followed by an infinite sequence of copies of ...
9
votes
2answers
1k views

Showing any countable, dense, linear ordering is isomorphic to a subset of $\mathbb{Q}$

I'm trying to knock out a few of the later exercises from Enderton's Elements of Set Theory. This problem is #17, found on page 227. A partial ordering $R$ is said to be dense iff whenever $xRz$, ...
13
votes
2answers
603 views

Intersection of Algebraic Topology/Geometry and Model Theory/Set Theory

Is there any intersection between the ideas of Algebraic Topology/Geometry (I know that there is most certainly a non-trivial intersection between Algebraic Geometry, Algebraic Topology, Arithmetic ...
2
votes
1answer
146 views

Validity of a second-order formula

This is exercise 22.6 from Boolos,Jeffrey,Burgess Computability and Logic 4th ed. You are asked to prove the validity of the following sentence (with second-order logic as the underlying logic and ...
8
votes
1answer
227 views

How to prove an extension of ZFC is conservative

Working in ZFC. I've defined a function-like binary predicate $R$ on a proper class. It has to be recursive; i.e. $R(a,b)$ must usually depend on one or more $R(c,d)$ for some $c$s and $d$s ...
4
votes
1answer
280 views

First-order Indistinguishibility of “the continuum”

Let us consider two different models of the continuum $\mathbb{R}$ (that is, we take two arbitrary ZF-models, and we look at the continuum in each one of these models). Let us now suppose that we ...
8
votes
3answers
479 views

Relationship between Category theory and Axiomatic set theory

I've recently started learning Category theory- and I have a pondering- wondering if anyone can help. Is it possible for two categories to satisfy two different set-axiom system. Namely- is it ...
5
votes
2answers
669 views

A first order sentence such that the finite Spectrum of that sentence is the prime numbers

The finite spectrum of a theory $T$ is the set of natural numbers such that there exists a model of that size. That is $Fs(T):= \{n \in \mathbb{N} | \exists \mathcal{M}\models T : |\mathcal{M}| =n\}$ ...
2
votes
1answer
344 views

some problems about axiomatizable classes resulting from compactness

I'm trying to work on the following problems: Prove that if a set S of sentences axiomatizes a finitely axiomatizable class K of structures then K can be axiomatized by a finite subset of S. I have ...
3
votes
1answer
119 views

does the definition of model depend on a theory or just a signature?

Σ:signature T:Σ-theory For M:Σ-model which satisfies T, is it proper to name it “Σ,T-model” or “Σ-model satisfying T”? In comparison, in the context of Lawvere theories, any Lawvere theory L ...
2
votes
0answers
70 views

Comparing symbolic and analog descriptions

I've never seen the following comparison before. Let me start with a specific example: Given a finite structure with two symmetric binary relations, i.e. a graph $G$ with one vertex set $V$ and two ...
3
votes
1answer
263 views

Class models in set theory and category theory

Is it a mistake ab initio to think of categories as of models of category theory, just as we think of (inner) models-of-set-theory as of models of set theory, graphs as of models of graph theory, ...
5
votes
2answers
507 views

Example of an UnDecidable Logical Theory which is an extension of a Logical Decidable Theory?

Let $T_1$ and $T_2$ be two first-order logical theories (over the same signature) such that $T_1 \subseteq T_2$ and both are recursively axiomatized. My question is the following: is it possible that ...
4
votes
1answer
326 views

(Un)Decidability of satisfiable but not finitely-satisfiable formulas

I am curios about the decidability or undecidability of the following decision problem. INPUT: a first-order formula $\varphi$ OUTPUT: Yes, if $\varphi$ is satisfiable but not finitely-satisfiable ...
1
vote
1answer
283 views

Finite Model Property on the First-Order Theory of Two Equivalence Relations

I know that there is a first-order sentence $\varphi$ such that $\varphi$ is written in the vocabulary given by just two binary relation symbols $E_1$, $E_2$ (and hence, without the equality ...
6
votes
2answers
235 views

Compactness on models with bounded finite size

I am aware that compactness fails on finite models, but the common counter-example uses models of arbitrary big finite size. So if we bound the size what results can we get? Assume we have an ...
5
votes
2answers
199 views

Logic in the metatheory

In Goldstern and Judah's The Incompleteness Phenomenon we are asked to prove that any model of the first two Peano Axioms: $$\forall x [Sx\neq0]$$ $$\forall x\forall y[Sx=Sy\implies x=y]$$ must be ...
2
votes
1answer
334 views

Model Theory-logic

Given the following formula: $$\bigg[\forall x P(x,x) \wedge \forall x \forall y \forall z\bigg( P(x,y) \wedge P(y,z) \Rightarrow P(x,z)\bigg) \wedge \forall x \forall y (P(x,y) \vee P(y,x)) \bigg] ...
6
votes
2answers
707 views

What is an example of a finite model in first order logic having a unique undefinable element?

This is (a slight paraphrase) of question 1.3.14 in Chang and Keisler's Model Theory book. "Show that for each natural number $n$, there is a language $L_n$ and finite model $M_n$ of $L$ such that ...
2
votes
1answer
147 views

Does this proposition hold if $\text{Mod}(\Gamma)=\emptyset$?

The following is the start of basic corollary in my logic text: For any set $\Gamma$ of sentences, $\Gamma\subseteq\text{Th}(\text{Mod}(\Gamma))$. What happens when $\text{Mod}(\Gamma)$ is empty? ...
14
votes
1answer
530 views

Is there a natural model of Peano Arithmetic where Goodstein's theorem fails?

Goodstein's Theorem is the statement that every Goodstein sequence eventually hits 0. It is known to be independent of Peano Arithemtic (PA), and in fact, was the first such purely number theoretic ...
8
votes
5answers
2k views

Example of non-isomorphic structures which are elementarily equivalent

I just started learning model theory on my own, and I was wondering if there are any interesting examples of two structures of a language L which are not isomorphic, but are elementarily equivalent ...