VE203-Assignment 3 Solved

Exercise 3.1 

Assume that Π is a partition of a set A. Define the relation RΠ as follows:

                                                                            xRΠy       ⇔         (∃B ∈ Π)(x ∈ B ∧ y ∈ B).

Show that RΠ is an equivalence relation on A.

Exercise 3.2 

(i)       Let π(x,y) be Cantor’s pairing function. Find x,y ∈ N such that π(x,y) = 333. You may do this question however you wish.

(ii)      Give an explicit formula that defines a bijection between N and N × N × N. You do not have to prove that this formula works!

Exercise 3.3 

Show that the following are posets.

(i)       Let J be the set of closed intervals of the real line, with the partial order defined on J by

                                                                                [a,b] ≤int [c,d]       ⇔       b ≤ c or [a,b] = [c,d].

(ii)      The set Nn, n ∈ N, with the lexicographic order defined on Nn by

(x1,...,xn) ≤ (y1,...,yn) ⇔ (x1,...,xn) = (y1,...,yn) or ∃k ∈ {1,...,n} with xi = yi for i < k and xk < yk (iii) (2pts) Given a poset (P,≤P), the dual of of P, denoted by Pd, with the dual order defined on P by

≤Pd:= {(a,b) | b ≤P a}.

Exercise 3.4 

Let 0 < a1 < a2 < ··· < asr+1 be sr + 1 integers, s,r ∈ N. Show that we can select either s + 1 of them, no one of which divides any other, or r + 1 of them, each dividing the following one.

Exercise 3.5 

Given Dilworth’s Theorem as follows, find out what goes wrong with the proof.

Theorem (Dilworth’s Theorem). Let P be a finite poset of width k. Then P can be partitioned into k chains.

Proof. Induction on n := |P|, n = 1 is obvious. For the induction step n to step n + 1, assume that Dilworth’s theorem holds for posets with n elements and let P be a poset with (n + 1) elements. Let m ∈ P be a maximal element. Then |P − {m}| = n. By induction hypothesis, there are chains C1,...,Cw(P−{m}) forming a partition of P − {m}. If w(P − {m}) = k − 1, set Ck := {m} and we are done. Otherwise, m has strict lower bounds and thus for some i0 ∈ {1,...,w(P − {m}}, we have that m is an upper bound of Ci0. Then Ci0 ∪ {m} is a chain, and C1,...,Ci0−1,Ci0 ∪ {m}, Ci0+1,...,Cw(P−{m}) form a chain partition of P.  

Remark:

•   The proof mentioned above is indeed problematic. No tricks here.

•   As we learned that an induction proof in general correspond to an algorithm and vice versa, it is also the case here. Try to provide an example on which the above induction proof fails. It is NOT acceptable to just answer this question with something like “how do we know blahblahblah is even true?”, since it is not a definite statement. Provide a concrete example/counterexample for the steps that does not go, and of course, explain why.

Exercise 3.6 

Find an explicit bijection between (0,1] and [0,1]. Provide a plot of the function, no proofs are needed.

Remark: To make the problem “simpler”, the task mentioned above is indeed possible, again no tricks here. (Topological Fact: continuous functions map closed/open sets to closed/open sets, resp. Hence the desired bijection cannot possibly be continuous.)

Page 1 of 2

Exercise 3.7 

(i)          Prove that the function f : {0,1}N × {0,1}N → {0,1}N defined by

f(a0a1 ···an ··· ,b0b1 ···bn ···) = a0b0a1b1 ···anbn ···

is a bijection, where ai,bi ∈ {0,1}, and {0,1}N is the set of countably infinite sequences of 0 and 1.

(ii)        Show that there exists a bijection between {0,1}N × {0,1}N and {0,1}N.

(iii)       Represent the reals in (0,1) by their decimal expansions WITHOUT the infinite suffix 99999···. Define the function h : (0,1) × (0,1) → (0,1) by

h(0.r0r1 ···rn ··· ,0.s0s1 ···sn ···) = 0.r0s0r1s1 ···rnsn ···

with ri,si ∈ {0,1,2,...,9}. Prove that h is injective but not surjective.

(iv)       If we pick in (iii) the decimal representations ending WITH the infinite suffix 99999··· rather that an infinite string of 0’s, prove that h is also injective but still not surjective.

(v)        Show that there exists a bijection between (0,1) × (0,1) and (0,1).

Exercise 3.8 

Given the Hasse diagrams of posets (up to isomorphism) with exactly 4 elements below.

(i)         Which of these posets are linear orders?

(ii)        What are the widths of these posets?

(iii)      What are the heights of these posets (counting nodes)?

 

                          (a)                                                    (b)                                                    (c)                                                    (d)

 

                          (e)                                                     (f)                                                     (g)                                                    (h)

 

                           (i)                                                     (j)                                                     (k)                                                     (l)

 

                          (m)                                                   (n)                                                    (o)                                                    (p)

Page 2 of 2