# Lab 04: QE, Lattices and Fixed points

## Exercise 1

Recall the algorithm for quantifier elimination for Presburger arithmetic.

Use this algorithm to eliminate quantifiers in the following formula in Presburger arithmetic.

## Exercise 2

Prove the following:

## Exercise 3

Let be a partial order such that every set has the greatest lower bound.

Prove that then every set has the least upper bound.

## Exercise 4

Let be the set of continuous functions from to the reals. Define on by if and only if for all . Show that is a partial order and that with this order forms a lattice.

## Exercise 5

Let be the interval of real numbers. Recall that, by definition of real numbers and complete lattice, is a complete lattice with least lattice element and greatest lattice element . Here is the least upper bound operator on sets of real numbers, also called *supremum* and denoted *sup* in real analysis.

Let function be given by

(It may help you to try to draw .)

#### Part a)

Prove that is monotonic and injective (so it is strictly monotonic).

#### Part b)

Compute the set of fixpoints of .

#### Part c)

Define . (This is in fact equal to when is a monotonic bounded function.)

Compute (prove that the computed value is correct by definition of , that is, that the value is indeed of the set of values). Is a fixpoint of ? Is a fixpoint of ? Is an -continuous function?