7:30 PM

Now that we can talk about functions of sets, and specifically whether the function is one-to-one, onto, both, or neither, we can compare the sizes of sets.

We can say that two sets have the same size, or that they have the same cardinality, if we can find a function that is both one-to-one and onto that maps from the first set to the second set. Symbolically, we can write the statement that X has the same cardinality as Y as X∼Y. Cardinality is an equivalence relation. That is, it obeys the reflexive, symmetric, and transitive properties.

The statement that cardinality is reflexive means that X∼X. This is one of those obvious statements that it's important to explicitly state, since sometimes obvious statements turn out to be wrong. We can prove it's true by defining the function f:X→X by f(x)=x for all x∈X. f is one-to-one and onto, so X has the same cardinality as itself for any set X.

Symmetry means that if X∼Y, then Y∼X. This is marginally less obvious that the previous statement. Since X∼Y, there exists a function f which maps X to Y and is one-to-one and onto. Since f is one-to-one and onto, there exists an inverse of f, f⁻¹, which maps Y to X and is also one-to-one and onto. Since f⁻¹ is one-to-one and onto, Y∼X.

Finally, the transitive property states that if X∼Y and Y∼Z, then X∼Z. If f maps X to Y and g maps Y to Z, then for any point x∈X, g(f(x)) is a point in Z. By following points back and forth through the functions, you can show that since both f and g are one-to-one and onto, g(f(x)) must also be one-to-one and onto. Therefore, g(f(x)) is a one-to-one and onto function that maps X to Z, so X and Z have the same cardinality.

0 comments