Discrete Mathematics Answers

If X,Y, and Z are sets and |X|=|Y| and |Y|=|Z|, show that |X|=|Z|. Note that we are not assuming that the given sets are finite.

(a) Show that a subset of a countable set is countable.

Let C={A1, A2, ..., An} be a collection of finite sets that are pairwise disjoint. Further suppose that |Ai|=i. Compute |U(i=1 to n)Ai|, and write your answer in the simplest closed form possible.

Let Bn={(x, y)|0≤x≤n and 0≤y≤n}, where n is a nonnegative integer. Find U(n=0 to infinity)Bn and ∩(n=0 to infinity)Bn.

If In= (-1/(5n),1/(5n)) where n≥1 is an integer and In represents an interval on the real number line, find U(n=1 to infinity) In and ∩(n=1 to infinity) In.

Let R be an equivalence relation on Z, which has P={{±i}|i ∈ N} as its collection of equivalence classes. Describe the equivalence relation R.

Let S be the set of ternary strings (i.e,. strings containing only the characters 0, 1,and 2), and let R be an equivalence relation on S. Suppose the collection of equivalence classes for R is P={Bi|i ∈ N}, where a typical representative of Bi is 222...2, a ternary string of length i consisting only of twos. Describe the equivalence relation R.

Let P1={B0, B1, B2} be a partition of Z, where B0={3n|n ∈ Z}, B1={3n+ 1|n ∈ Z}, and B2={3n+ 2|n ∈ Z}. Describe the equivalence relation R1 corresponding to P1.

(b) Let S={1,2,3}, and define the poset (P(S),⪯) by A⪯B if and only if A⊆B. Verify that this poset is a lattice. Is it a total ordering?
(c) Using your work in part (b), is every lattice necessarily a total ordering?

(a) Is every total ordering a lattice? Why or why not?