ONT Re: Higher Order Categorical Logic -- Discussion
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
HOC. Discussion Note 7
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
Here is a simple example of a morphism f : (X, L) -> (Y, M).
Let X be the integers, X = {..., -3, -2, -1, 0, 1, 2, 3, ...},
and let L c X^3 be the 3-adic relation on X whose 3-tuples we
commonly represent by means of the following "addition table":
... ... ... ... ... ... ...
... [-2, 2, 0] [-1, 2, 1] [ 0, 2, 2] [ 1, 2, 3] [ 2, 2, 4] ...
... [-2, 1, -1] [-1, 1, 0] [ 0, 1, 1] [ 1, 1, 2] [ 2, 1, 3] ...
... [-2, 0, -2] [-1, 0, -1] [ 0, 0, 0] [ 1, 0, 1] [ 2, 0, 2] ...
... [-2, -1, -3] [-1, -1, -2] [ 0, -1, -1] [ 1, -1, 0] [ 2, -1, 1] ...
... [-2, -2, -4] [-1, -2, -3] [ 0, -2, -2] [ 1, -2, -1] [ 2, -2, 0] ...
... ... ... ... ... ... ...
The entries in the table have the form [x_1, x_2, x_3], where x_1 + x_2 = x_3.
Let Y be the integers modulo 2, to wit, Y = {0, 1},
and take M c Y^3 as the 3-adic relation on Y whose
3-tuples are given by the following addition table:
+ | 0 1
---o---o---o
0 | 0 | 1 |
o---o---o
1 | 1 | 0 |
o---o---o
The column heads give y_1, the row heads give y_2,
and the entries in the table give y_3 = y_1 + y_2.
The obvious morphism in this case is the map f : X -> Y
that sends all even integers in X to the element 0 in Y
and sends all odd integers in X to the element 1 in Y.
We need to check that "the image of the sum is the sum of the images",
otherwise formulated, that f(x_1 + x_2) = f(x_1) + f(x_2), where the
first "+" uses the 1st table and the second "+" uses the 2nd table.
Bur all this just means that:
Evens plus Evens are Even,
Evens plus Odds are Odd,
Odds plus Evens are Odd,
Odds plus Odds are Even,
which is clear enough.
In summary, f gives the parity of an integer, 0 for Even, 1 for Odd,
and the parity of the integer sum is the mod two sum of the parities.
Finally, observe that "structure-preserving" does not imply that all
of the structure is preserved, but only an identifiable aspect of it.
Parity On, Dude!
Jon Awbrey
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
http://www.cs.bsu.edu/homepages/mighty/history.html
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o