On computable formal concepts in computable formal contexts

We introduce and study the notions of computable formal context and computable formal concept. We give some examples of computable formal contexts in which the computable formal concepts fail to form a lattice and study the complexity aspects of formal concepts in computable contexts. In particular, we give some sufficient conditions under which the computability or noncomputability of a formal concept could be recognized from its lattice-theoretic properties. We prove the density theorem showing that in a Cantor-like topology every formal concept can be approximated by computable ones. We also show that not all formal concepts have lattice-theoretic approximations as suprema or infima of families of computable formal concepts.     

On Classifying Subsets of Natural Numbers by Their Computable Permutations

We introduce some alternative definitions of the concept of computable automorphism of a set of natural numbers. We study their relationships and investigate whether some classes of sets having isomorphic groups of automorphisms coincide with other classes of sets usual in computability. Finally, we show that the classification of sets by these groups of automorphisms is nontrivial.     

On a Hierarchy of Groups of Computable Automorphisms

Basics and results on groups of computable automorphisms are collected in [1].We recall the main definitions. A computable model $$\mathfrak{M} = \langle A,f_0^{n_0 } ,...;P_0^{m_0 } ,...\rangle $$ is a model in which A is a computable subset of the set ! of natural numbers, the mappings i 7! ni(the number of arguments of fi) and i ? mi (the number of arguments of Pi) are computable, andall operations fi and predicates Pi are computable uniformly in i. A computable automorphism ofa computable model M is an automorphism of $\mathfrak{M}$ which is a computable function on its universe. Allsuch automorphisms form a group denoted by Autc $\mathfrak{M}$ .     

The general and special superalgebras of formal vectorfields

The natural filtrations of the general algebra W and the special algebra S of formal vectorfields are proved to be invariant. Furthermore, the automorphism groups of W and S are proved to be isomorphic to the corresponding admissible automorphism groups of the base superalgebra U. Then the automorphisms of W or 5 can be induced by the continue automorphisms of U.     

Boolean Algebras with Finite Families of Computable Automorphisms

We prove that each computable Boolean algebra has a computable presentation in which for every computable family of automorphisms the set of atoms moved by at least one of its members is finite. This implies that each computable atomic Boolean algebra has a computable presentation in which its every computable family of automorphisms is finite. The priority argument is not used in the proof.     

Automorphism Groups of Computably Enumerable Predicates

We study automorphism groups of two important predicates in computability theory: the predicate W_y and the graph of a universal partially computable function. It is shown that all automorphisms of the predicates in question are computable. The actions of the automorphism groups on some index sets are examined, and we establish a number of results on the structure of these. We also look into homomorphisms of the two predicates. In this case the situation changes: all homomorphisms of the universal function are computable, but in each Turing degree, homomorphisms of W_y exist.     

自由正交模格FMOk(n)的自同构群

文章先利用自同构映射保有限并的性质研究了一般正交模格的次直积的自同构群与自同构群的次直积的关系,再用块置换的方法研究了MOk的自同构群的生成元集,由此得到自由正交模格FMOk(n)的自同构群的直积分解式,从而完全解决了FMOk(n)的自同构群的结构问题.     

Some constructions on the class of groups of computable automorphisms

We show that the computable inverse limit of a computable family of computable groups, the computable wreath product of a group of computable automorphisms and a computable group, as well as the commutant and center of every computable group can be realized as groups of computable automorphisms of suitable computable models.     

On Homeomorphisms of Effective Topological Spaces

We study effective presentations and homeomorphisms of effective topological spaces. By constructing a functor from the category of computable models into the category of effective topological spaces, we show in particular that there exist homeomorphic effective topological spaces admitting no hyperarithmetical homeomorphism between them and there exist effective topological spaces whose autohomeomorphism group has the cardinality of the continuum but whose only hyperarithmetical autohomeomorphism is trivial. It is also shown that if the group of autohomeomorphisms of a hyperarithmetical topological space has cardinality less than 2 then this group is hyperarithmetical. We introduce the notion of strong computable homeomorphism and solve the problem of the number of effective presentations of T ₀-spaces with effective bases of clopen sets with respect to strong homeomorphisms.     

On a Hierarchy of Groups of Computable Automorphisms

Basics and results on groups of computable automorphisms are collected in [1].We recall the main definitions. A computable model

Automorphisms with only infinite orbits on non-algebraic elements

 This paper generalizes results of F. K?rner from [4] where she established the existence of maximal automorphisms (i.e. automorphisms moving all non-algebraic elements). An ω-maximal automorphism is an automorphism whose powers are maximal automorphisms. We prove that any structure has an elementary extension with an ω-maximal automorphism. We also show the existence of ω-maximal automorphisms in all countable arithmetically saturated structures. Further we describe the pairs of tuples (ˉa,ˉb) for which there is an ω-maximal automorphism mapping ˉa to ˉb. Received: 12 December 2001 / Published online: 10 October 2002 Supported by the ``Fonds pour la Formation à la Recherche dans l'Industrie et dans l'Agriculture' Mathematics Subject Classification (2000): Primary: 03C50; Secondary: 03C57 Key words or phrases: Automorphism – Recursively saturated structure     

Metric ends,fibers and automorphisms of graphs

Several results on the action of graph automorphisms on ends and fibers are generalized for the case of metric ends. This includes results on the action of the automorphisms on the end space, directions of automorphisms, double rays which are invariant under a power of an automorphism and metrically almost transitive automorphism groups. It is proved that the bounded automorphisms of a metrically almost transitive graph with more than one end are precisely the kernel of the action on the space of metric ends. (© 2007 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

The Order of Automorphisms of Quasigroups

We prove quadratic upper bounds on the order of any autotopism of a quasigroup or Latin square, and hence also on the order of any automorphism of a Steiner triple system or 1‐factorization of a complete graph. A corollary is that a permutation σ chosen uniformly at random from the symmetric group will almost surely not be an automorphism of a Steiner triple system of order n, a quasigroup of order n or a 1‐factorization of the complete graph . Nor will σ be one component of an autotopism for any Latin square of order n. For groups of order n it is known that automorphisms must have order less than n, but we show that quasigroups of order n can have automorphisms of order greater than n. The smallest such quasigroup has order 7034. We also show that quasigroups of prime order can possess autotopisms that consist of three permutations with different cycle structures. Our results answer three questions originally posed by D.  Stones.     

Hyperarithmetical Boolean Algebras with a Distinguished Ideal

We prove a general theorem that allows us to pass from a hyperarithmetical Boolean algebra with a distinguished ideal to some computable Boolean algebra connected with the former by natural algebraic operations. Some examples are given.     

Three-Dimensional Classical Groups Acting on Polytopes

Let V be a three-dimensional vector space over a finite field. We show that any irreducible subgroup of GL(V) that arises as the automorphism group of an abstract regular polytope preserves a nondegenerate symmetric bilinear form on V. In particular, the only classical groups on V that arise as automorphisms of such polytopes are the orthogonal groups.     

Spectral automorphisms in CB-effect algebras

Spectral automorphisms have been introduced in [IVANOV, A.—CARAGHEORGHEOPOL, D.: Spectral automorphisms in quantum logics, Internat. J. Theoret. Phys. 49 (2010), 3146–3152]_in an attempt to construct, in the abstract framework of orthomodular lattices, an analogue of the spectral theory in Hilbert spaces. We generalize spectral automorphisms to the framework of effect algebras with compression bases and study their properties. Characterizations of spectral automorphisms as well as necessary conditions for an automorphism to be spectral are given. An example of a spectral automorphism on the standard effect algebra of a finite-dimensional Hilbert space is discussed and the consequences of spectrality of an automorphism for the unitary Hilbert space operator that generates it are shown. The last section is devoted to spectral families of automorphisms and their properties, culminating with the formulation and proof of a Stone type theorem (in the sense of Stone’s theorem on strongly continuous one-parameter unitary groups — see, e.g. [REED, M.#x2014;SIMON, B.: Methods of Modern Mathematical Physics, Vol. I, Acad. Press, New York, 1975]) for a group of spectral automorphisms.     

Automorphisms of Formal Matrix Algebras

We consider the automorphisms of formal matrix algebras over a given commutative ring. In some cases the automorphism group of these algebras is a semidirect product of certain subgroups whose structure is known.     

The structure of skew products with ergodic group automorphisms

We prove that ergodic automorphisms of compact groups are Bernoulli shifts, and that skew products with such automorphisms are isomorphic to direct products. We give a simple geometric demonstration of Yuzvinskii’s basic result in the calculation of entropy for group automorphisms, and show that the set of possible values for entropy is one of two alternatives, depending on the answer to an open problem in algebraic number theory. We also classify those algebraic factors of a group automorphism that are complemented.     

Σ-Definability of countable structures over real numbers, complex numbers, and quaternions

We study Σ-definability of countable models over hereditarily finite {ie193-01} superstructures over the field ℝ of reals, the field ℂ of complex numbers, and over the skew field ℍ of quaternions. In particular, it is shown that each at most countable structure of a finite signature, which is Σ-definable over {ie193-02} with at most countable equivalence classes and without parameters, has a computable isomorphic copy. Moreover, if we lift the requirement on the cardinalities of the classes in a definition then such a model can have an arbitrary hyperarithmetical complexity, but it will be hyperarithmetical in any case. Also it is proved that any countable structure Σ-definable over {ie193-03}, possibly with parameters, has a computable isomorphic copy and that being Σ-definable over {ie193-04} is equivalent to being Σ-definable over {ie193-05}. Supported by RFBR-DFG, grant No. 06-01-04002 DFGa. __________ Translated from Algebra i Logika, Vol. 47, No. 3, pp. 335–363, May–June, 2008.