Saturday, December 11, 2010

Countability of Countable Union of Countable Sets Requires Countable Choice

The union of a bunch of countable sets is usually countable. This is very obvious if there are finitely many sets, say A, B, C. Pick an order for each set A={A1, A2, A3, ...} and then you can use the obvious ordering

  1. A1
  2. B1
  3. C1
  4. A2
  5. B2
  6. C2
  7. A3
  8. B3
  9. C3
  10. ...
So the finite union of countable sets is countable. So far so good.

But what if you have infinitely many countable sets to union together? If there are countably many sets, you might think of the elements of the union in a sort of lattice arrangement and trace the diagonals:
  1. A1
  2. A2
  3. B1
  4. A3
  5. B2
  6. C1
  7. A4
  8. B3
  9. C2
  10. D1
  11. ...
It would take a little more work to write a closed form expression for what number goes with which element, but every element of every set gets covered eventually. It's obvious, right?

I sure thought so. I have used this principle fairly frequently throughout my schooling assuming it was a straightforward principle. Speaking with several other math folks, no one seemed to be aware of a subtle problem: each set is countable, meaning each set has a bijection with the natural numbers (there is at least one way to enumerate the elements of each set). We could also say that for each set, there is a non-empty set of bijections with the natural numbers.

The problem is that, picking one element (bijection/enumeration) from each of infinitely many sets (the sets of ways to enumerate the elements of our sets) is not always possible under the ZF axioms. In other words, since all you know is that it is possible to enumerate each of the sets, the normal assumptions about math don't let you assign an enumeration to each of infinitely many things. It requires a special assumption called the axiom of choice (or the weaker "countable choice" for the case of a countable collection of sets).

So be warned! You must not assume willy-nilly that the countable union of countable sets is countable. You must include countable choice with your other assumptions.

If you're still interested, I recently found this interesting discussion of the problem:
https://www.dpmms.cam.ac.uk/~tf/cupbook3AC.pdf

Tuesday, December 7, 2010

Easement Law as a Pro-life Precedent

Anti-abortion messages often rely heavily on name-calling, but the immorality of abortion is not simply a subjective ideal. It's an application of a principle with thousands of years of legal precedent: the easement.
Easement is the legal right of an individual to use another's property, sometimes without permission. For example, if a farmer must cross another's land to reach the nearest town, he has partial claim on the part of the land he crosses. This claim is strengthened if there is any kind of implied permission on the part of the owner--such as having allowed the farmer to cross many times before.
In order for anyone to pass from conception to infancy, he or she must pass through another's property, that is, the mother's womb. Rights of easement are based at least partly on need, and the child's life depends on this passage. Thus, from a need-to-cross perspective, children have more right to the womb than any farmer ever had to a dirt road. Furthermore, a
llowing the egg to be fertilized in the first place may be interpreted as a type of implied permission to cross. According to the tradition of easement, the mother is obligated to allow the person to pass without interference.
No one needs to shout slogans about murdering babies to fight legalizing abortion. Besides the religious and philosophical objections we should all have to it, the law is clear about the right to pass through another's private property when one's livelihood, or one's life, is at stake.