Proving that axioms hold for (finite) algebraic structure

Question

If I make up an algebraic structure, say a field, by defining addition and multiplication like this for example:

$b \equiv -a$

\begin{array}{|c|c|c|c|} \hline \oplus& 0 & 1 & a & b \\ \hline 0 & 0 & 1 & a & b \\ \hline 1 & 1 & 0 & b & a \\ \hline a & a & b & 1 & 0 \\ \hline b & b & a & 0 & 1 \\ \hline \end{array}

$b \equiv a^{-1}$

\begin{array}{|c|c|c|c|} \hline \otimes & 1 & 0 & a & b \\ \hline 1 & 1 & 0 & a & b \\ \hline 0 & 0 & 1 & b & a \\ \hline a & a & b & 0 & 1 \\ \hline b & b & a & 1 & 0 \\ \hline \end{array}

How could I prove for instance associativity without going through all combinations of three variables?

I found this proof for natural numbers:

https://en.wikipedia.org/wiki/Proofs_involving_the_addition_of_natural_numbers#Proof_of_associativity

But if I don't have an ordering relation and a successor function defined on my set that won't work. So, how do you prove axioms to hold for structures that one made up oneself?

Answer 1

There's only finitely many possibilities for what I input into my multiplication/addition axioms. For instance, to verify that addition is commutative, I have 6 different pairs of things to add:

$0+1=1=1+0$

$0+b=b=b+0$

$0+a=a=a+0$

$a+1=b=1+a$

$b+1=a=1+b$

$a+b=1=b+a$

And since all six of those equations have flipped arguments and the same value, I know commutativity works. I also need to check the existence of an additive identity, of additive inverses, and associativity; and I need to check identity, commutativity and associativity for multiplication, and the existence of inverses for elements that aren't 0; and then that the distributive property holds. In general this will be a lot of relations to check, but if I know something else about how the object is structured, I might be able to do so more readily. (For instance, if I describe 0/1/a/b as vectors mod 2, (0,0), (0,1), (1,0), and (1,1), then I immediately know all my addition properties work.)

There are also lots of tricks I can use to try to speed up checking these, when given a table as above. For instance, commutativity of addition and multiplication is checked by verifying that each "matrix" is symmetric (equal to its own transpose). The existence of identity is checked that the row next to 0 (for addition) or next to 1 (for multiplication) is the same as the top header. The existence of inverses is done by checking that each row in each table is a permutation of the elements in the field. This leaves just associativity and distributivity, which are definitely more annoying; for these you probably want to plug the values into a computer to quickly check all 64 possibilities, or you want to come up with some description of the field that you can prove it with less directly.

Answer 2

To show associativity, I would identify these tables with more well-known structures. For example, your table for $\oplus$ is isomorphic to the structure $(\mathbb{Z}/4,+)$, with a bijection sending $\{0,a,1,b\}$ to $\{0,1,2,3\}$.

Likewise, your table for $\otimes$ is also isomorphic to $(\mathbb{Z}/4,+)$, with the slightly different bijection sending $\{1,a,0,b\}$ to $\{0,1,2,3\}$.

So both operations are group operations, and in particular they are associative. However, there is no way that what you have written down is a field—in your structure, every element has a multiplicative inverse, which is impossible in a field. In fact, distributivity fails:

$$b=a\otimes (1\oplus 1) \neq (a\otimes 1) \oplus (a\otimes 1)=1$$