Elementary class of $T$-ec structures

Question

In Exercise 3.2.1. Martin Ziegler, Katrin Tent: A Course in Model Theory it is stated:

Exercise 3.2.1. Let $L$ be the language containing a unary function $f$ and binary relation symbol $R$ and consider the $L$-theory $T=\{\forall x\forall y(R(x,y)\to R(x,f(y)))\}$. Show following

1) For any $T$-ec structure $\mathfrak{M}$ and $a,b\in M$ with $b\notin\{a,f^\mathfrak{M}(a),\left(f^\mathfrak{M}\right)^2(a),...\}$ we have $\mathfrak{M}\vDash\exists z(R(z,a)\wedge\neg R(z,b))$.

2) Let $\mathfrak{M}$ be a model of $T$ and $a$ an element of $M$ such that $\{a,f^\mathfrak{M}(a),\left(f^\mathfrak{M}\right)^2(a),...\}$ is infinite. Then in an elementar extension $\mathfrak{M}'$ there is an element $b$ with $\mathfrak{M}'\vDash\forall z(R(z,a)\to R(z,b))$.

3) The class of $T$-ec structures is not elementary, so $T$ does not have a model companion.

1) Seems clear to me: $\{\exists a\exists b\exists z(R(z,a)\wedge\neg R(z,b)\wedge \neg f^n(a)\dot{=}b)\;|\;n\geq 0\}$ is independent of $T$ therefore realized in a sufficiently large model $\mathfrak{B}\vDash T$ and by $\mathfrak{M}$ being $T$-ec we may assume $\mathfrak{M}\subseteq\mathfrak{B}$. Therefore, we may assume that there is $a$ in $M$ and $b\notin\{a,f^\mathfrak{M}(a),\left(f^\mathfrak{M}\right)^2(a),...\}$ so that $\mathfrak{M}\vDash\exists z(R(z,a)\wedge\neg R(z,b))$.

2) Seems confusingly stated. Any $b\in\{a,f^\mathfrak{M}(a),\left(f^\mathfrak{M}\right)^2(a),...\}$ satisfies the formula. Assume that $b\notin\{a,f^\mathfrak{M}(a),\left(f^\mathfrak{M}\right)^2(a),...\}$ is intended for $\mathfrak{M}'$, then the theory $\{\forall a\exists b\forall z(\neg(R(z,a)\wedge\neg R(z,b))\wedge \neg f^n(a)\dot{=}b)\;|\;n\geq 0\}$ is always satisfied by $\mathfrak{M}$ and any sufficiently large $\mathfrak{M}'\succ\mathfrak{M}$ for $b\notin M$. (I am confused about whether I got the point here.)

3) Now I am not sure how to combine a) and b) correctly to deduce the last statement. I assume the $|\{a,f^\mathfrak{M}(a),\left(f^\mathfrak{M}\right)^2(a),...\}|\geq\aleph_0$ property for $\mathfrak{M}:=\mathfrak{M}_2$ from b) makes sure, that $\mathfrak{M}_2$ is $T$-ec as it then satisfies $T_\infty=\{\exists x_1\cdots\exists x_n\,\bigwedge_{i<j}\neg x_i\dot{=}x_j\;|\;n\geq 1\}$ which has to be satisfied in any $T$-ec structure.

I am thankful for any hint.

Answer 1

There is a typo in part (2) of the question, which you've correctly identified. But aside from that, you seem to have a lot of serious misconceptions. I've written some line-by-line feedback below, I hope it helps!

1) Seems clear to me: $\{\exists a\exists b\exists z(R(z,a)\wedge\neg R(z,b)\wedge \neg f^n(a)\dot{=}b)\;|\;n\geq 0\}$ is independent of $T$ therefore realized in a sufficiently large model $\mathfrak{B}\vDash T$...

The correct thing to say here is that this set of sentences is consistent with $T$. That means that the set is realized in some model of $T$. I'm not sure what the phrase "sufficiently large" is doing here.

...and by $\mathfrak{M}$ being $T$-ec we may assume $\mathfrak{M}\subseteq\mathfrak{B}$...

Why?

... Therefore, we may assume that there is $a$ in $M$ and $b\notin\{a,f^\mathfrak{M}(a),\left(f^\mathfrak{M}\right)^2(a),...\}$ so that $\mathfrak{M}\vDash\exists z(R(z,a)\wedge\neg R(z,b))$.

This is not what the set of sentences you wrote down above expresses. To say that $\mathfrak{B}\models \{\exists a\exists b\exists z(R(z,a)\wedge\neg R(z,b)\wedge \neg f^n(a)=b)\mid n\geq 0\}$ is to say that for every $n\geq 0$, there is some $a_n$, some $b_n$, and some $z_n$ such that $\mathfrak{B}\models (R(z_n,a_n)\wedge\neg R(z_n,b_n)\wedge \neg f^n(a_n)=b_n)$. But there's no reason why we should have $a_n = a_m$ when $n\neq m$. Also, you're supposed to show the existence of such a $z$ for any $a$ and any $b\notin \{f^n(a)\mid n\geq 0\}$.

Hint: You know $\mathfrak{M}$ is $T$-ec. You want to show it satisfies the existential formula $\exists z\, (R(z,a)\land \lnot R(a,b))$ with parameters from $\mathfrak{M}$. So all you have to do is find some model of $T$ extending $\mathfrak{M}$ which satisfies that formula...

2) Seems confusingly stated. Any $b\in\{a,f^\mathfrak{M}(a),\left(f^\mathfrak{M}\right)^2(a),...\}$ satisfies the formula. Assume that $b\notin\{a,f^\mathfrak{M}(a),\left(f^\mathfrak{M}\right)^2(a),...\}$ is intended for $\mathfrak{M}'$...

Correct, this condition should be written in the exercise.

...then the theory $\{\forall a\exists b\forall z(\neg(R(z,a)\wedge\neg R(z,b))\wedge \neg f^n(a)\dot{=}b)\;|\;n\geq 0\}$ is always satisfied by $\mathfrak{M}$ and any sufficiently large $\mathfrak{M}'\succ\mathfrak{M}$ for $b\notin M$. (I am confused about whether I got the point here.)

Your assertion about this theory is both false and irrelevant to what you want to show. Think about what it means for $\mathfrak{M}$ to individually satisfy each of the sentences you wrote down.

Hint: To actually solve this part of the exercise, look at the type $$p(y) = \{\forall z\, (R(z,a)\rightarrow R(z,y))\}\cup \{y\neq f^n(a)\mid n\geq 0\}.$$ Use the compactness theorem to realize this type in an elementary extension of $\mathfrak{M}$.

3) Now I am not sure how to combine a) and b) correctly to deduce the last statement. I assume the $|\{a,f^\mathfrak{M}(a),\left(f^\mathfrak{M}\right)^2(a),...\}|\geq\aleph_0$ property for $\mathfrak{M}:=\mathfrak{M}_2$ from b) makes sure, that $\mathfrak{M}_2$ is $T$-ec as it then satisfies $T_\infty=\{\exists x_1\cdots\exists x_n\,\bigwedge_{i<j}\neg x_i\dot{=}x_j\;|\;n\geq 1\}$ which has to be satisfied in any $T$-ec structure.

Are you saying that every infinite model of $T$ is $T$-ec? It's true that every $T$-ec structure satisfies $T_\infty$ (at least when $T$ has infinite models), but that doesn't mean the converse is true!

Hint: Suppose for contradiction that the class of $T$-ec models is elementary. Can you find a model $\mathfrak{M}$ which is $T$-ec and which contains an element $a$ such that $\{f^n(a)\mid n\geq 0\}$ is infinite? Then the model $\mathfrak{M}'$ from (2) is also $T$-ec (why?). Now do you see why (1) and (2) directly give you a contradiction?

Answer 2

Thank you so much for your effort! I try to do the proof

1) By definition we can embed $\mathfrak{M}$ into a $\mathfrak{A}\vDash T$. Construct $\mathfrak{M}'\supseteq\mathfrak{A}$ with $M'=A\cup\{c\}$ for $c\notin A$ so that $\mathfrak{M}'_{M'}\vDash R(c,a)\wedge\neg R(c,b)\wedge f(c)\dot{=}c$. Since $\{R(c,a)\wedge\neg R(c,b)\wedge f(c)\dot{=}c\}\cup T$ is a consistent $L(M')$-theory, we see that $\mathfrak{M}'$ is a model of $T$ and satisfies \begin{equation} \mathfrak{M}'_{M}\vDash \exists z(R(z,a)\wedge\neg R(z,b)). \end{equation} Since $a,b\in M$ and $\mathfrak{M}$ is $T$-e.a. and $\mathfrak{M}\subseteq\mathfrak{M'}$ we know that \begin{equation} \mathfrak{M}_{M}\vDash \exists z(R(z,a)\wedge\neg R(z,b)). \end{equation} 2) Since $|\mathfrak{M}|\geq \aleph_0$ by Löwenheim-Skolem for any cardinal $\kappa\geq\aleph_0$ there exists an elementary extension $\mathfrak{M}'$. The set of formulas (doesn't seem to be a type since it is not maximal) \begin{equation} p(x):=\{\forall z(R(z,a)\to R(z,x))\}\cup\{\neg x\dot{=}f^n(a)\;|\;n\in\mathbb{N}_0\} \end{equation} is finitely satisfable in $\mathfrak{M}$ (just by $f^m(a)$ for sufficiently big $m\in\mathbb{N}$ for any finite subset) and therefore in $\mathfrak{M}'$. By the formula version of compactness theorem (Lemma 2.2.7.) we know that $p(x)$ is satisfable in $\mathfrak{M}$ and $\mathfrak{M}'$. This means, that there is $b\in M'$ with $b\notin\{a,f^\mathfrak{M}(a),...\}$ so the $\mathfrak{M'}\vDash\forall z(R(z,a)\to R(z,b))$

3) Let class of $T$-ec structures by elementary with theory $T^*$. We pick a model $\mathfrak{A}\vDash T$ with $a\in A$ so that $|\{a,f^\mathfrak{M}(a),...\}|\geq\aleph_0$. By Lemma 3.2.11. I can embed $\mathfrak{A}$ into a $T$-ec structure $\mathfrak{B}$.

Now comes the step I am not sure about: As $T$ contains only a universal sentence. As there is a theory of $T$-ec structures(which by Theorem 3.2.14. is the Kaiser hull $T^{KH}=T^*$) all $T$-ec structures are models of $T_{\forall\exists}\supseteq T_\forall\supseteq T$, we know that $\mathfrak{B}\vDash T, \mathfrak{B}$ $T$-ec and we have an $a\in A\subseteq B$ with $|\{a,f^\mathfrak{M}(a),...\}|\geq \aleph_0$. By the 2) part we know that there is a $\mathfrak{B}'\succ \mathfrak{B}$( which is also $T$-ec by elementary equivalence) and $b'\in B'$ $b'\notin \{a,f^\mathfrak{M}(a),...\}$ so that \begin{equation} \mathfrak{B}_{B'}\vDash\neg\exists z(R(z,a)\wedge\neg R(z,b)) \end{equation} and by part 1) we have \begin{equation} \mathfrak{B}'_{B'}\vDash\exists z(R(z,a)\wedge\neg R(z,b)) \end{equation} which is the contradiction.