On computable automorphisms in formal concept analysis (Q606025)

A formal context, see [\textit{B. Ganter} and \textit{R. Wille}, Formal concept analysis. Berlin: Springer (1999; Zbl 0909.06001)], is a triple \({\mathcal F}=\langle G,M,\models\rangle\), where \(\models \,\subseteq G\times M\). Intuitively, \(G\) and \(M\) mean the set of objects and the set of their properties respectively and \(g\models m\) means that \(g\) has the property \(m\). Every formal context \(\langle G,M,\models\rangle\) can be considered as a classical model-theoretic structure \(\langle G\cup M;W,\models\rangle\), where \(W\) is a unary predicate distinguishing \(G\). Thus many concepts in model theory are applicable to the formal contexts. The author considers groups of automorphisms of formal contexts, especially groups of effective automorphisms of effectively given formal contexts. In this case, effectiveness means computability or hyperarithmeticity. A general method of transforming results on the auto\-mor\-phisms of computable structures into results on the automorphisms of computable formal contexts is proposed. Using this method, the author proves that the abstract class of groups of (computable) automorphisms of computable structures coincides with the abstract class of groups of (computable) automorphisms of computable formal contexts. It is proved that there is a formal context \(\mathcal F\) that has a nontrivial automorphism but each hyperarithmetical formal context \({\mathcal F}'\) isomorphic to \(\mathcal F\) has no nontrivial hyperarithmetical automorphism. There exist two isomorphic computable formal contexts \({\mathcal F}_0\) and \({\mathcal F}_1\) such that \({\mathcal F}_0\) has a nontrivial computable automorphism but \({\mathcal F}_1\) has not.