Count of Binary Operations on Set/Examples/Order 2

From ProofWiki
Jump to navigation Jump to search

Example of Use of Count of Binary Operations on Set

The Cayley tables for the complete set of magmas of order $2$ are listed below.

The underlying set in all cases is $\set {a, b}$.

$\begin{array}{r|rr}
 & a & b \\

\hline a & a & a \\ b & a & a \\ \end{array} \qquad \begin{array}{r|rr} 

 & a & b \\

\hline a & a & a \\ b & a & b \\ \end{array} \qquad \begin{array}{r|rr} 

 & a & b \\

\hline a & a & a \\ b & b & a \\ \end{array} \qquad \begin{array}{r|rr} 

 & a & b \\

\hline a & a & a \\ b & b & b \\ \end{array}$

$\begin{array}{r|rr}
 & a & b \\

\hline a & a & b \\ b & a & a \\ \end{array} \qquad \begin{array}{r|rr} 

 & a & b \\

\hline a & a & b \\ b & a & b \\ \end{array} \qquad \begin{array}{r|rr} 

 & a & b \\

\hline a & a & b \\ b & b & a \\ \end{array} \qquad \begin{array}{r|rr} 

 & a & b \\

\hline a & a & b \\ b & b & b \\ \end{array}$

$\begin{array}{r|rr}
 & a & b \\

\hline a & b & a \\ b & a & a \\ \end{array} \qquad \begin{array}{r|rr} 

 & a & b \\

\hline a & b & a \\ b & a & b \\ \end{array} \qquad \begin{array}{r|rr} 

 & a & b \\

\hline a & b & a \\ b & b & a \\ \end{array} \qquad \begin{array}{r|rr} 

 & a & b \\

\hline a & b & a \\ b & b & b \\ \end{array}$

$\begin{array}{r|rr}
 & a & b \\

\hline a & b & b \\ b & a & a \\ \end{array} \qquad \begin{array}{r|rr} 

 & a & b \\

\hline a & b & b \\ b & a & b \\ \end{array} \qquad \begin{array}{r|rr} 

 & a & b \\

\hline a & b & b \\ b & b & a \\ \end{array} \qquad \begin{array}{r|rr} 

 & a & b \\

\hline a & b & b \\ b & b & b \\ \end{array}$


Equivalence Classes

Consider the Cayley tables for the complete set of magmas of order $2$.

Let these be arranged into classes such that $2$ Cayley tables are in the same class if and only if the entry in each cell of one Cayley table is not the same as the entry in the diagonally opposite cell in the other.

The classes are as follows:

$(1): \quad \begin{array}{r|rr}
 & a & b \\

\hline a & a & a \\ b & a & a \\ \end{array} \quad \begin{array}{r|rr} 

 & a & b \\

\hline a & b & b \\ b & b & b \\ \end{array}$

$(2): \quad \begin{array}{r|rr}
 & a & b \\

\hline a & a & a \\ b & a & b \\ \end{array} \quad \begin{array}{r|rr} 

 & a & b \\

\hline a & a & b \\ b & b & b \\ \end{array}$

$(3): \quad \begin{array}{r|rr}
 & a & b \\

\hline a & a & a \\ b & b & a \\ \end{array} \quad \begin{array}{r|rr} 

 & a & b \\

\hline a & b & a \\ b & b & b \\ \end{array}$

$(4): \quad \begin{array}{r|rr}
 & a & b \\

\hline a & a & b \\ b & a & a \\ \end{array} \quad \begin{array}{r|rr} 

 & a & b \\

\hline a & b & b \\ b & a & b \\ \end{array}$

$(5): \quad \begin{array}{r|rr}
 & a & b \\

\hline a & b & a \\ b & a & a \\ \end{array} \quad \begin{array}{r|rr} 

 & a & b \\

\hline a & b & b \\ b & b & a \\ \end{array}$

$(6): \quad \begin{array}{r|rr}
 & a & b \\

\hline a & a & b \\ b & b & a \\ \end{array} \quad \begin{array}{r|rr} 

 & a & b \\

\hline a & b & a \\ b & a & b \\ \end{array}$

$(7): \quad \begin{array}{r|rr}
 & a & b \\

\hline a & a & a \\ b & b & b \\ \end{array}$

$(8): \quad \begin{array}{r|rr}
 & a & b \\

\hline a & a & b \\ b & a & b \\ \end{array}$

$(9): \quad \begin{array}{r|rr}
 & a & b \\

\hline a & b & a \\ b & b & a \\ \end{array}$

$(10): \quad \begin{array}{r|rr}
 & a & b \\

\hline a & b & b \\ b & a & a \\ \end{array}$


They are all isomorphic to the $16$ Binary Truth Functions.


Of these:

$(1): \quad$ These are the constant operations on $\set {a, b}$.
From Constant Operation is Commutative and Constant Operation is Associative, both of these are associative and commutative.


$(2): \quad$ These are isomorphic to the conjunction and disjunction on $\set {a, b}$.
From Rule of Association and Rule of Commutation, both of these are associative and commutative.


$(3)$ and $(4): \quad$ These are isomorphic to the conditionals on $\set {a, b}$, either $a \implies b$ or $b \implies a$, with $a$ and $b$ identified with $\T$ and $\F$ in either order.
From Conditional is not Commutative‎ and Conditional is not Associative, these are neither commutative nor associative.


$(5): \quad$ These are isomorphic to the logical NOR and logical NAND on $\set {a, b}$.
From NAND is Commutative‎ and NOR is Commutative‎, both of these are commutative.
However, from NAND is not Associative‎ and NOR is not Associative, neither are associative.
For example:
for the first of these: $b \paren {a a} = b b = a$ but $\paren {b a} a = a a = b$
for the second of these: $a \paren {b b} = a a = b$ but $\paren {a b} b = b b = a$


$(6): \quad$ These are isomorphic to the biconditional and exclusive or on $\set {a, b}$.
From Biconditional is Associative and Exclusive Or is Associative, both of these is associative.
From Biconditional is Commutative and Exclusive Or is Commutative, both of these is commutative.


$(7): \quad$ This is the left operation, which is isomorphic to the first projection on $\set {a, b}$.
From Left Operation is Associative, this is associative.
From Left Operation is Anticommutative, this is not commutative:
$a b = a$ but $b a = b$.


$(8): \quad$ This is the right operation, which is isomorphic to the second projection on $\set {a, b}$.
From Right Operation is Associative, this is associative.
From Right Operation is Anticommutative, this is not commutative:
$a b = b$ but $b a = a$.


$(9): \quad$ This is isomorphic to the negation of the first projection on $\set {a, b}$.
This is neither associative nor commutative:
$\paren {a b} a = b a = a$ but $a \paren {b a} = a a = b$
$a b = b$ but $b a = a$.


$(10): \quad$ This is isomorphic to the negation of the second projection on $\set {a, b}$.
This is neither associative nor commutative:
$\paren {a b} a = a a = b$ but $a \paren {b a} = a b = a$
$a b = a$ but $b a = b$.


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Count_of_Binary_Operations_on_Set/Examples/Order_2&oldid=546439"