2
$\begingroup$

Exercise goes as follows:

Assume $T$ is $\mathcal{L}$-theory, where $|\mathcal{L}|$ is finite and it has a model $\mathcal{M}$ which is isomorphic to it's own proper substructure. Show that $T$ has a countable model isomorphic to it's own proper substructure.

To begin with, I'm confused of how it is possible that some model $\mathcal{M}$ has a proper substructure $\mathcal{N}$ such that there is isomorphic $\mathcal{L}$-embedding $\eta: N \to M$. Since $\eta$ is isomorphic, how it is possible that $\mathcal{N}$ is proper substructure? I think proper would mean $N \subsetneq M$.

I would appreciate any help of explaining it.

EDIT: Now I understand the text of the exercise fully, but how can I show it is true for any such $T$? I would appreciate any hints on how can I prove this.

EDIT2: So here is my attempt to prove it:

Let $T$ be a theory in a finite language $\mathcal{L}$ and let $\mathcal{L}$-structures $\mathcal{M}$, $\mathcal{N}$ be such that $\mathcal{M} \models T$, $\mathcal{N} \subsetneq \mathcal{M}$ and $\mathcal{N} \cong \mathcal{M}$. Let $\mathcal{L}^* = \mathcal{L}\cup \{f\}$, where $f$ a new unary function symbol and let $\varphi = \varphi_1 \land \varphi_2 \land \varphi_3$, where $$ \varphi_1 \text{ is } \forall v_1 \forall v_2 (f(v_1) = f(v_2) \Rightarrow v_1 = v_2) \quad \text{(}f\text{ is an injection)} $$ $$ \varphi_2 \text{ is } \forall v_2 \exists v_1 (f(v_1) = v_2) \quad \text{(}f\text{ is onto)} $$ $$ \varphi_3 \text{ is } \exists v_3 \forall v_1 \forall v_2 (f(v_1) = v_2 \Rightarrow \neg(v_1 = v_3)) \quad \text{(image of }f\text{ is not equal to its domain)} $$ and $$ T^* = T \cup \{ \varphi \} $$ Let $\eta: \mathcal{M} \to \mathcal{N}$ be an $\mathcal{L}$-isomorphism. If we let $f^{\mathcal{M}}(a) = \eta(a)$, then clearly $\mathcal{M} \models T^*$ as an $\mathcal{L}^*$-structure. Now, by Lowenheim–Skolem theorem, there exist countable elementary $\mathcal{L}^*$-substructure $\mathcal{S} \preceq \mathcal{M}$. Therefore, by the construction of $T^*$, $f^{\mathcal{S}}: S \to f^{\mathcal{S}}[S]$ is an isomorphism. Moreover, by $\varphi_3$, $f^{\mathcal{S}}[S] \neq S$, so $f^{\mathcal{S}}$ defines a proper isomorphic $\mathcal{L}^*$-substructure of $\mathcal{S}$. Finally, since $\mathcal{S} \models T^*$, then $\mathcal{S} \models T$, so $\mathcal{S}$ is a countable model of $T$ isomorphic to its own proper substructure.

$\endgroup$
7
  • 1
    $\begingroup$ hi chandz. consider for example the theory $T$ of infinite sets in the empty language $\mathcal{L}_{\varnothing}=\varnothing$. let $N\subsetneq M$ be any sets of the same cardinality. (eg take $N=\mathbb{Z}$ and $M=\mathbb{Q}$.) then $N$ and $M$ are both models of $T$, and any bijection $\eta:N\to M$ is an isomorphism of $\mathcal{L}_{\varnothing}$-structures. does that example help? $\endgroup$ Jan 19, 2022 at 18:00
  • 2
    $\begingroup$ Lots of structures are isomorphic to proper substructures of themselves, in the same way that lots of sets are in bijection with proper subsets of themselves. In fact, in the empty language, "structure" amounts exactly to "set" and "isomorphism" reduces to just "bijection," so this gives an example (as Atticus Stonestrom says above). $\endgroup$ Jan 19, 2022 at 18:06
  • 1
    $\begingroup$ if that example feels too trivial, let $\mathcal{L}_{<}=\{<\}$ be a language with a single binary relation $<$. make $M=\mathbb{N}$ and $N=2\mathbb{N}\subsetneq M$ into $\mathcal{L}_{<}$-structures in the natural way. can you show that the map $\eta:M\to N$ taking $n$ to $2n$ is an isomorphism? $\endgroup$ Jan 19, 2022 at 18:07
  • $\begingroup$ @AtticusStonestrom Oh damn, yes, it helps, it is obvious, I had some brain fog I think $\endgroup$
    – xorandiff
    Jan 19, 2022 at 18:07
  • 1
    $\begingroup$ Improved hint: show that is consistent to extend the theory with a new function symbol $f(x)$ and axioms asserting that $f(x)$ is an isomorphism of the universe with a proper substructure. $\endgroup$
    – Rob Arthan
    Jan 19, 2022 at 18:30

1 Answer 1

2
$\begingroup$

Hint: Add an extra unary function symbol $f$ and choose an $L\cup \{f\}$ theory whose models (as $L$-structures) are exactly the $M\models T$ such $f$ is an isomorphism between $M$ and $f[M]\neq M$, and notice that by hypothesis, this theory is consistent. Then apply Lowenheim-Skolem.

$\endgroup$
4
  • $\begingroup$ I wrote a proof of it, could you take a look and say if it is correct? I'm actually not sure if it is correct. $\endgroup$
    – xorandiff
    Jan 21, 2022 at 16:53
  • 1
    $\begingroup$ @chandx: Two things: the way you wrote the axioms, it looks like $f$ is a binary relation symbol (which you use to represent the graph of a function). That is okay, but if you actually use an unary function instead, it's a bit less cumbersome to write. Secondly and more importantly, you did not write any axioms saying that $f$ actually is an isomorphism, only that it is an injection and not a surjection. That is definitely not enough. $\endgroup$
    – tomasz
    Jan 21, 2022 at 21:11
  • $\begingroup$ Of course, axioms were bad, but I think now they are good, is it right? $\endgroup$
    – xorandiff
    Jan 21, 2022 at 21:50
  • 1
    $\begingroup$ @chandx: Unfortunately, no. You have not addressed the most important part of my comment: the $f$ you describe is not an isomorphism, only an injection. Nowhere in your axioms do you refer to the other symbols of $L$. $\endgroup$
    – tomasz
    Jan 21, 2022 at 22:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .