# Tagged Questions

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 ...

2answers
63 views

### Prove that, for any sentence A of the predicate calculus with identity, at least one of spectrum(A) and spectrum(¬ A) is cofinite

I got the following exercise: Prove that, for any sentence A of the predicate calculus with identity, at least one of spectrum(A) and spectrum(¬ A) is cofinite. I already tried to prove this ...
1answer
35 views

### Why does the undefinability proof fail for $\mathbb{N}$ in $(\mathbb{Z}, 0, <)$?

An exercise asks to prove that: $\mathbb{N}$ is not definable in $(\mathbb{Z}, <)$, but definable in $(\mathbb{Z}, 0, <)$ (in the first-order logic). The solution to the former one relies ...
1answer
51 views

### What's the meaning this DOT notation?

I'm reading a chapter in a Model Checking book. I came across this chapter "Symbolic Model Checking", in which the author mentions Fixed Point representation. I don't know how to explain the context, ...
1answer
54 views

### Why does every complete theory have joint embedding property?

I came across a sentence in page 196 Chang & Keisler's model theory book that I don't understand. It says: Every complete theory has the joint embedding property. Def. A theory $T$ has joint ...
1answer
56 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. ...
0answers
41 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 ...
0answers
25 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 $<$ ...
0answers
19 views

0answers
22 views

0answers
39 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\}^*$ ...
2answers
30 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 ...
1answer
57 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 ...
2answers
68 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 ...
1answer
42 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 ...
1answer
73 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 ...
1answer
72 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 ...
2answers
103 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 ...
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$ ...
2answers
48 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 ...
3answers
84 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 \; \...
3answers
115 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 ...
2answers
82 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 ...
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 ...
3answers
65 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 ...
0answers
88 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 ...
0answers
85 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 ...
3answers
93 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 ...
1answer
104 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 ...