Page 198 - Discrete Mathematics and Its Applications

2.6 Matrices 177

18. Show that if A and B are sets |A|=|B|, then |P(A)|= 33. Use the Schröder-Bernstein theorem to show that (0, 1)
|P(B)|. and [0, 1] have the same cardinality
19. Show that if A, B, C, and D are sets with |A|=|B| and 34. Show that (0, 1) and R have the same cardinality. [Hint:
|C|=|D|, then |A × C|=|B × D|. Use the Schröder-Bernstein theorem.]
20. Show that if |A|=|B| and |B|=|C|, then |A|=|C|. 35. Show that there is no one-to-one correspondence from
the set of positive integers to the power set of the set of
21. Show that if A, B, and C are sets such that |A|≤|B| and
|B|≤|C|, then |A|≤|C|. positive integers. [Hint: Assume that there is such a one-
to-one correspondence. Represent a subset of the set of
22. Suppose that A is a countable set. Show that the set B is positive integers as an infinite bit string with ith bit 1 if i
also countable if there is an onto function f from A to B.
belongs to the subset and 0 otherwise. Suppose that you
23. Show that if A is an infinite set, then it contains a count- can list these infinite strings in a sequence indexed by the
ably infinite subset. positive integers. Construct a new bit string with its ith
+
24. Show that there is no infinite setA suchthat |A| < |Z |= bit equal to the complement of the ith bit of the ith string
ℵ 0 . in the list. Show that this new bit string cannot appear in
25. Prove that if it is possible to label each element of an the list.]
infinite set S with a finite string of keyboard characters, ∗ 36. Show that there is a one-to-one correspondence from the
from a finite list characters, where no two elements of S set of subsets of the positive integers to the set real num-
have the same label, then S is a countably infinite set. bers between 0 and 1. Use this result and Exercises 34 and
+
26. Use Exercise 25 to provide a proof different from that 35 to conclude that ℵ 0 < |P(Z )|=|R|.[Hint: Look at
in the text that the set of rational numbers is countable. the first part of the hint for Exercise 35.]
[Hint: Show that you can express a rational number as a ∗ 37. Show that the set of all computer programs in a partic-
string of digits with a slash and possibly a minus sign.] ular programming language is countable. [Hint: A com-
∗ 27. Show that the union of a countable number of countable puter program written in a programming language can be
thought of as a string of symbols from a finite alphabet.]
sets is countable.
∗ 38. Show that the set of functions from the positive inte-
28. Show that the set Z × Z is countable.
+
+
gers to the set {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} is uncountable.
∗ 29. Show that the set of all finite bit strings is countable.
[Hint: First set up a one-to-one correspondence between
∗ 30. Show that the set of real numbers that are solutions of the set of real numbers between 0 and 1 and a subset of
2
quadratic equations ax + bx + c = 0, where a, b, and c these functions. Do this by associating to the real number
are integers, is countable. 0.d 1 d 2 ...d n ... the function f with f (n) = d n .]
∗ 31. Show that Z × Z + is countable by showing that ∗ 39. We say that a function is computable if there is a com-
+
+
the polynomial function f : Z × Z + → Z + with puter program that finds the values of this function. Use
f (m, n) = (m + n − 2)(m + n − 1)/2 + m is one-to- Exercises 37 and 38 to show that there are functions that
one and onto. are not computable.
2
∗ 32. Show that when you substitute (3n + 1) for each occur- ∗ 40. Show that if S is a set, then there does not exist an onto
2
rence of n and (3m + 1) for each occurrence of m in the function f from S to P(S), the power set of S. Con-
right-hand side of the formula for the function f (m, n) clude that |S| < |P(S)|. This result is known as Cantor’s
in Exercise 31, you obtain a one-to-one polynomial func- theorem.[Hint: Suppose such a function f existed. Let
tion Z × Z → Z. It is an open question whether there is T ={s ∈ S | s ∈ f(s)} and show that no element s can
a one-to-one polynomial function Q × Q → Q. exist for which f(s) = T.]

2.6 Matrices

Introduction

Matrices are used throughout discrete mathematics to express relationships between elements
in sets. In subsequent chapters we will use matrices in a wide variety of models. For instance,
matrices will be used in models of communications networks and transportation systems. Many
algorithmswillbedevelopedthatusethesematrixmodels.Thissectionreviewsmatrixarithmetic
that will be used in these algorithms.