Pinter Algebra Chapter 2 Summary

This is part of a series of summaries I am writing for Pinter’s A Book of Abstract Algebra.¹ Chapter 2 is about binary operations, about which I have already written a post earlier. So from this post we will take the definition of binary operations (which will simply be regarded as operations here) and what makes them associative and commutative, as well as the definition of sets having identities and their elements having inverses with respect to an operation.

When defining/verifying operations on sets, there are a few key properties as a result of the definitions that need to be considered. For example, let \(*\) be an operation on \(A\), then the operation \(*\) is a map \(\func{*}{A \times A}{A}\) that maps ordered pairs \((a, b)\) where \(a, b \in A\) to another (not necessarily distinct) element in \(A\); we denote \(*(a, b)\) as \(a*b\). Then, we need to consider these following properties.

• \(a*b\) is defined for all ordered pairs \((a, b) \in A \times A\) with no exceptions. For example, usual division (\(/\)) is not an operation on \(\R\) because it is not defined for the ordered pair \((3, 0)\) for example (division by zero).
• \(a*b\) must be uniquely defined because the map \(*\) is a single-valued relation, i.e. \(a*b\) must yield one and only one (unique) result.
• \(*\) must be closed under \(A\), i.e. for every ordered pair \((a, b) \in A \times A\), \(a*b \in A\). When \(*\) is applied to elements of \(A\), it must not take us out of \(A\)

An operation on a finite set of order \(n\) needs to be well defined for \(n^{2}\) distinct ordered pairs as input. Two operations (defined on the same set) are equal their output is equal for each input. Note also that for some operation \(*\) defined on \(A\), \(A\) needs to have an identity element with respect to \(*\) for the concept that elements of \(A\) may have inverses to make sense.

Automata: The Algebra of Input/Output Sequences

An input sequence is a finite sequence of symbols from some alphabet A. For instance, if \(A= \set{0, 1}\), then examples of input sequences are 011010 and 10101111. Output sequences are defined in the same way as input sequences. The set of all sequences of symbols in the alphabet \(A\) is denoted by \(A^*\).

There is an operation on \(A^*\) called concatenation. For \(\mbf{a}, \mbf{b} \in A^*\) where \(\mbf{a} = a_1 a_2 \cdots a_n\) and \(\mbf{b} = b_1 b_2 \cdots b_m\), then

\[\mbf{ab} = a_1 a_2 \ldots a_n b_1 b_2 \cdots b_m.\]

And \(\lambda\) denotes the empty sequence.

And if we let \(\mbf{c} = c_1 c_2 \cdots c_t\), then we see that

\[ \mbf{a}(\mbf{bc}) = a_1 a_2 \cdots a_n (b_1 b_2 \cdots b_m c_1 c_2 \cdots c_t) = a_1 a_2 \ldots a_n b_1 b_2 \cdots b_m c_1 c_2 \cdots c_t, \\ (\mbf{ab})\mbf{c} = (a_1 a_2 \cdots a_n b_1 b_2 \cdots b_m) c_1 c_2 \cdots c_t = a_1 a_2 \ldots a_n b_1 b_2 \cdots b_m c_1 c_2 \cdots c_t. \]

Concatenation is clearly an associative operation. Furthermore, if we take the alphabet to be nontrivial and consist of at least two elements, then two of its distinct elements \(a\) and \(b\) and output sequences \(\mbf{a} = a, \mbf{b} = b\) demonstrates that concatenation is not commutative.

\[ \mbf{ab} = ab \neq ba = \mbf{ba} \]

Finally, since concatenating the empty sequence \(\lambda\) to either side of a sequence does not change the sequence, which means for every sequence \(\mbf{a} \in A^*\) (where \(\mbf{a} = a_1 a_2 \ldots a_n\)) for each alphabet \(A\) we have that

\[ \lambda\mbf{a} = \mbf{a}\lambda = \mbf{a} = a_1 a_2 \ldots a_n \]

which means \(\lambda\) is the identity. Also note that since the identity is the only element with “length” zero, and that concatenation only increases the “length” of the sequences, the identity \(\lambda\) is the only element to have an inverse under concatenation (which is itself).

An Example of Operations on Sets of Order 2

Consider the set \(A=\set{0, 1}\).² There are 16 distinct possible operations on \(A\), label them \(*_{0}\) through \(*_{15}\). There is a clever way of defining the operations based on the subscript. We could change the subscripts into binary, where they will range from 0000 to 1111. Let the first digit be the value of \(0*0\), then the subsequent ones be the values of \(0*1, 1*0, 1*1\) respectively, then each subscript specifies an unique operation, and collectively the 16 operations make up the collection of all possible operations. Now we will determine the properties of each operation.

First, notice that the operation is commutative if and only if \(0*1 = 1*0\). We still have to check all cases for associativity. Then we just have to check whether the following holds for \(e = 0, 1.\)

\[\begin{cases} 1*e = e*1 = 1 \\ 0*e = e*0 = 0 \end{cases}\]

If there exists an identity, then we will perform similar checks on whether 1 and 0 have inverse elements. Refer to the following table for the 16 operations (by subscript).

Operation	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
\(0*0\)	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
\(0*1\)	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
\(1*0\)	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
\(1*1\)	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1

Before we move on, notice that there are a few familiar operations in the table. \(*_1\) is the AND operation/gate, \(*_6\) is the XOR operation/gate, \(*_7\) is the NAND operation/gate, \(*_8\) is the NOR operation/gate, \(*_9\) is the XNOR operation/gate, and \(x_{14}\) is the NAND gate. Notice that these logic gates are all commutative, and in fact, all commutative operatoions are either one of the aforementioned logic gates or an operation that returns 0 or 1 exclusively.

We could try to determine/verify these properties directly as in the the following.

• \(*_0\) is clearly commutative and associative (every calculation results in zero). However, since no calculation satisfies \(1*e = 1\), there is no identity.
• \(*_1\) is commutative, associative, and has identity 1. However, 0 does not have an inverse because \(0*0 = 0*1 \neq 1\).

However, such will be too tedious to check for all 16 operations. Therefore, I wrote a python script to verify these calculations for me, which I included in the Appendix (along with its output). If a property does not hold, then the script will return the exact calculation at which point the script finds that the property does not hold. With the aid of computer, we can determine the properties of all of the operations.

Operation	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
Associative	✅	✅	❌	✅	❌	✅	✅	✅	❌	✅	❌	❌	❌	❌	❌	✅
Commutative	✅	✅	❌	❌	❌	❌	✅	✅	✅	✅	❌	❌	❌	❌	✅	✅
Identity	❌	1	❌	❌	❌	❌	0	0	❌	1	❌	❌	❌	❌	❌	❌
Inverses	❌	❌	❌	❌	❌	❌	✅	❌	❌	✅	❌	❌	❌	❌	❌	❌

Appendix: Python Code for the Example

Here is the Python code I wrote for the example. The code is not optimal in part because I wanted the code to output exactly which step helped it determine when an operation does not have a certain property. However, the amount of computation needed is little (albeit quite straining if they were to be computed manually), and the code runs very fast.

As commutativity is quite trivial in this case, the code does not report on it. And if the identity test fails, then it will not attempt the inverse test, returning “NaN” instead.

def getfun(n): # creates an operator function/map given subscript
    assert 0<=n<16, "need to be four digit binary"
    def fun(a, b): # a, b are in {0, 1}
        if a:
            if b:
                return n%2  # 1*1 last digit
            else:
                return (n>>1)%2  # 1*0 third digit
        else:
            if b:
                return (n>>2)%2  # 0*1 second digit
            else:
                return n>>3  # 0*0 first digit

    return fun


def demofun(f): # for testing purposes
    return (f(0, 0), f(0, 1), f(1, 0), f(1, 1))


# Tests the associativity of an operator and three given terms
assoctestone = lambda f, a, b, c: f(a, f(b, c)) == f(f(a, b), c)

def assoctest(f): # determines associativity
    for a in [0, 1]:
        for b in [0, 1]:
            for c in [0, 1]:
                if not assoctestone(f, a, b, c):
                    print(f"Associativity fails at {a}*({b}*{c}) = {f(a,f(b,c))} ≠ ({a}*{b})*{c} = {f(f(a,b),c)}.")
                    return False
    return True


def identitytest(f): # determines whether an identity exists
    zero = "e*0 = 0*e ≠ 0" if f(0, 0)!=0 else "e*1 ≠ 1" if f(0, 1)!=1 else "1*e ≠ 1" if f(1, 0)!=1 else ""
    one = "e*1 = 1*e ≠ 1" if f(1, 1)!=1 else "e*0 ≠ 0" if f(1, 0)!=0 else "0*e ≠ 0" if f(0, 1)!=0 else ""
    if zero and one:
        print(f"Identity fails for e=0 at {zero}; for e=1 at {one}")
        return False, False
    else:
        return True, 1 if zero else 0


def inversetest(f, e): # e is identity
    cross = f(0, 1) == f(1, 0) == e # 0 has inverse 1 and vice versa
    zero = f(0, 0) == e # 0 is its own inverse
    one = f(1, 1) == e # 1 is its own inverse
    if cross or (zero and one): return True # both 0 and 1 have inverses
    # else
    if not zero:
        print(f"Inverse Failed at 0: 0⁻¹≠0 as 0*0 ≠ e={e} and 0⁻¹≠1 as ", f"{'' if f(0, 1) == e else '0*1 '}{'' if f(1, 0) == e else '= 1*0 '}≠ e={e}")
    else:
        print(f"Inverse Failed at 1: 1⁻¹≠1 as 1*1 ≠ e={e} and 1⁻¹≠0 as ", f"{'' if f(0, 1) == e else '0*1 '}{'' if f(1, 0) == e else '= 1*0 '}≠ e={e}")
    return False

for i in range(16): # tests all operators 0..15
    f = getfun(i)
    a = assoctest(f)
    iden, e = identitytest(f)
    print(f"*_{i}: Assoc: {a}, Comm: {f(0, 1)==f(1, 0)}, Iden: {e if iden else iden},", "Inv: NaN" if not iden else f"Inv: {inversetest(f, e)}", "\n", "-"*10, end="\n")

The script gave the following output:

Identity fails for e=0 at e*1 ≠ 1; for e=1 at e*1 = 1*e ≠ 1
*_0: Assoc: True, Comm: True, Iden: False, Inv: NaN
 ----------
Inverse Failed at 0: 0⁻¹≠0 as 0*0 ≠ e=1 and 0⁻¹≠1 as  0*1 = 1*0 ≠ e=1
*_1: Assoc: True, Comm: True, Iden: 1, Inv: False
 ----------
Associativity fails at 1*(0*1) = 1 ≠ (1*0)*1 = 0.
Identity fails for e=0 at e*1 ≠ 1; for e=1 at e*1 = 1*e ≠ 1
*_2: Assoc: False, Comm: False, Iden: False, Inv: NaN
 ----------
Identity fails for e=0 at e*1 ≠ 1; for e=1 at e*0 ≠ 0
*_3: Assoc: True, Comm: False, Iden: False, Inv: NaN
 ----------
Associativity fails at 1*(0*1) = 0 ≠ (1*0)*1 = 1.
Identity fails for e=0 at 1*e ≠ 1; for e=1 at e*1 = 1*e ≠ 1
*_4: Assoc: False, Comm: False, Iden: False, Inv: NaN
 ----------
Identity fails for e=0 at 1*e ≠ 1; for e=1 at 0*e ≠ 0
*_5: Assoc: True, Comm: False, Iden: False, Inv: NaN
 ----------
*_6: Assoc: True, Comm: True, Iden: 0, Inv: True
 ----------
Inverse Failed at 1: 1⁻¹≠1 as 1*1 ≠ e=0 and 1⁻¹≠0 as  0*1 = 1*0 ≠ e=0
*_7: Assoc: True, Comm: True, Iden: 0, Inv: False
 ----------
Associativity fails at 0*(0*1) = 1 ≠ (0*0)*1 = 0.
Identity fails for e=0 at e*0 = 0*e ≠ 0; for e=1 at e*1 = 1*e ≠ 1
*_8: Assoc: False, Comm: True, Iden: False, Inv: NaN
 ----------
*_9: Assoc: True, Comm: True, Iden: 1, Inv: True
 ----------
Associativity fails at 0*(0*0) = 0 ≠ (0*0)*0 = 1.
Identity fails for e=0 at e*0 = 0*e ≠ 0; for e=1 at e*1 = 1*e ≠ 1
*_10: Assoc: False, Comm: False, Iden: False, Inv: NaN
 ----------
Associativity fails at 0*(0*0) = 0 ≠ (0*0)*0 = 1.
Identity fails for e=0 at e*0 = 0*e ≠ 0; for e=1 at e*0 ≠ 0
*_11: Assoc: False, Comm: False, Iden: False, Inv: NaN
 ----------
Associativity fails at 0*(0*0) = 1 ≠ (0*0)*0 = 0.
Identity fails for e=0 at e*0 = 0*e ≠ 0; for e=1 at e*1 = 1*e ≠ 1
*_12: Assoc: False, Comm: False, Iden: False, Inv: NaN
 ----------
Associativity fails at 0*(0*0) = 1 ≠ (0*0)*0 = 0.
Identity fails for e=0 at e*0 = 0*e ≠ 0; for e=1 at 0*e ≠ 0
*_13: Assoc: False, Comm: False, Iden: False, Inv: NaN
 ----------
Associativity fails at 0*(0*1) = 1 ≠ (0*0)*1 = 0.
Identity fails for e=0 at e*0 = 0*e ≠ 0; for e=1 at e*1 = 1*e ≠ 1
*_14: Assoc: False, Comm: True, Iden: False, Inv: NaN
 ----------
Identity fails for e=0 at e*0 = 0*e ≠ 0; for e=1 at e*0 ≠ 0
*_15: Assoc: True, Comm: True, Iden: False, Inv: NaN
 ----------

1. Charles C. Pinter, A Book of Abstract Algebra, 2nd ed. (Mineola, NY: Dover Publications, 2013), 19-24. ↩

2. The numbers 0 and 1 do not mean anything in this context, they could be replaced by any other variable but I found 0 and 1 to be convenient. Note that in the book, however, \(a\) and \(b\) are used instead. ↩