Here is the second part of Example $7)$ of Kechris' "Classical Descriptive Set Theory" (pp. $59-60$):

More generally, consider a structure $$\mathcal{A}=(A,(R_i)_{i\in I},(f_j)_{j\in J},(c_k)_{k\in K})$$ (in the sense of model theory) condisting of a set $A$, a family of relation $(R_i)_{i\in I}$, operations $(f_j)_{j\in J}$ and distinguished elements $(c_k)_{k\in K})$ on $A$. Assume $A$ is countably infinite. Let $Aut(\mathcal{A})$ be the group of automorphisms of $\mathcal{A}$. Thinking, without loss of generally, of $A$ as being $\mathbb{N}$, $Aut(\mathcal{A})$ is a closed subgroup of $S(\mathbb{N})$ group of permutations over $\mathbb{N}$.

I don't see how to prove that $Aut(\mathcal{A})$ is closed in $S(\mathbb{N})$.

Thank you in advance for your help.

  • 1
    $\begingroup$ What's the topology? $\endgroup$ – Thinking Torus Apr 14 at 0:21
  • 1
    $\begingroup$ It might be easier to think about proving that the complement of $\operatorname{Aut}(\mathcal A)$ is open in $S(\mathbb N)$. $\endgroup$ – bof Apr 14 at 0:43
  • 1
    $\begingroup$ @ThinkingTorus I guess $S(\mathbb N)$ is topologized as a subspace of $\mathbb N^\mathbb N$ with the Tychonoff product topology. So it has a subbase consisting of sets of the form $\{\alpha\in S(\mathbb N):\alpha(m)=n\}$. $\endgroup$ – bof Apr 14 at 0:49
  • $\begingroup$ The topology is that of pointwise convergence. $A$ doesn't have to be countable for $\mathrm{Aut}(\mathcal{A})$ to be closed in $S(A)$. So I'd rather write "Think, in view of this loss of generality" :) $\endgroup$ – YCor Apr 14 at 14:06
  • $\begingroup$ Why separate those constants $c_k$ from the operations? A constant is just a 0-ary operation $\endgroup$ – YCor Apr 14 at 14:08

A permutation is an automorphism when it preserves the interpretations of all the basic relation, function, and constant symbols. But preserving the interpretation of the symbols is the same as not failing to preserve the symbols. So the idea is to check that "for every symbol in the language, for every possible way $\sigma$ could fail to preserve the symbol, $\sigma$ doesn't do that" is a closed condition.

More precisely: for any finite tuples $\overline{a}$ and $\overline{b}$ in $\mathbb{N}^k$, there is an open set $$U(\overline{a},\overline{b}) = \{\sigma\in S(\mathbb{N})\mid \sigma(\overline{a}) = \overline{b}\}.$$ It's complement is a closed set $$C(\overline{a},\overline{b}) = \{\sigma\in S(\mathbb{N})\mid \sigma(\overline{a}) \neq \overline{b}\}.$$

Now the set of automorphisms of the structure $\mathcal{A}$ with domain $\mathbb{N}$ is the intersection of the following closed sets:

  • For every $k$-ary relation symbol $R$ in the language, and for any pair of tuples $\overline{a}$ and $\overline{b}$ in $\mathbb{N}^k$ such that $\mathcal{A}\models R(\overline{a})\not\leftrightarrow R(\overline{b})$, the closed set $C(\overline{a},\overline{b})$.
  • For every $k$-ary function symbol $f$ in the language, for any pair of tuples $\overline{a}$ and $\overline{b}$ in $\mathbb{N}^k$, and for any element $d$ in $\mathbb{N}$ such that $\mathcal{A}\models d\neq f(\overline{b})$, the closed set $C(\overline{a}f^{\mathcal{A}}(\overline{a}),\overline{b}d)$.
  • For every constant symbol $c$ in the language, and for any element $b$ in $\mathbb{N}$ such that $\mathcal{A}\models c\neq b$, the closed set $C(c^\mathcal{A},b)$.

More efficiently (but less explicitly), we can show that $\text{Aut}(\mathcal{A})$ is closed in $S(\mathbb{N})$ by showing that its complement is open, i.e. for every $\sigma\in S(\mathbb{N})\setminus \text{Aut}(\mathcal{A})$, $\sigma$ has an open neighborhood contained in $S(\mathbb{N})\setminus \text{Aut}(\mathcal{A})$.

Well, if $\sigma$ fails to be an automorphism, this is already witnessed by some finite tuple $\overline{a}$, in the sense there is some symbol in the language such that $\sigma$ fails to preserve this symbol because it maps $\overline{a}$ to $\overline{b} = \sigma(\overline{a})$. Then any permutation of $\mathbb{N}$ that maps $\overline{a}$ to $\overline{b}$ will fail to be an automorphism, so $U(\overline{a},\overline{b})$ is an open neighborhood of $\sigma$ in $S(\mathbb{N})\setminus \text{Aut}(\mathcal{A})$, as desired.

  • $\begingroup$ First of all, thank you for the answer. Secondly, I have tried to work out the details in order to prove the closedness of such "$3$ kinds of sets", but I didn't succeed. For instance, if $R$ is a $k$-ary relation, following your idea, I want to show that $\{\sigma\in S(\Bbb{N})\mid \text{$\sigma$ preserves $R$}\}$ is closed in $S(\Bbb{N})$. But $\sigma$ preserves $R$ iff $\forall \overline{a}\in\Bbb{N}^k$ we have $\overline{a}\in R\iff\sigma(\overline{a})\in R$ and I simply don't see why it is closed... What is wrong/I miss? I apologize for the elementary explanation I need. $\endgroup$ – LBJFS Apr 17 at 15:42
  • $\begingroup$ @LBJFS (1) Do you agree that the set I called $C(\overline{a},\overline{b})$ is closed? (2) The observation is that can rephrase "$\sigma$ preserves $R$" as $\forall \overline{a},\overline{b}\in \mathbb{N}^k\, ((\overline{a}\in R\not\leftrightarrow \overline{b}\in R)\rightarrow \sigma(\overline{a})\neq \overline{b})$. This is $\bigcap C(\overline{a},\overline{b})$, where the intersection is over all tuples $\overline{a}$ and $\overline{b}$ such that $(\overline{a}\in R\not\leftrightarrow \overline{b}\in R)$. $\endgroup$ – Alex Kruckman Apr 17 at 15:44
  • $\begingroup$ I've also added another explanation to the end of the answer, in case you find that one easier to follow. $\endgroup$ – Alex Kruckman Apr 17 at 15:49
  • $\begingroup$ $(1)$ $C(\overline{a},\overline{b})$ is closed by definition of product topology, as you stated in your answer and I understand that. But I don't see why $(2)$ holds $\endgroup$ – LBJFS Apr 17 at 15:50
  • 1
    $\begingroup$ @LBJFS That's ok! The formula I wrote is equivalent to $\forall \overline{a}, \overline{b}\in \mathbb{N}^k\, ((\sigma(\overline{a}) = \overline{b}) \rightarrow (\overline{a}\in R\leftrightarrow \overline{b}\in R))$, which is equivalent to $\forall \overline{a} (\overline{a}\in R \leftrightarrow \sigma(\overline{a})\in R)$, which is the definition of $\sigma$ preserving $R$. $\endgroup$ – Alex Kruckman Apr 17 at 16:00

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.