Questions tagged [model-theory]

Model theory is the study of (classes of) mathematical structures (e.g. groups, fields, graphs, universes of set theory) using tools from mathematical logic. Objects of study in model theory are models for formal languages which are structures that give meaning to the sentences of these formal languages. Not to be confused with mathematical modeling.

Filter by
Sorted by
Tagged with
1 vote
1 answer
28 views

Are these restatements of m-equivalence correct?

I am not sure if these formulations of the $m$-equivalence of two structures $\mathfrak{A}$ and $\mathfrak{B}$ are correct. Two structures $\mathfrak{A}$ and $\mathfrak{B}$ are $m$-equivalent iff for ...
schuelermine's user avatar
8 votes
1 answer
112 views

Erratum in Kossak's "Model theory for beginners"

My question is about what I think is a mistake in Roman Kossak's book Model theory for beginners (which is in my opinion a good book; I at least enjoyed a lot what I've read so far). In chapter 5, ...
PseudoNeo's user avatar
  • 9,631
0 votes
1 answer
67 views

Question about Finite Model on Robinson Arithmetic

So I was supposed to create a finite model for Robinson Arithmetic in an exam and show that it was a finite model, but I was unable to do so. Would appreciate any help with this problem because I feel ...
John Doe's user avatar
1 vote
2 answers
80 views

Model Theory in the Language of Peano Arithmetic

Most introductory textbooks on model theory establish the theory based on the ZF set theory (e.g. [1]). In particular, a structure is defined to be a 4-tuple of sets, and so on. In [2], I came to ...
Student's user avatar
  • 1,812
-2 votes
1 answer
201 views

Why Löwenheim–Skolem theorem asserts the non-existence of such predicates in 1st order logic

Suppose there was a predicate, in the language of 1st order $ \mathsf {PA} $, such that it is only true for standard natural numbers i.e. it accepts ALL and ONLY standard natural number, and it ...
Alex Matyasaur's user avatar
8 votes
1 answer
211 views

Does independence-friendly logic have a completeness theorem?

It is a well-known (and frankly magical) property that first-order logic is strongly semantically complete (Gödels completeness theorem). Independence-friendly logic is just like first-order logic but ...
Kevin De Keyser's user avatar
9 votes
1 answer
654 views

Finding a property that is true for every left ideal but not for right ideals

I'm trying to find (or prove that it cannot exist) a property that is true for all left ideals of a ring (with unity) but fails for some right ideal. To rephrase this more rigorously: Consider the ...
Eduardo Magalhães's user avatar
2 votes
1 answer
58 views

If the exponential is definable in an expansion of $\mathbb{\overline{R}},$ then it is definable without parameters

Let $\mathcal{R}$ be an expansion of $(\mathbb{R},+,\cdot,-,<,0,1)$, and suppose that the exponential map is definable. I am asked to show that it is definable without parameters using the fact ...
Donnie Darko's user avatar
1 vote
1 answer
58 views

(soft question) I'm giving a talk on model theory to undergrads in a few weeks, thoughts topics to include/exclude

I am an undergrad and have been doing independent study on model theory for 6+ months now, and am slated to give a talk to undergrads later this month on model theory. I aim to give a soft ...
August's user avatar
  • 97
4 votes
0 answers
83 views

Using Model-Theoretic Proof of Ax-Grothendieck for the Riemann Hypothesis

A proof of Ax-Grothendieck utilizes model theory and the fact that the theorem is true for finite fields, and also algebraic closures of finite fields. See here. I have a (perhaps naive) question: ...
abiteofdata's user avatar
7 votes
2 answers
396 views

Does satisfaction at all arithmetical sets of a second-order arithmetic formula with no bound predicate variables imply its satisfaction?

Let $\varphi(X_1,\ldots,X_r)$ be a second-order arithmetic formula with no bound predicate variables and free predicate variables $X_1,\ldots,X_r$ (all of arity $1$ for simplicity). Assume every ...
Gro-Tsen's user avatar
  • 5,521
3 votes
1 answer
95 views

Why does first-order logic lack of a description like the Stone duality?

Stone Duality characterizes Boolean algebras in terms of spaces. I regard this as being done by identifying an algebra with its ``space of models'', and feel like the barrier for a similar thing to be ...
Y.X.'s user avatar
  • 3,935
1 vote
1 answer
81 views

Is the problem of whether there is a computable model of a given first-order sentence recursively enumerable?

Trakhtenbrot's theorem states that given a sentence $\phi$ in a finite vocabulary (M. Viswanathan, "Finite Model Theory", notes, 2018), the problem of whether $\phi$ is satisfied in a finite ...
C7X's user avatar
  • 1,110
1 vote
0 answers
89 views

The provability predicate in incompleteness theorem [duplicate]

The prooffor(x,y) predicate in godel's 1st incompleteness theorem is primitive recursive, so if there is a statement ' S ' within the theory , which would be 1st order PA in godel's case , and it has ...
user avatar
2 votes
1 answer
133 views

Statement that neither can be proved nor disproved nor proved to be independent exists? [duplicate]

Godel's first incompleteness theorem states that any consistent formal system $F$ within which a certain amount of elementary arithmetic can be carried out is incomplete. I know we can prove Continuum ...
wsz_fantasy's user avatar
  • 1,546
0 votes
0 answers
29 views

Is pointwise definability of a model of PA equivalent to it being the standard model? [duplicate]

The standard model of Peano Arithmetic is pointwise definable, because every finite natural number is parameter-free definable. What about the converse? That is, if a model $M$ of PA is pointwise ...
user107952's user avatar
  • 20.1k
1 vote
1 answer
62 views

Bi-interpretability implies isomorphism of the automorphism groups?

The theorem of Ahlbrandt and Ziegler says that two countable $\omega$-categorical structures $M$ and $N$ are bi-interpretable if and only if $Aut(M)\cong Aut(N)$ as topological groups. Dropping the ...
Focaccia's user avatar
4 votes
1 answer
180 views

What are the parameter-free definable elements of a model of Peano Arithemetic?

Let $M$ be a model of Peano Arithmetic. What are the parameter-free definable elements of $M$? I conjecture that they are precisely the standard natural numbers, meaning, no nonstandard infinite ...
user107952's user avatar
  • 20.1k
1 vote
0 answers
35 views

Defining an infinite circle in signature {E}

Let the signature $s$ be $s=\{E\}$ (a 'graph', kind of). Is it possible to create a $s$-structure that represents a infinitely long circle (I.E. a circle with an infinite number of nodes $(v_0,v_1,...,...
FrontendC's user avatar
  • 139
1 vote
0 answers
55 views

Is there a model theoretic proof for the deduction lemma?

Using proof theory one can prove the following statement: Let $T$ be an $\mathcal{L}$-Theory, $\chi$ a $\mathcal{L}$-sentence, $\varphi$ a $\mathcal{L}$-formula, then $T \cup \{\chi\} \vdash \varphi \...
Hugo Chavez's user avatar
1 vote
0 answers
76 views

What is the significance of the difference between I$\Sigma_3$, I$\Sigma_{30}$ and I$\Sigma_{3000000}$ and $PA$?

There is of course a difference for logicians, but from a non-logician-mathematician's perspective, what is the real significance of arbitrarily complex induction predicates? Are there perhaps ...
10012511's user avatar
  • 682
1 vote
1 answer
75 views

Why is $S \models \bot$ the "same" as $S$ has no model?

In a lecture I attended, the instructor used the phrases $S$ has no model $S\models \bot$ interchangeably. While I get that (2) implies (1) because if there is a valuation $v$ such that $v(s)=1 \,\...
S. Chitratta's user avatar
1 vote
1 answer
68 views

Are Euclidean domains first-order axiomatizable in just the language of rings?

The notion of an Euclidean domain is defined using the auxiliary machinery of a Euclidean function. But, I wonder, is that auxiliary machinery actually needed? More precisely, in the language $\{+,-,*,...
user107952's user avatar
  • 20.1k
1 vote
0 answers
30 views

What are some surprising theories that contain Robinson arithmetic?

I'm looking for theories that enable defining natural numbers and proving Robinson arithmetic (like ZF and Peano) but in a nontrivial or even a surprising way.
OMGsh's user avatar
  • 244
1 vote
2 answers
59 views

Doing an modal logic exercise. The tableau for both the argument and its negation are open. Am I doing something wrong?

I am doing an exercise from Graham Priest's textbook "An Introduction to Nonclassical Logic", and I think I'm doing something wrong. The exercise is to determine the validity of α=β, ◇Pα, ⊢ ◇...
Alex4963's user avatar
1 vote
1 answer
148 views

Permutation model in which infinite sets are weakly Dedekind-infinite but not Dedekind-infinite

I’m trying to create a permutation model $N$ in which every infinite set is weakly Dedekind-infinite (i.e. for every infinite set $A\in N$ there is a surjective map $f:A\rightarrow\omega$ in $N$), but ...
JLB's user avatar
  • 312
1 vote
2 answers
97 views

Modeling a formula with free variables for quantifier elimination, i.e. $\mathfrak{M} \models \phi (x) \leftrightarrow \psi (x)$

I am an undergrad doing an independent study with a professor on model theory using David Marker's Model Theory : An Introduction. I am new to the subject so this question may be naïve or misguided. I ...
August's user avatar
  • 97
3 votes
0 answers
53 views

Can This Classical-Kleene Combination for Intuitionistic Fragment $\{ \neg, \vee, \wedge \}$ Be Extended to Include $\rightarrow$?

Over a year ago, I worked out a classical-Kleene combination logic that worked to preserve intuitionistic tautologies over the intuitionistic fragment with operators $\{ \neg, \vee, \wedge \}$, which ...
Joshua Harwood's user avatar
3 votes
0 answers
63 views

Why does model theory usually study complete theories?

Is it just a matter of complete theories being the simpler ones to understand? Do the methods of model theory essentially require that the theories be complete. It seems that even for a complete ...
IllogicalUser's user avatar
-1 votes
1 answer
144 views

Can WS1S encode any power of $2$? [closed]

I was wondering if I can write in weak monadic second order theory of one successor can encode the number $2^x$ for a variable $x$.
user1868607's user avatar
  • 5,739
3 votes
2 answers
201 views

How to create infinitely many disjoint sets from infinitely many sets

Suppose we have a countably infinite set $X$ and we have (countably) infinitely many subsets $A_1,A_2,\cdots\subseteq X$ which are non-empty and distinct (i.e. for any $i\neq j$ either $A_i\setminus ...
JLB's user avatar
  • 312
0 votes
0 answers
53 views

What is the formal definition of monster model?

What is the formal definition of a monster model for a theory? I have read that term in many model theory books, but I have never seen a rigorous definition of it. Is there even a rigorous definition ...
user107952's user avatar
  • 20.1k
-2 votes
1 answer
87 views

Model vs Axiom vs Theory... difference [closed]

I am not a student but I am interested in logic, I am reading a book about model theory. The problem is I guess book is not so interested in defining notions and I also couldn't understand the ...
A. T.'s user avatar
  • 1
2 votes
1 answer
64 views

Would the Following Table Strategy Work as an Intuitionistic Decision Procedure?

I had previously sought some insight for handling logical operators in the Rieger-Nishimura lattice and, with assistance here, was able to work out a fairly rigorous way. To the best of my ability, I ...
Joshua Harwood's user avatar
9 votes
2 answers
423 views

If $a$ and $b$ are elements of a group $G$ that satisfy the same first order formulas, is there always an automorphism of $G$ that maps $a$ to $b$?

Let $a$ and $b$ be elements of group $G$ and assume that for any natural number $n$ and for any first-order formula $\varphi (x_1,x_2,...,x_n)$ with $n$ free variables in the language of groups, $G \...
Hussein Aiman's user avatar
4 votes
1 answer
72 views

Different intervals in an ordered vector space over $\mathbb{Q}$

Consider an ordered vector space $V$ over $\mathbb{Q}$ in the usual language of ordered vector spaces $(<,0,-,+,\lambda\cdot)_{\lambda \in \mathbb{Q}}$. For the duration of this question, the word ...
Z. A. K.'s user avatar
  • 10.9k
4 votes
1 answer
74 views

Is there a difference between computable model theory and computable structure theory?

I have the seen the books/notes with both titles and there seems to be quite some overlap, but I'm not sure if people in the field view them as having slightly different focuses.
IllogicalUser's user avatar
2 votes
2 answers
134 views

Are There Universal Entailments Under the Rieger-Nishimura Lattice for Conditionals When the Antecedent is Higher on It?

I'm working on a bottom-up (atomics-to-proposition) intuitionistic decision procedure, and I encountered some fruits with the Rieger-Nishimura lattice. Specifically, I am looking at this article from ...
Joshua Harwood's user avatar
1 vote
0 answers
65 views

back-and-forth in lovely pairs

This is a question about the following proof of Lemma 3.8 in the paper Lovely pairs of models of Itay Ben-Yaacov, Anand Pillay and Evgueni Vassiliev. The paper can be found here. Let $f:a→b$ be the ...
Maksim's user avatar
  • 61
0 votes
1 answer
95 views

Is it possible to integrate real numbers into my custom vocabulary within the framework of model theory?

So, I want to use model theory to approach an applied task. Developing the corresponding vocabulary, I realized I needed real numbers within my formulas and, thus, real numbers within the language. I ...
Seeker's user avatar
  • 327
1 vote
1 answer
65 views

Complete finitely axiomatizable theory of a single binary relation with any finite number of countable models other than 1 or 2.

I am interested in this question, which asks for a complete finitely axiomatizable theory with three countable models. The standard example of $(\mathbb{Q}, <)$ with an ascending sequence of ...
Greg Nisbet's user avatar
  • 11.6k
1 vote
1 answer
126 views

Question about proof of completeness theorem

I am reading a book about logic and in the proof of the completeness theorem there is a point I would like to clarify. The part that is troubling me is the "easy" part, so basicly that $T \...
Le Grand Spectacle's user avatar
1 vote
0 answers
65 views

Elimination set for the term algebra in A Shorter Model Theory

I'm reading Hodges' A Shorter Model Theory. In the section about quantifier elimination, theorem $2.7.5$ proves that some set of formulas is an elimination set of the term algebra (under a different ...
Frousse's user avatar
  • 434
3 votes
0 answers
120 views

Seeking Suggestions for PhD Topics in Model Theory, Focused on Combinatorics in NIP Theories and Tameness

Hello Math Stack Exchange Community, As I embark on the journey of selecting a PhD research topic in mathematics, my interests are gravitating towards model theory, with a specific focus on ...
Shostak8's user avatar
  • 159
0 votes
1 answer
233 views

Set theory and model theory: which set is ZFC?

I have yet another post about what is model theory doing and why is it valid; I hope I can be coherent. (1) https://mathoverflow.net/questions/23060/set-theory-and-model-theory (2) What exactly is the ...
Riley Moriss's user avatar
10 votes
0 answers
202 views

Elementary embedding between transitive sets

I was originally going to ask whether this statement has consistency strength over $\mathsf{ZFC}$: there exist transitive sets $M,N$ with $N\subseteq M$ and a nontrivial elementary embedding $j:M\...
Lxm's user avatar
  • 876
2 votes
1 answer
65 views

Show that the direct product of structures satisfies a Horn sentence

This is exercise 3.4.16 from Mathematical Logic by Ebbinghaus. Formulas which are derivable in the following calculus are called Horn formulas: Horn formulas without free variables are called Horn ...
iwjueph94rgytbhr's user avatar
4 votes
2 answers
149 views

Describe the class of groups that satisfy $(x^2y^2)^2 \approx 1$

I have trouble with the following assignment: Let $A$ denote the class of all Abelian groups satisfying the identity $x^2 \approx 1$. Show that the class $$\{G \mid \exists N: N \trianglelefteq G \...
Björn's user avatar
  • 140
0 votes
1 answer
48 views

Does this propositional theory have an independent axiomatization?

I was reading this question by user107952 and trying to come up with an example of a theory with no independent axiomatization or at least no independent recursive axiomatization. I've come up with ...
Greg Nisbet's user avatar
  • 11.6k
3 votes
1 answer
154 views

how to prove that Seq(A) exists

I was reading "Introduction to Set Theory" - Thomas Jech, and up until the Recursion Theorem section only the following axioms were presented: Extensionality, Comprehension, Pair, Union, ...
Xenônio's user avatar

1
2 3 4 5
86