14 1. Let’s Count!
A correspondence with these properties is called aone-to-one correspon-
dence(orbijection). If we can make a one-to-one correspondence between
the elements of two sets, then they have the same number of elements.
1.3.1Under the correspondence between numbers and subsets described above,
which numbers correspond to (a) subsets with 1 element, (b) the whole set? (c)
Which sets correspond to even numbers?
1.3.2What is the number of subsets of a set withnelements, containing a
given element?
1.3.3Show that a nonempty set has the same number of odd subsets (i.e.,
subsets with an odd number of elements) as even subsets.
1.3.4What is the number of integers with (a) at mostn(decimal) digits; (b)
exactlyndigits (don’t forget that there are positive and negative numbers!)?
1.4 The Approximate Number of Subsets.............
So, we know that the number of subsets of a 100-element set is 2^100. This
is a large number, but how large? It would be good to know, at least, how
many digits it will have in the usual decimal form. Using computers, it
would not be too hard to find the decimal form of this number (2^100 =
1267650600228229401496703205376), but suppose we have no computers
at hand. Can we at least estimate the order of magnitude of it?
We know that 2^3 =8<10, and hence (raising both sides of this inequal-
ity to the 33rd power) 2^99 < 1033. Therefore, 2^100 < 2 · 1033 .Now2· 1033
is a 2 followed by 33 zeros; it has 34 digits, and therefore 2^100 has at most
34 digits.
We also know that 2^10 = 1024>1000 = 10^3 ; these two numbers are
quite close to each other^2. Hence 2^100 > 1030 , which means that 2^100 has
at least 31 digits.
This gives us a reasonably good idea of the size of 2^100. With a little more
high-school math, we can get the number of digits exactly. What does it
mean that a number has exactlykdigits? It means that it is between 10k−^1
and 10k(the lower bound is allowed, the upper is not). We want to find
the value ofkfor which
10 k−^1 ≤ 2100 < 10 k.(^2) The fact that 2 (^10) is so close to 10 (^3) is used—or rather misused—in the name “kilo-
byte,” which means 1024 bytes, although it should mean 1000 bytes, just as a “kilogram”
means 1000 grams. Similarly, “megabyte” means 2^20 bytes, which is close to 1 million
bytes, but not exactly equal.