0
$\begingroup$

(I noticed that there was a very recent question which dealt with similar material here; I didn't want to query in the comments, but merged answers might be appropriate.)

My expectation with this proof was, "Well, there are some chains in $X$ which are going to be maximal (under the ordering in $\mathscr{X})$, and these chains will have upper bounds, so those upper bounds will be maximal elements in X. So (loosely) we should just pick any maximal chain using AC and take its upper bound." But the maximal element which was located belonged to something called a tower (see the link for definition).

It seems to me that the smallest tower is uniquely determined by an arbitrary choice function. We have at least one choice function $f: \mathcal{P}(X) \to X$, and given some starting choice from $\hat{A} = \{x \in X: A \cup \{x\} \in \mathscr{X}\}$ for $A$ = $\varnothing$, it seems like the sequence of terms which belong to any "tower" is determined by the arbitrary choice function. I say this because we start necessarily with $\varnothing$, and continue to add elements to any "tower" based on the choice function for whatever set results from the last element we added. (To wit: we get some $a_0$ to union with the empty set from our "adjunction function," $g(A) = A \cup f(\hat{A} - A)$, i.e. $a_0$ = $g(\varnothing)$. Then there is again a predetermined $a_1 = g(\{a_0\})$ which we must union with $\{a_0\}$; and so forth.) So every tower contains $\varnothing$ and has to contain its "successor" under $g$, and so forth.

Call a chain in $\mathscr{X}$ "complete" if it contains its maximal element (under inclusion ordering); denote the complete chain determined by the choice function as $\mathscr{C_0}$. My question is: is the set of towers just the set of unions of any number of complete chains with $\mathscr{C_0}$?

  • 1
    The existence of maximal chains is predicated on the possibility of having a chain to which we cannot add any elements. You cannot just *assume* that maximal chains exist if you are trying to establish, essentially, that they do. So that's why one needs to do a bit more work in order to show that there actually *are* such things as maximal chains.2012-07-01
  • 0
    Are you referring to the "executive summary" in the preface?2012-07-01
  • 1
    The argument you give is very similar to the one given by George Bergman in his Zorn's Lemma handout [here](http://math.berkeley.edu/~gbergman/grad.hndts/) available in Postscript. While it is true that the "smallest tower" is determined, it would be difficult to establish this formally within set theory without developing a lot of other machinery; the "and so forth" needs to be formalized, and this is difficult to do without transfinite induction and ordinals, which Halmos does not have in hand at this stage.2012-07-01
  • 0
    (To answer your first comment, yes, I was)2012-07-01
  • 0
    @Arturo Are you saying that the minimal tower *is* what I think it is?2012-07-01
  • 0
    You do not know whether every chain has a maximal element. The hypotheses of Zorn's Lemma only guarantee that chains have *upper bounds*, not necessarily maximal elements. So you cannot talk about "its maximal element" in relation to an arbitrary chain in your set until you determine whether it is the case that every chain has a maximal element. So your proposed definition of "complete" is not necessarily well-defined.2012-07-01
  • 0
    To answer your second comment: Yes, I *think* you are correct. If you can, take a look at Bergman's handout (I know some people have trouble reading it because it's in postscript).2012-07-01
  • 0
    I am somewhat confused, maybe over terminology. I say $b$ is an upper bound of $A$ included in $X$ if every $a \in A$ satisfies $a \leq b$; I say $m$ is a maximal element if there is nothing in $A$ which is strictly larger than $m$. Doesn't the former imply the latter?2012-07-01
  • 0
    No, it does not. A maximal element is an element $a$ of $A$ such that no element of $A$ is strictly larger than $a$. In the case of a totally ordered set, a maximal element must also be a maximum. Bounded above does not imply "has a maximal element". Consider a set $X$ that contains a copy of $\mathbb{N}$, and "then" another copy of $\mathbb{N}$, think of them as "blue and red naturals", with blue naturals all smaller than the red naturals. The subset of all blue naturals is bounded above (for example, by the red $0$), but it contains no maximal elements.2012-07-01
  • 0
    Your point is that chains (of chains) may have upper bounds which are not chains?2012-07-01
  • 0
    No, my point is that chains may have upper bounds but not have maximal elements. Again: if $P$ is a partially ordered set, then a **maximal element** $p\in P$ is an element such that for every $x\in P$, $p\leq x\implies p=x$. That's the "maximal" to which Zorn's Lemma refers. **In abstract**, being a tower does not, by itself, imply that the tower must contain a maximal element. The definition does not require it; the fact that the tower is contained in a set that satisfies the assumptions of Zorn's lemma does not require it. (cont)2012-07-01
  • 0
    (cont) If you want to argue that a tower in $X$ *must* contain a maximal element (and presumably, you mean "maximal-in-the-tower", not "maximal-in-$X$"), then *you have to prove it*. Under the assumptions of Zorn's Lemma, you require every chain to have upper bounds; you do **not** require every chain to contain maximal elements. The set $\mathbb{N}\cup\{\omega\}$, ordered so that $\omega$ is larger than every natural number, is a set that satisfies the assumptions of Zorn's Lemma, but the chain $\mathbb{N}$ *has no maximal element*.2012-07-01
  • 0
    (I'm sorry, I was forgetting the necessity of being a member of the chain to be a maximal element, versus the case for upper bounds. I take your point.)2012-07-01
  • 0
    What does this mean, however, for my argument?2012-07-01
  • 0
    It means your argument is not well founded; you are *assuming* that every chain will "have a maximal element". And the definition seems to assume that this maximal element may be in the chain or outside it. This is incorrect. Now, you could define instead a chain to be complete if it has a **maximum** (that makes sense, and is in fact what would happen if a chain contained a maximal element). The rest of your argument is ill-founded, because you have not established that the choice function "determines" a complete chain. The "and so forth" is not a valid mathematical argument. (cont)2012-07-01
  • 0
    (cont) That's **precisely** why Halmos has to go through the acrobatics he does in order to establish his result: because "and so forth" is not a valid set operation that you can use to "set the process going". You need a lot more machinery than you have in hand to actually *formalize* that intuitive idea, so your choices are to either develop that machinery, or get around it. Halmos gets around it; you are trying to do without the machinery and still go through the idea, and you can't.2012-07-01
  • 0
    Hmm, you're right. If we rephrase the criterion for completeness as the third criterion of being a tower (this is basically what I had in mind), then is my description of the set of towers accurate?2012-07-01
  • 0
    Just to be clear, I do take your point; you could have a totally ordered set of terms, put in an increasing sequence without terminus, but still have it be bounded above. I'm just trying to say that a tower is basically "a chain which is as big as it can be, and includes the minimal tower". Do I need ordinals to say that correctly?2012-07-01
  • 0
    I don't think so. Let $X$ be the set that contains $\mathbb{N}$ in its natural order, and two other objects, $\omega$ and $\Omega$, which are incomparable, and both greater than every natural number (this can be constructed with sets so that we are dealing with towers in the same sense as Halmos). Your choice function will be defined to give the least upper bound if the set is contained in $\mathbb{N}$ and bounded above, $\omega$ if it is contained in $\mathbb{N}$ and unbounded, and the maximum otherwise. (cont)2012-07-01
  • 0
    (cont) Then your set $\mathcal{C}_0$ would be $\mathbb{N}\cup\{\omega\}$; but I believe that $\mathbb{N}\cup\{\Omega\}$ would also be a tower, and yet not be a union of elements of $\mathcal{C}_0$.2012-07-01
  • 0
    As to your last comment: No; a tower is not a "chain that is as big as it can be". If that were the case, then no tower could properly contain another tower, and that is false.2012-07-01
  • 0
    I am trying to follow your examples with $\mathbb{N}$ and the omegas; the conditions are somewhat unclear.2012-07-01
  • 0
    You might put the counterexample into the form of an answer; then I could accept it.2012-07-01
  • 0
    I'm not giving you sets that directly satisfy the extra conditions that Halmos puts on the sets in which he defines towers, rather I'm giving you partially ordered sets directly. If you want to translate them into sets in which the order is by inclusion, etc., you need to use the same "translation" Halmos uses in the first part of his proof.2012-07-01

0 Answers 0