Rings and Fields
Rings and Fields have a single set of elements, but have two binary operations on those elements. This section provides examples of Ring and Field construction. See the section, “Definitions”, for definitions of these algebraic structures
Imports
The following functions are imported below:
make_finite_algebra – RECOMMENDED way to create any algebra using the internal rep. described below
generate_powerset_ring – An automated way to create a finite Ring of any size, n
generate_algebra_mod_n – An automated way to create a finite Ring or Field of any size, n
Algebra – A context manager that allows infix notation to be used for abstract arithmetic
>>> from finite_algebras import make_finite_algebra
>>> from finite_algebras import generate_powerset_ring, generate_algebra_mod_n
>>> from finite_algebras import InfixNotation
>>> import json # Needed for (de)serialization of algebras
The following imports assume that the user has setup an environment variable, PYPROJ, that points to the folder on the user’s file system where the abstract_algebra repository resides.
>>> import os
>>> aa_path = os.path.join(os.getenv("PYPROJ"), "abstract_algebra")
>>> alg_dir = os.path.join(aa_path, "Algebras")
Internal Representation of Rings & Fields
Internally, a FiniteAlgebra can take several different forms. For
algebras that have only one set of elements and two binary operations,
such as Rings and Fields, the internal representation is as shown below.
The first four components are the same as for Groups, Monoids, etc. The
only difference is the addition of table2. It defines Ring
multiplication.
name: (
str) A short name for the algebra;description: (
str) Any additional, useful information about the algebra;elements: (
listofstr) Names of the algebras’s elements.table: (
listoflistofint) The algebra’s multiplication table, where each list in the list represents a row of the table, and each integer represents the position of an element in ‘element_names’. Optionally, element names (str) may be used in the table, rather than integers.table2: Similar to table, above. Required when defining a Ring or Field.
Ring
Ring – \(\langle S, +, \cdot \rangle\), where \(\langle S, + \rangle\) is an abelian\(^\dagger\) Group, \(\langle S, \cdot \rangle\) is a Semigroup, and \(\cdot\) distributes\(^\ddagger\) over \(+\)
\(^\dagger\) An algebra is abelian (or commutative) for a binary operation, \(\circ\), if \(a \circ b = b \circ a\) for all \(a,b \in S\).
\(^\ddagger\) An operation, \(\cdot\), distributes over another operation, \(+\), if \(a \cdot (b + c) = (a \cdot b) + (a \cdot c)\) for all \(a,b,c \in S\).
Autogeneration of Rings & Fields
There are several functions for autogenerating finite Rings and Fields of specified size:
generate_powerset_ring: \(A+B \equiv A \bigtriangleup B\) and \(A \times B \equiv A \cap B\), where \(A,B \in P(\{0, 1, ..., n-1\})\)generate_algebra_mod_n: Combination of generate_cyclic_group (\(+\)) and generate_commutative_monoid (\(\times\))If n is prime, then this will be a Field, otherwise it will be a Ring
Ring Based on Powerset of a Set
In this ring, “addition” is symmetric difference, \(\bigtriangleup\), and “multiplication” is intersection, \(\cap\).
>>> rng = generate_powerset_ring(2)
>>> rng.about(use_table_names=True)
** Ring **
Name: PSRing2
Instance ID: 4445654384
Description: Autogenerated Ring on powerset of {0, 1} w/ symm. diff. (add) & intersection (mult)
Order: 4
Identity: '{}'
Commutative? Yes
Cyclic?: No
Elements:
Index Name Inverse Order
0 '{}' '{}' 1
1 '{0}' '{0}' 2
2 '{1}' '{1}' 2
3 '{0, 1}' '{0, 1}' 2
Cayley Table (showing names):
[['{}', '{0}', '{1}', '{0, 1}'],
['{0}', '{}', '{0, 1}', '{1}'],
['{1}', '{0, 1}', '{}', '{0}'],
['{0, 1}', '{1}', '{0}', '{}']]
Mult. Identity: '{0, 1}'
Mult. Commutative? Yes
Zero Divisors: ['{0}', '{1}']
Multiplicative Cayley Table (showing names):
[['{}', '{}', '{}', '{}'],
['{}', '{0}', '{}', '{0}'],
['{}', '{}', '{1}', '{1}'],
['{}', '{0}', '{1}', '{0, 1}']]
Additive & Multiplicative Identity Elements
A Ring’s additive and multiplicative identity elements can be obtained as follows:
rng.add_identity
'{}'
rng.mult_identity
'{0, 1}'
Or, perhaps more suggestively as follows:
rng.zero
'{}'
rng.one
'{0, 1}'
Ring Addition and Multiplication
Ring addition, add, is the same as the operation, op, inherited
from its superclass, Group.
Recall that, in this module, all elements are represented by strings
(names). So, even though the actual elements of a powerset Ring are sets
(e.g., {0, 1}), those elements are represented as strings (e.g., “{0,
1}”). The two examples below show “addition” and “multiplication”
operations in set notation, along with the same operations as performed
by the Ring’s add and mult operators.
Ring “addition” using set notation: \(\{1\} \bigtriangleup \{0,1\} = \{0\}\)
>>> rng.add("{1}", "{0, 1}")
'{0}'
Ring “multiplication” using set notation: \(\{1\} \cap \{0,1\} = \{1\}\)
>>> rng.mult("{1}", "{0, 1}")
'{1}'
Or, using infix notation via the Algebra context:
>>> with InfixNotation(rng) as r:
>>> print(r['{1}'] + r['{0, 1}'])
>>> print(r['{1}'] * r['{0, 1}'])
{0}
{1}
Zero Divisors of a Ring
Suppose \(\alpha \ne 0 \in S\), where \(0\) is the additive identity element of the Ring, \(\langle S, +, \times \rangle\).
Then, \(\alpha\) is a left zero divisor, if \(\exists \beta \in S, \beta \ne 0\) such that \(\alpha \times \beta = 0\).
Similarly, \(\alpha\) is a right zero divisor, if \(\exists \gamma \in S, \gamma \ne 0\) such that \(\gamma \times \alpha = 0\).
The Ring just created has two zero divisors:
>>> rng.zero_divisors()
['{0}', '{1}']
Ring Based on 2x2 Matrices
See Example 6 in this reference: http://www-groups.mcs.st-andrews.ac.uk/~john/MT4517/Lectures/L3.html
Example 6 is a Ring based on the following matrices, where arithmetic is done modulo 2:
\(0 = \begin{bmatrix} 0 & 0 \\ 0 & 0 \end{bmatrix}, a = \begin{bmatrix} 0 & 1 \\ 0 & 0 \end{bmatrix}, b = \begin{bmatrix} 0 & 1 \\ 0 & 1 \end{bmatrix}, c = \begin{bmatrix} 0 & 0 \\ 0 & 1 \end{bmatrix}\)
>>> addtbl = [['0', 'a', 'b', 'c'],
['a', '0', 'c', 'b'],
['b', 'c', '0', 'a'],
['c', 'b', 'a', '0']]
>>> multbl = [['0', '0', '0', '0'],
['0', '0', 'a', 'a'],
['0', '0', 'b', 'b'],
['0', '0', 'c', 'c']]
>>> ex6 = make_finite_algebra(
'Ex6',
'Example 6: http://www-groups.mcs.st-andrews.ac.uk/~john/MT4517/Lectures/L3.html',
['0', 'a', 'b', 'c'],
addtbl,
multbl)
>>> ex6
Ring(
'Ex6',
'Example 6: http://www-groups.mcs.st-andrews.ac.uk/~john/MT4517/Lectures/L3.html',
('0', 'a', 'b', 'c'),
[[0, 1, 2, 3], [1, 0, 3, 2], [2, 3, 0, 1], [3, 2, 1, 0]],
[[0, 0, 0, 0], [0, 0, 1, 1], [0, 0, 2, 2], [0, 0, 3, 3]]
)
>>> ex6.about(use_table_names=True)
** Ring **
Name: Ex6
Instance ID: 4824709904
Description: Example 6: http://www-groups.mcs.st-andrews.ac.uk/~john/MT4517/Lectures/L3.html
Order: 4
Identity: '0'
Commutative? Yes
Cyclic?: No
Elements:
Index Name Inverse Order
0 '0' '0' 1
1 'a' 'a' 2
2 'b' 'b' 2
3 'c' 'c' 2
Cayley Table (showing names):
[['0', 'a', 'b', 'c'],
['a', '0', 'c', 'b'],
['b', 'c', '0', 'a'],
['c', 'b', 'a', '0']]
Mult. Identity: None
Mult. Commutative? No
Zero Divisors: ['a', 'b', 'c']
Multiplicative Cayley Table (showing names):
[['0', '0', '0', '0'],
['0', '0', 'a', 'a'],
['0', '0', 'b', 'b'],
['0', '0', 'c', 'c']]
Extracting a Ring’s Additive & Multiplicative “Subalgebras”
In the Definitions section, a Ring is described as being a combination of a commutative Group, under addition, and a Semigroup, under multiplication (with distributivity of multiplication over addition). This section shows how those algebraic components of a Ring can be extracted.
The implementation of the two extraction methods, illustrated below,
operates by calling make_finite_algebra using the relevant portions
of the Ring. That way, the appropriate algebras are returned: a
commutative Group for the additive portion, and, at a minimum, a
Semigroup for the multiplicative portion.
The example to follow uses the Ring, ex6, created above.
>>> ex6
Ring(
'Ex6',
'Example 6: http://www-groups.mcs.st-andrews.ac.uk/~john/MT4517/Lectures/L3.html',
('0', 'a', 'b', 'c'),
[[0, 1, 2, 3], [1, 0, 3, 2], [2, 3, 0, 1], [3, 2, 1, 0]],
[[0, 0, 0, 0], [0, 0, 1, 1], [0, 0, 2, 2], [0, 0, 3, 3]]
)
The additive portion of this example ring is a commutative Group, as expected:
>>> ex6_add = ex6.extract_additive_algebra()
>>> ex6_add.about()
** Group **
Name: Ex6.Add
Instance ID: 4825145296
Description: Additive-only portion of Ex6
Order: 4
Identity: '0'
Commutative? Yes
Cyclic?: No
Elements:
Index Name Inverse Order
0 '0' '0' 1
1 'a' 'a' 2
2 'b' 'b' 2
3 'c' 'c' 2
Cayley Table (showing indices):
[[0, 1, 2, 3], [1, 0, 3, 2], [2, 3, 0, 1], [3, 2, 1, 0]]
'<Group:Ex6.Add, ID:4825145296>'
And, the multiplicative portion is a Semigroup:
>>> ex6_mult = ex6.extract_multiplicative_algebra()
>>> ex6_mult
Semigroup(
'Ex6.Mult',
'Multiplicative-only portion of Ex6',
('0', 'a', 'b', 'c'),
[[0, 0, 0, 0], [0, 0, 1, 1], [0, 0, 2, 2], [0, 0, 3, 3]]
)
Autogenerating a Commutative Ring
The documentation for the function, generate_algebra_mod_n, is shown
below:
help(generate_algebra_mod_n)
Help on function generate_algebra_mod_n in module finite_algebras:
generate_algebra_mod_n(n, elem_name='', name=None, description=None)
Generate a Ring (or Field) based on integer addition and multiplication modulo n.
If n is prime, then result will be a Field, otherwise it will be a Ring.
Here’s an example:
>>> r6 = generate_algebra_mod_n(6)
>>> r6.about()
** Ring **
Name: R6
Instance ID: 4824710544
Description: Autogenerated Ring of integers mod 6
Order: 6
Identity: '0'
Commutative? Yes
Cyclic?: Yes
Generators: ['1', '5']
Elements:
Index Name Inverse Order
0 '0' '0' 1
1 '1' '5' 6
2 '2' '4' 3
3 '3' '3' 2
4 '4' '2' 3
5 '5' '1' 6
Cayley Table (showing indices):
[[0, 1, 2, 3, 4, 5],
[1, 2, 3, 4, 5, 0],
[2, 3, 4, 5, 0, 1],
[3, 4, 5, 0, 1, 2],
[4, 5, 0, 1, 2, 3],
[5, 0, 1, 2, 3, 4]]
Mult. Identity: '1'
Mult. Commutative? Yes
Zero Divisors: ['2', '3', '4']
Multiplicative Cayley Table (showing indices):
[[0, 0, 0, 0, 0, 0],
[0, 1, 2, 3, 4, 5],
[0, 2, 4, 0, 2, 4],
[0, 3, 0, 3, 0, 3],
[0, 4, 2, 0, 4, 2],
[0, 5, 4, 3, 2, 1]]
Notice that there is a multiplicative identity in the Ring, above. So, if we extract the multiplicative portion of that Ring we should expect to obtain a Monoid, instead of a Semigroup, and we do, as shown below.
>>> r6mult = r6.extract_multiplicative_algebra()
>>> r6mult.about()
** Monoid **
Name: R6.Mult
Instance ID: 4824710864
Description: Multiplicative-only portion of R6
Order: 6
Identity: 1
Associative? Yes
Commutative? Yes
Cyclic?: No
Elements: ('0', '1', '2', '3', '4', '5')
Has Inverses? No
Cayley Table (showing indices):
[[0, 0, 0, 0, 0, 0],
[0, 1, 2, 3, 4, 5],
[0, 2, 4, 0, 2, 4],
[0, 3, 0, 3, 0, 3],
[0, 4, 2, 0, 4, 2],
[0, 5, 4, 3, 2, 1]]
Field
Field – a Ring \(\langle S, +, \cdot \rangle\), where \(\langle S\setminus{\{0\}}, \cdot \rangle\) is a commutative Group\(^{\dagger\dagger}\)
\(^{\dagger\dagger}S\setminus{\{0\}}\) is the set \(S\) with the additive identity element removed.
Example: A field with four elements
Reference: Wikipedia: “Field with four elements”
>>> elems = ['0', '1', 'a', '1+a']
>>> add_table = [[ '0' , '1' , 'a' , '1+a'],
[ '1' , '0' , '1+a', 'a' ],
[ 'a' , '1+a', '0' , '1' ],
['1+a', 'a' , '1' , '0' ]]
>>> mult_table = [['0', '0' , '0' , '0' ],
['0', '1' , 'a' , '1+a'],
['0', 'a' , '1+a', '1' ],
['0', '1+a', '1' , 'a' ]]
>>> f4 = make_finite_algebra('F4',
'Field with 4 elements',
elems,
add_table,
mult_table
)
>>> f4.about()
** Field **
Name: F4
Instance ID: 4825145632
Description: Field with 4 elements
Order: 4
Identity: '0'
Commutative? Yes
Cyclic?: Yes
Generators: ['1+a', 'a']
Elements:
Index Name Inverse Order
0 '0' '0' 1
1 '1' '1' 2
2 'a' 'a' 2
3 '1+a' '1+a' 2
Cayley Table (showing indices):
[[0, 1, 2, 3], [1, 0, 3, 2], [2, 3, 0, 1], [3, 2, 1, 0]]
Mult. Identity: '1'
Mult. Commutative? Yes
Zero Divisors: None
Multiplicative Cayley Table (showing indices):
[[0, 0, 0, 0], [0, 1, 2, 3], [0, 2, 3, 1], [0, 3, 1, 2]]
Addition & Multiplication in Fields
A Field’s addition and multiplication operations are inherited from its superclass, Ring.
>>> f4.add('a', '1')
'1+a'
>>> f4.mult('a', 'a')
'1+a'
Or, using infix notation via the Algebra context. Note the use of the power operator here:
>>> with InfixNotation(f4) as f:
>>> print(f['a'] + f['1'])
>>> print(f['a']**2)
1+a
1+a
Division in Fields
The method, div, is a convenience method in Fields for computing
“\(\alpha \div \beta, \beta \ne 0\)”, that is,
\(\alpha \times \beta^{-1}\) where \(\alpha, \beta \in S\) and
\(F = \langle S, +, \times \rangle\) is a field.
>>> a = 'a'
>>> b = '1+a'
>>> print(f"For example, \"{a} / {b}\" = {a} * inv({b}) = {a} * {f4.mult_inv(b)} = {f4.mult(a, f4.mult_inv(b))}")
For example, "a / 1+a" = a * inv(1+a) = a * a = 1+a
>>> f4.div(a, b)
'1+a'
Or, using infix notation:
>>> with InfixNotation(f4) as f:
>>> print(f['a'] / f['1+a'])
1+a
Recall the definition of a Field, given in the Definition section:
Field – a Ring \(\langle S, +, \times \rangle\), where \(\langle S\setminus{\{0\}}, \times \rangle\) is a commutative Group.
During Field construction, the commutative Group, mentioned in the
definition, is also constructed and stored inside the Field instance. It
is used to obtain multiplicative inverses and to define the division
method, div.
The div method, for example, can be used to construct the “Division
x/y” table shown in the Wikipedia entry, “Field with four
elements”:
>>> div_table = [[f4.div(x, y) for y in f4.elements if y != f4.zero] for x in f4.elements]
>>> for row in div_table:
>>> print(row)
['0', '0', '0']
['1', '1+a', 'a']
['a', '1', '1+a']
['1+a', 'a', '1']
Autogenerated Field
Reference: [Sawyer 1978] “A Concrete Approach to Abstract Algebra”, by Sawyer, W.W., 1978, Dover Publications.
As noted earlier, the built-in algebra generator,
generate_algebra_mod_n, will generate a field of order \(n\), if
\(n\) is a prime number.
For n=5, this field is called the “Miniature Arithmetic” in [Sawyer 1978].
This section provides an example of computations with “fractions” in the “Miniature Arithmetic”.
Note: Remember, in the finite_algebras module all elements are strings.
The method, generate_algebra_mod_n, uses modular arithmetic to
generate numeric elements, which are then turned into strings. By
default, the strings are prefixed with ‘a’, but the default prefix can
be changed by setting the input parameter, elem_name, to something else.
For example, setting it to the empty string, ’‘, as done below, will
result in element names that are simply the string versions of the
numbers they represent (e.g., ’0’, ‘1’, ‘2’, …).
n = 5
F5 = generate_algebra_mod_n(n, elem_name='', name='F5', description="Sawyer's Miniature Arithmetic")
F5.about()
** Field **
Name: F5
Instance ID: 4826792656
Description: Sawyer's Miniature Arithmetic
Order: 5
Identity: '0'
Commutative? Yes
Cyclic?: Yes
Generators: ['2', '1', '4', '3']
Elements:
Index Name Inverse Order
0 '0' '0' 1
1 '1' '4' 5
2 '2' '3' 5
3 '3' '2' 5
4 '4' '1' 5
Cayley Table (showing indices):
[[0, 1, 2, 3, 4],
[1, 2, 3, 4, 0],
[2, 3, 4, 0, 1],
[3, 4, 0, 1, 2],
[4, 0, 1, 2, 3]]
Mult. Identity: '1'
Mult. Commutative? Yes
Zero Divisors: None
Multiplicative Cayley Table (showing indices):
[[0, 0, 0, 0, 0],
[0, 1, 2, 3, 4],
[0, 2, 4, 1, 3],
[0, 3, 1, 4, 2],
[0, 4, 3, 2, 1]]
Example: Fractions in Sawyer’s “Miniature Arithmetic”
Here, we use the Algebra context manager to illustrate Sawyer’s
“fraction” example using the “Miniature Arithmetic”.
Let \(F_5 = \langle S, +, \cdot \rangle\), where \(S = \{0, 1, 2, 3, 4\}\), be Sawyer’s Miniature Arithmetic,
and \(A = \Large \frac{\left( \frac{1}{2} + \frac{2}{3} \right) \cdot \left( \frac{2}{3} - \frac{3}{4} \right)}{\left( \frac{3}{2} - \frac{3}{4} \right)}\)
then,
with InfixNotation(F5) as x:
A = ( (x['1']/x['2'] + x['2']/x['3']) \
* (x['2']/x['3'] - x['3']/x['4'])) \
/ (x['3']/x['2'] - x['3']/x['4'] )
A
'2'
Serialization
Rings and Fields can be converted to and from JSON strings/files and Python dictionaries.
Instantiate Algebra from JSON File
First setup some path variables:
one that points to the abstract_algebra directory
and the other points to a subdirectory containing algebra definitions in JSON format
Also, the code here assumes that there is an environment variable,
PYPROJ, that points to the parent directory of the abstract_algebra
directory.
Here’s the path to the JSON file for the “field with four elements”, and a listing of the file itself.
>>> f4_json = os.path.join(alg_dir, "field_with_four_elements.json")
>>> !cat {f4_json}
{"name": "F4",
"description": "Field with 4 elements (from Wikipedia)",
"elements": ["0", "1", "a", "1+a"],
"table": [[0, 1, 2, 3],
[1, 0, 3, 2],
[2, 3, 0, 1],
[3, 2, 1, 0]],
"table2": [[0, 0, 0, 0],
[0, 1, 2, 3],
[0, 2, 3, 1],
[0, 3, 1, 2]]
}
And here’s the field created from the JSON file.
>>> f4 = make_finite_algebra(f4_json)
>>> f4
Field(
'F4',
'Field with 4 elements (from Wikipedia)',
('0', '1', 'a', '1+a'),
[[0, 1, 2, 3], [1, 0, 3, 2], [2, 3, 0, 1], [3, 2, 1, 0]],
[[0, 0, 0, 0], [0, 1, 2, 3], [0, 2, 3, 1], [0, 3, 1, 2]]
)
Convert Algebra to Python Dictionary
The example, below, shows a Field, being converted into dictionary.
>>> f4_dict = f4.to_dict()
>>> f4_dict
{'name': 'F4',
'description': 'Field with 4 elements (from Wikipedia)',
'elements': ('0', '1', 'a', '1+a'),
'table': [[0, 1, 2, 3], [1, 0, 3, 2], [2, 3, 0, 1], [3, 2, 1, 0]],
'table2': [[0, 0, 0, 0], [0, 1, 2, 3], [0, 2, 3, 1], [0, 3, 1, 2]]}
Instantiate Algebra from Python Dictionary
>>> f4_from_dict = make_finite_algebra(f4_dict)
>>> f4_from_dict
Field(
'F4',
'Field with 4 elements (from Wikipedia)',
('0', '1', 'a', '1+a'),
[[0, 1, 2, 3], [1, 0, 3, 2], [2, 3, 0, 1], [3, 2, 1, 0]],
[[0, 0, 0, 0], [0, 1, 2, 3], [0, 2, 3, 1], [0, 3, 1, 2]]
)
Convert Algebra to JSON String
>>> f4_json_string = f4.dumps()
>>> f4_json_string
'{"name": "F4", "description": "Field with 4 elements (from Wikipedia)", "elements": ["0", "1", "a", "1+a"], "table": [[0, 1, 2, 3], [1, 0, 3, 2], [2, 3, 0, 1], [3, 2, 1, 0]], "table2": [[0, 0, 0, 0], [0, 1, 2, 3], [0, 2, 3, 1], [0, 3, 1, 2]]}'
WARNING: Although an algebra can be constructed by loading its
definition from a JSON file, it cannot be constructed directly from a
JSON string, because make_finite_algebra interprets a single string
input as a JSON file name. To load an algebra from a JSON string, first
convert the string to a Python dictionary, then input that to
make_finite_algebra, as shown below:
>>> make_finite_algebra(json.loads(f4_json_string))
Field(
'F4',
'Field with 4 elements (from Wikipedia)',
('0', '1', 'a', '1+a'),
[[0, 1, 2, 3], [1, 0, 3, 2], [2, 3, 0, 1], [3, 2, 1, 0]],
[[0, 0, 0, 0], [0, 1, 2, 3], [0, 2, 3, 1], [0, 3, 1, 2]]
)
Autogeneration of Rings & Fields
There are several functions for autogenerating finite Rings and Fields of specified size:
generate_powerset_ring: \(A+B \equiv A \bigtriangleup B\) and \(A \times B \equiv A \cap B\), where \(A,B \in P(\{0, 1, ..., n-1\})\)generate_algebra_mod_n: Combination of generate_cyclic_group (\(+\)) and generate_commutative_monoid (\(\times\))If n is prime, then this will be a Field, otherwise it will be a Ring
Direct Products
The direct product of two or more algebras can be generated using
Python’s multiplication operator, *:
Direct Product of Multiple Fields
The direct product of a Ring with another Ring, including itself, will produce a Ring. Since a Field is also a Ring, the direct product of two or more fields will produce a Ring, but not a Field. See the following example.
>>> f4_sqr = f4 * f4
>>> f4_sqr.about(max_size=16)
** Ring **
Name: F4_x_F4
Instance ID: 4824903632
Description: Direct product of F4 & F4
Order: 16
Identity: '0:0'
Commutative? Yes
Cyclic?: No
Elements:
Index Name Inverse Order
0 '0:0' '0:0' 1
1 '0:1' '0:1' 2
2 '0:a' '0:a' 2
3 '0:1+a' '0:1+a' 2
4 '1:0' '1:0' 2
5 '1:1' '1:1' 2
6 '1:a' '1:a' 2
7 '1:1+a' '1:1+a' 2
8 'a:0' 'a:0' 2
9 'a:1' 'a:1' 2
10 'a:a' 'a:a' 2
11 'a:1+a' 'a:1+a' 2
12 '1+a:0' '1+a:0' 2
13 '1+a:1' '1+a:1' 2
14 '1+a:a' '1+a:a' 2
15 '1+a:1+a' '1+a:1+a' 2
Cayley Table (showing indices):
[[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15],
[1, 0, 3, 2, 5, 4, 7, 6, 9, 8, 11, 10, 13, 12, 15, 14],
[2, 3, 0, 1, 6, 7, 4, 5, 10, 11, 8, 9, 14, 15, 12, 13],
[3, 2, 1, 0, 7, 6, 5, 4, 11, 10, 9, 8, 15, 14, 13, 12],
[4, 5, 6, 7, 0, 1, 2, 3, 12, 13, 14, 15, 8, 9, 10, 11],
[5, 4, 7, 6, 1, 0, 3, 2, 13, 12, 15, 14, 9, 8, 11, 10],
[6, 7, 4, 5, 2, 3, 0, 1, 14, 15, 12, 13, 10, 11, 8, 9],
[7, 6, 5, 4, 3, 2, 1, 0, 15, 14, 13, 12, 11, 10, 9, 8],
[8, 9, 10, 11, 12, 13, 14, 15, 0, 1, 2, 3, 4, 5, 6, 7],
[9, 8, 11, 10, 13, 12, 15, 14, 1, 0, 3, 2, 5, 4, 7, 6],
[10, 11, 8, 9, 14, 15, 12, 13, 2, 3, 0, 1, 6, 7, 4, 5],
[11, 10, 9, 8, 15, 14, 13, 12, 3, 2, 1, 0, 7, 6, 5, 4],
[12, 13, 14, 15, 8, 9, 10, 11, 4, 5, 6, 7, 0, 1, 2, 3],
[13, 12, 15, 14, 9, 8, 11, 10, 5, 4, 7, 6, 1, 0, 3, 2],
[14, 15, 12, 13, 10, 11, 8, 9, 6, 7, 4, 5, 2, 3, 0, 1],
[15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]]
Mult. Identity: '1:1'
Mult. Commutative? Yes
Zero Divisors: ['0:1', '0:a', '0:1+a', '1:0', 'a:0', '1+a:0']
Multiplicative Cayley Table (showing indices):
[[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3],
[0, 2, 3, 1, 0, 2, 3, 1, 0, 2, 3, 1, 0, 2, 3, 1],
[0, 3, 1, 2, 0, 3, 1, 2, 0, 3, 1, 2, 0, 3, 1, 2],
[0, 0, 0, 0, 4, 4, 4, 4, 8, 8, 8, 8, 12, 12, 12, 12],
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15],
[0, 2, 3, 1, 4, 6, 7, 5, 8, 10, 11, 9, 12, 14, 15, 13],
[0, 3, 1, 2, 4, 7, 5, 6, 8, 11, 9, 10, 12, 15, 13, 14],
[0, 0, 0, 0, 8, 8, 8, 8, 12, 12, 12, 12, 4, 4, 4, 4],
[0, 1, 2, 3, 8, 9, 10, 11, 12, 13, 14, 15, 4, 5, 6, 7],
[0, 2, 3, 1, 8, 10, 11, 9, 12, 14, 15, 13, 4, 6, 7, 5],
[0, 3, 1, 2, 8, 11, 9, 10, 12, 15, 13, 14, 4, 7, 5, 6],
[0, 0, 0, 0, 12, 12, 12, 12, 4, 4, 4, 4, 8, 8, 8, 8],
[0, 1, 2, 3, 12, 13, 14, 15, 4, 5, 6, 7, 8, 9, 10, 11],
[0, 2, 3, 1, 12, 14, 15, 13, 4, 6, 7, 5, 8, 10, 11, 9],
[0, 3, 1, 2, 12, 15, 13, 14, 4, 7, 5, 6, 8, 11, 9, 10]]
More on Cayley Tables
Under normal usage, there should be no need to directly create Cayley
Tables. This section, however, provides a brief glimse at the
CayleyTable class.
All of the properties of a finite algebra can be determined from its
Cayley Table, or in the case of this Python module, its CayleyTable.
That functionality is passed through to the appropriate methods of the
various algebras. Below, is a demonstration of how distributivity
between two binary operations can be determined using their Cayley
Tables.
The two tables, below, were generated from the powerset of a 3 element set, where “addition” is symmetric difference and “multiplication” is intersection. Recall, the order of the powerset is \(2^n\), where \(n\) is the size of the set.
The element names are simply the string representations of the sets in the powerset:
[‘{}’, ‘{0}’, ‘{1}’, ‘{2}’, ‘{0, 1}’, ‘{0, 2}’, ‘{1, 2}’, ‘{0, 1, 2}’]
And the tables, below, contain the positions (indices) of the 8 elements in the powerset:
>>> addtbl = [[0, 1, 2, 3, 4, 5, 6, 7],
[1, 0, 4, 5, 2, 3, 7, 6],
[2, 4, 0, 6, 1, 7, 3, 5],
[3, 5, 6, 0, 7, 1, 2, 4],
[4, 2, 1, 7, 0, 6, 5, 3],
[5, 3, 7, 1, 6, 0, 4, 2],
[6, 7, 3, 2, 5, 4, 0, 1],
[7, 6, 5, 4, 3, 2, 1, 0]]
>>> multbl = [[0, 0, 0, 0, 0, 0, 0, 0],
[0, 1, 0, 0, 1, 1, 0, 1],
[0, 0, 2, 0, 2, 0, 2, 2],
[0, 0, 0, 3, 0, 3, 3, 3],
[0, 1, 2, 0, 4, 1, 2, 4],
[0, 1, 0, 3, 1, 5, 3, 5],
[0, 0, 2, 3, 2, 3, 6, 6],
[0, 1, 2, 3, 4, 5, 6, 7]]
>>> from cayley_table import CayleyTable
>>> addct = CayleyTable(addtbl)
>>> addct.about(True)
Order Associative? Commutative? Left Id? Right Id? Identity? Inverses? Algebra?
----------------------------------------------------------------------------------------------------
8 True True 0 0 0 True Group
>>> mulct = CayleyTable(multbl)
>>> mulct.about(True)
Order Associative? Commutative? Left Id? Right Id? Identity? Inverses? Algebra?
----------------------------------------------------------------------------------------------------
8 True True 7 7 7 False Monoid
Checking Tables for Distributivity
Multiplication distributes over addition.
>>> mulct.distributes_over(addct)
True
But, addition does not distribute over multiplication.
>>> addct.distributes_over(mulct)
False