# A generic argument in Kuratowski-Zorn Lemma

Many applications of Kuratowski-Zorn Lemma exhibit a common principle, that I could best summarise as:

If one defines a structure by "nice" conditions, then Kuratowski-Zorn shows a maximal structure exists.

Here, "nice" conditions are roughly the ones of the form $\forall a,b,c ... : \ \phi$ where $\phi$ is a condition not involving any quantifiers, of some special form.

This is admittedly vague, and my question is precisely how can this be made precise and rigorous. I think the general principle is best shown by an example.

Suppose that you want to use K-Z Lemma to show that maximal ideals exist in any ring $A$ (commutative and with $1$). The natural thing is to consider the family of all ideals $\mathcal{I}$ (excluding $A$ itself) as family of sets partially ordered by inclusion, and then show that it satisfies the assumptions of K-Z Lemma --- once we do this, the Lemma ensures the existence of the sought maximal element.

Thus, it remains to show that $\mathcal{C} \subset \mathcal{I}$ is a chain, then it has an upper bound, and the only natural candidate for this upper bound is $\bigcup \mathcal{C}$. Note that until this point, we never mentioned what it means for a set $I$ to be a ideal. A possible (natural) definition could be:

1. $I \cdot A \subset I$
2. $I+I\subset I$
3. $1 \not \in I$

but we can just as well write it as:

1. $(\forall a,b \in A) :\ (a \in I) \Rightarrow (a \cdot b \in I)$
2. $(\forall a,b \in A):\ (a,b \in I) \Rightarrow (a + b \in I)$
3. $\neg (1 \in I)$

Now, the problem boils down to proving that the conditions 1,2,3 are preserved by arbitrary unions of pairwise comparable sets. Thus, let $M := \bigcup \mathcal{C}$, assume that one of the conditions holds for all $I \in \mathcal{C}$; we show that it holds for $I = M$. For condition 3., things are not very interesting, so let us restrict the attention to 1,2. Each of these conditions is of the form $(\forall a,b \in A) :\ (\square \in I) \Rightarrow (\triangle \in I)$. To prove this holds for $I = M$, we can proceed as follows: First fix $a,b \in A$. Then pick $I_0 \in \mathcal{C}$ sufficiently large that $\square \in I_0$ (if no such $I_0$ exists, then the implication is vacuously true!). Since the condition holds for $I = I_0$, $\triangle \in I_0$. But $I_0 \subset M$, so $\triangle \in M$. Since $a,b$ were chosen arbitrarily, condition holds.

The argument runs smoothly enough, and one could certainly argue that I am overcomplicating things. What pains me, however, is that I could have put anything (made up from $\cdot$,$+$ and the variables) in the place of $\square$ and $\triangle$ above, and the argument would remain unchanged. Thus a more general fact is true:

If a structure is defined by requiring that $S$ is such structure if and only if it satisfies any number of conditions of the form $(\forall a,b,\dots):\ (\square \in S) \Rightarrow (\triangle \in S)$, then there is a maximal such structure contained in $A$.

In principle, this is not a big problem, since one can always do the standard reasoning, paste in the appropriate place a verification that everything works fine when passing to the monotonous sum, and be done. Nevertheless, it does feel a little "unmathematical" to be repeating the same reasoning all over.

What interests me is: what is the most general "type" of conditions that can be used in the "standard" reasoning? (i.e.: How can one make the notion of "nice" from the top precise?) Can the above thoughts be turned into something rigorous?

-
An interesting (counter)example is that there is a group with no maximal subgroup: en.wikipedia.org/wiki/Pr%C3%BCfer_group –  Colin McQuillan Jan 30 '13 at 21:49
@Colin Although if you allow the group itself as a subgroup, then the Kuratowski–Zorn lemma shows that a maximal subgroup exists because of what you said in your answer (of course you don't need the lemma for this; I just wanted to point out that it does apply.) –  Trevor Wilson Feb 13 '13 at 20:39

A first order theory $T$ is called inductive if it consists of formulas of the form $$(\forall x_1) \dots (\forall x_k) (\exists y_1) \dots (\exists y_\ell) p$$ where $p$ is quantifier-free. If $M$ is a structure for the language of $T$, and $M$ is the union of a family of substructures $(B_i\mid i\in I)$, totally ordered by inclusion, such that each $B_i$ is a $T$-model, then $M$ is a $T$-model (exercise 3.4.b, Notes on Logic and Set Theory, P. T. Johnstone).

This includes your example of ideals in a ring, by considering the theory of $A$-modules. An example of a theory that cannot be expressed as an inductive theory is the theory of totally ordered sets with a greatest and least element, and indeed $\mathbb R=\bigcup_{n\in\mathbb N} [-n,n]$ shows that the union of such sets does not always have a greatest and least element.

-

I think the answer you are looking for is unlikely to exist. Instead of Zorn's Lemma we can consider just the principle of induction (the former is a generalization of the latter, so treating a simpler case and showing an answer to be unrealistic should suffice).

So, for the principle of mathematical induction you can argue as well that it is 'unmathematical' to go through the motions each time you use induction to prove something. It would be a lot nicer to just be able to look at the proposition you are trying to prove and have a simple criteria that will tell you "sure, that can be proved by induction". But, it is very unlikely for such a criterion to exist. Sometimes induction argument are trivial and sometimes they are complicated. Sometimes it is clear what to induct on and sometimes not. Moreover, the principle of mathematical induction is a second order statement in Peano Arithmetic, so you might as well be asking for a quick criterion, given a set of natural numbers, to deduce if it's all of the naturals or not. Again, unlikely.

Moreover, I think the question is barking up the wrong tree. If is not the fault of a technique that you are becoming good at it. The first time you see induction or an application of Zorn's Lemma it may look very difficult. But after you saw 100 such arguments then things become easy. It's a good sign that you have mastered a technique. It does not mean the technique is 'unmathematical' just because some parts of it are routine.

-
Apologies for making it sound as if I were complaining that Kuratowski-Zorn Lemma is "unmathematical". My feelings were rather that there seem to be many proofs that seem to share a large part in common, so hopefully a part of those reasonings could be "abstracted away". Thank you for pointing out how unlikely a general criterion is to exist. –  Feanor Jan 30 '13 at 22:01

I would think that "nice" would imply something which allows using the KZL. The usual argument would be the construct a partial order via inclusions, or some other directed system, and if we can show that every chain has an upper-bound, then we can use the KZL.

For example linearly independent sets have this "nice" property. Ideals as well. Note that those are very nice. The upper-bound of a chain would be its union, although it doesn't have to be that way.

If we want to characterize "very nice" structures then we would say that those are the structures where the union of a $\subseteq$-chain is its upper-bound. For this we want to have properties which reflect "down", so if they would fail, the would have to fail somewhere in the middle of the chain. This would be a contradiction, because those properties should hold for all the members of the chain.

If we return to linearly independent sets, then we see that if the union of the sets in the chain is not linearly independent then it must occur somewhere within the chain, i.e. one (and so cofinally many times) of the members in the chain is not linearly independent.

-