Skip to main content

Questions tagged [model-theory]

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 languages. Not to be confused with mathematical modeling.

Filter by
Sorted by
Tagged with
7 votes
3 answers
1k views

How to verify satisfialibility in a model? (Confusions with Gödel's Completeness Theorem)

I just cannot believe that Gödel's Completeness Theorem is right. Let say we fixed some first order logic with some structure. Theorem claims that for any sentence $P$ in this logic we have that $$\...
Fallen Apart's user avatar
  • 3,815
20 votes
5 answers
9k 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$, ...
yunone's user avatar
  • 22.4k
5 votes
2 answers
2k views

Clarifying the definition of an axiomatic system

I'm a really beginner in Mathematical Logic.I'm currently reading Shoenfield Mathematical's Logic and i'm having a hard time trying to relate the concept of Formal Systems with the concept of Axiom ...
nerdy's user avatar
  • 3,308
20 votes
7 answers
6k views

In what sense of "structure" do group homomorphisms "preserve structure"?

It is commonly said that group homomorphisms "preserve the structure of the group", e.g., from Wikipedia: The purpose of defining a group homomorphism as it is, is to create functions that preserve ...
Dennis's user avatar
  • 2,527
4 votes
1 answer
2k views

Connection between interpretation, variable assignment and truth valuation.

Let us have some formal language $\mathcal{L}$ and an $\mathcal{L}$-structure $\mathcal{U}=(A,\mathcal{I})$. Where $A$ - non-empty set, called domain, and $\mathcal{I}$ - interpretation. I know that ...
Sergey Dylda's user avatar
4 votes
1 answer
697 views

Model of concatenation theory with left-cancellation but no right-cancellation

The theory of concatenation (TC) can be equivalently expressed as the following assumptions: Closure of strings under concatenation $+$. Existence of an empty string $e$, namely $e+x = x = x+e$ for ...
user21820's user avatar
  • 58.2k
8 votes
2 answers
932 views

What axioms need to be added to second-order ZFC before it has a unique model (up to isomorphism)?

What axioms need to be added to ZFC2 (second-order ZFC) before the theory has a unique model (up to isomorphism)? I was thinking: adjoin the generalized continuum hypothesis (GCH) and a statement ...
goblin GONE's user avatar
  • 67.9k
30 votes
1 answer
4k 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 ...
Hans-Peter Stricker's user avatar
29 votes
4 answers
5k views

How can there be genuine models of set theory?

I know that this a beginner's question asked too many times, but I still didn't get an answer which lets me quit asking: Given that a model/interpretation of a theory (in the Tarskian sense) is a ...
Hans-Peter Stricker's user avatar
24 votes
5 answers
8k 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 (...
user avatar
27 votes
3 answers
4k views

Is the compactness theorem (from mathematical logic) equivalent to the Axiom of Choice?

Or more importantly, is it independent of the axiom of choice. The compactness theorem states the given a set of sentences $T$ in a first order Language $L, T$ has a model iff every finite subset of $...
Mr X's user avatar
  • 907
18 votes
2 answers
6k views

Is there a bijection between the reals and naturals?

I found this pop math article saying that there was a paper published last year that proved that the cardinalities of the reals and naturals are equal. Is this true or is it a misinterpretation of the ...
Eben Kadile's user avatar
28 votes
10 answers
6k views

Learning Model Theory

What books/notes should one read to learn model theory? As I do not have much background in logic it would be ideal if such a reference does not assume much background in logic. Also, as I am ...
Eugene's user avatar
  • 7,642
17 votes
1 answer
710 views

Is this a characterization of well-orders?

While grading some papers and thinking about a question related to well-orders (in particular, pointing a mistake in a solution), I came to think of a reasonable characterization for well-orders. I ...
Asaf Karagila's user avatar
  • 395k
5 votes
2 answers
309 views

Indiscernible to create descending chain of elementary models

Let $M$ an infinite structure such that $\mid M \mid \ge \mid L(M) \mid $. Show that exists a proper elementary extension $N$ and a chain $\langle N_{i} \mid i < \omega \rangle $ such that $$N=N_{0}...
Jhon Jairo's user avatar
  • 1,031
5 votes
2 answers
709 views

Compactness and axiomatisability

Let $C$ be an axiomatisable class of structures for some given first-order signature, i.e. there is a set $T$ of sentences whose models are exactly the members of $C$. Apparently it follows from the ...
akkarin's user avatar
  • 1,293
28 votes
3 answers
8k views

What is an example of a non standard model of Peano Arithmetic?

According to here, there is the "standard" model of Peano Arithmetic. This is defined as $0,1,2,...$ in the usual sense. What would be an example of a nonstandard model of Peano Arithmetic? What would ...
user avatar
28 votes
1 answer
4k 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 $\...
Hans-Peter Stricker's user avatar
19 votes
4 answers
3k views

How can we know we're not accidentally talking about non-standard integers?

This question is mostly from pure curiosity. We know that any formal system cannot completely pin down the natural numbers. So regardless of whether we're reasoning in PA or ZFC or something else, ...
N. Virgo's user avatar
  • 7,242
19 votes
5 answers
4k views

Most astonishing applications of compactness theorem outside logic

The compactness theorem has a lot of applications to logic and model theory. I'm looking for applications. I'm looking for theorems in other areas of mathematics which seem at first sight to have ...
Dominik's user avatar
  • 14.4k
9 votes
1 answer
717 views

Is an interpretation just a homomorphism between theories?

I don't understand model theory, but I think I've read enough about it that I can pretend to by parroting the language of model theorists. So instead of asking "how does model theory work," I'm going ...
R. Burton's user avatar
  • 4,992
9 votes
2 answers
1k views

Number of Non-isomorphic models of Set Theory

Assume that the meta theory allows for model theoretic techniques and handling infinite sets etc (The meta theory itself is, informally, "strong as ZFC"). Also assume that I'm studying ZFC inside this ...
UserB1234's user avatar
  • 2,208
7 votes
1 answer
2k views

$2\mathbb Z$ is not a definable set in the structure $(\mathbb Z, 0, S,<)$

This is (a translation of) an excerpt from a model theory textbook that shows that $2\mathbb Z$ is not a definable set in the structure $(\mathbb Z, 0, S, <)$, where $S$ is the successor function. ...
Pteromys's user avatar
  • 7,250
6 votes
1 answer
2k views

Confusion over the definition of "model"

In my question yesterday I asked about the definition and usage of the word "model", for which I was told the following definition: A formula of propositional logic is true under an interpretation ...
user525966's user avatar
  • 5,641
2 votes
3 answers
451 views

Why are $\vdash$ and $\vDash$ symbols from metalanguage?

I've read in some textbooks that $\vdash$ and $\vDash$ are symbols present only in metalanguage. From this, I infer that their use in object language is unacceptable. I would like to know why. Can't ...
Incognito's user avatar
  • 1,195
37 votes
6 answers
2k views

What is an efficient nesting of mathematical theorems?

Various mathematical areas of research evolved from a wide and diverse range of questions. Many are physical in nature or come from informatics/computer science, some are procedural or optimization ...
Nikolaj-K's user avatar
  • 12.3k
32 votes
4 answers
5k views

Tarski's decidability proof on real closed field and Peano arithmetic

It seems very confusing that real closed field (which also can be used as the theory of real number) is decidable, while Peano arithmetic, which seems to be a subset of real closed field is ...
user1894's user avatar
  • 669
30 votes
1 answer
3k views

Does there exist any uncountable group , every proper subgroup of which is countable?

Does there exist an uncountable group , every proper subgroup of which is countable ?
user avatar
18 votes
1 answer
585 views

The complexity of finiteness

Say that a second-order sentence in the empty language, $\varphi$, characterizes finiteness iff for every set $X$ we have $X\models\varphi$ iff $X$ is finite. I'm interested in the optimal complexity ...
Noah Schweber's user avatar
17 votes
3 answers
1k views

Fraïssé limits and groups

I was recently reading up on Fraïssé limits in Hodges' "A shorter model theory." I was trying to think of some examples and wanted to see if I could take the Fraïssé limit on the category of finite ...
CWcx's user avatar
  • 608
12 votes
2 answers
615 views

Dedekind completion of ordered fields

Let $\mathbb S$ be an ordered field of cardinality larger than $\mathbb R$. Let $\mathbb S^*$ be the completion of $\mathbb S$ via Dedekind cuts. Now it is well-known that $\mathbb R$ is the unique ...
mbsq's user avatar
  • 2,049
11 votes
3 answers
853 views

Confusion of the decidability of $(N,s)$

In some context the PA has only the successor operator $'s'$, but in logic we always refer the structure of PA is $(\mathbb{N},0,1,s,+,\times)$. I believed the theory of the two sturctures are ...
Chao Chen's user avatar
  • 762
11 votes
3 answers
1k views

Uniqueness of hyperreals contructed via ultrapowers

The construction I've seen of the field of hyperreal numbers considers a non-principal ultrafilter $\mathcal{U}$ on $\mathbb{N}$, then takes the quotient of $\mathbb{R}^{\mathbb{N}}$ by equivalence ...
LCL's user avatar
  • 1,185
10 votes
2 answers
2k views

How is "interpretation" used differently in propositional vs. first-order logic?

I am confused on the usage of the word "interpretation" and/or "model" when it comes to propositional logic versus first-order logic because there are so many conflicting / unclear notions that I ...
user525966's user avatar
  • 5,641
9 votes
2 answers
1k views

Why continuum hypothesis implies the unique hyperreal system, ${}^{\ast}{\Bbb R}$?

On page 33, Robert Goldblatt, Lectures on Hyperreals(1998): Now it has been shown under certain set-theoretic assumption called continuum hypothesis the choice of $\mathcal F$ is irrelevant: All ...
Metta World Peace's user avatar
9 votes
2 answers
1k views

Henkin vs. "Full" Semantics for Second-order Logic and Multi-Sorted First Order Interpretations

In this paper by Jeff Ketland, he notes: With Henkin semantics, the Completeness, Compactness and Löwenheim-Skolem Theorems all hold, because Henkin structures can be re-interpreted as many-sorted ...
Dennis's user avatar
  • 2,527
8 votes
1 answer
998 views

Does the existence of a $\mathbb{Q}$-basis for $\mathbb{R}$ imply that choice holds up to $\frak c$?

The axiom of choice is, for ZF, equivalent to the statement that every vector space has a basis. The implication of AoC by the existence of a basis for any vector space is shown in this paper. The ...
Desiato's user avatar
  • 1,610
8 votes
2 answers
817 views

Why is quantifier elimination desirable for a given theory?

We say that a given theory $T$ admits QE in a language $\mathcal{L}$ if for every $\mathcal{L}$-formula, there is an equivalent quantifier free $\mathcal{L}$-formula. That is for every $\mathcal{L}$-...
quanticbolt's user avatar
  • 1,766
7 votes
1 answer
582 views

Can't EF game theory be applied to finite languages WITH function symbols?

Let $\mathcal{M}$ and $\mathcal{N}$ be two structures in a language $\mathcal{L}$. We define the finite determined game $G_n(\mathcal{M},\mathcal{N})$ as a game with $n$ rounds where in each round ...
Anguepa's user avatar
  • 3,129
6 votes
1 answer
956 views

Are the standard natural numbers an outstanding model of PA?

Is the model $\mathcal N$ of the standard natural numbers in any way outstanding from all the possible (non-standard) models of PA? For example, might it be that $\mathcal N$ is some kind of a minimal ...
M. Winter's user avatar
  • 30.1k
5 votes
2 answers
379 views

Is "tautology" a syntactical notion?

I was reading Jerome Keisler's Model Theory and I have found the following characterization of tautology. He first defines what makes a formula valid and points out it could be very difficult to find ...
Calado's user avatar
  • 53
3 votes
1 answer
152 views

Understanding why $V^B$ is full

In Chapter 14 of Jech's Set Theory, he introduces the notion of the Boolean-valued model $V^B$ where $B$ is a complete Boolean algebra (see here for the definition of a Boolean algebra, and ...
Connor Gordon's user avatar
3 votes
1 answer
219 views

A proper pseudo-elementary class whose complement is an elementary class

Fix a first-order signature $L$. Is there a class of $L$-structures $K$ which is a pseudo-elementary class but not an elementary class, whose complement $K'$ is an elementary class?
user107952's user avatar
  • 20.9k
2 votes
2 answers
1k views

Proof- vs. model-theoretic definitions of extension and of conservative extension

Let $L_0, L_1$ be first-order languages, such that $L_0$'s signature is a subset of $L_1$'s signature, in the sense that, for all $n\in\{0,1,2,\dots\}$: every $n$-ary function/predicate of $L_0$ is ...
Evan Aad's user avatar
  • 11.5k
1 vote
1 answer
158 views

What is an explicit axiomatization of the complex field along with the real numbers?

Consider the structure $(\mathbb{C};+,-,*,0,1,R)$ where $R$ is a predicate that picks out the real numbers. I would be very interested in an explicit axiomatization of the complete theory of that ...
user107952's user avatar
  • 20.9k
1 vote
2 answers
802 views

How to finish proof that $T$ has an infinite model?

I'm trying to prove the following: If $T$ is a first-order theory with the property that for every natural number $n$ there is a natural number $m>n$ such that $T$ has an $m$-element model then $T$ ...
Rudy the Reindeer's user avatar
0 votes
1 answer
236 views

Represent the definition of elementary substructure in FOL

I know the definition of elementary substructure $\mathcal{M} \prec \mathcal{N}$, when $M$ and $N$ are two structure of a language $\mathcal{L}$. My doubt is how to represent the relation $\mathcal{M} ...
Minghui Ouyang's user avatar
36 votes
5 answers
2k views

Is $\mathbb{N}$ impossible to pin down?

I don't know if this is appropriate for math.stackexchange, or whether philosophy.stackexchange would have been a better bet, but I'll post it here because the content is somewhat technical. In ZFC, ...
goblin GONE's user avatar
  • 67.9k
30 votes
3 answers
3k views

Applications of model theory to analysis

Some of the more organic theories considered in model theory (other than set theory, which, from what I've seen, seems to be quite distinct from "mainstream" model theory) are those which arise from ...
tomasz's user avatar
  • 35.7k
29 votes
2 answers
1k 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 for ...
Michaël Cadilhac's user avatar

1
2 3 4 5
14