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
95 views

Show that if $L$ is countable and contains a two-place predicate symbol, there are $2^{2^{\aleph_0}}$ classes of $L$-structures closed under $\equiv$

We say that a class of structures $K$ is closed under elementary equivalence ($\equiv$) if for all $A, B$, if $A \in K$ and $A \equiv B$, then $B \in K$. How to show that if $L$ (as a set of specific ...
4
votes
1answer
84 views

Model of complete extension of Zermelo set theory

Chang and Keisler's Model theory gives the following exercise problem: Prove that there is a complete extension $T$ of Zermelo set theory which has arbitrary large natural models. (A model $\...
0
votes
1answer
67 views

Why are there $\leq$ $2^{\operatorname{card}(\operatorname{Form}(L))}$ elementarily nonequivalent structures for $L$?

Let $L$ be a set of specific symbols and $\operatorname{Form}(S)$ be the set of all first-order formulas over $L$. Why are there $\leq$ $2^{\operatorname{card}(\operatorname{Form}(L))}$ elementarily ...
2
votes
1answer
66 views

How to prove that $max(\aleph_{0}, card(X)) = max(\aleph_{0}, card(L(X)))$?

I struggle with the following problem. Let $X$ be a set of elementary sentences and $L(X)$ be the smallest elementary language in which we can express all the sentences from $X$. How to prove that $...
2
votes
1answer
122 views

Cardinalities of Collections of Models

Let $T$ be a complete theory in a countable language (with only infinite models). Recall the spectrum function: $I(\aleph_\alpha,T)=$ the number of non-isomorphic models of $T$ of cardinality $\aleph_\...
6
votes
1answer
89 views

A model which has only one undefinable element over a language with only a finite number of symbols

I try to solve the problem 1.3.14 in Chang and Keisler's Model theory: For each $n\in\omega$, find a model $\mathfrak{A}_n$ for $\mathcal{L}$ a language with only a finite number of symbols, which ...
7
votes
3answers
217 views

Can $(\Bbb N,\leq)$ have an $\aleph_0$-categorical theory (in a larger language)?

One of the nicer consequences of compactness is that there is no statement in first-order logic whose content "$\leq$ is a well-order". So we can show that there are countable structure $(M,\leq)$ ...
2
votes
0answers
41 views

Counter example of monotone union [duplicate]

I saw this exercise in "Elements of Abstract and Linear Algebra" by E. H. Connell: Suppose $G$ is a group. Suppose $T$ is an index set and for each $t \in T$, $H_t$ is a subgroup of $G$. Furthermore, ...
1
vote
1answer
116 views

On the number of countable models of complete theories of models of ZFC [duplicate]

Fix the language of set theory $\mathcal{L}=\{\in\}$. Let $\langle M,\in\rangle$ be a set or proper class model of ZFC (e.g. $M$ could be $L$, $HOD$, $V_{\kappa}$ for some inaccessible cardinal $\...
1
vote
1answer
285 views

Why is the cardinality of a language defined as $||\mathcal{L}||$?

I'm reading Chang and Keisler's Model Theory and I don't quite understand the notation they use for the cardinality of a language. Elsewhere in the book, the cardinality of a set $X$ is denoted by $|...
3
votes
1answer
94 views

Inuition regarding Lowenheim-Skolem applied to models of set theory

According to wikipedia, ...the Löwenheim–Skolem Theorem states that for every signature $σ$, every infinite $σ$-structure $M$ and every infinite cardinal number $κ ≥ |σ|$, there is a $σ$-...
2
votes
3answers
90 views

One-element model of first-order PA

The First-Order axiomatisation of PA is: $\forall x. x = x$ $\forall x, y. x = y \rightarrow y = x$ $\forall x, y, z. x = y \land y = z \rightarrow x = z$ $\forall x. 0 \ne S(x)$ $\forall x, y. S(x) ...
0
votes
1answer
69 views

elementary class and abstract elementary class

I think I confused with the concept of elementary class and abstract elementary class. We see in the definition of AEC that each elementary class is an AEC. Let $l=\{\le\}$, $T=\emptyset$, $K=mod(T)...
4
votes
0answers
141 views

Countable transitive $T \vDash ZFC-P$ with $\approx$ not absolute: why do we need $H(\aleph_3)$?

I am trying to solve Exercise IV.3.31 from Kunen's Foundations of Mathematics. I think I have a solution but I am confused by one of the hints. By request, here is the text of the exercise. ...
3
votes
1answer
86 views

Existence of theories with exactly two countable models

I read a result of Vaught(a little down the page) that says that there cannot be any first order theory which has exactly two countable models upto isomorphism. Is this not a counter example: The ...
2
votes
1answer
121 views

Absolute confusion! (A question about absolute *sentences*)

I'm seriously confused about absoluteness. A formula in the language of a theory $T$ is absolute for $T$ structures if its truth value is the same in all standard transitive models of $T$ (this may ...
2
votes
0answers
180 views

How large or small can the gap in Shelah's main gap theorem be, up to consistency?

Shelah's main gap theorem in model theory says: For each first order complete theory $T$ in a countable language if $I(T,\kappa)$ denotes the number of its models of size $\kappa$ then one of ...
0
votes
3answers
69 views

The differences between Model Theory and Computation Theory

Model Theory seems more interested with Gödel's completeness theorem, Tarski' quantifier elimination and logic systems that Turing computability and Church recursivity. However, both theories overlap ...
4
votes
1answer
122 views

Elementary equivalence versus equivalence between the total theory in model theory

In the page for elementary equivalence on wikipedia, in the introduction, they say: "If N is a substructure of M, one often needs a stronger condition. In this case N is called an elementary ...
2
votes
1answer
75 views

Are there any purely semantic proofs of the compactness theorem that don't use the full axiom of choice? [duplicate]

Using Godel's completeness theorem, it can be shown that the compactness theorem is equivalent to the ultrafilter lemma. The compactness theorem can also be proven using ultraproducts and Los's ...
1
vote
2answers
59 views

Prove that ⊨ is not symmetric

Another question from a beginner: We want to prove that ⊨ is not symmetric by finidng concrete formulas φ and ψ for which we can show that φ ⊨ ψ and ψ ⊭ φ. Thank you for your help!
0
votes
0answers
121 views

Show that $(V_\omega,\in) \models \mathrm{Power\ set}$

Let "$\mathrm{Power\ set}$" denote the Power set axiom. I'd like if some of you could tell me if the solution of the following exercise is correct. I want to prove that $(V_\omega,\in)\models \...
3
votes
1answer
76 views

Is first-order logic complete with respect to countable structures?

Question. Let $\Gamma$ denote a first-order signature, and consider a sentence $\tau$ and a set of sentences $\Sigma$ in the language generated by $\Gamma$. If every countable $\Gamma$-structure that ...
5
votes
1answer
75 views

Nonstandard models of PA with a decidable order relation.

There this exercise in Models of Peano Arithmetic (Kaye 1991, p.157), which asks to define a recursive binary relation on $\mathbb{N}^2$, such that $M \upharpoonright < $ is isomorphic to $(\mathbb{...
0
votes
0answers
74 views

Absolute formula

I'm trying to study the model of Set Theory and I have a problem. If I know that a formula is absolute for a class, could I infer that the formula is true in my class? Namely, I'm trying to prove in $...
3
votes
0answers
82 views

Examples of Jónsson Models

Let $T$ be a complete first order theory. Suppose that $M\models T$. Then, $M$ is said to be a Jónsson Model of $T$ if for all $N$, such that $N\prec M$ and $N\models T$, we have $|N|<|M|$ (Note ...
8
votes
1answer
171 views

Every elementary submodel of $H(\aleph_1)$ is transitive

I am trying to solve the first part of Exercise II.17.30 in Kunen's Foundations of Mathematics which asks: Prove that every $A \preccurlyeq H(\aleph_1)$ is transitive. Here we are working over ...
6
votes
1answer
117 views

Ultraproducts of models of ZFC

Let $D$ be a non-principal ultrafilter over $\mathbb{N}$. Let $A_i$ for $i\in\mathbb{N}$ be (countable) models of ZFC such that $A_i\models \mathfrak{c}=\aleph_i$. Then, what is the size of the ...
2
votes
2answers
724 views

What is the real meaning of Hilbert's axiom of completeness

According to Greenberg's book of geometry it is sufficient to consider the axiom of Dedekind along with Hilbert's axioms (except of course for the Archimedian Principle and his Axiom of Completeness) ...
4
votes
1answer
95 views

The class of finite groups (models) and that of countable groups are not elementary classes (a generalized version).

First some definitions: For a set $\Sigma$ of $\mathcal{L}$-sentences, $Mod(\Sigma)$ denotes the class of all models that satisfy $\Sigma$. For a class $\mathcal{M}$ of models, we say it is $EC$ if $\...
4
votes
1answer
87 views

Models of infinite groups and 'Group-like' objects

Let $G$ be an infinite group, and for simplicity, we will assume that $G$ is also countable. Now, with $G$ in mind, we construct a new language $L_G=\{f_{a_i\_},f_{\_a_i}:a_i\in G\}$ where $f_{a_i\_}(...
5
votes
2answers
514 views

There is no smallest infinitely large prime

I'm reading Kunen's Foundations of Mathematics and trying to solve Exercise II.16.19, which constructs an elementary extension of the reals as an ordered field, and asks the reader to prove various ...
3
votes
2answers
237 views

Universe cardinals and models for ZFC

I'm reading through Joel David Hamkins' set theory lecture notes. On page 14, on the subject of inaccessible cardinals and submodels of ZFC in $V$, he defines a universe cardinal to be a cardinal $\...
2
votes
1answer
75 views

How can we get rid of function symbols in model theory?

I understand the presentation of a language in logic as having relations with arities, functions with arities and constants. I understand that a constant can be thought as a function with arity $0$. ...
1
vote
1answer
177 views

What is the point of (Compactness Theorem in the) Overspill Principle?

I am trying to understand the basics of computation theory. The Overspill Principle (also at google) basically says if you are cool you can do everything Let Г be a sentence of predicate logic ...
2
votes
1answer
148 views

Existence of an automorphism of $\Bbb C$ that fixes a finite set pointwise but does not fix $\Bbb R$ setwise

I would like to construct a (ring-theoretic) automorphism of $\Bbb C$ that fixes a finite set $A$ pointwise but does not fix $\Bbb R$ setwise. Marker's Model Theory, Corollary 1.3.6 does that in this ...
1
vote
1answer
52 views

Partial order version of elementary equivalence

Elementary equivalence is an important concept in mathematical logic. Two models $\mathfrak{M}$ and $\mathfrak{N}$ of the same signature are elementarily equivalent, written $\mathfrak{M} \equiv \...
3
votes
2answers
59 views

Does having a filter which is not maximal implies the negation of Łoś theorem?

If we have a family $(\mathfrak{M}_i)_{i\in I}$ of $L$-structures, and a filter $\mathcal{F}$ over $I$, we can define the reduced product $\prod_{i\in I}\mathfrak{M }_i/\mathcal{F}$. If $\mathcal{F}$ ...
4
votes
3answers
140 views

Are surjective polynomial maps injective?

An injective polynomial map $p:\mathbb{C}^n\mapsto\mathbb{C}^n$ is surjective (Ax-Grothendieck theorem). What is known about the reverse implication (surjective implies injective)? Why does the model-...
5
votes
1answer
122 views

Showing $2$ is not definable in $(\mathbb{Q},+)$.

As stated, I'm to show that $2$ is not definable in $(\mathbb{Q},+)$. I tried proving it by contradiction by showing that if $2$ were definable, then we could define $\mathbb{N}$ and multiplication ...
3
votes
3answers
183 views

Goedel's completeness theorem in and/or for intuitionistic first order logic

Warning: I am neither a logician nor a set theorist, just curious about foundations of classical and intuitionistic mathematics. Therefore it might well be that the things to come are plain wrong, and ...
0
votes
1answer
49 views

Prove that Th(N, +, .) has uncountably many 1-types over some finite set

not sure how to go about answering the above question. Thanks for your help! (alternative: Prove that Th(N, +, .) has uncountably many n-types over the empty set.)
6
votes
1answer
318 views

Is it possible to prove the axiom of infinity from the real number axioms?

What I mean by the title is whether, given that there is a class $\Bbb R$ and operations $+,\cdot,<$ that satisfy the ordered field axioms and the least upper bound axiom, you can prove the ...
3
votes
1answer
108 views

Showing there does not exist a formal proof of a formula $\phi$.

My problem:Suppose $R$ is a binary predicate and use the soundness theorem to show that there does not exist a formal proof of $$ \phi =\forall y\exists xR(x,y)\rightarrow \exists x\forall yR(x,y).$$ ...
5
votes
2answers
315 views

Finite Model Theory

It seems that finite model theory is regarded (in a sense) as a computer theoretic subject. Is this the case or are there questions of interest that are of interest to mathematical logicians or more ...
3
votes
1answer
106 views

“Syntactic models” and the proof of the Completeness Theorem

In Computational Complexity by Papadimitriou (page 107), he outlines the basic idea for a proof of the completeness theorem for first-order logic - namely, that given a consistent set $\Delta$ of ...
53
votes
8answers
5k views

How is the Gödel's Completeness Theorem not a tautology?

As a physicist trying to understand the foundations of modern mathematics (in particular Model Theory) $-$ I have a hard time coping with the border between syntax and semantics. I believe a lot would ...
3
votes
1answer
235 views

Non-isomorpic uncountable dense linear orderings (a textbook example)

We know that two countable dense open orderings are isomorphic, and we know that this is generally not true for uncountable structures. Now I quote from the textbook, that is "Model-Theoretic Logics": ...
3
votes
0answers
94 views

Finding a finite model

Hello I am having difficulty with this question, I am not even sure what strategy one would go about proving something like this: Suppose $L$ is a language which includes an infinite list $c_1,c_2,...
0
votes
2answers
86 views

Is there a name for models whose every element is named by (one or more) variable-free terms?

Let $T$ denote a first-order theory. Is there a name for those models $M$ of $T$ such that for all $x \in M$, there is a variable-free term in the language of $T$ whose interpretation under $M$ is $x$?...