# Questions tagged [model-theory]

Model theory is the branch of mathematical logic which deals with the connection between a formal language and its interpretations, or models.

1,219
questions

2
votes

0
answers

107
views

### Inevitable consistency strength, take 2

This is an attempt to repair this old question of mine.
Say that a good candidate is a first-order sentence $\varphi$ in a language $\{<,...\}$ containing a distinguished binary relation symbol $&...

7
votes

0
answers

140
views

### Which sentences are "strategically preserved"?

Below, everything is first-order.
Say that a sentence $\varphi$ is strategically preserved iff player 2 has a winning strategy in the following game:
Players 1 and 2 alternately build a sequence of ...

1
vote

0
answers

180
views

### Is there a computable model of HoTT?

Among the various models of homotopy type theory (simplicial sets, cubical sets, etc.), is there a computable one?
Can the negative follow from the Gödel-Rosser incompleteness theorem?
If there is no ...

16
votes

6
answers

1k
views

### Book recommendation introduction to model theory

Next semester I will be teaching model theory to master students. The course is designed to be "soft", with no ambition of getting to the very hardcore stuff. Currently, this is the syllabus....

4
votes

0
answers

99
views

### Is there an abstract logic satisfying the Löwenhein-Skolem property for single sentences but not for countable sets of sentences?

An abstract logic satisfies the LS property for single sentences if each satisfiable sentence has a countable model. Similarly, the LS property for countable sets of sentences holds if every ...

5
votes

1
answer

187
views

### What is the theory of computably saturated models of ZFC with an *externally well-founded* predicate?

For any model of $M$ of ZFC, we can extend it to a model $M_{ew}$ with an "externally well-founded" predicate $ew$. For $x \in M$, We say that $M_{ew} \vDash ew(x)$ when there is no infinite ...

1
vote

0
answers

92
views

### Effortless automated proofs for "simple" formulae?

From small cases to all of them. This is in the spirit of 15 theorem see https://en.wikipedia.org/wiki/15_and_290_theorems
EXAMPLE : Suppose you have the following problem: P(a)
For any fixed non ...

7
votes

1
answer

163
views

### Is Presburger arithmetic in stronger logics still complete?

Originally asked at MSE:
Let $\Sigma=\{+,<,0,1\}$ be the usual language of Presburger arithmetic. Given a "reasonable" logic $\mathcal{L}$, let $\mathbb{Pres}(\mathcal{L})$ be the $\...

3
votes

0
answers

118
views

### Comparing two fragments of SOL with the downward Lowenheim-Skolem property

For $S$ a set of (parameter-free) second-order formulas and $\mathfrak{A},\mathfrak{B}$ structures, write $\mathfrak{A}\trianglelefteq^S\mathfrak{B}$ iff $\mathfrak{A}$ is a substructure of $\mathfrak{...

4
votes

1
answer

172
views

### Can we have external automorphisms over intersectional models?

Is the following inconsistent:
By "intersectional" set I mean a set having the intersectional set of every nonempty subset of it, being an element of it.
$\forall S \subset M: S\neq \...

4
votes

0
answers

159
views

### In finite model theory, is "invariant FOL with $\varepsilon$-operator" unavoidably second-order?

Throughout, all structures are finite.
Say that a class of finite structures $\mathbb{K}$ is $\mathsf{FOL}_\varepsilon^\text{inv}$-elementary iff it is the class of finite models of a sentence in the ...

1
vote

1
answer

546
views

### Natural Numbers

Let $L$ be a countable language and $M$ be a model of $L^N$ (the realization of $L$ in the natural numbers $N$) in which every recursive unary relation is expressible. Show that $M$ is not recursive.

13
votes

1
answer

2k
views

### Are some interesting mathematical statements minimal?

Gödel's set $\mathrm{L}$, of constructible sets, decides many interesting mathematical statements, as the Continuum hypothesis and the Axiom of Choice.
Are some interesting mathematical questions, ...

5
votes

1
answer

515
views

### The "first-order theory of the second-order theory of $\mathrm{ZFC}$"

$\newcommand\ZFC{\mathrm{ZFC}}\DeclareMathOperator\Con{Con}$It is often interesting to look at the theory of all first-order statements that are true in some second-order theory, giving us things like ...

4
votes

1
answer

322
views

### Expressiveness in arithmetic

Let $\mathcal{S}$ be a formal system for arithmetic (e.g. $P$ or $PA$), $f:N^q\rightarrow N^p$ a function of $N^q$ on $N^ p$ and $\alpha(\mathbf{x})$ a formula of $\mathcal{S}$ with $p$ free variables....

10
votes

1
answer

196
views

### Is $(\mathbb R_{\mathrm{an}}, (x\mapsto x^r)_{r\in\mathbb R})$ still the largest known polynomially bounded o-minimal structure so far?

From Chris Miller's paper in 1995, the structure $(\mathbb R_{\mathrm{an}}, (x\mapsto x^r)_{r\in\mathbb R})$,is the largest known polynomially bounded o-minimal structure as of that time. I wonder if ...

8
votes

0
answers

127
views

### What is this quotient of the free product?

Previously asked at MSE. The construction here can generalize to arbitrary algebras (in the sense of universal algebra) in the same signature with the only needed tweak being the replacement of "...

21
votes

1
answer

1k
views

### Are the real numbers isomorphic to a nontrivial ultraproduct of fields?

Let $K_1, K_2, \dots$ be a countable sequence of fields, and let $\prod_{\mathcal F} K_i$ be the ultraproduct with respect to some nonprincipal ultrafilter $\mathcal F$.
Question: Can there be a field ...

1
vote

0
answers

67
views

### Finitely presentable groups are residually finite if and only if they are universally pseudofinite

Suppose $G$ is finitely presentable. Then residual finiteness of $G$ is equivalent to $G$ satisfying the universal theory of finite groups (equivalently, to every existential statement true in $G$ ...

6
votes

0
answers

222
views

### Do maximal compact logics exist?

By "logic" I mean regular logic in the sense of abstract model theory (see e.g. the last section of Ebbinghaus/Flum/Thomas' book). My question is simple:
Is there a logic $\mathcal{L}$ ...

1
vote

1
answer

186
views

### Gödel coding and the function $z(x)$

The function $z(x)$ that associates to each formula $\alpha$ of $P$ its Gödel number $z(\alpha)$ is external to the system. How then can expressions in which $z(x)$ be involved be expressed in $P$? ...

1
vote

0
answers

200
views

### Interpretation of model theory in algebraic geometry

I found a paper Some applications of a model theoretic fact to (semi-) algebraic geometry by Lou van den Dries. In this paper, the author uses model theoretical methods to prove the completeness of ...

9
votes

2
answers

1k
views

### Truth in a different universe of sets?

I understand that provability and truth as different concepts.
Provability is syntactic, it only concerns whether the given
sentence can be derived by reiterating the inference rules over a
collection ...

0
votes

0
answers

126
views

### Provability predicates

We know that there are provability predicates, that is, predicates derived from the recursive relation "x is a demonstration of y", with which Godel's second incompleteness theorem would not ...

4
votes

0
answers

281
views

### Which countable sets don't drastically change the definable topologies on $\mathbb{R}$?

For $\mathcal{M}$ an expansion of $\mathcal{R}=(\mathbb{R};+,\times)$ and $A\subseteq\mathbb{R}$, let $\tau^\mathcal{M}_A$ be the topology on $\mathbb{R}$ generated by the sets definable in $\mathcal{...

11
votes

1
answer

651
views

### On the classification of second-countable Stone spaces

Let $X$ be a Stone space (i.e. totally disconnected compact Hausdorff). Then the following are equivalent:
$X$ is second countable
$X$ is metrizable
$X$ has countably many clopen subsets
$X$ is an ...

4
votes

1
answer

474
views

### Truth Values of Statements in non-standard models

Excuse me, if the question sounds too naive.
Non-standard models of PA will have statements of non-standard lengths, basically infinite. And it is also true that every statement of a theory will have ...

3
votes

0
answers

139
views

### Lindström's theorem part 2 for non-relativizing logics

By "logic" I mean the definition gotten by removing the relativization property from "regular logic" — see e.g. Ebbinghaus/Flum/Thomas — and adding the condition that for every ...

8
votes

1
answer

1k
views

### Worst of both worlds?

It's well known that $\mathsf{AC}$ implies the existence of non-measurable sets. And it's also true that, if all sets are measurable, then $|\mathbb{R}/\mathbb{Q}| > |\mathbb{R}|$. But is there a ...

0
votes

0
answers

103
views

### Can a definable group of definable automorphisms of a field contain the Frobenius automorphism?

Let $K$ be an infinite definable field of characteristic $p >0$ in a certain theory $T$ with a definable group of definable automorphisms. Can this group contain the Frobenius automorphism?

2
votes

0
answers

493
views

### Gödel's second incompleteness theorem [closed]

Apparently, see Feferman or Wikipedia, in a consistent system there are formulations of consistency that are demonstrable in the system itself while others are not. What distinguishes one from another?...

6
votes

1
answer

308
views

### Original motivations of Fraïssé's amalgamation construction

Roland Fraïssé introduced in the 50's his famous construction of Fraïssé limits, and then Ehud Hrushowski modified it in the early 90's to construct new structures.
The motivations for the latter was ...

11
votes

1
answer

435
views

### Are flat functors out of a finite category necessarily finite?

Note: I've originally asked this question on math stack exchange, but I have learnt that this is the better place to ask for research level questions, so I have deleted the original question there.
...

3
votes

1
answer

98
views

### Is the filter generated by $A$-generic sets S1-prime?

Let $\mathfrak U$ be a monster model.
Let $A\subseteq\mathfrak U$ be a small set of parameters.
A set $\mathfrak D\subseteq\mathfrak U^{|x|}$ is $A$-generic if finitely many translations of $\mathfrak ...

2
votes

1
answer

554
views

### Logical content of Gauss's Lemma (arithmetic)

In the context where $a$, $b$, $c$ are integers we have $(a \mid bc, a\land b = 1) \Rightarrow a\mid c$. This result is called Gauss's Lemma in French Highschool.
It is well known that (Steve Awodey, ...

5
votes

0
answers

216
views

### Classical first-order model theory via hyperdoctrines

I have been reading this discussion by John Baez and Michael Weiss and I find this approach to model theory using boolean hyper-doctrines very interesting. One of their goal was to arrive at a proof ...

4
votes

0
answers

149
views

### Can this theory of dyadic rationals prove that multiplying by three is the same as summing thrice?

(This question arose from a discussion with Jade Vanadium about a theory of dyadic rationals.)
Let $T$ be the 2-sorted FOL theory with sorts $ℕ,ℚ$ and constant-symbols $0,1$ and binary function-...

1
vote

1
answer

213
views

### Seeking clarification of ultrapower nonstandard model of arithmetic

I've read that one nonstandard model of arithmetic is:
take $\mathbb{N}^\mathbb{N}$, the set of countably infinite sequences of natural numbers
take a quotent that gives the ultrapower: identify ...

4
votes

1
answer

201
views

### If a theory has many mutually non-embeddable countable models can it have a countable $\omega$-saturated model?

A theory can have $2^\omega$-many non-isomorphic countable models but has a countable $\omega$-saturated model. (https://math.stackexchange.com/questions/305602/if-a-theory-has-a-countable-omega-...

12
votes

1
answer

3k
views

### Is there a "halting machine" which halts on itself?

The crux of the halting problem is that there can be no Turing machine $M$ such that $\text{Halt}(M(N))=\neg \text{Halt}(N(N))$ for all Turing machines $N$, since $\text{Halt}(M(M))=\neg \text{Halt}(M(...

2
votes

0
answers

84
views

### Do Fagin's zero-one laws hold on stochastic block model?

Let $n$ be a positive integer (the number of vertices), $k$ be a positive integer (the number of communities), $p = (p_1, . . . , p_k)$ be a probability vector on $[k] := \{1, . . . , k\}$ (the prior ...

3
votes

0
answers

166
views

### Can the set of parafinite congruences be descriptive-set-theoretically complicated?

Fix an algebra $\mathfrak{A}$ with underlying set $\mathbb{N}$ and finite language $\Sigma$. The set of congruences on $\mathfrak{A}$ is a closed subset $C_\mathfrak{A}$ of $2^\mathbb{N}$ (with the ...

1
vote

1
answer

141
views

### Congruences that aren't "finite from above," take 2: semigroups

This is a hopefully less trivial version of this question. Briefly, say that a congruence is parafinite if it is the largest congruence contained in some equivalence relation with finitely many ...

5
votes

3
answers

531
views

### Congruences that aren't "finite from above"

Let $\mathfrak{A}=(A;...)$ be an algebra in the sense of universal algebra. Say that a congruence $\sim$ on $\mathfrak{A}$ is parafinite iff there is an equivalence relation $E\subseteq A^2$ with ...

7
votes

1
answer

250
views

### Is the Rado graph the unique countable graph that has all finite graphs as induced subgraphs?

I understand that since the Rado graph is the Fraïsse limit of the class of finite graphs, it is the unique homogeneous graph with this property. Is there another graph not isomorphic to the Rado ...

6
votes

0
answers

162
views

### Elementary equivalence for rings

Let $\mathcal{L}$ be a first-order language, and $M$ and $N$ be two $\mathcal{L}$-structures. We say that $M$ and $N$ are elementarily equivalent (write $M \approx N$) if they satisfy the same first-...

3
votes

1
answer

138
views

### Posets of equational theories of "bad quotients"

This is a follow-up to an older question of mine:
Suppose $\mathfrak{A}=(A;...)$ is an algebra (in the sense of universal algebra) and $E$ is an equivalence relation - not necessarily a congruence - ...

8
votes

1
answer

608
views

### Concept of bedrock and mantle in the multiverse view in the philosophy of mathematics

To be clear, I am not a mathematics educated student and I can not follow the details of the technicality of the forcing extension, but I feel that I have a good understanding of the big picture (of ...

3
votes

1
answer

225
views

### Is Morse-Kelley set theory with Class Choice bi-interpretable with itself after removing Extensionality for classes?

Let $\sf MKCC$ stand for Morse-Kelley set theory with Class Choice. And let this theory be precisely $\sf MK$ with a binary primitive symbol $\prec$ added to its language, and the following axioms ...

1
vote

1
answer

236
views

### "On models of elementary elliptic geometry"

While perusing p. 237 of the 3rd ed. of Marvin Greenberg's book on Euclidean and non-Euclidean geometries, I learned that it can actually be proven that "all possible models of hyperbolic ...