Curs 2
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View Curs 2 as PDF for free.
More details
- Words: 3,718
- Pages: 38
n−ary operations on a set. Universal algebras
Definition Let A be an arbitrary set and n ∈ N. A function ω : An −→ A is called n-ary operation on the set A. The number n is called the arity or the type of the operation ω.
Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
1 / 21
n−ary operations on a set. Universal algebras
Definition Let A be an arbitrary set and n ∈ N. A function ω : An −→ A is called n-ary operation on the set A. The number n is called the arity or the type of the operation ω. If B ⊆ An , a function ω : B −→ A is called partial n-ary operation on the set A, with the domain B.
Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
1 / 21
n−ary operations on a set. Universal algebras
Definition Let A be an arbitrary set and n ∈ N. A function ω : An −→ A is called n-ary operation on the set A. The number n is called the arity or the type of the operation ω. If B ⊆ An , a function ω : B −→ A is called partial n-ary operation on the set A, with the domain B.
Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
1 / 21
Example 1) A binary operation on a set A is a function ω : A × A −→ A : (a, b) 7−→ (a, b)ω , through which to any two elements of A one associates an element of A. Generally, in the case of binary operations, in stead of writing (a, b)+ or (a, b)· , we write a + b and a · b. 2) A unary operation on a set A is a function ω : A −→ A.
Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
2 / 21
Example 1) A binary operation on a set A is a function ω : A × A −→ A : (a, b) 7−→ (a, b)ω , through which to any two elements of A one associates an element of A. Generally, in the case of binary operations, in stead of writing (a, b)+ or (a, b)· , we write a + b and a · b. 2) A unary operation on a set A is a function ω : A −→ A. 3) A nullary operation on a nonempty set A is a function ω : A0 −→ A. Because A0 = A∅ = {∅ = (∅, A, ∅)} consists of a single element, ω is completely determined by the element (∅)ω ∈ A. A nullary operation may be identified for this reason with its corresponding image element.
Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
2 / 21
Example 1) A binary operation on a set A is a function ω : A × A −→ A : (a, b) 7−→ (a, b)ω , through which to any two elements of A one associates an element of A. Generally, in the case of binary operations, in stead of writing (a, b)+ or (a, b)· , we write a + b and a · b. 2) A unary operation on a set A is a function ω : A −→ A. 3) A nullary operation on a nonempty set A is a function ω : A0 −→ A. Because A0 = A∅ = {∅ = (∅, A, ∅)} consists of a single element, ω is completely determined by the element (∅)ω ∈ A. A nullary operation may be identified for this reason with its corresponding image element.
Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
2 / 21
Remark An n-ary operation ω defined on a set A determines an n + 1−ary relation on A, with the graph Gω = {(a1 , a2 , . . . , an , (a1 , a2 , . . . , an )ω )| ai ∈ A, i = 1, n} .
Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
3 / 21
Definition Let A be a set and Ω a set of operations defined on A. The pair (A, Ω) is called universal algebra with the operations domain Ω, or Ω−algebra. If Ω = {ω1 , ω2 , . . . , ωk }, we write (A, ω1 , ω2 , . . . , ωk ) in stead of (A, Ω).
Remark Any set may be considered a universal algebra with the operations domain Ω = ∅.
Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
4 / 21
Definition Let A be a set and Ω a set of operations defined on A. The pair (A, Ω) is called universal algebra with the operations domain Ω, or Ω−algebra. If Ω = {ω1 , ω2 , . . . , ωk }, we write (A, ω1 , ω2 , . . . , ωk ) in stead of (A, Ω).
Remark Any set may be considered a universal algebra with the operations domain Ω = ∅.
Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
4 / 21
Definition Let (A, Ω) be an universal algebra. The function τ : Ω −→ N, defined by (ω)τ = the arity of ω is called the type of the algebra (A, Ω).
Example Let M be a nonempty set. We can define on the set of parts of M the universal algebra (P(M), ∩, ∪, CM , ∅, M), whose type is ∩ ∪ CM ∅ M τ= . 2 2 1 0 0
Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
5 / 21
Definition Let (A, Ω) be an universal algebra. The function τ : Ω −→ N, defined by (ω)τ = the arity of ω is called the type of the algebra (A, Ω).
Example Let M be a nonempty set. We can define on the set of parts of M the universal algebra (P(M), ∩, ∪, CM , ∅, M), whose type is ∩ ∪ CM ∅ M τ= . 2 2 1 0 0
Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
5 / 21
Definition Let (A, Ω) be a universal algebra of type τ and B ⊆ A. If for any operation ω ∈ Ω and any elements b1 , b2 , . . . , b(ω)τ ∈ B it follows that (b1 , b2 , . . . , b(ω)τ )ω ∈ B, then B is called a subalgebra of (A, Ω). In this case we write B ≤Ω A or B ≤ A,
Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
6 / 21
Definition Let (A, Ω) be a universal algebra of type τ and B ⊆ A. If for any operation ω ∈ Ω and any elements b1 , b2 , . . . , b(ω)τ ∈ B it follows that (b1 , b2 , . . . , b(ω)τ )ω ∈ B, then B is called a subalgebra of (A, Ω). In this case we write B ≤Ω A or B ≤ A, and by S(A, Ω) we denote the set of all subalgebras of the universal algebra (A, Ω).
Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
6 / 21
Definition Let (A, Ω) be a universal algebra of type τ and B ⊆ A. If for any operation ω ∈ Ω and any elements b1 , b2 , . . . , b(ω)τ ∈ B it follows that (b1 , b2 , . . . , b(ω)τ )ω ∈ B, then B is called a subalgebra of (A, Ω). In this case we write B ≤Ω A or B ≤ A, and by S(A, Ω) we denote the set of all subalgebras of the universal algebra (A, Ω).
Remark 1) A ∈ S(A, Ω).
Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
6 / 21
Definition Let (A, Ω) be a universal algebra of type τ and B ⊆ A. If for any operation ω ∈ Ω and any elements b1 , b2 , . . . , b(ω)τ ∈ B it follows that (b1 , b2 , . . . , b(ω)τ )ω ∈ B, then B is called a subalgebra of (A, Ω). In this case we write B ≤Ω A or B ≤ A, and by S(A, Ω) we denote the set of all subalgebras of the universal algebra (A, Ω).
Remark 1) A ∈ S(A, Ω). 2) If Ω contains nullary operations, and B ≤Ω A, then B 6= ∅.
Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
6 / 21
Definition Let (A, Ω) be a universal algebra of type τ and B ⊆ A. If for any operation ω ∈ Ω and any elements b1 , b2 , . . . , b(ω)τ ∈ B it follows that (b1 , b2 , . . . , b(ω)τ )ω ∈ B, then B is called a subalgebra of (A, Ω). In this case we write B ≤Ω A or B ≤ A, and by S(A, Ω) we denote the set of all subalgebras of the universal algebra (A, Ω).
Remark 1) A ∈ S(A, Ω). 2) If Ω contains nullary operations, and B ≤Ω A, then B 6= ∅. 3) If Ω does not contain nullary operations, then ∅ ∈ S(A, Ω).
Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
6 / 21
Definition Let (A, Ω) be a universal algebra of type τ and B ⊆ A. If for any operation ω ∈ Ω and any elements b1 , b2 , . . . , b(ω)τ ∈ B it follows that (b1 , b2 , . . . , b(ω)τ )ω ∈ B, then B is called a subalgebra of (A, Ω). In this case we write B ≤Ω A or B ≤ A, and by S(A, Ω) we denote the set of all subalgebras of the universal algebra (A, Ω).
Remark 1) A ∈ S(A, Ω). 2) If Ω contains nullary operations, and B ≤Ω A, then B 6= ∅. 3) If Ω does not contain nullary operations, then ∅ ∈ S(A, Ω).
Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
6 / 21
Example Let M be a nonempty set and N ⊂ M. If Ω1 = {∩, ∪}, and Ω2 = {∩, ∪, CM }, then P(N) ≤Ω1 P(M), but P(N) 6≤Ω2 P(M).
Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
7 / 21
Definition Let (A1 , Ω1 ) be a universal algebra of type τ1 , (A1 , Ω1 ) a universal algebra of type τ1 , and θ : Ω1 −→ Ω2 a surjective function. We call the (A1 , Ω1 ) θ−similar to the algebra (A2 , Ω2 ) if the diagram θ
Ω1 −→ Ω2 τ1 & . τ2 N is commutative(i.e., θ · τ2 = τ1 ). The function θ is called similarity application.
Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
8 / 21
Remark 1) The surjective function θ : Ω1 −→ Ω2 is a similarity application if and only if for any ω ∈ Ω1 , the operations ω and (ω)θ have the same arity. 2) If (A1 , Ω1 ), (A2 , Ω2 ) and (A3 , Ω3 ) are universal algebras, and the functions θ : Ω1 −→ Ω2 and θ0 : Ω2 −→ Ω3 are similarity applications, then the function θ · θ0 : Ω1 −→ Ω3 is a similarity application.
Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
9 / 21
Remark 1) The surjective function θ : Ω1 −→ Ω2 is a similarity application if and only if for any ω ∈ Ω1 , the operations ω and (ω)θ have the same arity. 2) If (A1 , Ω1 ), (A2 , Ω2 ) and (A3 , Ω3 ) are universal algebras, and the functions θ : Ω1 −→ Ω2 and θ0 : Ω2 −→ Ω3 are similarity applications, then the function θ · θ0 : Ω1 −→ Ω3 is a similarity application.
Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
9 / 21
Definition Let (A1 , Ω1 ) and (A2 , Ω2 ) be two universal algebras of types τ1 and τ2 , such that there is a similarity function θ : Ω1 −→ Ω2 . A function f : A1 −→ A2 is called a θ−homomorphism of universal algebras(or, simply, θ−homomorphism) if for any operation ω ∈ Ω1 and any elements a1 , a2 , . . . , a(ω)τ1 ∈ A1 the following equality holds θ
((a1 , a2 , . . . , a(ω)τ1 )ω )f = ((a1 )f , (a2 )f , . . . , (a(ω)τ1 )f )(ω) . The function f is called θ−isomorphism if θ and f are bijective functions, f is a θ−homomorphism, and f −1 is a θ−1 −homomorphism. If there is a θ−isomorphism from the universal algebra (A1 , Ω1 ) to (A2 , Ω2 ), we say that (A1 , Ω1 ) is isomorphic to (A2 , Ω2 ), and we write (A1 , Ω1 ) ∼ = (A2 , Ω2 ), or A1 ∼ = A2 .
Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
10 / 21
Definition Let (A1 , Ω1 ) and (A2 , Ω2 ) be two universal algebras of types τ1 and τ2 , such that there is a similarity function θ : Ω1 −→ Ω2 . A function f : A1 −→ A2 is called a θ−homomorphism of universal algebras(or, simply, θ−homomorphism) if for any operation ω ∈ Ω1 and any elements a1 , a2 , . . . , a(ω)τ1 ∈ A1 the following equality holds θ
((a1 , a2 , . . . , a(ω)τ1 )ω )f = ((a1 )f , (a2 )f , . . . , (a(ω)τ1 )f )(ω) . The function f is called θ−isomorphism if θ and f are bijective functions, f is a θ−homomorphism, and f −1 is a θ−1 −homomorphism. If there is a θ−isomorphism from the universal algebra (A1 , Ω1 ) to (A2 , Ω2 ), we say that (A1 , Ω1 ) is isomorphic to (A2 , Ω2 ), and we write (A1 , Ω1 ) ∼ = (A2 , Ω2 ), or A1 ∼ = A2 . A θ−homomorphism from a universal algebra (A, Ω) into itself is called θ−endomorphism of the algebra (A, Ω). A θ−isomorphism from (A, Ω) to (A, Ω) is called θ−automorphism of the algebra (A, Ω). Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
10 / 21
Definition Let (A1 , Ω1 ) and (A2 , Ω2 ) be two universal algebras of types τ1 and τ2 , such that there is a similarity function θ : Ω1 −→ Ω2 . A function f : A1 −→ A2 is called a θ−homomorphism of universal algebras(or, simply, θ−homomorphism) if for any operation ω ∈ Ω1 and any elements a1 , a2 , . . . , a(ω)τ1 ∈ A1 the following equality holds θ
((a1 , a2 , . . . , a(ω)τ1 )ω )f = ((a1 )f , (a2 )f , . . . , (a(ω)τ1 )f )(ω) . The function f is called θ−isomorphism if θ and f are bijective functions, f is a θ−homomorphism, and f −1 is a θ−1 −homomorphism. If there is a θ−isomorphism from the universal algebra (A1 , Ω1 ) to (A2 , Ω2 ), we say that (A1 , Ω1 ) is isomorphic to (A2 , Ω2 ), and we write (A1 , Ω1 ) ∼ = (A2 , Ω2 ), or A1 ∼ = A2 . A θ−homomorphism from a universal algebra (A, Ω) into itself is called θ−endomorphism of the algebra (A, Ω). A θ−isomorphism from (A, Ω) to (A, Ω) is called θ−automorphism of the algebra (A, Ω). Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
10 / 21
Remark The function f : A1 −→ A2 is a θ−homomorphism of universal algebras if and only if for any operation ω ∈ Ω1 the diagram (ω)τ1
A1 ω↓ A1
f (ω)
τ1
−→ f
−→
(ω)τ1 (=((ω)θ )τ2 )
A2 ↓ (ω)θ A2
is commutative.
Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
11 / 21
Remark All the notions defined above may be simplified by considering that Ω is a common operations domain for the universal algebras which are discussed. We call such algebras Ω−algebras. A idΩ −homomorphism between two Ω−algebras is called then homomorphism of Ω−algebras. f : A1 −→ A2 is a homomorphism of Ω−algebras if and only if ((a1 , a2 , . . . , a(ω)τ )ω )f = ((a1 )f , (a2 )f , . . . , (a(ω)τ )f )ω , for any a1 , a2 , . . . , a(ω)τ ∈ A1 and any ω ∈ Ω.
Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
12 / 21
Proposition Let f : A −→ B and g : B −→ C be two homomorphisms of Ω−algebra. Then f · g : A −→ C is a homomorphism of Ω−algebras.
Proposition Let f : A −→ B be a bijective homomorphism of Ω−algebras. Then f −1 : B −→ A is also a homomorphism of Ω−algebras.
Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
13 / 21
Proposition Let f : A −→ B and g : B −→ C be two homomorphisms of Ω−algebra. Then f · g : A −→ C is a homomorphism of Ω−algebras.
Proposition Let f : A −→ B be a bijective homomorphism of Ω−algebras. Then f −1 : B −→ A is also a homomorphism of Ω−algebras.
Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
13 / 21
Proposition Let f : A −→ B be a homomorphism of Ω−algebras, A0 ⊆ A and B 0 ⊆ B. Then 1) If A0 ≤Ω A, then A0f ≤Ω B. −1 2) If B 0 ≤Ω B, then B 0f ≤Ω A.
Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
14 / 21
Definition Let (A, Ω) be a universal algebra of type τ on the set A. An equivalence relation ρ on A is called congruence pe (A, Ω) if for any operation ω ∈ Ω and any elements a1 , a2 , . . . , a(ω)τ , b1 , b2 , . . . , b(ω)τ ∈ A such that ai ρ bi , (∀)i = 1, (ω)τ , it follows that (a1 , a2 , . . . , a(ω)τ )ω ρ (b1 , b2 , . . . , b(ω)τ )ω . The equivalence classes [a]ρ are called in this case congruence classes. We denote Cong (A, Ω) = {ρ ∈ Eq(A)| ρ − congruence on (A, Ω)}.
Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
15 / 21
Remark For any universal algebra (A, Ω), we have idA , TA2 ∈ Cong (A, Ω) .
Definition A universal algebra (A, Ω) such that Cong (A, Ω) = {idA , TA2 } is called simple algebra.
Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
16 / 21
Remark For any universal algebra (A, Ω), we have idA , TA2 ∈ Cong (A, Ω) .
Definition A universal algebra (A, Ω) such that Cong (A, Ω) = {idA , TA2 } is called simple algebra.
Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
16 / 21
Proposition Let f : A −→ B be a homomorphism of Ω−algebras, and ρ ∈ Cong (B, Ω) a congruence on (B, Ω). Then the relation ρf induced by ρ on A by means of the function f is a congruence on (A, Ω).
Remark If f : A −→ B is a homomorphism of Ω−algebras, since idB ∈ Cong (B, Ω), from the proposition above we deduce that ker (f ) ∈ Cong (A, Ω).
Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
17 / 21
Proposition Let f : A −→ B be a homomorphism of Ω−algebras, and ρ ∈ Cong (B, Ω) a congruence on (B, Ω). Then the relation ρf induced by ρ on A by means of the function f is a congruence on (A, Ω).
Remark If f : A −→ B is a homomorphism of Ω−algebras, since idB ∈ Cong (B, Ω), from the proposition above we deduce that ker (f ) ∈ Cong (A, Ω).
Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
17 / 21
Proposition Let (A, Ω) be a Ω−algebra, ρ ∈ Cong (A, Ω), and A/ρ the factor set of the congruence classes of A with respect to congruent¸a ρ. Then, for any ω ∈ Ω, the application ω : (A/ρ)(ω)τ −→ A/ρ, defined by ([a1 ]ρ , [a2 ]ρ , . . . , [a(ω)τ ]ρ )ω = [(a1 , a2 , . . . , a(ω)τ )ω ]ρ is a correctly defined operation on A/ρ, and the canonical projection πρ : A −→ A/ρ defined by (a)πρ = [a]ρ , is a homomorphism of Ω−algebras such that ker (πρ ) = ρ.
Remark In the proposition above we have identified the operation domains Ω and Ω = {ω| ω ∈ Ω}.
Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
18 / 21
Proposition Let (A, Ω) be a Ω−algebra, ρ ∈ Cong (A, Ω), and A/ρ the factor set of the congruence classes of A with respect to congruent¸a ρ. Then, for any ω ∈ Ω, the application ω : (A/ρ)(ω)τ −→ A/ρ, defined by ([a1 ]ρ , [a2 ]ρ , . . . , [a(ω)τ ]ρ )ω = [(a1 , a2 , . . . , a(ω)τ )ω ]ρ is a correctly defined operation on A/ρ, and the canonical projection πρ : A −→ A/ρ defined by (a)πρ = [a]ρ , is a homomorphism of Ω−algebras such that ker (πρ ) = ρ.
Remark In the proposition above we have identified the operation domains Ω and Ω = {ω| ω ∈ Ω}.
Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
18 / 21
Definition The algebra (A/ρ, Ω) defined in the preceding proposition is called the factor algebra(or quotient algebra) of the algebra (A, Ω) with respect to the congruence ρ.
Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
19 / 21
Proposition (The fundamental isomorphism theorem for Ω−algebras) Let (A, Ω) and (B, Ω) be two Ω−algebras, and f : A −→ B a homomorphism of Ω−algebras. Then there is an isomorphism of Ω−algebras f : A/ker (f ) −→ Im(f ) such that the diagram f
A −→ B πker (f ) ↓ ↑ iIm(f ) f
A/ker (f ) −→ Im(f ) is commutative. Also, f is unique with this property.
Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
20 / 21
Definition Let A be an arbitrary set and n ∈ N. A function ω : An −→ A is called n-ary operation on the set A. The number n is called the arity or the type of the operation ω.
Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
1 / 21
n−ary operations on a set. Universal algebras
Definition Let A be an arbitrary set and n ∈ N. A function ω : An −→ A is called n-ary operation on the set A. The number n is called the arity or the type of the operation ω. If B ⊆ An , a function ω : B −→ A is called partial n-ary operation on the set A, with the domain B.
Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
1 / 21
n−ary operations on a set. Universal algebras
Definition Let A be an arbitrary set and n ∈ N. A function ω : An −→ A is called n-ary operation on the set A. The number n is called the arity or the type of the operation ω. If B ⊆ An , a function ω : B −→ A is called partial n-ary operation on the set A, with the domain B.
Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
1 / 21
Example 1) A binary operation on a set A is a function ω : A × A −→ A : (a, b) 7−→ (a, b)ω , through which to any two elements of A one associates an element of A. Generally, in the case of binary operations, in stead of writing (a, b)+ or (a, b)· , we write a + b and a · b. 2) A unary operation on a set A is a function ω : A −→ A.
Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
2 / 21
Example 1) A binary operation on a set A is a function ω : A × A −→ A : (a, b) 7−→ (a, b)ω , through which to any two elements of A one associates an element of A. Generally, in the case of binary operations, in stead of writing (a, b)+ or (a, b)· , we write a + b and a · b. 2) A unary operation on a set A is a function ω : A −→ A. 3) A nullary operation on a nonempty set A is a function ω : A0 −→ A. Because A0 = A∅ = {∅ = (∅, A, ∅)} consists of a single element, ω is completely determined by the element (∅)ω ∈ A. A nullary operation may be identified for this reason with its corresponding image element.
Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
2 / 21
Example 1) A binary operation on a set A is a function ω : A × A −→ A : (a, b) 7−→ (a, b)ω , through which to any two elements of A one associates an element of A. Generally, in the case of binary operations, in stead of writing (a, b)+ or (a, b)· , we write a + b and a · b. 2) A unary operation on a set A is a function ω : A −→ A. 3) A nullary operation on a nonempty set A is a function ω : A0 −→ A. Because A0 = A∅ = {∅ = (∅, A, ∅)} consists of a single element, ω is completely determined by the element (∅)ω ∈ A. A nullary operation may be identified for this reason with its corresponding image element.
Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
2 / 21
Remark An n-ary operation ω defined on a set A determines an n + 1−ary relation on A, with the graph Gω = {(a1 , a2 , . . . , an , (a1 , a2 , . . . , an )ω )| ai ∈ A, i = 1, n} .
Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
3 / 21
Definition Let A be a set and Ω a set of operations defined on A. The pair (A, Ω) is called universal algebra with the operations domain Ω, or Ω−algebra. If Ω = {ω1 , ω2 , . . . , ωk }, we write (A, ω1 , ω2 , . . . , ωk ) in stead of (A, Ω).
Remark Any set may be considered a universal algebra with the operations domain Ω = ∅.
Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
4 / 21
Definition Let A be a set and Ω a set of operations defined on A. The pair (A, Ω) is called universal algebra with the operations domain Ω, or Ω−algebra. If Ω = {ω1 , ω2 , . . . , ωk }, we write (A, ω1 , ω2 , . . . , ωk ) in stead of (A, Ω).
Remark Any set may be considered a universal algebra with the operations domain Ω = ∅.
Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
4 / 21
Definition Let (A, Ω) be an universal algebra. The function τ : Ω −→ N, defined by (ω)τ = the arity of ω is called the type of the algebra (A, Ω).
Example Let M be a nonempty set. We can define on the set of parts of M the universal algebra (P(M), ∩, ∪, CM , ∅, M), whose type is ∩ ∪ CM ∅ M τ= . 2 2 1 0 0
Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
5 / 21
Definition Let (A, Ω) be an universal algebra. The function τ : Ω −→ N, defined by (ω)τ = the arity of ω is called the type of the algebra (A, Ω).
Example Let M be a nonempty set. We can define on the set of parts of M the universal algebra (P(M), ∩, ∪, CM , ∅, M), whose type is ∩ ∪ CM ∅ M τ= . 2 2 1 0 0
Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
5 / 21
Definition Let (A, Ω) be a universal algebra of type τ and B ⊆ A. If for any operation ω ∈ Ω and any elements b1 , b2 , . . . , b(ω)τ ∈ B it follows that (b1 , b2 , . . . , b(ω)τ )ω ∈ B, then B is called a subalgebra of (A, Ω). In this case we write B ≤Ω A or B ≤ A,
Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
6 / 21
Definition Let (A, Ω) be a universal algebra of type τ and B ⊆ A. If for any operation ω ∈ Ω and any elements b1 , b2 , . . . , b(ω)τ ∈ B it follows that (b1 , b2 , . . . , b(ω)τ )ω ∈ B, then B is called a subalgebra of (A, Ω). In this case we write B ≤Ω A or B ≤ A, and by S(A, Ω) we denote the set of all subalgebras of the universal algebra (A, Ω).
Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
6 / 21
Definition Let (A, Ω) be a universal algebra of type τ and B ⊆ A. If for any operation ω ∈ Ω and any elements b1 , b2 , . . . , b(ω)τ ∈ B it follows that (b1 , b2 , . . . , b(ω)τ )ω ∈ B, then B is called a subalgebra of (A, Ω). In this case we write B ≤Ω A or B ≤ A, and by S(A, Ω) we denote the set of all subalgebras of the universal algebra (A, Ω).
Remark 1) A ∈ S(A, Ω).
Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
6 / 21
Definition Let (A, Ω) be a universal algebra of type τ and B ⊆ A. If for any operation ω ∈ Ω and any elements b1 , b2 , . . . , b(ω)τ ∈ B it follows that (b1 , b2 , . . . , b(ω)τ )ω ∈ B, then B is called a subalgebra of (A, Ω). In this case we write B ≤Ω A or B ≤ A, and by S(A, Ω) we denote the set of all subalgebras of the universal algebra (A, Ω).
Remark 1) A ∈ S(A, Ω). 2) If Ω contains nullary operations, and B ≤Ω A, then B 6= ∅.
Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
6 / 21
Definition Let (A, Ω) be a universal algebra of type τ and B ⊆ A. If for any operation ω ∈ Ω and any elements b1 , b2 , . . . , b(ω)τ ∈ B it follows that (b1 , b2 , . . . , b(ω)τ )ω ∈ B, then B is called a subalgebra of (A, Ω). In this case we write B ≤Ω A or B ≤ A, and by S(A, Ω) we denote the set of all subalgebras of the universal algebra (A, Ω).
Remark 1) A ∈ S(A, Ω). 2) If Ω contains nullary operations, and B ≤Ω A, then B 6= ∅. 3) If Ω does not contain nullary operations, then ∅ ∈ S(A, Ω).
Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
6 / 21
Definition Let (A, Ω) be a universal algebra of type τ and B ⊆ A. If for any operation ω ∈ Ω and any elements b1 , b2 , . . . , b(ω)τ ∈ B it follows that (b1 , b2 , . . . , b(ω)τ )ω ∈ B, then B is called a subalgebra of (A, Ω). In this case we write B ≤Ω A or B ≤ A, and by S(A, Ω) we denote the set of all subalgebras of the universal algebra (A, Ω).
Remark 1) A ∈ S(A, Ω). 2) If Ω contains nullary operations, and B ≤Ω A, then B 6= ∅. 3) If Ω does not contain nullary operations, then ∅ ∈ S(A, Ω).
Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
6 / 21
Example Let M be a nonempty set and N ⊂ M. If Ω1 = {∩, ∪}, and Ω2 = {∩, ∪, CM }, then P(N) ≤Ω1 P(M), but P(N) 6≤Ω2 P(M).
Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
7 / 21
Definition Let (A1 , Ω1 ) be a universal algebra of type τ1 , (A1 , Ω1 ) a universal algebra of type τ1 , and θ : Ω1 −→ Ω2 a surjective function. We call the (A1 , Ω1 ) θ−similar to the algebra (A2 , Ω2 ) if the diagram θ
Ω1 −→ Ω2 τ1 & . τ2 N is commutative(i.e., θ · τ2 = τ1 ). The function θ is called similarity application.
Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
8 / 21
Remark 1) The surjective function θ : Ω1 −→ Ω2 is a similarity application if and only if for any ω ∈ Ω1 , the operations ω and (ω)θ have the same arity. 2) If (A1 , Ω1 ), (A2 , Ω2 ) and (A3 , Ω3 ) are universal algebras, and the functions θ : Ω1 −→ Ω2 and θ0 : Ω2 −→ Ω3 are similarity applications, then the function θ · θ0 : Ω1 −→ Ω3 is a similarity application.
Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
9 / 21
Remark 1) The surjective function θ : Ω1 −→ Ω2 is a similarity application if and only if for any ω ∈ Ω1 , the operations ω and (ω)θ have the same arity. 2) If (A1 , Ω1 ), (A2 , Ω2 ) and (A3 , Ω3 ) are universal algebras, and the functions θ : Ω1 −→ Ω2 and θ0 : Ω2 −→ Ω3 are similarity applications, then the function θ · θ0 : Ω1 −→ Ω3 is a similarity application.
Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
9 / 21
Definition Let (A1 , Ω1 ) and (A2 , Ω2 ) be two universal algebras of types τ1 and τ2 , such that there is a similarity function θ : Ω1 −→ Ω2 . A function f : A1 −→ A2 is called a θ−homomorphism of universal algebras(or, simply, θ−homomorphism) if for any operation ω ∈ Ω1 and any elements a1 , a2 , . . . , a(ω)τ1 ∈ A1 the following equality holds θ
((a1 , a2 , . . . , a(ω)τ1 )ω )f = ((a1 )f , (a2 )f , . . . , (a(ω)τ1 )f )(ω) . The function f is called θ−isomorphism if θ and f are bijective functions, f is a θ−homomorphism, and f −1 is a θ−1 −homomorphism. If there is a θ−isomorphism from the universal algebra (A1 , Ω1 ) to (A2 , Ω2 ), we say that (A1 , Ω1 ) is isomorphic to (A2 , Ω2 ), and we write (A1 , Ω1 ) ∼ = (A2 , Ω2 ), or A1 ∼ = A2 .
Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
10 / 21
Definition Let (A1 , Ω1 ) and (A2 , Ω2 ) be two universal algebras of types τ1 and τ2 , such that there is a similarity function θ : Ω1 −→ Ω2 . A function f : A1 −→ A2 is called a θ−homomorphism of universal algebras(or, simply, θ−homomorphism) if for any operation ω ∈ Ω1 and any elements a1 , a2 , . . . , a(ω)τ1 ∈ A1 the following equality holds θ
((a1 , a2 , . . . , a(ω)τ1 )ω )f = ((a1 )f , (a2 )f , . . . , (a(ω)τ1 )f )(ω) . The function f is called θ−isomorphism if θ and f are bijective functions, f is a θ−homomorphism, and f −1 is a θ−1 −homomorphism. If there is a θ−isomorphism from the universal algebra (A1 , Ω1 ) to (A2 , Ω2 ), we say that (A1 , Ω1 ) is isomorphic to (A2 , Ω2 ), and we write (A1 , Ω1 ) ∼ = (A2 , Ω2 ), or A1 ∼ = A2 . A θ−homomorphism from a universal algebra (A, Ω) into itself is called θ−endomorphism of the algebra (A, Ω). A θ−isomorphism from (A, Ω) to (A, Ω) is called θ−automorphism of the algebra (A, Ω). Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
10 / 21
Definition Let (A1 , Ω1 ) and (A2 , Ω2 ) be two universal algebras of types τ1 and τ2 , such that there is a similarity function θ : Ω1 −→ Ω2 . A function f : A1 −→ A2 is called a θ−homomorphism of universal algebras(or, simply, θ−homomorphism) if for any operation ω ∈ Ω1 and any elements a1 , a2 , . . . , a(ω)τ1 ∈ A1 the following equality holds θ
((a1 , a2 , . . . , a(ω)τ1 )ω )f = ((a1 )f , (a2 )f , . . . , (a(ω)τ1 )f )(ω) . The function f is called θ−isomorphism if θ and f are bijective functions, f is a θ−homomorphism, and f −1 is a θ−1 −homomorphism. If there is a θ−isomorphism from the universal algebra (A1 , Ω1 ) to (A2 , Ω2 ), we say that (A1 , Ω1 ) is isomorphic to (A2 , Ω2 ), and we write (A1 , Ω1 ) ∼ = (A2 , Ω2 ), or A1 ∼ = A2 . A θ−homomorphism from a universal algebra (A, Ω) into itself is called θ−endomorphism of the algebra (A, Ω). A θ−isomorphism from (A, Ω) to (A, Ω) is called θ−automorphism of the algebra (A, Ω). Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
10 / 21
Remark The function f : A1 −→ A2 is a θ−homomorphism of universal algebras if and only if for any operation ω ∈ Ω1 the diagram (ω)τ1
A1 ω↓ A1
f (ω)
τ1
−→ f
−→
(ω)τ1 (=((ω)θ )τ2 )
A2 ↓ (ω)θ A2
is commutative.
Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
11 / 21
Remark All the notions defined above may be simplified by considering that Ω is a common operations domain for the universal algebras which are discussed. We call such algebras Ω−algebras. A idΩ −homomorphism between two Ω−algebras is called then homomorphism of Ω−algebras. f : A1 −→ A2 is a homomorphism of Ω−algebras if and only if ((a1 , a2 , . . . , a(ω)τ )ω )f = ((a1 )f , (a2 )f , . . . , (a(ω)τ )f )ω , for any a1 , a2 , . . . , a(ω)τ ∈ A1 and any ω ∈ Ω.
Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
12 / 21
Proposition Let f : A −→ B and g : B −→ C be two homomorphisms of Ω−algebra. Then f · g : A −→ C is a homomorphism of Ω−algebras.
Proposition Let f : A −→ B be a bijective homomorphism of Ω−algebras. Then f −1 : B −→ A is also a homomorphism of Ω−algebras.
Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
13 / 21
Proposition Let f : A −→ B and g : B −→ C be two homomorphisms of Ω−algebra. Then f · g : A −→ C is a homomorphism of Ω−algebras.
Proposition Let f : A −→ B be a bijective homomorphism of Ω−algebras. Then f −1 : B −→ A is also a homomorphism of Ω−algebras.
Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
13 / 21
Proposition Let f : A −→ B be a homomorphism of Ω−algebras, A0 ⊆ A and B 0 ⊆ B. Then 1) If A0 ≤Ω A, then A0f ≤Ω B. −1 2) If B 0 ≤Ω B, then B 0f ≤Ω A.
Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
14 / 21
Definition Let (A, Ω) be a universal algebra of type τ on the set A. An equivalence relation ρ on A is called congruence pe (A, Ω) if for any operation ω ∈ Ω and any elements a1 , a2 , . . . , a(ω)τ , b1 , b2 , . . . , b(ω)τ ∈ A such that ai ρ bi , (∀)i = 1, (ω)τ , it follows that (a1 , a2 , . . . , a(ω)τ )ω ρ (b1 , b2 , . . . , b(ω)τ )ω . The equivalence classes [a]ρ are called in this case congruence classes. We denote Cong (A, Ω) = {ρ ∈ Eq(A)| ρ − congruence on (A, Ω)}.
Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
15 / 21
Remark For any universal algebra (A, Ω), we have idA , TA2 ∈ Cong (A, Ω) .
Definition A universal algebra (A, Ω) such that Cong (A, Ω) = {idA , TA2 } is called simple algebra.
Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
16 / 21
Remark For any universal algebra (A, Ω), we have idA , TA2 ∈ Cong (A, Ω) .
Definition A universal algebra (A, Ω) such that Cong (A, Ω) = {idA , TA2 } is called simple algebra.
Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
16 / 21
Proposition Let f : A −→ B be a homomorphism of Ω−algebras, and ρ ∈ Cong (B, Ω) a congruence on (B, Ω). Then the relation ρf induced by ρ on A by means of the function f is a congruence on (A, Ω).
Remark If f : A −→ B is a homomorphism of Ω−algebras, since idB ∈ Cong (B, Ω), from the proposition above we deduce that ker (f ) ∈ Cong (A, Ω).
Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
17 / 21
Proposition Let f : A −→ B be a homomorphism of Ω−algebras, and ρ ∈ Cong (B, Ω) a congruence on (B, Ω). Then the relation ρf induced by ρ on A by means of the function f is a congruence on (A, Ω).
Remark If f : A −→ B is a homomorphism of Ω−algebras, since idB ∈ Cong (B, Ω), from the proposition above we deduce that ker (f ) ∈ Cong (A, Ω).
Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
17 / 21
Proposition Let (A, Ω) be a Ω−algebra, ρ ∈ Cong (A, Ω), and A/ρ the factor set of the congruence classes of A with respect to congruent¸a ρ. Then, for any ω ∈ Ω, the application ω : (A/ρ)(ω)τ −→ A/ρ, defined by ([a1 ]ρ , [a2 ]ρ , . . . , [a(ω)τ ]ρ )ω = [(a1 , a2 , . . . , a(ω)τ )ω ]ρ is a correctly defined operation on A/ρ, and the canonical projection πρ : A −→ A/ρ defined by (a)πρ = [a]ρ , is a homomorphism of Ω−algebras such that ker (πρ ) = ρ.
Remark In the proposition above we have identified the operation domains Ω and Ω = {ω| ω ∈ Ω}.
Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
18 / 21
Proposition Let (A, Ω) be a Ω−algebra, ρ ∈ Cong (A, Ω), and A/ρ the factor set of the congruence classes of A with respect to congruent¸a ρ. Then, for any ω ∈ Ω, the application ω : (A/ρ)(ω)τ −→ A/ρ, defined by ([a1 ]ρ , [a2 ]ρ , . . . , [a(ω)τ ]ρ )ω = [(a1 , a2 , . . . , a(ω)τ )ω ]ρ is a correctly defined operation on A/ρ, and the canonical projection πρ : A −→ A/ρ defined by (a)πρ = [a]ρ , is a homomorphism of Ω−algebras such that ker (πρ ) = ρ.
Remark In the proposition above we have identified the operation domains Ω and Ω = {ω| ω ∈ Ω}.
Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
18 / 21
Definition The algebra (A/ρ, Ω) defined in the preceding proposition is called the factor algebra(or quotient algebra) of the algebra (A, Ω) with respect to the congruence ρ.
Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
19 / 21
Proposition (The fundamental isomorphism theorem for Ω−algebras) Let (A, Ω) and (B, Ω) be two Ω−algebras, and f : A −→ B a homomorphism of Ω−algebras. Then there is an isomorphism of Ω−algebras f : A/ker (f ) −→ Im(f ) such that the diagram f
A −→ B πker (f ) ↓ ↑ iIm(f ) f
A/ker (f ) −→ Im(f ) is commutative. Also, f is unique with this property.
Lect.dr. M.Chi¸s ()
Lecture 2
13.X.2008
20 / 21
