Affine completeness of the algebra of full binary trees
- PDF / 322,097 Bytes
- 9 Pages / 439.37 x 666.142 pts Page_size
- 8 Downloads / 183 Views
Algebra Universalis
Affine completeness of the algebra of full binary trees Andr´e Arnold, Patrick C´egielski, Serge Grigorieff and Ir`ene Guessarian To the memory of Kate Karagueuzian-Gibbons and Giliane Arnold. Abstract. A function on an algebra is congruence preserving if, for any congruence, it maps pairs of congruent elements onto pairs of congruent elements. We show that on the algebra of full binary trees whose leaves are labeled by letters of an alphabet containing at least three letters, a function is congruence preserving if and only if it is polynomial. This exhibits an example of a non commutative and non associative 1–affine complete algebra. As far as we know, it is the first example of such an algebra. Mathematics Subject Classification. 06A99, 08A30, 08B20. Keywords. Congruence, Affine completeness, Full binary trees.
1. Introduction A function on an algebra is congruence preserving if, for any congruence, it maps pairs of congruent elements onto pairs of congruent elements. Such functions were introduced in Gr¨ atzer [4], where they are said to have the “substitution property”. A polynomial function on an algebra is a function defined by a term of the algebra using variables, constants and the operations of the algebra. Obviously, every polynomial function is congruence preserving. In most algebras this inclusion is strict. A very simple example where the inclusion is strict is the additive algebra of natural integers N, +, cf. [1]. Up to the example studied in [2], all affine complete algebras studied so far were commutative and associative, see [3,7,5,9]. The example in [2] is the free monoid on an alphabet Presented by M. Haviar. 0123456789().: V,-vol
55
Page 2 of 9
A. Arnold et al.
Algebra Univers.
with at least three letters: its operation is non commutative but associative. The present paper is a follow-up of [2] though it does not depend on it. We here prove that the free algebra with one binary operation and at least three generators is 1–affine complete, i.e., every unary function preserving congruences is polynomial. This gives a nontrivial example of a non associative and non commutative 1–affine complete algebra.
2. Preliminary definitions For an algebra A with domain A, a congruence ∼ on A is an equivalence relation on A which is compatible with the operations of A. Lemma 2.1. Let A = A , , B = B , ∗ be two algebras with binary operations and ∗, and θ : A → B a homomorphism. Then ∼θ defined on A by x ∼θ y iff θ(x) = θ(y) is a congruence called the kernel ker(θ) of θ. Definition 2.2. Let Σ be a nonempty alphabet whose elements are called letters. The free monoid generated by Σ is the algebra Σ∗ , ·. Its elements are the finite sequences (or words) of elements from Σ. It is endowed with the concatenation operation and the unit element is the empty word denoted by ε. The free monoid will be abbreviated as Σ∗ in the sequel. The length of a word w ∈ Σ∗ is the total number of occurrences of letters in w and it is denoted |w|. As usual Σ+ denotes the set Σ∗ \ {ε}. Definition 2.3. Let Γ be a sub
Data Loading...
