Skip to main content

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.

Filter by
Sorted by
Tagged with
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 $&...
Noah Schweber's user avatar
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 ...
Noah Schweber's user avatar
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 ...
richardIII's user avatar
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....
Ivan Di Liberti's user avatar
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 ...
Rodrigo Freire's user avatar
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 ...
Christopher King's user avatar
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 ...
Jérôme JEAN-CHARLES's user avatar
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 $\...
Noah Schweber's user avatar
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{...
Noah Schweber's user avatar
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 \...
Zuhair Al-Johar's user avatar
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 ...
Noah Schweber's user avatar
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.
Speltzu's user avatar
  • 265
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, ...
Frode Alfson Bjørdal's user avatar
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 ...
Mike Battaglia's user avatar
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....
Speltzu's user avatar
  • 265
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 ...
user506835's user avatar
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 "...
Noah Schweber's user avatar
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 ...
Tim Campion's user avatar
  • 62.3k
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$ ...
tomasz's user avatar
  • 1,238
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}$ ...
Noah Schweber's user avatar
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$? ...
Speltzu's user avatar
  • 265
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 ...
George's user avatar
  • 241
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 ...
Student's user avatar
  • 5,038
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 ...
Speltzu's user avatar
  • 265
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{...
Noah Schweber's user avatar
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 ...
Tim Campion's user avatar
  • 62.3k
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 ...
Amiren's user avatar
  • 1
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 ...
Noah Schweber's user avatar
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 ...
Zemyla's user avatar
  • 309
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?
Invictus's user avatar
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?...
Speltzu's user avatar
  • 265
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 ...
huurd's user avatar
  • 1,005
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. ...
Lingyuan Ye's user avatar
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 ...
Domenico Zambella's user avatar
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, ...
smed's user avatar
  • 29
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 ...
Antoine Labelle's user avatar
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-...
user21820's user avatar
  • 2,750
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 ...
Dave Pritchard's user avatar
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-...
LYS's user avatar
  • 105
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(...
Milo Moses's user avatar
  • 2,837
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 ...
SagarM's user avatar
  • 131
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 ...
Noah Schweber's user avatar
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 ...
Noah Schweber's user avatar
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 ...
Noah Schweber's user avatar
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 ...
Vilhelm Agdur's user avatar
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-...
jg1896's user avatar
  • 3,084
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 - ...
Noah Schweber's user avatar
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 ...
Arian's user avatar
  • 183
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 ...
Zuhair Al-Johar's user avatar
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 ...
José Hdz. Stgo.'s user avatar

1
2 3 4 5
25