Homework 03: Solutions

Problem 1

Let ${\cal F}$ be the set of all first-order formulas (viewed as syntax trees, so e.g. $(x \land y)$ is a different formula from $(y \land x)$ and let $r$ be the implication relation on formulas:

$\begin{equation*} r = \{ (F_1,F_2) \mid \models F_1 \rightarrow F_2 \} \end{equation*}$

Check whether $r$ is reflexive, antisymmetric, and transitive relation.

Solution

The relation is both reflexive and transitive.

It is not antisymmetric. As a counterexample consider the example that is given in the problem statement: $F_1=x\wedge y$ and $F_2 = y\wedge x$

Problem 2

Let $(A,\sqsubseteq)$ be a partial order such that every set $S \subseteq A$ has the greatest lower bound. Prove that then every set $S \subseteq A$ has the least upper bound.

Problem 3

Galois connection is defined by two monotonic functions $\alpha : C \to A$ and $\gamma : A \to C$ between partial orders $\leq$ on $C$ and $\sqsubseteq$ on $A$ , such that

$\begin{equation*} \alpha(c) \sqsubseteq a\ \iff\ c \leq \gamma(a) \qquad (*) \end{equation*}$

for all $c$ and $a$ (intuitively, the condition means that $c$ is approximated by $a$ ).

Part a) Show that the condition $(*)$ is equivalent to the conjunction of these two conditions:

$\begin{eqnarray*} c &\leq& \gamma(\alpha(c)) \\ \alpha(\gamma(a)) &\sqsubseteq& a \end{eqnarray*}$

hold for all $c$ and $a$ .

Part b) Let $\alpha$ and $\gamma$ satisfy the condition of Galois connection. Show that the following three conditions are equivalent:

$\alpha(\gamma(a)) = a$ for all $a$
$\alpha$ is a surjective function
$\gamma$ is an injective function

Problem 4

Consider Problem 3 on the Space of Invariants in the previous homework, Homework 02.

a): Is the set $Invs$ a lattice? If it is a lattice, is it complete? If it is not a lattice, can it be modified to become a lattice?

b): From now on, fix the relation $r$ . Define $\alpha(I) = sp(I,r)$ and define $g(I) = wp(r,I)$ . Are functions $f$ and $g$ monotonic? Do they form a Galois connection? Prove or give a counterexample.

c): For each of the functions $f$ , $g$ , describe the space of prefix points, postfix points, as well as the least and the greatest fixpoints. You may find Fixed Point Theorems useful.