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

For a compact logic, strong completeness follows from weak completeness

I have heard it said from reputable sources that one of the differences between a compact and a non-compact logic is that in a compact logic, strong completeness follows from weak completeness. ...
1
vote
0answers
34 views

Definable over $(\mathbb{R}, <, +, \cdot, 0, 1)$

I have to solve the following task and got some problems with it: a) Be $n\in\mathbb{Z}$. Is $\{n\}$ definable over $(\mathbb{R}, <, +, \cdot, 0, 1)$ b) Be $q\in\mathbb{Q}$. Is $\{q\}$ definable ...
1
vote
0answers
20 views

Definable over $(\mathbb{R}, +, \cdot)$

I have the following task and I am not so sure about my solution: a) Is $\{0\}$ definable over $(\mathbb{R}, +, \cdot)$? b) Is $\{1\}$ definable over $(\mathbb{R}, +, \cdot)$? c) Is $<$ ...
0
votes
0answers
11 views

Showing that $(p(x)\rightarrow q(x)) \leftrightarrow (\neg q(x) \rightarrow \neg p(x))$ is a valid $\mathcal{L}$-formula

If $\mathcal{L}=\{p,q\}$ with $p,q \in \mathcal{P}_1$, would showing that $(p(x)\rightarrow q(x))$ and $(\neg q(x) \rightarrow \neg p(x))$ have the same truth table prove that $(p(x)\rightarrow q(x)) ...
1
vote
1answer
29 views

If a formula has a Morley Rank then it is less then $|T|^+$

We saw in class that given a complete theory $T$, then if $MR\varphi\ge (2^{|T|})^+$ then $MR\varphi=\infty$ And we ware told that Lachlan improved this result to $|T|^+$. To prove it, I assume ...
3
votes
1answer
58 views

Is $\mathbb{N}$ definable over $(\mathbb{R},<,+,\cdot,0,1)$

is it possible to define the set $\mathbb{N}$ over the modell $(\mathbb{R},<,+,\cdot,0,1)$? So, does a formula $\varphi$ exist which describes the natural numbers. Unfortunatly I have no clue how ...
2
votes
1answer
19 views

How to prove: If $(\omega, <) \equiv \mathcal{M}$, then $(\omega, <) \prec_{f} \mathcal{M}$

To prove that If $(\omega, <) \equiv \mathcal{M}$, then there exists a function $f: \omega \to M$ (the domain of $\mathcal{M}$) such that $(\omega, <) \prec_{f} \mathcal{M}$. where, the ...
4
votes
1answer
128 views

$\vDash \varphi$ iff $\| \varphi \|_A =1$ for every boolean valued structure $A$

In the book Axiomatic Set Theory (Takeuti, G; Zaring, W.M. - 1973) the theorem 6.4 states that if $\varphi$ is a closed formula of a given language then it is satisfied in every boolean valued ...
2
votes
1answer
23 views

Spectrum of a set of first order formulas

Let ψ be a first order formula. Wikipedia defines the spectrum of the formula ψ as follows: The spectrum of ψ is the set of natural numbers n such that there is a finite model for ψ with n elements. ...
0
votes
1answer
18 views

Equivalence infinite Spectrum problem and finite spectrum problem

Definitions: For a given first order sentence $\phi$ define $\text{spectrum}(\phi)$ to be the set of all cardinalities of the finite models of $\phi$. A set $S\subseteq\mathbb N_+$ is said to be a ...
2
votes
2answers
34 views

How to define the functions and relations for a logical model?

In model theory one has to define functions and relations on a set for the function and relation symbols of the logical theory. My questions are: What kind of operations are allowed to define ...
0
votes
1answer
39 views

Is T an infinity spectrum whenever T is a spectrum?

Definitions: For a given first order sentence $\phi$ define $\text{spectrum}(\phi)$ to be the set of all cardinalities of the finite models of $\phi$. A set $S\subseteq\mathbb N_+$ is said to be a ...
1
vote
1answer
46 views

Infinite Spectrum Problem

Let us work in a class theory like NBG. For a given first order sentence $\phi$ define $\infty\text{-spectrum}(\phi)$ to be the class of all cardinal numbers $\kappa$ for which there is a model $M$ ...
0
votes
1answer
24 views

List of primes and compactness

I'm working on the following problem: Let $p_0,p_1,...$ be a list of the prime numbers in increasing order. Show that for any set $X\subseteq\mathbb{N}$, there is a model of Th($\mathbb{N})$ which ...
4
votes
1answer
34 views

Ordinal pair $(α,β)$ such that $α<β$ and $Th(α,<) = Th(β,<)$

A number of weeks ago I was thinking of finding an example of a complete countable theory with only one binary predicate that is not $ω$-categorical. I later realized that $Th(\mathbb{Z},<)$ works, ...
0
votes
1answer
20 views

Are isomorphisms between finitely generated substructures determined on a set of generators?

Let $K$ be a structure, $\varphi: A \to B$ be an isomorphism of finitely generated substructures of $K$. Let $a_0,\dots,a_n$ be generators of $A$. Do the images $\varphi(a_i)$ of the generators $a_i$ ...
3
votes
1answer
86 views

Ultraproduct with no long descending sequence

I have a countably infinite well-ordered structure $M$ (over a countable language if it helps), and an uncountable regular cardinal $κ$, and I wanted to construct an elementarily equivalent structure ...
2
votes
1answer
53 views

why can't this proof of Löwenheim-Skolem Theorem be shorter?

An algebraic introduction to mathematical logic page 46 has the following: the proof continues on, but it seems to me we can stop here. Every consistent theory has a model, and we've just proven ...
0
votes
0answers
22 views

Modelltheory, validity of a formula

I have a question to the following task: $M=\{1,2,3\}$ and $R=\{(1,2),(1,3)\}$ Let $\mathcal{L}$ be a first order language with a binary relationsymbol $\overline{R}$ so, that $\mathcal{M}=(M,R) is ...
0
votes
0answers
63 views

Profane Model Theory, sacred Proof Theory

Dirck van Dalen starts the Preface to his Logic and Structure with the following words: "Logic appears in a ‘sacred’ and in a ‘profane’ form; the sacred form is dominant in proof theory, the ...
2
votes
1answer
52 views

Every $\alpha < \kappa^+$ can be embedded in any interval of $\kappa^{<\omega}$.

Let $\kappa$ be a cardinal. I want to show that every ordinal $\alpha < \kappa^+$ can be embedded (as an order) in any interval of $\kappa^{<\omega}$, ordered lexicographically. This is exactly ...
0
votes
0answers
30 views

Find a $\mathcal{L}$-formula to fullfill a condition

Let $\mathcal{L} = \{f,g\}$ where $f$ is binary and $g$ unary. Consider the $\mathcal{L}$-structure $\mathfrak{M}$ with underlying set $\mathbb{R}$ and $f^{\mathfrak{M}}$ is the default ...
1
vote
2answers
26 views

Definition of an ideal in a L-language

Let $\mathcal{L}_\text{ring}=\{0,1,+, \cdot, I\}$ where $0,1$ are constants, $+, \cdot$ are binary function symbols and $I$ is an unary relation symbol. Give $\mathcal{L}$-formulas which ...
7
votes
1answer
106 views
+150

Surjective exponentials for algebraically closed fields

The existence of the exponential on $\mathbb{C}$ has a very basic, yet very strong consequence : $(\mathbb{C}^*,\cdot)$ is a quotient of $(\mathbb{C},+)$. This question is concerned with fields $K$ ...
7
votes
0answers
69 views

Definable subset of the additive theory of integers

I strongly suspect that the subset $\{ -1,1 \}$ of $(\mathbb{Z},+)$ is not definable, despite being fixed under all automorphisms of the structure. However, I can't seem to be able find a proof. Does ...
3
votes
1answer
40 views

Does equivalence of algebraic categories imply bi-interpratibility of their theories?

By an algebraic theory $\mathcal{T}$ I mean any category with finite products such that the objects are given by all finite powers of some object $X$. Let $Alg\mathcal{T}$ be the concrete category of ...
1
vote
1answer
23 views

Application of compactness theorem: finite exponent groups

We call $G$ a torsion group if for every $g\in G$ there exists a natural $n>0$ such that $g^n=1$. We say that $G$ has finite exponent if the inverse quantification holds, i.e. there exists a ...
1
vote
0answers
36 views

Quantifier Elimination Tree

I found this example in "A Course in Model Theory", but don't seem to figure out why it is true. Let $L$ be a language having a unary predicate $P_s$ for each (finite) binary string $s \in \{0,1\}^*$ ...
3
votes
2answers
24 views

Properties of an elementary substructure

Let $M$ and $N$ be structures for a first order language $L$, with $M$ an elementary substructure of $N$. This means that $M$ is a substructure of $N$ and if $\varphi(x_1,\ldots,x_n)$ is a formula ...
1
vote
1answer
54 views

What is a universal function in model theory?

What does it mean that a function in a model is universal? Let A be the domain of a model. As I understand it, an empty function is a function that is not defined for any object in A; an empty n-ary ...
0
votes
2answers
62 views

Does Second-Order Comprehension make second-order ZFC inconsistent due to Russell's Paradox?

When we do set theory, we take our first-order variables to range over all sets. But if we take our second-order variables to range over sets of sets in the range of the first-order variables, then ...
3
votes
1answer
39 views

Rigid relations and Choice

A binary relation $R$ on a set $D$ is rigid iff the unique $D → D$ bijection that fixes $R$ is the identity function. Any well-ordering is rigid, so the Well-Ordering Principle has the consequence ...
3
votes
1answer
61 views

Does no non-standard model of Peano Arithmetic make the integers a principal ideal domain?

Though I do not find a reference now, I have heard no non-standard model of Peano Arithmetic has a principal ideal domain as its ring of integers. Is that right? Is it trivial? Or is there a good ...
1
vote
1answer
53 views

Completeness Theorem in logic and Completeness of a theory

Completeness Theorem says: $\Gamma \models \phi \longrightarrow \Gamma \vdash \phi$ And from definition of satisfaction: $\neg(\Gamma \models \phi) \longleftrightarrow \Gamma \models \neg\phi$ Now ...
6
votes
2answers
82 views

Is the axiom of induction constructively verifiable for a non-standard model of Peano arithmetic?

There exist models of the natural numbers which include infinite numbers. Such models are called non-standard models of arithmetic. (Proof: by the compactness theorem, there exist models of Peano ...
1
vote
1answer
33 views

Model isomorphisms of a set of sentences

I have a question about models of a set of sentences $T$, specifically the following: Let $S=\{R\}$ where $R$ is a unary relation symbol. Let $T$ be the set of sentences that for each $n\geq 1$ ...
3
votes
2answers
45 views

Prove that there exists a sentence $\varphi$

I'm doing some excercises from the book "The Incompleteness Phenomenom" from Goldstern and Judah. I have to do this and I don't know how to start. Let $\Sigma_1 $ and $\Sigma_2$ be sets of sentences ...
4
votes
3answers
65 views

Undefinability of evenness in first order logic

My question is to show there is no sentence $\psi$ in a language of first order logic without any non-logical symbols such that for every finite structure $\mathcal{A}$: $$\mathcal{A} \vDash \psi \; ...
4
votes
3answers
99 views

Minimal model of ZFC without power set axiom

We know that $L$ is the minimal standard model of ZFC. The question is, what is the minimal "standard" model of ZFC$^-$ (meaning ZFC without the Power Set axiom)? This is really two questions: Is ...
4
votes
2answers
70 views

Non existence of Prime models

Let $L$ be a countable language. Let $T$ be a complete $L$ theory. We know that if $T$ is small, then there is a prime model of the theory. But $\text{Th}(\mathbb{N},+,\times,0,1)$ is not small but it ...
1
vote
2answers
50 views

elementary question about definability

My understanding is that an object, m, from the domain of a model, M, is definable by a formula, F(x), just in case M |= (Vx)[F(x) <----> x = m]. However, this assumes that there is a name for the ...
2
votes
3answers
58 views

About definition of model

In Model theory, the definition of a model is a set. Can it be a proper class? ZFC has a model and maybe some models is a proper class. Definition of a model needs to include a proper class. Is it ...
0
votes
0answers
84 views

Gödel's incompleteness theorem applys to ZFC theory

When I assume ZFC's consistency, it is impossible to prove ZFC's consistency in itself from Gödel's incompleteness theorem 2. If ZFC's consistency have done, its proof need to be done in stronger ...
2
votes
0answers
82 views

How can I understand about ZFC and Gödel's Completeness theorem [closed]

English 1 ZFC could be formulated as First order logic. 2 Gödel's Completeness theorem is a theorem within ZFC. 3 I think a lot of books about set theory is implicitly assuming Gödel's ...
1
vote
3answers
91 views

In relatively simple words: What could be a model of $\sf {ZFC}$?

An $\text{interpretation}$ of a theory consists of A domain of discourse $\mathcal U$, usually required to be non-empty. For every constant symbol, an element of $\mathcal U$ as its ...
1
vote
1answer
102 views

absoluteness and and transitivity

I'm early in my reading about absoluteness, but one thing has me stuck, so I thought I'd ask. One reason absoluteness seems to matter is that we feel confident that we know what we're talking about ...
1
vote
0answers
33 views

Affine space over $\mathbb {Q}$ prime model, and dimension.

For homework, i need to prove the following: Let $M$ be a structure with universe $\mathbb {Q}$ of the language that cosiest only of function symbols $f_{\bar {\alpha}}(\bar{x})$ for all $\bar ...
5
votes
1answer
108 views

Limits of finite structures - first order logic

Assume that $\mathcal{C}=\{M_i:i\in I\}$ is an infinite collection of different finite $\mathcal{L}$-structures in a first-order language $\mathcal{L}$. The question is: What kind of infinite ...
0
votes
0answers
25 views

Lemma (?) on syntactically saturated maximal sets of sentences and existential sentences

Is there a proof of the following claim? $$\not \vdash_{{\rm FS}(L,M)} \exists x ~\alpha \implies [\alpha][x/c] \tag{T}$$ where no variable other than $x$ occurs free, $c$ is a name, ${\rm FS}$ ...
7
votes
3answers
113 views

What is the importance of “variety of algebras” in Universal Algebra?

Given an algebraic category, Birkhoff's Variety Theorem gives a categorical characterization of the full subcategories whose object-class forms a variety (i.e. can be defined by equations in the sense ...