 2.5.1E: Determine whether each of these sets is finite, countably infinite,...
 2.5.2E: Determine whether each of these sets is finite, countably infinite,...
 2.5.3E: Determine whether each of these sets is countable or uncountable. F...
 2.5.4E: Show that a finite group of guests arriving at Hilbert’s fully occu...
 2.5.5E: Show that a finite group of guests arriving at Hilbert’s fully occu...
 2.5.6E: Suppose that Hilbert’s Grand Hotel is fully occupied, but the hotel...
 2.5.7E: Suppose that Hilbert’s Grand Hotel is fully occupied on the day the...
 2.5.8E: Show that a countably infinite number of guests arriving at Hilbert...
 2.5.9E: Suppose that a countably infinite number of buses, each containing ...
 2.5.10E: Give an example of two uncountable sets A and B such that A ? B isa...
 2.5.11E: Give an example of two uncountable sets A and B such that A?B isa) ...
 2.5.12E: Show that if A and B are sets and A? B then A ? B.
 2.5.13E: Explain w by the set A is countable if and only if A ? Z+.
 2.5.14E: Show that if A and B are sets with the same cardinality, then A ?...
 2.5.15E: Show that if A and B are sets. A is uncountable, and A ? B. then B ...
 2.5.16E: Show that a subset of a countable set is also countable.
 2.5.17E: Ifa is an uncountable set andb is a countable set. musta ? b be unc...
 2.5.18E: Show that if A and B are sets A = B, then
 2.5.19E: Show that if A, B, C, and D are sets with A = B and C = D, ...
 2.5.20E: Show that if A = B and B = C, then A = C.
 2.5.21E: Show that if A, B, and C are sets such that A? B and B ? C,...
 2.5.22E: Suppose that A is a countable set. Show that the set B is also coun...
 2.5.23E: Show that if A is an infinite set, then it contains a countably inf...
 2.5.24E: Show that there is no infinite set A such that  A<Z+ = N0.
 2.5.25E: Prove that if it is possible to label each element of an infinite s...
 2.5.26E: Use Exercise 25 to provide a proof different from that in the text ...
 2.5.27E: Show that the union of a countable number of countable sets is coun...
 2.5.28E: Show that the set Z+ × Z+ is countable.
 2.5.29E: Show that the set of all finite bit strings is countable.
 2.5.30E: Show that the set of real numbers that are solutions of quadratic e...
 2.5.31E: Show that Z+ × Z+ is countable by showing that the polynomial funct...
 2.5.32E: Show that when you substitute (3n + 1) for each occurrence of n an...
 2.5.33E: Use the SchroderBernstein theorem to show that (0, 1) and [0, 1] h...
 2.5.34E: Show that (0. 1) and R have the same cardinality. [Hint: Use the Sc...
 2.5.35E: Show that there is no onetoone correspondence from the set of pos...
 2.5.36E: Show that there is a onetoone correspondence from the set of subs...
 2.5.37E: Show that the set of all computer programs in a particular programm...
 2.5.38E: Show that the set of functions from the positive integers to the se...
 2.5.39E: We say that a function is computable if there is a computer program...
 2.5.40E: Show that if S is a set, then there does not exist an onto function...
Solutions for Chapter 2.5: Discrete Mathematics and Its Applications 7th Edition
Full solutions for Discrete Mathematics and Its Applications  7th Edition
ISBN: 9780073383095
Solutions for Chapter 2.5
Get Full SolutionsThis textbook survival guide was created for the textbook: Discrete Mathematics and Its Applications, edition: 7. Since 40 problems in chapter 2.5 have been answered, more than 150256 students have viewed full stepbystep solutions from this chapter. This expansive textbook survival guide covers the following chapters and their solutions. Chapter 2.5 includes 40 full stepbystep solutions. Discrete Mathematics and Its Applications was written by and is associated to the ISBN: 9780073383095.

Adjacency matrix of a graph.
Square matrix with aij = 1 when there is an edge from node i to node j; otherwise aij = O. A = AT when edges go both ways (undirected). Adjacency matrix of a graph. Square matrix with aij = 1 when there is an edge from node i to node j; otherwise aij = O. A = AT when edges go both ways (undirected).

Cholesky factorization
A = CTC = (L.J]))(L.J]))T for positive definite A.

Dimension of vector space
dim(V) = number of vectors in any basis for V.

Echelon matrix U.
The first nonzero entry (the pivot) in each row comes in a later column than the pivot in the previous row. All zero rows come last.

Exponential eAt = I + At + (At)2 12! + ...
has derivative AeAt; eAt u(O) solves u' = Au.

Full column rank r = n.
Independent columns, N(A) = {O}, no free variables.

Kirchhoff's Laws.
Current Law: net current (in minus out) is zero at each node. Voltage Law: Potential differences (voltage drops) add to zero around any closed loop.

Linear combination cv + d w or L C jV j.
Vector addition and scalar multiplication.

Linear transformation T.
Each vector V in the input space transforms to T (v) in the output space, and linearity requires T(cv + dw) = c T(v) + d T(w). Examples: Matrix multiplication A v, differentiation and integration in function space.

Nullspace N (A)
= All solutions to Ax = O. Dimension n  r = (# columns)  rank.

Pivot.
The diagonal entry (first nonzero) at the time when a row is used in elimination.

Plane (or hyperplane) in Rn.
Vectors x with aT x = O. Plane is perpendicular to a =1= O.

Right inverse A+.
If A has full row rank m, then A+ = AT(AAT)l has AA+ = 1m.

Rotation matrix
R = [~ CS ] rotates the plane by () and R 1 = RT rotates back by (). Eigenvalues are eiO and eiO , eigenvectors are (1, ±i). c, s = cos (), sin ().

Row space C (AT) = all combinations of rows of A.
Column vectors by convention.

Similar matrices A and B.
Every B = MI AM has the same eigenvalues as A.

Skewsymmetric matrix K.
The transpose is K, since Kij = Kji. Eigenvalues are pure imaginary, eigenvectors are orthogonal, eKt is an orthogonal matrix.

Spanning set.
Combinations of VI, ... ,Vm fill the space. The columns of A span C (A)!

Transpose matrix AT.
Entries AL = Ajj. AT is n by In, AT A is square, symmetric, positive semidefinite. The transposes of AB and AI are BT AT and (AT)I.

Vandermonde matrix V.
V c = b gives coefficients of p(x) = Co + ... + Cn_IXn 1 with P(Xi) = bi. Vij = (Xi)jI and det V = product of (Xk  Xi) for k > i.