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
226 votes
2 answers
8k views

Is there a 0-1 law for the theory of groups?

For each first order sentence $\phi$ in the language of groups, define : $$p_N(\phi)=\frac{\text{number of nonisomorphic groups $G$ of order} \le N\text{ such that } \phi \text{ is valid in } G}{\...
Dominik's user avatar
  • 14.4k
83 votes
0 answers
2k views

Complete, Finitely Axiomatizable, Theory with 3 Countable Models

Does there exist a complete, finitely axiomatizable, first-order theory $T$ with exactly 3 countable non-isomorphic models? A few relevant comments: There is a classical example of a complete theory ...
Primo Petri's user avatar
  • 5,194
57 votes
8 answers
7k 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 ...
Lurco's user avatar
  • 1,240
53 votes
5 answers
9k views

I don't understand Gödel's incompleteness theorem anymore

Here's the picture I have in my head of Model Theory: a theory is an axiomatic system, so it allows proving some statements that apply to all models consistent with the theory a model is a particular ...
Abhimanyu Pallavi Sudhir's user avatar
51 votes
5 answers
44k views

In plain language, what's the difference between two things that are 'equivalent', 'equal', and 'identical'?

In plain language, what's the difference between two things that are 'equivalent', 'equal', 'identical', and isomorphic? If the answer depends on the area of mathematics, then please take the ...
Hal's user avatar
  • 3,426
45 votes
3 answers
2k views

Distinguishing non-isomorphic groups with a group-theoretic property

I am teaching a first-semester course in abstract algebra, and we are discussing group isomorphisms. In order to prove that two group are not isomorphic, I encourage the students to look for a group-...
Julian Rosen's user avatar
  • 16.2k
39 votes
7 answers
4k views

Do the axioms of set theory actually define the notion of a set?

In Henning Makholm's answer to the question, When does the set enter set theory?, he states: In axiomatic set theory, the axioms themselves are the definition of the notion of a set: A set is ...
justin's user avatar
  • 4,781
38 votes
1 answer
1k views

Does any uncountable complete theory have exactly two countable models?

The following is a theorem by Vaught. Theorem. Let $T$ be a complete theory in a countable language. Then, $T$ cannot have exactly two countably infinite models (up to isomorphism). A proof can ...
ll_n's user avatar
  • 657
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
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
34 votes
2 answers
1k views

Is $ \pi $ definable in $(\Bbb R,0,1,+,×, <,\exp) $?

Is there a first-order formula $\phi(x) $ with exactly one free variable $ x $ in the language of ordered fields together with the unary function symbol $ \exp $ such that in the standard ...
Dominik's user avatar
  • 14.4k
34 votes
3 answers
2k views

Murder at Hilbert's Hotel! A study of the testimony of infinitely many suspects.

I'm sorry if this is a duplicate in any way. I doubt it's an original question. Due to my ignorance, it's difficult for me to search for appropriate things. Motivation. This question is inspired by ...
Shaun's user avatar
  • 45.5k
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
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
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
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
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
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
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
3 answers
2k views

Is there a *simple* example of how the axiom of choice can lead to a counterintuitive result?

This question is quite subjective, but here goes: The axiom of choice notoriously leads to many extremely counterintuitive results, like the Hausdorff, Von Neumann, and (most famously) Banach-Tarski ...
tparker's user avatar
  • 6,240
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
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
28 votes
1 answer
2k views

Is there a natural model of Peano Arithmetic where Goodstein's theorem fails?

Goodstein's Theorem is the statement that every Goodstein sequence eventually hits 0. It is known to be independent of Peano Arithemtic (PA), and in fact, was the first such purely number theoretic ...
Jason DeVito - on hiatus's 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
26 votes
4 answers
5k views

How does Gödel Completeness fail in second-order logic?

So a while ago I saw a proof of the Completeness Theorem, and the hard part of it (all logically valid formulae have a proof) went thusly: Take a theory $K$ as your base theory. Suppose $\varphi$ ...
Red's user avatar
  • 950
26 votes
1 answer
555 views

Subgroups defined by negative formulas

I start with a simple problem that I was able to solve: Let $G$ be a group. Let $a\in G$. Assume that $H := \{g \in G : g^2 \neq a\}$ is a subgroup of $G$. The question: Can we define $H$ with a "...
Ali Nesin's user avatar
  • 597
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
24 votes
2 answers
3k views

Are there number systems corresponding to higher cardinalities than the real numbers?

As most of you know, the set $\omega$ with cardinality $\aleph_0$ corresponds to what we normally know as the natural numbers $\mathbb{N}$, and the set $\mathcal{P}(\omega)$ with cardinality $\aleph_1$...
mrp's user avatar
  • 5,106
24 votes
1 answer
1k views

Is $\Bbb R$ definable in $(\Bbb C,0,1,+,*,\exp)$?

Is there a first-order formula ϕ(x) with exactly one free variable $x$ in the language of fields together with the unary function symbol $\exp$ such that in the standard interpretation of this ...
Dominik's user avatar
  • 14.4k
24 votes
1 answer
453 views

Relations that ensure continuity

We say that a function $f: \mathbb{R} \rightarrow \mathbb{R}$ preserves the binary relation $\sim \subseteq \mathbb{R}^2$ if $x \sim y$ implies $f(x) \sim f(y)$ for all $x,y\in\mathbb{R}$. We say that ...
Z. A. K.'s user avatar
  • 11.5k
23 votes
3 answers
767 views

Are $C([0,1])$ and $C(\mathbb{R})$ elementarily equivalent as rings?

For a topological space $X$, let $C(X)$ denote the ring of continuous functions $X\to\mathbb{R}$, equipped with pointwise addition and multiplication. This question is related to this one of Noah ...
Atticus Stonestrom's user avatar
23 votes
2 answers
2k views

Intersection of Algebraic Topology/Geometry and Model Theory/Set Theory

Is there any intersection between the ideas of Algebraic Topology/Geometry (I know that there is most certainly a non-trivial intersection between Algebraic Geometry, Algebraic Topology, Arithmetic ...
Jonathan Beardsley's user avatar
23 votes
1 answer
546 views

Identifying the finite symmetric groups

Is there a single first-order sentence $\varphi$ in the language of groups such that for every finite $\mathfrak{A}$ we have $$\mathfrak{A}\models\varphi\quad\iff\quad\mathfrak{A}\cong S_n\mbox{ for ...
Noah Schweber's user avatar
23 votes
1 answer
1k views

Model existence for infinitary logics

One of the problems of infinitary logic is that it is possible for compactness to fail in a spectacular way: for example, one can concoct an inconsistent set of axioms whose proper subsets are all ...
Zhen Lin's user avatar
  • 90.5k
22 votes
4 answers
3k views

Why can't we prove consistency of ZFC like we can for PA?

this might be a silly question, but I was wondering: PA cannot prove its consistency by the incompleteness theorems, but we can "step outside" and exhibit a model of it, namely $\mathbb{N}$, so we ...
K. 622's user avatar
  • 923
22 votes
1 answer
588 views

What kind of compactness does "expanding $\mathbb{R}$ by constants" have?

EDIT: Now crossposted at mathoverflow. This arose from my answer to another question. Say that a theory $T$ in the language of ordered fields + constants is $\mathbb{R}$-satisfiable if it has a model ...
Noah Schweber's user avatar
21 votes
2 answers
2k views

Expressing associativity with only two variables

I'm wondering if it is possible to axiomatize associativity using a set of equations in only two variables. Suppose we have a signature consisting of one binary operation $\cdot$. Is it possible to ...
Tom's user avatar
  • 1,158
21 votes
2 answers
1k views

Comparing countable models of ZFC

Let us consider the class $\cal C$ of countable models of ZFC. For ${\mathfrak A}=(A,{\in}_A)$ and ${\mathfrak B}=(B,{\in}_B)$ in $\cal C$ I say that ${\mathfrak A}<{\mathfrak B}$ iff there is a ...
Ewan Delanoy's user avatar
  • 61.6k
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
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
20 votes
2 answers
6k views

What is Model Theory

I've been reading up on some Model Theory lately. My question is simple. What is the purpose of the theory to begin with? How does it enrich mathematics? A-priori, it doesn't seem like we're doing ...
Joe Shmo's user avatar
  • 977
20 votes
2 answers
1k views

Has a conjecture ever originally been decided by constructing the proof with mathematical logic?

So, one of the things that mathematical logic does is study theorems as abstract objects. There also many theorems about mathematical logic, and these theorems can have connections to other fields. ...
Christopher King's user avatar
20 votes
2 answers
2k views

What is the definition of a definition?

In mathematical logic or other formal systems, what is the definition of a definition, formally? If "A" is defined as "B", what is the definition of "A" like? Does it ...
Tim's user avatar
  • 47.6k
20 votes
1 answer
1k views

Non-axiomatisability and ultraproducts

Let $T$ be a first-order theory over a language $L$, and let $\mathcal{M}$ be a subclass of the class of models of $T$. As I understand it, if there is no theory $\hat{T}$ over $L$ whose class of ...
Zhen Lin's user avatar
  • 90.5k
19 votes
7 answers
4k views

Does a finite first-order theory which has a model always have a finite model?

I'm curious whether this is true or not: Let T be a finite, first-order theory. If T has a model, then T has a finite model. I would assume the answer is 'yes', but I wanted to make sure I haven't ...
Koz Ross's user avatar
  • 315
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
19 votes
2 answers
1k views

Can Russell's paradox, Halting problem and Godel's Incompleteness theorem be generalized?

All these three theorems (I am not 100% sure about the third, but I have heard it has a similar argument with the other two) use self-referentiability as contradiction and they talk about the ...
Cezar98's user avatar
  • 458
19 votes
2 answers
1k views

Are there non-standard counterexamples to the Fermat Last Theorem?

This is another way to ask if Wiles's proof can be converted into a "purely number-theoretic" one. If there is no proof in Peano Arithmetic then there should be non-standard integers that satisfy the ...
Conifold's user avatar
  • 11.8k
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

1
2 3 4 5
88