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
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$ ...
tomasz's user avatar
  • 1,184
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}$ ...
Noah Schweber's user avatar
-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 ...
Speltzu's user avatar
  • 169
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 ...
Wenchuan Zhao's user avatar
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$? ...
Speltzu's user avatar
  • 169
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 ...
George's user avatar
  • 449
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,008
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 ...
Speltzu's user avatar
  • 169
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{...
Noah Schweber's user avatar
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 ...
Tim Campion's user avatar
  • 60.5k
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 ...
Amiren's user avatar
  • 1
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 ...
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
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?
Invictus's user avatar
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?...
Speltzu's user avatar
  • 169
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 ...
huurd's user avatar
  • 995
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. ...
Lingyuan Ye's user avatar
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 ...
Domenico Zambella's user avatar
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, ...
smed's user avatar
  • 29
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 ...
Antoine Labelle's user avatar
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-...
user21820's user avatar
  • 2,734
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 ...
Dave Pritchard's user avatar
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-...
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,799
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 ...
SagarM's user avatar
  • 131
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 ...
Noah Schweber's user avatar
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 ...
Noah Schweber's user avatar
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 ...
Noah Schweber's user avatar
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 ...
Vilhelm Agdur's user avatar
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-...
jg1896's user avatar
  • 2,683
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 - ...
Noah Schweber's user avatar
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 ...
Arian's user avatar
  • 183
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 ...
Zuhair Al-Johar's user avatar
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 ...
José Hdz. Stgo.'s user avatar
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 ...
Noah Schweber's user avatar
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 ...
Nai-Chung Hou's user avatar
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 ...
Noah Schweber's user avatar
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+\...
Tom Bouley's user avatar
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 ...
Mikhail Katz's user avatar
  • 15.1k
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 ...
Tesla Daybreak's user avatar
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 ...
Noah Schweber's user avatar
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 ...
Noah Schweber's user avatar
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 ...
Monroe Eskew's user avatar
  • 18.1k
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 ...
Weier's user avatar
  • 151
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 ...
E8 Heterotic's user avatar
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 ...
Nathan Lowry's user avatar
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 ...
symmetrickittens's user avatar
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 ...
Charles Wang's user avatar
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 $\...
kevkev1695's user avatar
  • 1,023
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) ...
Âloh's user avatar
  • 63

1
2 3 4 5
25