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,204
questions
1
vote
0
answers
57
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$ ...
5
votes
0
answers
164
views
+100
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}$ ...
-2
votes
0
answers
224
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 ...
1
vote
1
answer
171
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
181
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
0
answers
272
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
556
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
453
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
133
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
97
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
471
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
299
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
417
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
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 ...
2
votes
1
answer
535
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
196
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
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-...
1
vote
1
answer
209
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
198
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
80
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
163
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
139
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
526
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
230
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
146
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
133
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
592
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
220
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
225
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 ...
1
vote
1
answer
78
views
Sizes of linearly ordered subalgebras of powers
On the grounds that I'm currently teaching a linear algebra class and I enjoy making my students furious, let a linear algebra be an algebra $\mathcal{A}$ in the sense of universal algebra equipped ...
23
votes
4
answers
3k
views
A Löwenheim–Skolem–Tarski-like property
I am interested in the following Löwenheim–Skolem–Tarski-like property.
Given a cardinal $\kappa$, what (if any) is a property $\phi(x)$ such that if $\phi(\kappa)$ holds, then we can prove the ...
9
votes
1
answer
286
views
Two notions of generalized quotient/substructure
Given a language $\Sigma$ and a $\Sigma$-algebra (in the sense of universal algebra) $\mathcal{A}=(A;\dotsc)$ and a function $f:A\rightarrow A$, let $\mathcal{A}_f$ be the $\Sigma$-algebra whose ...
14
votes
1
answer
568
views
Extensions of $PA+\neg Con(PA)$ with large consistency strength
There is a large hierarchy of theories strengthening $PA$ eg $PA+Con(PA)$, $PA+Con(PA+Con(PA))$,..., second-order arithmetic and $ZFC$, ordered by consistency strength.
Is there an extension of $PA+\...
6
votes
5
answers
2k
views
Standard models of N and R: An Alice/Bob approach
This is a question about a comment in a recent publication by Roman
Kossak. Kossak wrote:
"Nonstandardness in set theory has a different nature. In
arithmetic, there is one intended object of ...
6
votes
0
answers
203
views
Reference for Understanding Shelah's Proof of Vaught's Conjecture for $\omega$-stable Theories
I'm looking for a source to help me better understand Shelah's proof of Vaught's Conjecture for $\omega$-stable Theories (https://shelah.logic.at/files/95409/158.pdf). An obvious candidate is Makkai's ...
3
votes
0
answers
90
views
Comparing computable structures via Kleene and Skolem
Below, by "structure" I mean "computable structure in a finite language with domain $\omega$," and by "sentence" I mean "finitary first-order sentence containing no ...
7
votes
0
answers
286
views
A system with distinct infinite cardinalities but no "best" version of $\mathbb{N}$
Let $\mathfrak{S}=(M_z,U_z)_{z\in\mathbb{Z}}$ be a sequence such that for each $z\in\mathbb{Z}$ we have
$M_z\models\mathsf{ZFC}+$ "$U_z$ is a nonprincipal ultrafilter on $\omega$" (so in ...
6
votes
0
answers
177
views
Interest in the size of ultrapowers in model theory
It seems that in the 60s (at least), there was interest in computing the size of ultrapowers by countably incomplete ultrafilters. For example, given an ultrafilter $U$ on some relatively small set ...
5
votes
1
answer
473
views
General algebraic result obtained from consideration on $\mathbb{Q}_p$
There are results in field theory which are obtained from, let's say, the complex numbers and then generalized to all algebraically closed fields.
For instance, the fact that a polynomial $P$ admits a ...
14
votes
5
answers
2k
views
How is it possible for PA+¬Con(PA) to be consistent?
I'm having some trouble understanding how a certain first-order theory isn't just straight-up inconsistent.
Let $PA$ be the axioms of (first-order) Peano arithmetic and let $C$ be the following ...
6
votes
1
answer
357
views
Interpreting group-theoretic sentences as statements about algebraic groups
Suppose we are given a sentence in the language of groups, e.g. $\phi=\forall x\forall y(x\cdot y=y\cdot x)$, and suppose that we are also given the data defining an algebraic group $G/k$. One can ...
0
votes
0
answers
166
views
Can a model of "true computation" exist? What would be its consequences?
Analogous to the model of True Arithmetic, the model of "True Computation" is defined to be the set of all true first-order statements about Turing machines i.e. answers to elementary ...
4
votes
2
answers
256
views
Symmetric monoidal functors from powers of the natural numbers to Set
Consider the full subcategory of $\mathbf{Set}$ consisting of the singleton $1$ and countable infinite sets. (Originally this came from the powers $\mathbb{N}^{\times k}$ and the morphisms between ...
1
vote
1
answer
120
views
For a pure-injective module $M$ does the property "$\operatorname{Hom}(-,M)$ is surjective" commute with certain limits?
$\DeclareMathOperator\Hom{Hom}$Let $M$ be a pure-injective module. Then $\Hom(\varphi,M)$ is surjective for a pure-mono $\varphi$. It is well-known that $\varphi$ is a direct limit of split monos $\...
2
votes
0
answers
51
views
Finite (schema) axiomatizability of representable cylindric algebras
If we know that the class of all representable cylindric algebras of dimension $\alpha$ (for any ordinal number $\alpha>2$) is NOT finitely (schema) axiomatizable*, then does it (perhaps trivially) ...