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

       Andreas van Cranenburgh 0440949
       Core Logic
       Sat Nov 28 18:15:14 CET 2009

Exercise 22
1) G0: total. For any non-bottom element x, either -x has to be the
bottom element, which is unique, or an element immediately preceding the 
bottom element which is neither above nor below x, which in the case of G0 is
only a2 and a3, so these also have a unique counterpart.
If x is the bottom element, then -x is the greatest element if it exists
uniquely, which it does.
i.e., -a2 = a3, -a3 = a2, -a4 = a0 and for the rest -x = a4
G1: total. Similar to above but simpler because there is only a single
element preceding the bottom element.
i.e., -b6 = b0, for the rest -x = b6
G2: partial, try -c1, then c2 and c3 both yield the bottom element but
c2 and c3 have no path between them, so they don't satisfy the uniqueness
condition.
2) No, take for example x = a1. Then -x = a4, but --x = a0, since
a0 is the greatest element. 
3) Yes. 
-x will always be the bottom element (b6),
--x will always be the greatest element (b0),
applying the first observation to the second, ---x will be the bottom element
again.
4) A Heyting algebra is a Boolean algebra with only a pseudo-complement
instead of a real complement. While x ^ -x = 0, it is not generally the case
that x v -x = 1 (law of excluded middle). Thus, Heyting algebras are useful
for representing intuitionistic logic. G0 is a Heyting algebra because the
law of double negation does not hold, and as a consequence, neither the law of
excluded middle.

Exercise 23
1) False, he wanted to proceed in incremental steps: ``Hilbert thus envisaged
his foundational project as a stepwise `simultaneous development of logic and
mathematics,' [...] ''. He first wanted to formalize arithmetic, then analysis,
and let the rest follow later.
2) Winter 1921: `` [...] Hilbert’s lecture course on Grundlagen der Mathematik
of 1921/22 (Hilbert, 1922a, 1922b), where the epsilon-operator is first used
[...]'' (p. 4)
3) Tau and alpha can be eliminated from any proof by finding numerical
substitutions, after which consistency can be shown using the
epsilon-substitution metod.
4) A shift in emphasis towards primitive recursion, in the hope that it could
subsume all number theoretic functions (p. 10)
5) In Hilbert's (1923) system, epsilon A denotes a counterexample, whereas
in Ackermann's (1924) system, epsilon A denotes a witness.
6) Ackermann (p. 32)

Exercise 24
1) There is the trivial model containing PA and 2+2=5. This will cause a
contradiction with 2+2=4 as following from PA, and thus, by Ex Falso Sequitur
Quodlibet, all statements of arithmetic will follow.
2) 2+2=5
3) ?

Exercise 25

DN_0 = []~[]~ phi -> phi
We have that ~[]~ is equivalent with <>, 
so DN_0 = []<> phi -> phi
Similarly for DN_1, DN_1 = phi -> []<>phi
1) Neither DN_0 and DN_1 hold in S4-frames. Countermodel for DN_0:


    { phi }  { phi }
      w_1    w_2
       ^      ^
        \    /
         \  /
         w_0 
       { ~phi }

(Reflexive connections left out). From the point of view of w_0 it is
necessarily the case that possibly phi: both in w_1 and in w_2, due to the
reflexive connections, phi is possible. In w_0 as well, phi is possible
because it is true in both w_1 and w_2. The consequent however is not true,
because phi is false in w_0.

By switching the negations we have a countermodel for DN_1:

   { ~phi }  { ~phi }
      w_1    w_2
       ^      ^
        \    /
         \  /
         w_0 
       { phi }

The same reasoning applies here in reverse. Although phi is true in w_0 it is
not the case that in all worlds it is possible, because w_1 and w_2 are
counterexamples to this.







2)
DN_0 is not valid in S5-frames, the first countermodel of the previous
question applies here as well, if we make the links to w_1 and w_2
bidirectional.

DN_1 is valid in S5-frames, because it is the formula that characterizes
symmetric frames. Proof that DN_1 is valid in symmetric frames:

Suppose R is a symmetric relation on W in F for some w in W:
 - suppose phi is false in w, then the conditional is true
 - alternatively, suppose phi is true in w, then []<>phi must be true as well
 - to see that this is the case, consider each world w' such that wRw',
   in each of these <>phi must hold. Since the relation is symmetric there
   is always the world w accessible from w', such that <>phi holds.

\end{verbatim}
\end{document}
