Finish ring axioms from previous class
Last class was about the ring axioms - what does it mean to be a
number system in which you can "do" arithmetic. We need to
finish that off.
Ring Axioms
A ring consists of a set of
elements and two binary
operators, which we call "$+$" and "$*$", that satisfy the
following axioms.
-
addition properties - you know all these! (note: can
write informally as well as in first-order syntax)
- associative $\forall x,y,z[ (x+y)+z = x+(y+z) ]$
- commutative $\forall x,y[ x+y = y+x ]$
- additive identity
$\exists x [ \forall y[ x + y = y ]]$ ← We
proved this "x" is unique and decided to call it "0"
- additive inverse $\forall x[ \exists y[ x + y = 0 ] ]$ ←
proved "y" is unique for each x and decided to call
it "-x"
-
multiplication properties - you know these too
- associative $\forall x,y,z[ (x*y)*z = x*(y*z) ]$
- commutative $\forall x,y[ x*y = y*x ]$ ← IMPORTANT! not
required! Rings in which this holds are called "commutative rings"
-
multiplicative identity - we have a constant called 1 such
that $\forall x[ 1*x = x ]$ and $\forall x[ x*1 = x ]$ ←
Note: if multiplication is commutative we only need the first one!
-
multiplicative inverses are not required! 0 never has an inverse.
Commutative rings in which all non-zero elements have a
multiplicative inverse are called "fields".
-
How multiplication and addition interact
- distributivity:
$\forall a,b,c[a*(b+c) = a*b + a*c]$ and
$\forall a,b,c[(b+c)*a = b*a + c*a]$
NOTE: if multiplication is commutative we only need the first kind!
Important!
The whole motivation for coming up with these axioms is to come
up with the minimum requirements necessary to "do arithmetic",
so that we can use the mathematical tools we know and love (like
algebra!) for new domains that do not, on the surface, look
anything like the number systems we have experience with from
grade school and high school. The in-class activity will
introduce you to some unusual-looking number systems, and they
will challenge some of your assumptions - show you that some of
the things you think *must* be true, are not necessarily true
for all number systems.
Coda to the activity
Let's see where we get an advantage from being able to view
unusual domains as rings.
-
Suppose I gave you the following
propositional logic formula, and asked you to fina $x$ and $y$
values satisfying it (w/o using computer programs!):
$$
(x \wedge y) \oplus (T \oplus x \wedge (T \oplus y) \oplus x) \ \Leftrightarrow\ (F \oplus x)
\wedge (x \oplus (T \oplus y)) \oplus T$$
It's hard, right? But because it's xors and ands, we can
translate it into our boolean ring from the activity, and
use algebra to solve:
$$
\begin{array}{rcll}
x \cdot y + (1 + x \cdot (1 + y) + x) &=& (0 + x) \cdot (1 + y))
+ 1&\text{$\leftarrow$ translate the formula into an equation in
the boolean ring}\\
xy + 1 + x + xy + 1 &=& x + xy + 1&\text{$\leftarrow$ expand
both sides}\\
xy + 1 &=& 0&\text{$\leftarrow$ the $x + xy+1$ on either
side cancel}\\
x y &=& 1&\text{$\leftarrow$ $1 = -1$ in this ring!}\\
x = T, y = T
\end{array}
$$
Because we know that T/F with and/xor is a ring, we know we
are allowed to "do algebra", which gave us a powerful (and
familiar!) set of tools to solve the problem with.
-
In the Shape Ring, suppose we wanted to solve the following problem:
Given:
△ y + ◇ x - ○ = □
◇ x + ○ y = ○
Find: x and y satisfying both these equations (or show that there are no solutions).
Once again, we can use algebra to solve this problem:
△ y + ◇ x - ○ = □ : equation 1 ◇ x + ○ y = ○ : equation 2
y + ◇ x - ○ = 0 : △ = 1, and □ = 0 ◇ x + ○*(○ + ◇ x) = ○ : use (A) to sub for y
y + ◇ x = ○ : add ○ to both sides ◇ x + ○*○ + ○*◇*x = ○ : distribute
y = ○ + -1*(◇ x) : -1*(◇ x) = -( ◇ x) ◇ x + 0 + ○*◇*x = ○ : ○*○ = 0
y = ○ + (-1*◇)*x : * is associative ◇ x + + ○ x = ○ : ○*◇ = ○
y = ○ + ◇ x : call this (A) (◇ + ○) x = ○ : distributive axiom
△ x = ○ : ◇ + ○ = △
x = ○ : △ = 1
y = ○ + ◇ ○ : sub x = ○ into (A)
y = □ : calculate
So ... x = ○, y = □
Christopher W Brown