\documentclass[10pt,a4paper]{article}
\usepackage{graphicx}
\begin{document}
%\texttt{
\begin{verbatim}

       Andreas van Cranenburgh 0440949
       Core Logic
       Wed Nov  4 12:08:33 CET 2009

Exercise 14

1) ~(pX | pY) v ~(pY _|_ nX)
2)
 X = <3, 6>
 Y = <6, 11>
 Z = <24, 13>
With these numbers the antecedent of Barbara is true, but the consequent is
false (pZ is coprime with nX).
3) Celerant reads like this in this formalization:
for all X, Y, Z: ((for all k >= 1 ( ~(px | k . py) v ~(k . py _|_ nx))
                                   ^ (py | pz ^ pz _|_ ny))
               --> (for all k >= 1 (~(px | k . pz) v ~(k . pz _|_ nx))))

Roughly one can say that this formula is valid because of the transitivity of
 "|". Assume the first part of the antecedent is true, no multiple of py can be
divided by px or the multiple is not coprime with nx. Now assume that the
second part is true as well, py divides pz. 
Then the conclusion follows because either k is such that px does not divide
the multiple of py and thus also not that of pz, which is a multiple of py, or
k is such that the multiple of py is not coprime with nx, and then also the
multiple of pz is not coprime with nx, again, since pz is a multiple of py,
because py divides pz.

Alternatively, the consequent can be rewritten in terms of py:
 (for all k >= 1 (~(px | k . (pz / py) . py) v ~(k . (pz / py) . py _|_ nx))))
By py | pz we know that pz / py is an integer, thus every instance of
k . (pz / py) in the consequent can be mapped on some k in the first part of
the antecedent, and thus the consequent follows.

Exercise 15

reflexive: x . x = x (idempotence)
transitive: we have x, y and z. 
Suppose x <= y and y <= z. Then the following hold:
 x . y = x
 y . z = y
Now we can substitute "y . z" for "y" in the first formula,
because of the second formula:
x . y . z = x
and then substitute "x" for "x . y" because of the first formula:
x . z = x
which is equivalent to x <= z.


antisymmetric:
Suppose we have x and y, and x =/= y. Then the relation holds either for
x and y but not for y and x, or vice versa. This is because it cannot be the
case that both x . y = x and x . y = y, since x is not equal to y.

1)
We have x . y = x. 
Then x + y = (x . y) + y         (substitute "x . y" for x, previous step)
x + y = (x . y) + y = (x + y) . (y + y)   (+ distributes over .)
  but y + y = y
x + y = (x + y) . y                       (idempotence of +)
  x . x = x, so we can replace (x + y) on the left with:
(x + y) . (x + y) = (x + y) . y           (idempotence of .)
x + y = y                                 (remove (x + y) from both sides)

Alternatively we can derive this using the following axiom:
x . (x + y) = x  (absorbtion)

x . y = x
x . y = x . (x + y) (substitute second axiom for x)
y = x + y           (remove "x ." from both sides)



2) x + y is an upper bound of x. We derive this by taking the definition
x <= y iff x . y = x, and filling in x + y for y and x for x.
Let's see if x . (x + y) equals x:
x . (x + y)
= (x . x) + (x + y)	(. distributes over +)
= x + (x . y)		(idempotence of .)
= (x . 1) + (x . y)     (x = x . 1)
= x . (1 + y)           (. distributes over +)
= x . 1			(1 + y = 1)
 = x			(x = x . 1)
so x <= x + y.
Similarly for y <= x + y (ie., y . (x + y) = y).

Now we must show that this upper bound is the least upper bound. Suppose
we have some upper bound b of x and y, then x <= b and y <= b. We check if
x + y <= b:
(x + y) . b
= (x . b) + (y . b)         (. distributes over +)
but by x <= b and y <= b we know that x . b = x and y . b = y, so:
= (x . x) + (y . y)
= x + y                     (idempotence of +)
And it is indeed the case.









3) Claim: {x_1 ... x_k} has least upper bound x_1 + ... + x_k
Proof: 
Base case: k = 0, has least upper bound 0. k = 1, trivial.
Induction step:
Induction hypothesis: {x_1, ..., x_k} has least upper bound x_1 + ... = x_k
for k = n
Then the claim is also true for k=n+1

We have the least upper bound b for {x_1 ... x_n}, then {b, x_n+1} has
least upper bound b + x_n+1 (see previous question), and thus 
{x_1 ... x_n+1} has least upper bound x_1 + ... + x_n+1


Exercise 16

mult: (x * x) * (y * y) = z
add: (x * y) * (x * y) = z
comp: x * x = z

Exercise 17
1) Assume we have a boolean algebra with elements {x, y, z}.
 x = -y, and y = -x.
Now either -z = x or -z = y, but either case gives a contradiction, because
then it cannot be the case that z = --z. 

A third possibility would be that -z = z. This also gives a contradiction:
if -z = z then z . -z = z and z + -z = z, but:
z . -z = 0
z + -z = 1

Hence we have to withdraw the assumption that there could be such a boolean
algebra.

2) Consider the set Z_3 consisting of the numbers 0, 1, 2 where addition and
multiplication are defined as follows:

for any x, y in Z_3, x + y is defined to be their arithmetical sum modulo 3
for any x, y in Z_3, x . y is defined to be their arithmetical product modulo 3

Because of the modulo the result of any operation will be within Z_3, and
because + and . follow the normal arithmetic definition their identities hold,
thus this definition represents a ring.

3) An infinite ring that is not isomorphic to any ring of the form R(B) is
< |R, +, ., 0, 1 >  where |R is the set of the real numbers.
There can be no isomorphism between this ring and R(B), because in a boolean
algebra each element has to be idempotent, ie., x * x = x for every operation
* and every element x. Clearly this is not the case in the infinite ring.
\end{verbatim}
\end{document}