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
11 votes
2 answers
422 views

Are all generalized Scott sets realized as generalized standard systems?

Below, I've focused on PA when lots of other theories would do. If replacing PA with a different theory leads to a more answerable question, feel free to do so. The standard system of a nonstandard ...
8 votes
0 answers
136 views

How strong is exponentiation with only open induction? (Or: "how low can we go?")

Do the strongest theories currently known to be unconstrained by Tennenbaum's theorem ($IOpen$ and some modest extensions) remain so when augmented with a definition of exponentiation and axiom $\...
2 votes
0 answers
92 views

Counterexamples to the definable (P,Q)-Theorem

Pierre Simon conjectured a model-theoretic definable version of Matoušek’s (p,q) -theorem in NIP theories: [Conjecture 5.1]: Let T be NIP and M⊨T . Let ϕ(x;d) ∈ L(U) a formula, non-forking over M . ...
4 votes
0 answers
107 views

What logics do the transfinite length pebble games capture?

See e.g. Libkin, Elements of finite model theory for background on the usual pebble game. Below, all languages are finite and relational, and "$\uparrow$" denotes an expression being ...
13 votes
1 answer
2k views

Elementary proof of Chevalley's Theorem on constructible sets

I am looking for a proof of the easiest affine version of Chevalley's Theorem on constructible sets : Theorem (Chevalley). The image of a constructible subset of $\mathbf C^n$ by a polynomial map $P:...
9 votes
1 answer
356 views

Various sizes of models of NBG inside NBG (what does a class-sized model give us?)

Following this question and that one illustrating how induction in NBG can be tricky, I realized I'm also confused about the notion of “model” of NBG. The goal of this confusion is to hopefully lift ...
2 votes
0 answers
189 views

Some questions about the Hyperuniverse Program

The Hyperuniverse Program, founded by Sy D. Friedman, intends to produce new second-order axioms of set theory which appropriately formalize "the universe is maximal" in one of a few ways. A ...
25 votes
6 answers
3k views

Is there a metamathematical $V$?

As with many of you, I've been following Peter Scholze's recent question about universes with great interest. In ring theory, we don't often have to deal with proper classes, but they occasionally ...
8 votes
3 answers
2k views

Russell's paradox as understood by current set theorists

Many mathematicians like to think of the set of natural numbers as existing as a completed object. But it is difficult to make set theory as concrete, because Russell's paradox, in conjunction with ...
2 votes
2 answers
334 views

dp-minimality and stability

What are some of the common popular stable theories that are known to be dp-minimal (or not dp-minimal)? Some dp-minimal examples I am aware of are strongly minimal theories, superstable theories of ...
4 votes
1 answer
259 views

Does every ordinal appearing in a model of ZF appear in a model of ZFC?

To be more precise, suppose that $M$ is a model of ZF, for simplicity (or tactility) a set in some larger model $V$ of ZFC+Con(ZF), and suppose that $M\vDash``\alpha$ is an ordinal$"$. Must there be a ...
12 votes
1 answer
444 views

What is the "iterated definability" limit of first-order logic?

Roughly speaking, given a set-sized logic $\mathcal{L}$ let $\mathcal{L}'$ be gotten by adding to $\mathcal{L}$ the ability to quantify over $\mathcal{L}$-definable relations. (The details are a bit ...
6 votes
1 answer
299 views

When can interpretations be "optimized"?

To make this more readable, I've put some definitions/conventions at the end of this question. I'm interested in when a given interpretation isn't "missing any information." Specifically, ...
9 votes
3 answers
549 views

Equational theories determined by "identities without variables"

How to characterize equational theories $T$ which have the following property: for any two terms $t(x_1,...,x_n)$ and $t'(x_1,...,x_n)$ in the signature of $T$, if for any closed terms (i. e. terms ...
0 votes
1 answer
255 views

Need proof on a model being elementarily equivalent but non-isomorphic

For countable models, elementary equivalence is not equivalent to isomorphism. For example, let $\frak{A}= \omega+\Bbb{Z}*\omega$ and $\frak{B}= \omega+\Bbb{Z}*\omega^*$ ($ω^∗$ is the reverse of $ω$)...
3 votes
0 answers
127 views

Is there an ordered algebra analogue of the HSP theorem?

For an algebraic signature (= set of function symbols) $\Sigma$, say that an ordered $\Sigma$-algebra is a pair $\mathfrak{A}=(\mathcal{A};\le)$ where $\mathcal{A}$ is a $\Sigma$-algebra in the sense ...
2 votes
0 answers
73 views

Question related to number of distinct forcing extensions of a countable model

A bit of context: the below question is motivated by roughly the following scenario: we have some countable model $\mathcal{M}$, and want to “count” the number of functions/sets $f$ such that $\...
42 votes
1 answer
2k views

Do the analogies between metamathematics of set theory and arithmetic have some deeper meaning?

By "formal analogies" between the metamathematics of $\mathsf{ZFC}$/set theory and $\mathsf{PA}$(=Peano Arithmetic)/first order arithmetic, I mean facts such as the following: We are considering a ...
38 votes
7 answers
6k views

Is V, the Universe of Sets, a fixed object?

When I first read Set Theory by Jech, I came under the impression that the Universe of Sets, $V$ was a fixed, well defined object like $\pi$ or the Klein four group. However as I have read on, I am ...
3 votes
0 answers
114 views

Does the "iterated definability" closure always fall short of standard (Boolean) infinitarization?

Given a (set-sized) logic $\mathcal{L}$, let $\mathcal{L}'$ be gotten from $\mathcal{L}$ by adding the ability to quantify over $\mathcal{L}$-definable relations. (I'm being a bit vague here, since e....
1 vote
0 answers
143 views

Is this approximation to infinitary equivalence coarse on countable structures?

This question is a kind of dual to this earlier one. Note that if we replace $\mathsf{FOL}$ with $\mathcal{L}_{\omega_1,\omega}$, things trivialize since we can use the theory $\{\varphi^A\...
8 votes
1 answer
306 views

Modal logic of "mostly-satisfiability"

For $n\in\omega+1$ let $\mathsf{ZFC}_n$ be $\mathsf{ZC}$ + $\{\Sigma_k$-$\mathsf{Rep}: k<n\}$. Let $\widehat{\mathsf{ZFC}}$ be the strongest consistent theory $\mathsf{ZFC}_n$ (so if $\mathsf{ZFC}$ ...
9 votes
1 answer
396 views

On a result by Rubin on elementary equivalence of homeomorphism groups and homeomorphisms of the underlying spaces

In the known paper On the reconstruction of topological spaces from their group of homeomorphisms by Matatyahu Rubin several deep reconstruction theorems of the form "if $X$ and $Y$ are ...
3 votes
1 answer
148 views

Is having a Frobenius pair first-order expressible in the language of groups?

I am trying to figure out whether or not the following property is first-order expressible in the language of groups. $$\text{$G$ has a subgroup $H$ with which it forms a Frobenius pair $(H,G)$.}$$ My ...
5 votes
0 answers
181 views

"Very $L$-like" models, part 1: large cardinals

(The original version of this question was much narrower and less natural; but see the edit history if interested.) Say that a good logic is a regular logic $\mathcal{L}$ containing $\mathsf{FOL}$ ...
8 votes
0 answers
238 views

First order formula describing connected components

I ask this question here after no answer came up in the original MathSE question. Let $\mathcal{L}$ be the language $\{+,-,\cdot,0,1,P\}$ where $P$ is some $n$-ary relation symbol. Is there a formula $...
3 votes
0 answers
147 views

Systems of elementary embeddings

Recently I've been thinking about elementary embeddings, partition cardinals, etc. as part of my never-ending quest for understanding of consistency strength :p I came up with this idea, called I* ...
2 votes
0 answers
75 views

Is "strongly unbounded logics are unbounded" equivalent to "no descending sequence of cardinals"?

This question is motivated by Vaananen's paper Generalized quantifiers in models of set theory. Say that a (set-sized, regular) logic $\mathcal{L}$ is unbounded if there are $\mathcal{L}$-sentences $\...
6 votes
1 answer
371 views

Poset of automorphism groups of variants of a structure

Say that two structures $\mathfrak{A},\mathfrak{B}$ in possibly different finite languages are parametrically equivalent - and write "$\mathfrak{A}\approx\mathfrak{B}$" - iff they have the ...
9 votes
2 answers
2k views

Are the models of infinitesimal analysis (philosophically) circular?

Infinitesimal analysis (by which I mean that originating from topos theory---not the nonstandard analysis of Robinson) seeks to recover the pre-limit notions of calculus (which are sufficiently useful ...
7 votes
1 answer
204 views

Does $\mathit{Aut}(\mathbb{R};+)$ have a copy in $L(\mathbb{R})$ granting large cardinals?

Throughout, work in $\mathsf{ZFC}$ + large cardinals (let's say a proper class of Woodin limits of Woodins but I'm happy to go higher if that would help). Let $\mathcal{R}=(\mathbb{R};+)$ be the ...
1 vote
1 answer
190 views

Recursively inaccessible ordinals and non locally countable ordinals

This answer seems to imply that: for an ordinal $\alpha$, to be recursively inaccessible (i.e. $\alpha$ is admissible and limit of admissible) implies to be not locally countable (i.e. $L_\alpha \...
6 votes
0 answers
146 views

Does every Tarski plane embed into a 3-dimensional Tarski space?

By a Tarski space I understand a mathematical structure $(X,B,\equiv)$ consisting of set $X$, a betweenness relation $B\subseteq X^3$ and a congruence relation ${\equiv}\subseteq X^2\times X^2$ ...
7 votes
1 answer
246 views

Complexity of infinitary satisfiability, part 2

This question is a follow-up to this one, which was almost entirely answered by Farmer S. Throughout, we work in $\mathsf{ZFC+V=L}$. Given a "pre-admissible" (= admissible or limit of ...
0 votes
1 answer
135 views

Is a right triangle with the given cathetus and the opposite angle constructible in the absolute plane?

Question. Is it possible to construct a right triangle with a given cathetus $a$ and a given opposite angle $\alpha$ using only compass and ruler in the absolute geometry (so without the axiom of ...
8 votes
0 answers
93 views

Is the hypotenuse operation associative in every Tarski plane?

By a Tarski space I understand a mathematical structure $(X,\mathsf B,\equiv)$ consisting of set $X$, a betweenness relation $\mathsf B\subseteq X^3$ and a congruence relation ${\equiv}\subseteq X^2\...
5 votes
0 answers
115 views

Is an equilateral triangle constructible in a Tarski plane?

By a Tarski space I understand a mathematical structure $(X,\mathsf B,\equiv)$ consisting of set $X$, a betweenness relation $\mathsf B\subseteq X^3$ and a congruence relation ${\equiv}\subseteq X^2\...
8 votes
3 answers
506 views

Elementary countable submodels in Gödel's universe

By the downward Lowenheim-Skölem theorem we can find two countable ordinals $\alpha < \beta$ such that $L_\alpha \prec L_{\omega_1}$ and $L_\beta \prec L_{\omega_1}$. That is, $L_\alpha$ and $L_\...
17 votes
3 answers
946 views

Minimum transitive models and V=L

Is there a c.e. theory $T⊢\text{ZFC}$ in the language of set theory such that the minimum transitive model of $T$ exists but does not satisfy $V=L$? You may assume that ZFC has transitive models. ...
3 votes
1 answer
152 views

If a theory speaks of sets that cannot be forced to be parameter free definable, then does this entail a large cardinal property?

If we say that an effectively generated first order theory $\sf T$ extends $\sf ZF$, such that every countable model of $\sf T$ doesn't have a class forcing extension that is pointwise definable. ...
10 votes
2 answers
767 views

Does every consistent extension of ZF have a model in the minimal transitive model of ZFC?

Suppose there exists a transitive model of $\sf ZFC$. Is it the case that every consistent theory that extends $\sf ZF$ must have a model that is an element of the minimal transitive model of $\sf ZFC$...
3 votes
1 answer
179 views

Definable closure in class-sized expansions of o-minimal groups

I am working in NBG set theory with limitation of size (i.e. the class of all sets is in bijection with the class of ordinals). Let $\mathbf{G}$ be a class-sized o-minimal expansion of an ordered ...
1 vote
1 answer
141 views

Is there a model of each of the following kinds of theories in the first transitive model of ZFC?

The question of whether the minimal transitive model $M$ of $\sf ZFC$ have a model of each consistent extension $\sf T$ of $\sf ZF$, is answered to the negative, basically because $M$ is countable and ...
1 vote
1 answer
83 views

Are externally pointwise definable models of ZFC subject to the same limitations of the internally pointwise definable ones?

By pointwise definable models, it's meant that every element of those models is definable after a formula in a parameter free manner, but that defining formula is in the language of that model, i.e., ...
5 votes
1 answer
205 views

What does the Ehrenfeucht-Fraïssé game on structures with infinitely many relations tell us?

EF-games are typically presented for structures with finitely many relations, and if you want to extend them to structures with functions, you can relationalize the functions. This seems to be to ...
3 votes
1 answer
219 views

Adding sort of sets over theory with multiple sorts?

It's relatively standard to add a sort of sets over some base theory and supplement the axioms with comprehension principles as in second order arithmetic. Is there a nice way to do this if your ...
4 votes
1 answer
169 views

The locale of morphisms vs a morphism to an ultrapower?

I'm fixing some type of structure $\Sigma$ (possibly multi-sorted, with functions symbols and relation symbols, though assuming it single sorted with only relation symbols wouldn't change anything). ...
21 votes
2 answers
900 views

Seymour's second neighborhood conjecture for infinite graphs

Let $G$ be a directed graph (say simple, so no loops and each pair of vertices has at most one directed edge between them). Suppose $G$ is 'locally finite', in the sense that each vertex has only ...
19 votes
1 answer
1k views

Is the theory of a partial order bi-interpretable with the theory of a pre-order?

A partial order relation $\leq$ on a set $A$ is a binary relation that is reflexive, transitive, and antisymmetric. A preorder relation $\unlhd$ (also sometimes known as a quasi order or pseudo order) ...
5 votes
1 answer
138 views

Does visible nonstandardness imply visible ill-foundedness?

For $X\subseteq\mathfrak{M}\models \mathsf{TA}$, say that $X$ is $\mathfrak{M}$-disruptive iff there is some formula $\varphi$ in the language of arithmetic + a new unary predicate symbol $U$ such ...

1 2 3
4
5
25