I have the following assignment question: Let $M$ be an $L$-model of cardinality $\kappa$. Assume $M$ is saturated. How can you show that $|\text{Aut}(M)|=2^{|M|}$?

I see two possible ideas/connections/intuitions here:

  1. Definable sets. Since $M$ is saturated, these are either finite or of cardinality $\kappa$. Then maybe you can somehow use the fact that these are preserved by automorphisms?

  2. Maybe some sort of diagonal argument. If you try to capture $\text{Aut}(M)$ with $\lambda<2^{|M|}$ automorphisms, then you can show that you'll be missing at least one.

There's this question, whose title was originally going to be my title, but I wanted to avoid confusion. While it doesn't really answer my question, perhaps the idea of moving non-definable points via automorphisms could yield the required cardinality for $\text{Aut}(M)$. I imagine using the finite definable sets (I believe these are called algebraic, but correct me if I'm wrong), and "permutating" the points outside of these sets? Then perhaps it becomes an easy cardinality argument...

I'm mostly thinking out loud, as I'm not sure how to make all of these ideas concrete, and I'm not even sure if they are on the right path. Help?

  • $\begingroup$ I think you can take an indiscernible sequence of length $\kappa$ and show that any increasing function from $\kappa$ to $\kappa$ yields an automorphism of $M$ which acts on $I$ according to the increasing function. I'm not sure about the technicals right now, though. $\endgroup$ – tomasz May 15 '13 at 0:30
  • $\begingroup$ @tomasz Makes sense, I'll try thinking about this approach. Two questions, perhaps related: why is saturation needed? How could you get such a long indiscernible sequence? (I'm not too familiar with indiscernibles, but I remember something called the Standard Lema?) $\endgroup$ – FPP May 15 '13 at 18:15
  • $\begingroup$ You can find arbitrarily long finite indiscernible sequences by Ramsey's theorem, and then by compactness and saturation you get one of length equal to the saturation number. $\endgroup$ – tomasz May 15 '13 at 21:09

I decided to write up an answer, so that this question can be removed form the list of unanswered questions.

First enumerate $M = \{m_\alpha : \alpha < \kappa\}$. For every $s \in 2^{<\kappa}$ we construct a partial automorphism $f_s$. I.e. $f_s : M \to M$ is an elementary map. The idea is that these automorphisms extends one another ($t \subseteq s$ implies $f_t \subseteq f_s$) but $f_{s0}$ and $f_{s1}$ disagree on some element. In the end for $q \in 2^\kappa$ we define $f_q = \bigcup_{\alpha < \kappa} f_{q|_\alpha}$, which by the above is a well defined elementary map and $f_q \neq f_p$ for $q \neq p \in 2^\kappa$. We also throw in the back and forth condition to make $f_q$-s automorphisms.

More precisely

  • Let $f_\emptyset = \emptyset$.
  • If $\delta$ is a limit ordinal and $s \in 2^\delta$, let $f_s = \bigcup_{\alpha < \delta} f_{s|_\alpha}$
  • If $s \in 2^{\alpha+1}$ consider two cases. If $\alpha$ is an even ordinal, then pick $m \in M$ of minimal index not in the domain of $f_{s|_\alpha}$. By saturation pick $n_0, n_1$ in $M$ such that $f_{si} = f_s \cup \{\langle m, n_i \rangle\}$ are elementary. If $\alpha$ is an odd ordinal, go back in a similar way. I.e. pick $n \in M$ with the least index not in the image of $f_{s|_\alpha}$ and find two distinct element to extend $f_{s|_\alpha}$ with.
  • $\begingroup$ Could you please explain the part "By saturation pick $n_0,n_1$ in $M$ such that $f_{si}$=$f_{s}\cup\{<m,n_i>\}$ are elementary". How saturation gives us that there are 2 such n's ? thanks $\endgroup$ – Binyamin Riahi Apr 9 '20 at 19:58

We assume $\mathsf{AC}$.

Let $\kappa=|M|$. Let $(I,<)$ be a linear order of size $\kappa$ such that for any $x,y\in I$ with $x<y$ we have $|(x,y)|=\kappa$, we call such order a $\kappa$-dense linear order; the existence of such an order can be shown using the fact that $\kappa\cdot\kappa=\kappa$ under $\mathsf{AC}$. Fix $A\subseteq I$ of size $\kappa$ such that its complement is $\kappa$-dense in $(I,<)$, that is, whenever $x,y\in I$ with $x<y$, then $|(x,y)\cap A^c|=\kappa$.

First we prove:

$\mathbf{Proposition \ 1.}$ Let $\mathcal M$ be a saturated structure of size $\kappa$ with an indiscernible sequence $(a_i)_{i\in I}$, with $(I,<)$ as above, then $|Aut(\mathcal M)|=2^\kappa$.

$\mathbf{Proof:}$ Let us prove that any increasing function $f:(a_i)_{i\in A}\rightarrow (a_i)_{i\in A}$; $A$ defined above, can be extended to some $\hat f\in Aut(\mathcal M)$. Let us construct $\hat f$ using back-and-forth, fix an enumeration $M=\{b_\alpha:\alpha<\kappa\}$. $\hat f$ will be constructed in such a way that for any $\alpha<\kappa$, if $A_{\alpha}$ is the set of all elements $b\in M$ for which $\hat f(b)$ has been defined before step $\alpha$, then $\hat f(b_{\alpha})$ realizes $\hat f(\mathbf{tp}(b_{\alpha}/A_\alpha))=\{\varphi(x,\hat f(\bar a)):\varphi(x,\bar a)\in \mathbf{tp}(b_\alpha/A_\alpha)\},$ this will ensure $\hat f$ is an automorphism of $\mathcal M$, provided we make $\hat f$ onto.

Suppose we have defined $\hat f(b_{\beta})$ for all $\beta<\alpha$ for some $\alpha<\kappa$.

Suppose $b_{\alpha}\notin (a_i)_{i\in A}$. As $\mathcal M$ is saturated, there is some $a\in M$ such that $a$ realizes $\hat f(\mathbf{tp}(b_{\alpha}/A_\alpha))$. If $a\notin (a_i)_{i\in A}$, we put $\hat f(b_{\alpha})=a$. If $a=a_i'$ for some $i'\in A$, choose $j\in I\setminus A$ such that $j$ is ordered with respect to $\{i:a_i\in A_{\alpha}\}$ the same way $i'$ is ordered with respect to $\{i:a_i\in A_{\alpha}\}$; $A^c$ is $\kappa$-dense in $(I,<)$, then clearly $a_j$ realizes $\hat f(\mathbf{tp}(b_{\alpha}/A_\alpha))$, so we put $\hat f(b_{\alpha})=a_j$.

If $b_{\alpha}\in (a_i)_{i\in A}$, we simply put $\hat f(b_{\alpha})=f(b_\alpha)$, then $\hat f(b_\alpha)$ realizes $\hat f(\mathbf{tp}(b_{\alpha}/A_\alpha))$ because of the assumptions on $(a_i)_{i\in I}$ and $f$, and the inductive hypothesis.

Now suppose $b_\beta$ has a preimage under $\hat f$ for all $\beta<\alpha$, for some $\alpha<\kappa$. We do a similar argument as above, taking care of extending $f$, to get a preimage for $b_{\alpha}$; considering $\hat f^{-1}(\mathbf{tp}(b_{\alpha}/f[A_\alpha]))=\{\varphi(x,\bar(a)):\varphi(x,f(\bar a))\in \mathbf{tp}(b_{\alpha}/f[A_\alpha])\}$ instead of $\hat f(\mathbf{tp}(b_\alpha/A_\alpha))$. This makes $\hat f$ onto.

Thus by transfinite induction we obtain $\hat f\in Aut(\mathcal M)$ such that $\hat f$ extends $f$. As there are $2^{\kappa}$ many increasing $f:(a_i)_{i\in A}\rightarrow (a_i)_{i\in A}$, it follows that $|Aut(\mathcal M)|=2^{\kappa}$.

Now let us prove that such sequence $(a_i)_{i\in I}$ exists in any saturated $\mathcal M$.

$\mathbf{Proposition \ 2.}$ Let $\mathcal M$ be a saturated structure of size $\kappa$ and $\mathbb I=(I,<)$ a $\kappa$-dense linear order of size $\kappa$, then $\mathcal M$ contains a sequence of indiscernibles $(a_i)_{i\in \mathbb I}$.

$\mathbf{Proof:}$ Let $L$ be the language of $\mathcal M$. Using Ramsey's Theorem and the compactness theorem it can be shown that there is a model $\mathcal N$ in the language $L$ such that $\mathcal N$ is elementary equivalent to $\mathcal M$ and has a sequence of indiscernibles $(a_i)_{i\in \mathbb I}$; this is lemma 15.3. on this book. Let $g:\kappa\rightarrow I$ be a bijection, then $(a_i)_{i\in \mathbb I}=\{a_{g(i)}:i<\kappa\}$

Let us construct a sequence $(c_i)_{i<\kappa}$ in $M$ by induction on $i$:

As $\mathcal N\equiv \mathcal M$ and $\mathcal M$ is saturated, there exists $c_0\in M$, such that $c_0$ realizes $\mathbf{tp}(a_{g(0)})$ in $\mathcal M$. If $c_\beta$ has been constructed for all $\beta<\alpha$ for some $0<\alpha<\kappa$, let $c_{\alpha}\in M$ be such that $c_\alpha$ realizes $\{\varphi(x,c_{i_0},\ldots,c_{i_n}):\varphi(x,c_{g(i_0)},\ldots,c_{g(i_n)})\in \mathbf{tp}(a_{g(\alpha)}/\{a_{g(i)}:i<\alpha\})\}$. Then $\{c_{g^{-1}(i)}:i\in \mathbb I\}$ is a sequence of indiscernibles in $\mathcal M$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.