Zorn’s Lemma and Revealed Preference

I don’t think I ever understand why Axiom of Choice is always singled out; why it is special (and controversial) relative to other axioms. Gradually, I realized that probably it is not. It is just one of the axioms that found set theory. Anyways, this is not what we, as economists, should care. This entry is about Zorn’s lemma and revealed preference. I mentioned axiom of choice first just because its close relation to Zorn’s lemma. To complete the discussion of axiom of choice, let me just put the version that I personally like most here

Axiom of Choice: Cartesian product of non-empty sets is non-empty.

Now Zorn’s lemma and revealed preference. Revealed preference is one of the most fundamental result in economics. It builds a bridge between observable choice data and underlying (but invisible) preferences. There are various versions of the result but the idea is the same

Revealed Preference: Any set of choice data that satisfies some axiom of revealed preference can be rationalized by a preference relation.

In other words, however limited the data are, we can find a preference defined over the whole commodity space to make sense of the data, given that the data satisfy some conditions. Zorn’s lemma allows a compatible extension from the limited scope provided by the data to the whole commodity space.

Zorn’s Lemma: If every chain in a partial-ordered set has a upper bound, then the partial-ordered set has a maximal element.

Zorn’s lemma is essential to the following result which basically makes the revealed preference a corollary.

Szpilrajn’s Theorem on total extension of preorders: Any preorder has a compatible extension to a total order.

Below I just list the definitions of the relevant concepts assuming familiarity of common properties of binary relations

  • Preorder Reflexive+Transitive
  • Partial order Preorder+Antisymmetric
  • Total order Partial order+Complete
  • Transitive closure of a binary relation R over X is the smallest relation over X that contains R and is transitive
  • Chain a totally ordered subset of a partial-ordered set
  • A binary relation R* over X is a compatible extension of R if R* extends R and preserves the asymmetry of R.

Proof of Szpilrajn’s Theorem:

Let R be a preorder over X and E the set of all preorders that compatibly extend R. Clearly E is non-empty as it contains at least R itself.

Consider any non-empty chain C in E by set inclusion. We want to show that U the union of elements in C is an upper bound of C (so that we can use Zorn’s lemma). That is we need to show that all elements of C is contained in U; alternatively, U is (still) a preorder that compatibly extends R. This can be shown easily by using the properties of individual element in C (at the end of the day, one needs to show that U is reflexive, transitive, and compatibly extends R).

By Zorn’s lemma, we know that E has a maximal element S. The last step is to show that S must be total. Suppose not and there exists a pair (x,y) such that neither xSy nor ySx. Consider T=S\cup\{(x,y)\} and W which is the transitive closure of T. Since W includes S, if we can show that W is a compatible extension of R (reflexive is obvious), we reach a contradiction (that S cannot be the maximal element).

Again suppose W does not compatibly extend R (or S) and there exists a pair (u,v) in X such that (uSv) \wedge\ ^\neg (vSu) but vWu. By definition of transitive closure, we can construct a finite sequence such that v=c_1 T c_2 T \cdots T c_{n-1} T c_n=u. Since T and S only differ over (x,y) and if no c_i is x or y, we obtain the contradiction. Otherwise, we can find (c_i, c_{i+1})=(x,y). If this is the case, y=c_{i+1} S\cdots S c_n=u S v=c_1 S \cdots c_i =x contradicting that S cannot rank x and y.

Thus the proof is complete and any maximal compatible extension of R is a total preorder.

The definitions and proof are from Aliprantis and Border’s book. I put it here just because I did not know why economists cared about Zorn’s lemma and this is an interesting illustration in my opinion. And I want to throw away my scratch papers.

[1]Aliprantis, Charalambos D., and C. Kim. “Border. 2006. Infinite Dimensional Analysis: A Hitchhikers Guide.”


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s