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

What is a good definition of a mathematical structure?

At the moment I am writing a textbook in Foundations of Mathematics for students and trying to give a precise definition of a mathematical structure, which is the principal notion of structuralist ...
19 votes
2 answers
976 views

Which graphs are elementarily equivalent to their own disjoint sums?

In Stefan Geschke's recent question, one of the solutions observed that the graph consisting of a single infinite beaded chain, a $\mathbb{Z}$-chain where each integer is connected to its nearest ...
16 votes
3 answers
2k views

Recommendations to learn about the use of toposes in logic?

I'd like to learn about the use of toposes in logic. The "logic" side I know quite well, but of the "topos" side I am totally ignorant. Which books/articles (formal and/or casual) ...
6 votes
0 answers
217 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
0 answers
61 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$ ...
3 votes
1 answer
428 views

Decidability survives new constants

Let $L$ be a finite first order language and let $M$ be an $L$-structure with universe $\mathbb{N}$ that interprets all $L$-symbols as recursive sets (so $M$ is a recursive $L$-structure). Let $L(c)$...
-2 votes
0 answers
234 views

Demonstration of the Diagonal Lemma

Let $f(x)$ be a recursive function, $\alpha(x)$ a class-sign and $\alpha_f(x)$ a class-sign equivalent to $\alpha(f(x))$, i.e.: $$\alpha_f(n)\Leftrightarrow\alpha(f(n))\,\textrm{ is provable for each ...
0 votes
0 answers
100 views

What are the primitive notions and axioms in model theory? [migrated]

I know every theory has its primitive notions and axioms. Now I am reading Basic Model Theory, and there is no term or sentence referred as to a primitive notion or an axiom. But, I think I know that ...
24 votes
3 answers
3k views

The closure-complement-intersection problem

Background $\DeclareMathOperator\Cl{Cl}$ Let $A$ be a subset of a topological space $X$. An old problem asks, by applying various combinations of closure and complement operations, how many distinct ...
6 votes
1 answer
474 views

Normal form for terms in language with two ring structures

Suppose I have two different ring structures on the same domain $\langle R,+,\cdot,0,1\rangle$, $\langle R,\oplus,\otimes,\bar 0,\bar 1\rangle$ and I throw the structures together into a single common ...
1 vote
1 answer
174 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$? ...
4 votes
0 answers
275 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{...
8 votes
2 answers
1k views

Is there one binary operation foundational for set theory?

The membership relationship "$\in$" is foundational for set theory, in the sense that the axioms of any set theory are formulated in the language of "$\in$". Naturally, the ...
1 vote
0 answers
186 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 ...
1 vote
0 answers
111 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
1 answer
456 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 ...
11 votes
1 answer
581 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 ...
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 ...
3 votes
0 answers
135 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 ...
3 votes
2 answers
961 views

Theory interpreted in non-set domain of discourse may be consistent?

Following the blow. I will try to ask question in order to check if I well understand what was pointed. I decide to ask another question, because mathoverflow is not projected to be good environment ...
10 votes
1 answer
343 views

Elementary equivalence between $n\mapsto n+1$ and its inverse on the Stone-Čech remainder?

Consider structures $(A,f)$ encoding a Boolean algebra $A$ endowed with an automorphism $f$. There is an obvious notion of isomorphism between such structures. Consider the endomorphism $\hat{\Phi}$ ...
-1 votes
1 answer
741 views

Is theory with domain of interpretation in second order objects a First Order Theory?

Thank everybody for answering my previous questions: first, and second. Here I would like to ask about some important thing which I do not understand clearly. Is it necessary for theory to have given ...
1 vote
1 answer
200 views

Minimal models in strong set theories - pt. 2

This is a follow-up to this question. So, as Noah elucidated (thanks Noah!), whenever $T$ is r.e., $M(T) < \sigma$ ($\sigma$ is the least stable ordinal, i.e. $L_\sigma\prec_{\Sigma_1}L$). In ...
0 votes
0 answers
98 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?
6 votes
1 answer
300 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 ...
2 votes
0 answers
476 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?...
11 votes
1 answer
418 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. ...
5 votes
1 answer
860 views

Smallest ordinal modelling $\aleph_1$?

Let $X_1$ be the class of all ordinals $\alpha$ such that there exists a transitive model $M$ of ZF(C) such that $M$ thinks that $\alpha$ is $\aleph_1$. Every class of ordinals has a minimum element (...
2 votes
1 answer
536 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, ...
38 votes
3 answers
3k views

Can one show that the real field is not interpretable in the complex field without the axiom of choice?

We all know that the complex field structure $\langle\mathbb{C},+,\cdot,0,1\rangle$ is interpretable in the real field $\langle\mathbb{R},+,\cdot,0,1\rangle$, by encoding $a+bi$ with the real-number ...
19 votes
0 answers
791 views

"Compactness for computability" - does it ever happen?

Throughout, "computable structure" means "first-order structure in a computable language with domain $\omega$ whose atomic diagram is computable." Say that a computable structure $...
3 votes
0 answers
164 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 ...
3 votes
1 answer
93 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 ...
1 vote
1 answer
226 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 ...
6 votes
1 answer
501 views

Parameter-free effective cardinals

In the paper "Effective cardinals and determinacy in third order arithmetic" by Juan Aguilera, effective cardinals is defined. I'm curious about its little variation, parameter-free ...
5 votes
0 answers
198 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 ...
7 votes
1 answer
939 views

Where do nonstandard elliptic curve angles come from?

This is a question which has bounced around my head over the past few years. At the same time, I am answering Riemann hypothesis for zeta function of algebraic curves over fields of infinite ...
4 votes
0 answers
141 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-...
13 votes
1 answer
500 views

Is there a complete uncountable theory with two countable models?

This is a question originally asked at MSE a few years ago; the original poster hasn't been active in a while, so I'm taking the liberty of asking it here: Is there a complete first-order theory $T$ ...
16 votes
4 answers
1k views

Can Suslin (or Aronszajn) lines ever be orderings of abelian groups?

I am interested in realizing linear orders as orderings of abelian groups. In particular, can Suslin lines (and other classes of line) be realised in this way? Let $\mathcal{C}$ be a class of (...
15 votes
2 answers
1k views

Decidability of decidability

The questions I'm going to ask are non formal because they concern decidability of decidability, and I couldn't find any references on that after some quick searches. I hope that this thread is still "...
6 votes
7 answers
5k views

Compactness Theorem for First Order Logic

Hi all, I am interested in proofs without using Goedel's completeness theorem. Does anyone have a reference to a proof of this theorem that uses Skolem Functions? How come Enderton's (Introduction to ...
1 vote
1 answer
210 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 ...
20 votes
6 answers
3k views

What are some nice uses of ultraproducts/ultrapowers?

Motivated by a recent post (Non-definability of graph 3-colorability in first-order logic), I was wondering: what are some nice arguments based on ultraproducts? I don't mind definability results, but ...
2 votes
1 answer
317 views

Is elementary equivalence absolute?

Assume we have two objects $M_1$ and $M_2$ models of respective $L_{\omega_1,\omega}$-sentences $\Sigma_1$ and $\Sigma_2$. Assume $M_1$ and $M_2$ are elementarily equivalent in some model of set ...
2 votes
2 answers
273 views

Interpreting peano arithmetic without parameters

I will accept an answer in the form of references to the literature about my question as well as any other information. I am quite ignorant of the area and that will be clear from my question. I ...
7 votes
1 answer
432 views

Under what conditions does $\mathcal{M} \vDash \mathsf{PA}$ and $\mathcal{K} \vDash \mathsf{PA}$ such that $\mathcal{M} \ncong \mathcal{K}$?

I'm currently learning some introductory model theory from Marker's "Model Theory: An Introduction", Kaye's "Models of Peano Arithmetic", and Hodges' "Model Theory", and I am confused by the Wikipedia ...
6 votes
2 answers
468 views

Reconstructing a model from its definable sets

Let $\mathcal{M}$ be an infinite model of a first-order language, and for each $n$, let $\mathcal{B}_n$ be the algebra of definable sets of $n$-tuples from $|\mathcal{M}|$. Given $\{\mathcal{B}_n\mid ...
12 votes
4 answers
1k views

Universal order type

Every countable order type, such as the countable ordinals, $\mathbb Z$, etc. can be embedded in $\mathbb Q$, so it is universal for countable order types. Is there a universal space for all linear ...

1
2 3 4 5
25