TheDeveloperBlog.com

Home | Contact Us

C-Sharp | Java | Python | Swift | GO | WPF | Ruby | Scala | F# | JavaScript | SQL | PHP | Angular | HTML

Discrete Mathematics SemiGroup

Discrete Mathematics SemiGroup with introduction, sets theory, types of sets, set operations, algebra of sets, multisets, induction, relations, functions and algorithms etc.

<< Back to DISCRETE

SemiGroup

Let us consider, an algebraic system (A, *), where * is a binary operation on A. Then, the system (A, *) is said to be semi-group if it satisfies the following properties:

  1. The operation * is a closed operation on set A.
  2. The operation * is an associative operation.

Example: Consider an algebraic system (A, *), where A = {1, 3, 5, 7, 9....}, the set of positive odd integers and * is a binary operation means multiplication. Determine whether (A, *) is a semi-group.

Solution: Closure Property: The operation * is a closed operation because multiplication of two +ve odd integers is a +ve odd number.

Associative Property: The operation * is an associative operation on set A. Since every a, b, c ∈ A, we have

                (a * b) * c = a * (b * c)

Hence, the algebraic system (A, *), is a semigroup.

Subsemigroup:

Consider a semigroup (A, *) and let B ⊆ A. Then the system (B, *) is called a subsemigroup if the set B is closed under the operation *.

Example: Consider a semigroup (N, +), where N is the set of all natural numbers and + is an addition operation. The algebraic system (E, +) is a subsemigroup of (N, +), where E is a set of +ve even integers.

Free Semigroup:

Consider a non empty set A = {a1,a2,.....an}.

Now, A* is the set of all finite sequences of elements of A, i.e., A* consist of all words that can be formed from the alphabet of A.

If α,β,and,γ are any elements of A*, then α,(β. γ)=( α.β).γ.

Here ° is a concatenation operation, which is an associative operation as shown above.

Thus (A*,°) is a semigroup. This semigroup (A*,°) is called the free semigroup generated by set A.

Product of Semigroup:

Theorem: If (S1,*)and (S2,*) are semigroups, then (S1 x S2*) is a semigroup, where * defined by (s1',s2')*( s1'',s2'')=(s1'*s1'',s2'*s2'' ).

Proof: The semigroup S1 x S2 is closed under the operation *.

Associativity of *.Let a, b, c ∈ S1 x S2

So,     a * (b * c) = (a1,a2 )*((b1,b2)*(c1,c2))
               = (a1,a2 )*(b1 *1 c1,b2 *2 c2)
                = (a1 *1 (b1 *1 c1 ),a2 *2 (b2 *2 c2)
                = ((a1 *1 b1) *1*1,( a2 *2 b2) *2 c2)
               = (a1 *1 b1,a2 *2 b2)*( c1,c2)
                = ((a1,a2)*( b1,b2))*( c1,c2)
                = (a * b) * c.

Since * is closed and associative. Hence, S1 x S2 is a semigroup.

Monoid:

Let us consider an algebraic system (A, o), where o is a binary operation on A. Then the system (A, o) is said to be a monoid if it satisfies the following properties:

  1. The operation o is a closed operation on set A.
  2. The operation o is an associative operation.
  3. There exists an identity element, i.e., the operation o.

Example: Consider an algebraic system (N, +), where the set N = {0, 1, 2, 3, 4...}.The set of natural numbers and + is an addition operation. Determine whether (N, +) is a monoid.

Solution: (a) Closure Property: The operation + is closed since the sum of two natural numbers.

(b)Associative Property: The operation + is an associative property since we have (a+b)+c=a+(b+c) ∀ a, b, c ∈ N.

(c)Identity: There exists an identity element in set N the operation +. The element 0 is an identity element, i.e., the operation +. Since the operation + is a closed, associative and there exists an identity. Hence, the algebraic system (N, +) is a monoid.

SubMonoid:

Let us consider a monoid (M, o), also let S ⊆M. Then (S, o) is called a submonoid of (M, o), if and only if it satisfies the following properties:

  1. S is closed under the operation o.
  2. There exists an identity element e ∈ T.

Example: Let us consider, a monoid (M, *), where * s a binary operation and M is a set of all integers. Then (M1, *) is a submonoid of (M, *) where M1 is defined as M1={ai│i is from 0 to n,a positive integer,and a∈M}.


Next TopicGroup




Related Links:


Related Links

Adjectives Ado Ai Android Angular Antonyms Apache Articles Asp Autocad Automata Aws Azure Basic Binary Bitcoin Blockchain C Cassandra Change Coa Computer Control Cpp Create Creating C-Sharp Cyber Daa Data Dbms Deletion Devops Difference Discrete Es6 Ethical Examples Features Firebase Flutter Fs Git Go Hbase History Hive Hiveql How Html Idioms Insertion Installing Ios Java Joomla Js Kafka Kali Laravel Logical Machine Matlab Matrix Mongodb Mysql One Opencv Oracle Ordering Os Pandas Php Pig Pl Postgresql Powershell Prepositions Program Python React Ruby Scala Selecting Selenium Sentence Seo Sharepoint Software Spellings Spotting Spring Sql Sqlite Sqoop Svn Swift Synonyms Talend Testng Types Uml Unity Vbnet Verbal Webdriver What Wpf