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

2
votes
1answer
107 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 ...
4
votes
1answer
49 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 ...
6
votes
3answers
136 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
39 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
77 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 ...
0
votes
1answer
33 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 ...
2
votes
1answer
78 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
78 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
37 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$, ...
3
votes
0answers
83 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
39 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
69 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
103 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
49 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
84 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
40 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
52 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
48 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
61 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
52 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 ...
0
votes
0answers
48 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 ...
2
votes
0answers
72 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 ...
7
votes
1answer
58 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 ...
4
votes
1answer
78 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 ...
0
votes
1answer
68 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
49 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
0answers
66 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 ...
5
votes
2answers
481 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
104 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
49 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
71 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 ...
1
vote
1answer
93 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
35 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
54 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}$ ...
3
votes
3answers
90 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 ...
4
votes
1answer
76 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 ...
2
votes
2answers
86 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 ...
1
vote
1answer
37 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
121 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
74 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
114 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
85 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 ...
48
votes
8answers
4k 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 ...
2
votes
1answer
41 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
69 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 ...
0
votes
2answers
69 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 ...
1
vote
3answers
139 views

ZFC Axioms to be extended?

Sorry if this is going to be a really loaded question. I was told several times that for virtually all theorems/corollaries/propositions of mathematics (except those cases not compatible with ZFC ...
1
vote
1answer
130 views

Definable subsets of the natural numbers using only the successor function

Consider the first-order language whose only nonlogical symbol is the unary function symbol $S$, and the structure $\mathfrak{N} = ( \mathbb{N} , S )$, where $S$ denotes the successor function. Why ...
0
votes
0answers
33 views

First-Order Logic: Non-Normal Model of Sentences True in all Normal Models?

Let $\mathcal{L}$ be a first-order language with quantifier $\forall$, connectives $\neg$ and $\rightarrow$, a two-place predicate $E$ and a one-place function symbol $f$. There are no other ...
3
votes
2answers
110 views

Model-theory and Proof-theory in Propositional Logic

I'm trying to link results of model theory and proof-theory in propositional language. Here i will use $\models$ to denote logical consequence, in the model-theory sense. Being $x,y$ two formulas of ...