Infinity

With the Q done, I have a chance to actually look at some of the other stuff I've done this semester. In particular, I botched one of the proofs on the first Set Theory homework rather badly. In discussing it with my professor today, I realized that it wasn't just gaps, the whole proof was plain wrong. Ah well, that's why you turn things in. Grades are secondary, it's the feedback that helps you learn.

Anyway, he suggested I give it some more thought. I did, and while I'm pretty sure you could come up with something to salvage my first effort, it's much simpler to turn things around. In general, I think that anytime you have a chance to work with finite sets, you should snatch it.

Any infinite partially ordered set contains either an infinite chain or an infinite totally unordered set.

My first attempt was to take a set that did not have an infinite totally unordered set and show that it must have an infinite chain. I did figure out how to make that work, but it's really messy. What about proving the contrapositive? That is:

Any partially ordered set that doesn't contain an infinite chain or infinite totally unordered subset is finite.

Let S be an partially ordered set that does not contain an infinite chain or infinite totally unordered subset. Let {u_i} be a maximal totally unordered subset of S. Let U_i = {s in S|u_i and s are ordered}. Let U_m be the largest such set.

Lots of definitions so far, but all pretty straightforward. We've got a finite number of sets, and every element of S is in at least one of the sets (or {u_i} wouldn't be maximal). If we can show the largest such set is finite, we're done.

Every element in U_m is in a finite chain with u_m. Consider only the maximal chains of U_m. The top element of each of those chains is either equal to or unordered with the top element of any other maximal chain (otherwise it the larger of the two could be added to the other "maximal" chain). Therefore, the top elements of all maximal chains form a totally unordered set and are must be finite in number. Remove them from U_m. The remaining chains are still maximal in the diminished U_m and thus the new top elements also form a finite totally unordered set. (I could introduce a bunch of new subscripts to formalize all this, but that's a pain in HTML, so I won't. Also, there is a little hand-waving here in that the claim that the remaining chains are maximal is one that really should be backed up. It's a fairly straightforward proof by contradiction that I'll leave as the proverbial "exercise for the reader"). Remove them as well. As all chains are of finite length, this process will result in an empty set after a finite number of iterations. Thus, U_m is a finite disjoint union of finite sets and must be finite.

Thus all of {U_i} are finite which implies S is finite.

Note, we never claimed (though it's true) that the number of chains is finite. The trick was seeing that, as long as our collections of ordered and unordered items are finite, we have really nice properties within those collections (like, maximal elements) that make the proof much easier. The same can be said when restricting arguments to countable collections versus uncountable. Generally speaking, the only uncountable sets of interest to stats guys like myself are pretty well behaved, but I do recall a few proofs from Probability Theory 30 years ago that got mighty complicated when all edge cases were considered. I expect we'll see a few more of those as this course goes on.