Problem Set 1, 26-28 Sept.

- The
*Fibonacci numbers*, , are defined by the recurrence relation , , , for . (Thus the first numbers in the sequence are 0, 1, 1, 2, 3, 5, 8, ...) Prove by induction on that for all ,

where denotes the ``golden ratio'' . - Let
. Draw the Hasse diagram of the order relation
, where

(Here denotes the standard ordering of the integers.) Is the corresponding relation, where ``and'' is replaced by ``or'' in the definition, also a partial order? - List all the equivalence relations (partitions) on the set .
- Draw the Hasse diagrams of all the (partial) orders on the set .

- Describe, in a general way, the structure of the ordered sets
and
.
(The notation ``|'' here denotes the divisibility relation
of the integers, i.e. iff is a factor of .)
What are the minimal elements of the orders? Immediate successors
of a given element? What is the maximal length in each order of
a
*chain*, i.e. a totally ordered sequence of elements ? - Prove that every finite ordered set contains a maximal,
but not necessarily a greatest element.
- The induction principle for natural numbers claims that
the following holds for any property of the natural numbers:
if is true, and the implication
is true for all
, then is true
for all
.
Prove the correctness of this principle, using the facts that
the standard ordering of the natural numbers
is a well-ordering with least element , and in addition
every element
has an immediate
predecessor .