Algebra univers. 60 (2009) 365–367 0002-5240/09/030365 – 03, published online March 16, 2009 DOI 10.1007/s00012-009-2109-1 c Birkh¨ ° auser Verlag, Basel, 2009
Algebra Universalis Mailbox
A Cayley theorem for distributive lattices ¨nger Ivan Chajda and Helmut La Abstract. A Cayley-like representation theorem for distributive lattices is proved.
Cayley’s Theorem provides a well-known representation of groups by means of certain unary functions (the so-called permutations) with composition as its binary operation. For Boolean algebras, a representation via binary functions (the so´ called guard functions) was settled by Bloom, Esik and Manes ([2], see also [1]). A similar approach was used by the first author for the so-called q-algebras (cf. [3]). In this note we will present a representation of distributive lattices by a different type of binary functions. First we define an algebra in which we will embed the distributive lattices. 2
Definition 1. For every set M , let F(M ) denote the algebra (M M , ⋄, ∗) of type (2, 2) defined by (f ⋄ g)(x, y) := f (g(x, y), y) and (f ∗ g)(x, y) := f (x, g(x, y)) for all 2 f, g ∈ M M and x, y ∈ M . F(M ) is not a lattice, but we can prove the following weaker fact: Lemma 2. ⋄ and ∗ are associative. 2
Proof. For all f, g, h ∈ M M and x, y ∈ M , ((f ⋄ g) ⋄ h)(x, y) = (f ⋄ g)(h(x, y), y) = f (g(h(x, y), y), y) = f ((g ⋄ h)(x, y), y) = (f ⋄ (g ⋄ h))(x, y) and ((f ∗ g) ∗ h)(x, y) = (f ∗ g)(x, h(x, y)) = f (x, g(x, h(x, y))) = f (x, (g ∗ h)(x, y)) = (f ∗ (g ∗ h))(x, y).
¤ 2
Next, for every lattice with base set L we define a mapping ϕ from L to LL . Presented by E. T. Schmidt. Received May 23, 2007; accepted in final form February 20, 2008. 2000 Mathematics Subject Classification: Primary: 06D05. Key words and phrases: distributive lattice, representation, binary function, composition of functions. Support of the research of the first author by the Czech Government Research Project MSM 6198959214 is gratefully acknowledged. 365
366
I. Chajda and H. L¨ anger
Algebra univers.
Definition 3. For every lattice (L, ∨, ∧) and every a ∈ L, let fa denote the mapping 2 (x, y) 7→ (a ∨ x) ∧ y from L2 to L and ϕ the mapping a 7→ fa from L to LL . Now we can state and prove our main result: Theorem 4. For every distributive lattice L = (L, ∨, ∧), the mapping ϕ is an embedding of L into F(L). Proof. Let (L, ∨, ∧) be a distributive lattice. Then, for all a, b, x, y ∈ L, fa∨b (x, y) = (a ∨ b ∨ x) ∧ y = (a ∧ y) ∨ (b ∧ y) ∨ (x ∧ y) = (a ∧ y) ∨ ((b ∨ x) ∧ y) = (a ∨ ((b ∨ x) ∧ y)) ∧ y = fa (fb (x, y), y) = (fa ⋄ fb )(x, y), and fa∧b (x, y) = ((a ∧ b) ∨ x) ∧ y = (a ∨ x) ∧ (b ∨ x) ∧ y = fa (x, fb (x, y)) = (fa ∗ fb )(x, y), and fa = fb implies a = (a ∨ b) ∧ a = fa (b, a) = fb (b, a) = (b ∨ b) ∧ a = b ∧ a = a ∧ b = (a ∨ a) ∧ b = fa (a, b) = fb (a, b) = (b ∨ a) ∧ b = b. Hence ϕ is an injective homomorphism from L to F(L).
¤
That, for a distributive lattice (L, ∨, ∧), the algebra (ϕ(L), ⋄, ∗) is a lattice follows from a more general result. In order to be able to formulate this result in a concise way we make the following definition: Definition 5. We call a subuniverse A of F(M ) full if, for all f, g ∈ A and x, y, z, u ∈ M , (i) f (x, x) = x, (ii) f (g(x, y), g(z, u)) = g(f (x, z), f (y, u)) and (iii) f (f (x, g(x, y)), y) = f (x, f (g(x, y), y)) = f (x, y). Now we can prove Theorem 6. If A is a full subuniverse of F(M ), then (A, ⋄, ∗) is a lattice. Proof. Let A be a full subuniverse of F(M ). Then, for all f, g ∈ A and x, y ∈ M , (f ⋄ g)(x, y) = f (g(x, y), y) = f (g(x, y), g(y, y)) = g(f (x, y), f (y, y)) = g(f (x, y), y) = (g ⋄ f )(x, y), (f ∗ g)(x, y) = f (x, g(x, y)) = f (g(x, x), g(x, y)) = g(f (x, x), f (x, y)) = g(x, f (x, y)) = (g ∗ f )(x, y), (f ⋄ (f ∗ g))(x, y) = f ((f ∗ g)(x, y), y) = f (f (x, g(x, y)), y) = f (x, y), and (f ∗ (f ⋄ g))(x, y) = f (x, (f ⋄ g)(x, y)) = f (x, f (g(x, y), y)) = f (x, y). The rest follows from Lemma 2.
¤
Vol. 60, 2009
A Cayley theorem for distributive lattices
367
That, for a distributive lattice (L, ∨, ∧), the algebra (ϕ(L), ⋄, ∗) is a lattice now follows from Theorem 7. If L = (L, ∨, ∧) is a distributive lattice, then ϕ(L) is a full subuniverse of F(L) and hence (ϕ(L), ⋄, ∗) is a lattice. Proof. Let (L, ∨, ∧) be a distributive lattice. Then, for all a, b, x, y, z, u ∈ L, fa (x, x) = (a ∨ x) ∧ x = x, fa (fb (x, y), fb (z, u)) = (a ∨ ((b ∨ x) ∧ y)) ∧ (b ∨ z) ∧ u = (a ∨ b ∨ x) ∧ (a ∨ y) ∧ (b ∨ z) ∧ u = (a ∨ b ∨ x) ∧ (b ∨ z) ∧ (a ∨ y) ∧ u = = (b ∨ ((a ∨ x) ∧ z)) ∧ (a ∨ y) ∧ u = fb (fa (x, z), fa (y, u)), fa (fa (x, fb (x, y)), y) = (a ∨ ((a ∨ x) ∧ (b ∨ x) ∧ y)) ∧ y = (a ∨ x) ∧ (a ∨ b ∨ x) ∧ (a ∨ y) ∧ y = (a ∨ x) ∧ y = fa (x, y), and fa (x, fa (fb (x, y), y)) = (a ∨ x) ∧ (a ∨ ((b ∨ x) ∧ y)) ∧ y = (a ∨ x) ∧ (a ∨ b ∨ x) ∧ (a ∨ y) ∧ y = (a ∨ x) ∧ y = fa (x, y). The rest follows from the proof of Theorem 4 and from Theorem 6.
¤
References ´ [1] S. L. Bloom and Z. Esik, Cayley iff Stone, Bull. EATCS 43 (1991), 159–161. ´ [2] S. L. Bloom, Z. Esik and E. G. Manes, A Cayley theorem for Boolean algebras, Amer. Math. Monthly 97 (1990), 831–833. [3] I. Chajda, A representation of the algebra of quasiordered logic by binary functions, Demonstratio Math. 27 (1994), 601–607. Ivan Chajda Palack´ y University Olomouc, Department of Algebra and Geometry, Tomkova 40, 77900 Olomouc, Czech Republic e-mail:
[email protected] ¨nger Helmut La Vienna University of Technology, Institute of Discrete Mathematics and Geometry, Wiedner Hauptstraße 8–10, 1040 Vienna, Austria e-mail:
[email protected]
