O Sweet Mr Math

wherein is detailed Matt's experiences as he tries to figure out what to do with his life. Right now, that means lots of thinking about math.

Tuesday, February 28, 2012

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−1, which maps Y to X and is also one-to-one and onto. Since f−1 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

RSS

FAQ

What does "rolls a hoover" mean, anyway?

"Roll a hoover" was coined by Christopher Locke, aka RageBoy (not worksafe). He enumerated some Hooverian Principles, but that might not be too helpful. My interpretation is that rolling a hoover means doing something that you know is stupid without any clear sense of what the outcome will be, just to see what will happen. In my case, I quit my job in an uncertain economy to try to start a business. I'm still not sure how that will work out.

Why is the HTML for this page not valid?

BlogSpot adds the advertisement that appears at the top of this page. That advertisement is not valid HTML and is outside of my control. I believe that aside from that ad, this page is valid HTML.