Algebraic Systems In Discrete Mathematics Pdf

\(\newcommand{\identity}{\mathrm{id}} \newcommand{\notdivide}{{\not{\mid}}} \newcommand{\notsubset}{\not\subset} \newcommand{\lcm}{\operatorname{lcm}} \newcommand{\gf}{\operatorname{GF}} \newcommand{\inn}{\operatorname{Inn}} \newcommand{\aut}{\operatorname{Aut}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\cis}{\operatorname{cis}} \newcommand{\chr}{\operatorname{char}} \newcommand{\Null}{\operatorname{Null}} \renewcommand{\vec}[1]{\mathbf{#1}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \)

An algebraic system is a mathematical system consisting of a set called the domain and one or more operations on the domain. If \(V\) is the domain and \(*_1, *_2, \ldots , *_n\) are the operations, \(\left[V;*_1, *_2, \ldots , *_n\right]\) denotes the mathematical system. If the context is clear, this notation is abbreviated to \(V\text{.}\)

Subsection 11.2.1 Monoids at Two Levels

Consider the following two examples of algebraic systems.

1. Let \(B^*\) be the set of all finite strings of 0's and 1's including the null (or empty) string, \(\lambda\text{.}\) An algebraic system is obtained by adding the operation of concatenation. The concatenation of two strings is simply the linking of the two strings together in the order indicated. The concatenation of strings \(a\) with \(b\) is denoted \(a+b\text{.}\) For example, \(01101+101 =01101101\) and \(\lambda +100 = 100\text{.}\) Note that concatenation is an associative operation and that \(\lambda\) is the identity for concatenation.

   A note on notation: There isn't a standard symbol for concatenation. We have chosen \(+\) to be consistent with the notation used in Python and Sage for the concatenation.

2. Let \(M\) be any nonempty set and let * be any operation on \(M\) that is associative and has an identity in \(M\text{.}\) Any such system is called a monoid. We introduce monoids briefly here, but will discuss them further in Chapter 14

Our second example might seem strange, but we include it to illustrate a point. The algebraic system \(\left[B^*;+\right]\) is a special case of \([M;*]\text{.}\) Most of us are much more comfortable with \(B^*\) than with \(M\text{.}\) No doubt, the reason is that the elements in \(B^*\) are more concrete. We know what they look like and exactly how they are combined. The description of \(M\) is so vague that we don't even know what the elements are, much less how they are combined. Why would anyone want to study \(M\text{?}\) The reason is related to this question: What theorems are of interest in an algebraic system? Answering this question is one of our main objectives in this chapter. Certain properties of algebraic systems are called algebraic properties, and any theorem that says something about the algebraic properties of a system would be of interest. The ability to identify what is algebraic and what isn't is one of the skills that you should learn from this chapter.

Now, back to the question of why we study \(M\text{.}\) Our answer is to illustrate the usefulness of \(M\) with a theorem about \(M\text{.}\)

Theorem 11.2.1 . A Monoid Theorem.

If \(a\text{,}\) \(b\) are elements of \(M\) and \(a * b = b * a\text{,}\) then \((a * b) * (a * b) = (a * a) * (b * b)\text{.}\)

Proof.

\begin{equation*} \begin{split} (a*b)*(a*b) &=a*(b*(a*b))\quad \textrm{ Why?} \\ &=a* ((b*a)*b)\quad \textrm{ Why?}\\ &= a*((a*b)*b)\quad \textrm{ Why?}\\ &= a*(a*(b*b))\quad \textrm{ Why?}\\ &= (a*a)*(b*b)\quad \textrm{ Why?} \end{split} \end{equation*}

The power of this theorem is that it can be applied to any algebraic system that \(M\) describes. Since \(B^*\) is one such system, we can apply Theorem 11.2.1 to any two strings that commute. For example, 01 and 0101. Although a special case of this theorem could have been proven for \(B^*\text{,}\) it would not have been any easier to prove, and it would not have given us any insight into other special cases of \(M\text{.}\)

Example 11.2.2 . Another Monoid.

Consider the set of \(2\times 2\) real matrices, \(M_{2\times 2}(\mathbb{R})\text{,}\) with the operation of matrix multiplication. In this context, Theorem 11.2.1 can be interpreted as saying that if \(A B = B A\text{,}\) then \((A B)^2= A^2B^2\text{.}\) One pair of matrices that this theorem applies to is \(\left( \begin{array}{cc} 2 & 1 \\ 1 & 2 \\ \end{array} \right)\) and \(\left( \begin{array}{cc} 3 & -4 \\ -4 & 3 \\ \end{array} \right)\text{.}\)

Subsection 11.2.2 Levels of Abstraction

One of the fundamental tools in mathematics is abstraction. There are three levels of abstraction that we will identify for algebraic systems: concrete, axiomatic, and universal.

Subsubsection 11.2.2.1 The Concrete Level

Almost all of the mathematics that you have done in the past was at the concrete level. As a rule, if you can give examples of a few typical elements of the domain and describe how the operations act on them, you are describing a concrete algebraic system. Two examples of concrete systems are \(B^*\) and \(M_{2\times 2}(\mathbb{R})\text{.}\) A few others are:

1. The integers with addition. Of course, addition isn't the only standard operation that we could include. Technically, if we were to add multiplication, we would have a different system.

2. The subsets of the natural numbers, with union, intersection, and complementation.

3. The complex numbers with addition and multiplication.

Subsubsection 11.2.2.2 The Axiomatic Level

The next level of abstraction is the axiomatic level. At this level, the elements of the domain are not specified, but certain axioms are stated about the number of operations and their properties. The system that we called \(M\) is an axiomatic system. Some combinations of axioms are so common that a name is given to any algebraic system to which they apply. Any system with the properties of \(M\) is called a monoid. The study of \(M\) would be called monoid theory. The assumptions that we made about \(M\text{,}\) associativity and the existence of an identity, are called the monoid axioms. One of your few brushes with the axiomatic level may have been in your elementary algebra course. Many algebra texts identify the properties of the real numbers with addition and multiplication as the field axioms. As we will see in Chapter 16, "Rings and Fields," the real numbers share these axioms with other concrete systems, all of which are called fields.

Subsubsection 11.2.2.3 The Universal Level

The final level of abstraction is the universal level. There are certain concepts, called universal algebra concepts, that can be applied to the study of all algebraic systems. Although a purely universal approach to algebra would be much too abstract for our purposes, defining concepts at this level should make it easier to organize the various algebraic theories in your own mind. In this chapter, we will consider the concepts of isomorphism, subsystem, and direct product.

Subsection 11.2.3 Groups

To illustrate the axiomatic level and the universal concepts, we will consider yet another kind of axiomatic system, the group. In Chapter 5 we noted that the simplest equation in matrix algebra that we are often called upon to solve is \(A X = B\text{,}\) where \(A\) and \(B\) are known square matrices and \(X\) is an unknown matrix. To solve this equation, we need the associative, identity, and inverse laws. We call the systems that have these properties groups.

Definition 11.2.3 . Group.

A group consists of a nonempty set \(G\) and a binary operation \(*\) on \(G\) satisfying the properties

1. \(*\) is associative on \(G\text{:}\) \((a*b)*c=a*(b*c)\) for all \(a, b, c \in G\text{.}\)

2. There exists an identity element, \(e \in G\text{,}\) such that \(a*e=e*a=a\) for all \(a \in G\text{.}\)

3. For all \(a \in G\text{,}\) there exists an inverse; that is, there exists \(b\in G\) such that \(a *b = b*a=e\text{.}\)

A group is usually denoted by its set's name, \(G\text{,}\) or occasionally by \([G; * ]\) to emphasize the operation. At the concrete level, most sets have a standard operation associated with them that will form a group. As we will see below, the integers with addition is a group. Therefore, in group theory \(\mathbb{Z}\) always stands for \([\mathbb{Z}; +]\text{.}\)

Example 11.2.5 . Some concrete groups.

1. The integers with addition is a group. We know that addition is associative. Zero is the identity for addition: \(0 + n = n + 0 = n\) for all integers \(n\text{.}\) The additive inverse of any integer is obtained by negating it. Thus the inverse of \(n\) is \(-n\text{.}\)

2. The integers with multiplication is not a group. Although multiplication is associative and 1 is the identity for multiplication, not all integers have a multiplicative inverse in \(\mathbb{Z}\text{.}\) For example, the multiplicative inverse of 10 is \(\frac{1}{10}\text{,}\) but \(\frac{1}{10}\) is not an integer.

3. The power set of any set \(U\) with the operation of symmetric difference, \(\oplus\text{,}\) is a group. If \(A\) and \(B\) are sets, then \(A\oplus B=(A\cup B)-(A\cap B)\text{.}\) We will leave it to the reader to prove that \(\oplus\) is associative over \(\mathcal{P}(U)\text{.}\) The identity of the group is the empty set: \(A\oplus \emptyset = A\text{.}\) Every set is its own inverse since \(A \oplus A = \emptyset\text{.}\) Note that \(\mathcal{P}(U)\) is not a group with union or intersection.

Definition 11.2.6 . Abelian Group.

A group is abelian if its operation is commutative.

Figure 11.2.7. Norwegian Stamp honoring Abel

Exercises 11.2.4 Exercises

1.

Discuss the analogy between the terms generic and concrete for algebraic systems and the terms generic and trade for prescription drugs.

Answer

The terms "generic" and "trade" for prescription drugs are analogous to "generic" and "concrete" algebraic systems. Generic aspirin, for example, has no name, whereas Bayer, Tylenol, Bufferin, and Anacin are all trade or specific types of aspirins. The same can be said of a generic group \([G; *]\) where \(G\) is a nonempty set and \(*\) is a binary operation on \(G\text{,}\) When examples of typical domain elements can be given along with descriptions of how operations act on them, such as \(\mathbb{Q}\)* or \(M_{2\times 2}(\mathbb{R})\text{,}\) then the system is concrete (has a specific name, as with the aspirin). Generic is a way to describe a general algebraic system, whereas a concrete system has a name or symbols making it distinguishable from other systems.

2.

Discuss the connection between groups and monoids. Is every monoid a group? Is every group a monoid?

3.

Which of the following are groups?

1. \(B^*\) with concatenation (see Subsection 11.2.1).

2. \(M_{2\times 3}(\mathbb{R})\) with matrix addition.

3. \(M_{2\times 3}(\mathbb{R})\) with matrix multiplication.

4. The positive real numbers, \(\mathbb{R}^+\text{,}\) with multiplication.

5. The nonzero real numbers, \(\mathbb{R}^*\text{,}\) with multiplication.

6. \(\{1, -1\}\) with multiplication.

7. The positive integers with the operation \(M\) defined by \(a M b = \textrm{ the larger of } a \textrm{ and } b\text{.}\)

Answer

The systems in parts b, d, e, and f are groups.

4.

Prove that, \(\oplus\text{,}\) defined by \(A \oplus B = (A \cup B) - (A \cap B)\) is an associative operation on \(\mathcal{P}(U)\text{.}\)

5.

The following problem supplies an example of a non-abelian group. A rook matrix is a matrix that has only 0's and 1's as entries such that each row has exactly one 1 and each column has exactly one 1. The term rook matrix is derived from the fact that each rook matrix represents the placement of \(n\) rooks on an \(n\times n\) chessboard such that none of the rooks can attack one another. A rook in chess can move only vertically or horizontally, but not diagonally. Let \(R_n\) be the set of \(n\times n\) rook matrices. There are six \(3\times 3\) rook matrices: \(\begin{array}{ccc} I=\left( \begin{array}{ccc} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{array} \right) & R_1=\left( \begin{array}{ccc} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \\ \end{array} \right) & R_2=\left( \begin{array}{ccc} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ \end{array} \right) \\ F_1=\left( \begin{array}{ccc} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \\ \end{array} \right) & F_2=\left( \begin{array}{ccc} 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \\ \end{array} \right) & F_3=\left( \begin{array}{ccc} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \\ \end{array} \right) \\ \end{array}\)

1. List the \(2\times 2\) rook matrices. They form a group, \(R_2,\) under matrix multiplication. Write out the multiplication table. Is the group abelian?

2. Write out the multiplication table for \(R_3\) . This is another group. Is it abelian?

3. How many \(4\times 4\) rook matrices are there? How many \(n\times n\) rook matrices are there?

Answer

1. Elements are \(I=\left( \begin{array}{cc} 1 & 0 \\ 0 & 1 \\ \end{array} \right)\text{,}\) and \(T=\left( \begin{array}{cc} 0 & 1 \\ 1 & 0 \\ \end{array} \right)\text{,}\) the group is abelian. Operation table is \(\begin{array}{c|cc} \cdot & I & T\\ \hline I & I & T\\ T & T & I\\ \end{array}\)

2. \begin{equation*} \begin{array}{c|c} & \begin{array}{cccccc} I & R_1 & R_2 & F_1 & F_2 & F_3 \\ \end{array} \\ \hline \begin{array}{c} I \\ R_1 \\ R_2 \\ F_1 \\ F_2 \\ F_3 \\ \end{array} & \begin{array}{cccccc} I & R_1 & R_2 & F_1 & F_2 & F_3 \\ R_1 & R_2 & I & F_2 & F_3 & F_1 \\ R_2 & I & R_1 & F_3 & F_1 & F_2 \\ F_1 & F & F_2 & I & R_2 & R_1 \\ F_2 & F_1 & F_3 & R_1 & I & R_2 \\ F_3 & F_2 & F_1 & R_2 & R_1 & I \\ \end{array} \\ \end{array} \end{equation*}

   This group is non-abelian since, for example, \(F_1 F_2=R_2\) and \(F_2 F_1=R_2\text{.}\)

3. 4! = 24, \(n!\text{.}\)

6.

For each of the following sets, identify the standard operation that results in a group. What is the identity of each group?

1. The set of all \(2\times 2\) matrices with real entries and nonzero determinants.

2. The set of \(2 \times 3\) matrices with rational entries.

7.

Let \(V = \{e,a,b, c\}\text{.}\) Let \(*\) be defined (partially) by \(x * x = e\) for all \(x \in V\text{.}\) Write a complete table for \(*\) so that \([V; * ]\) is a group.

Answer

The identity is \(e\text{.}\) \(a*b = c\text{,}\) \(a*c= b\text{,}\) \(b*c = a\text{,}\) and \([V; *]\) is abelian. (This group is commonly called the Klein-4 group.)

8.

Consider the following set of six algebraic expressions, each defining a function on the set of real numbers excluding the numbers 0 and 1.

\begin{equation*} \mathcal{H}=\left\{x,1-x,\frac{1}{1-x},\frac{1}{x},\frac{x-1}{x},\frac{x}{x-1}\right\} =\left\{y_1,y_2,y_3,y_4,y_5,y_6\right\} \end{equation*}

We can operate on any two of these expressions using function composition. For example,

\begin{equation*} (y_3 \circ y_4)(x) = y_3(y_4(x))=y_3(\frac{1}{x})=\frac{1}{1-\frac{1}{x}}=\frac{x}{x-1}=y_6(x) \end{equation*}

Therefore, \(y_3 \circ y_4 = y_6\text{.}\) Complete the following operation table for function composition on \(\mathcal{H}\text{.}\)

Figure 11.2.8. Partially completed operation table for \(\mathcal{H}\)

Is \([\mathcal{H},\circ]\) a monoid? Is it a group?

Solution

Yes, this is a group. You might see some similarities with the group of three by three rook matrices.

Algebraic Systems In Discrete Mathematics Pdf

Source: https://faculty.uml.edu/klevasseur/ads/s-algebraic-systems.html

Posted by: gilmoretooffer55.blogspot.com

Share this post