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,203
questions
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 ...