![[a small gif of the unit interval]](unit_interval_small.gif)
larger; the same size;
one-to-one correspondence
The notions of "larger" and "the same size" are fairly intuitive for finite sets. However, for infinite sets, they are not as simple. Cantor developed a clever way to make these notions more precise. Cantor defined two sets to be equivalent if they can be placed in a one-to-one correspondence. A one-to-one correspondence is like the buddy system used for swimming at summer camp: each member of one set is assigned a unique member of the other set as its partner. No element in either set is to be left without a partner and no element is assigned more than one partner. If this can be done, the assignment is a one-to-one correspondence and the sets are equivalent.
As an example, the whole numbers and the even whole numbers are equivalent sets. One possible one-to-one correspondence is:
1:2, 2:4, 3:6, 4:8, etc.
that is, each whole number n is assigned the even number 2n.
If set A is equivalent to set B, we informally say that A and B are of the same size. If set A is not equivalent to set B, but A is equivalent to a proper subset of B, we say that B is larger than A.
Notice the two different uses of the notation (0,1). In the first instance, the notation represents the interval on the real line between 0 and 1:
In the second instance, it represents the upper left corner of the unit square:
![[a small gif of the unit square]](unit_square.gif)
The change from the open interval (0,1) to the closed interval [0,1] occurs because Cantor did his work with open intervals, but the space-filling Sierpinski Curves are mappings defined on the closed interval.
The recurrence relation g(n) = 4 g(n - 1) + 4 fails to be homogeneous because of the "+ 4". A homogeneous recurrence relation would contain only terms that are multiples of g(k), for various values of k. See [Rosen] for a complete definition of the phrase "linear homogeneous recurrence relation with constant coefficients".
The astute student will recognize this as a euphemism for a pending homework problem.
Data Structures + Algorithms = Programs
by Niklaus Wirth
Prentice-Hall, 1976
pages 134 - 137
Journey Through Genius: the great theorems of mathematics
by William Dunham
Wiley and Sons, 1990
pages 271-273
Discrete Mathematics and its Applications, 3rd edition
by Kenneth H. Rosen
McGraw-Hill, 1995
pages 318-323
Return to the recursive functions section.
Return to the combinatorial explosion section.
Space-Filling Curves
by Hans Sagan
Springer-Verlag, 1994