Exercises
- Let r be a binary relation in P(X) for some nonempty set X, such
that
A r B iff A ∪ B = B
- Prove that r is a partial ordering.
- Find minimal, maximal, the least and the greatest elements
(if they exist).
- Consider the relation r in the set ( P(X)/{ ∅
})/{X} and find distinguished elements (minimal and maximal elements
etc.) as in the previous point.
- Prove that if <X, r> is a partially ordered set, then
<X,r-1> is partially ordered. Could we stated the same
- if r is a linear order?
- if r is a well-order?
- Give an example of a partially ordered set which has
- several minimal elements,
- exactly one minimal element,
- exactly one minimal element and which has no the least
element.
For each of the examples, draw the Hasse diagram.
- Prove that the relation r (produt ordering) defined in the
product X × Y of two partially ordered sets
<X, ≤1>, <Y, ≤2 > by
(x,y) r (x',y') wttw x ≤1x' and
y ≤2 y' is a partial ordering relation.
- Is it linear order?
- Is it well order?
- Let X=Y={1,2,3}. Draw Hasse diagram of the produt ordering in
X ×Y and find the distinguished elements.
- Prove that the lexicographical order in N3 is a linear
order.
- Consider the set R ordered by the relation ≤.
- Is it a lattice?
- Give an example of a subset of R which has no upper bound
in R.
- Find sup{x ∈
R : x<23}
- sup{x ∈ R : x2 <
23}, sup{ x ∈ N : x2 < 23}
- inf {x ∈
R : x2< 23}, inf {x ∈
N : x2 < 23}
- Let E(N) be the set of all subsets of N that has the even number
of elements and let ⊆ be partial ordering relation
in it.
- Give two different upper bounds of the set {A, B} in E(N), if
A = {1,2}, B = {1,3} .
- Has the set {A, B} supremum in E(N)? Infimum?
- Is E(N) a lattice?
- Range the following words in the lexicographical order:
rola, kopa, pora, para, kara, poza, koza, ropa. Try to generalised your
method of solving the problem in the form of algorithms that work
correctly on any sequence od 4-letters words.
- On the rectangular notice-board sized n x m there are k
rectangular posters, where n, m are natural numbers. Unfortunately,
some
of them are partially covered by others. Construct the algorithm
that allows to establish which of the posters are totally visible. We
assume that the position of the left-up corner of every poster is
known, the length of sides are integres and the posters are placed
parallely to the sides of the notice-board.