# What kind of Choice am I making in this argument?

I have an argument that's supposed to imply Choice, but I'm afraid it may be using some choice. If it does, how much choice?

This is the part of the argument that might use some Choice. I marked the parts that I think MIGHT use Choice ("[1]", "[2]", "[3]").

Assume:

• $X$ is compact. (Every open cover (collection of open sets whose union is $X$) has a finite subcover.)
• We are given a collection of open sets $P$ from $X$ such that:
• $P$ covers $X$.
• For every totally ordered subcollection of $P$, there is an element in $P$ which contains the union of that subcollection (i.e. every chain has an upper bound, the hypothesis of Zorn's Lemma).

Claim:

• $P$ has a maximal element (the conclusion of Zorn's Lemma).

Proof?:

• Let $P_0 := P$.
• Assume $P$ has no maximal element.
• At step 0:
• [1]Take a finite subcover of $P_0$.
• Since it's finite, we can select the open sets to be independent: each open set contains a point not in the others.
• Call it $Q_0$.
• For each element $q_i$ in $Q_0$, set $s_{i, 0} := q_i$.
• Set $P_1$ to be the elements of $P$ which are greater (strictly contain) some element of $Q_0$.
• None of the elements of $Q_0$ were maximal, so $P_1$ covers $X$.
• At step $n$:
• Do the same process as above to construct $P_{n+1}$.
• [2]Choose $s_{i, n+1}$ to be some element of $Q_n$ (as in the base case) which contains $s_{i, n}$.
• For limit step $<\alpha$:
• [3]Take upper bounds for each of the sequences we've built so far.
• The sequences we built form totally ordered subcollections of $P$, so each has an upper bound in $P$.
• Since each element of the original cover $Q_0$ is contained in the upper bound, this forms a finite subcover.
• Adjoin these upper bounds to the sequences.
• As before: Choose $P_{\alpha}$ to be the elements of $P$ which are greater than these upper bounds.
• Since we always remove the finite subcover from the next step, each sequence is a sequence of distinct elements (though not necessarily distinct from each other).
• By transfinite induction, we inject the ordinals into $P$.
• By contradiction, $P$ has a maximal element.
• First mistake, not related to choice, just because the open cover is finite doesn't mean you can choose it to be disjoint, what if the space is $[0,1]$ and you chose the finite subcover to be $\{[0,\frac12),(\frac14,1]\}$? Commented Oct 23, 2014 at 18:55
• Not disjoint. Independent. I want each one to be "essential" to covering: for each open set in the finite subcover, there should be a point that only it covers. Commented Oct 23, 2014 at 19:06
• Oh, alright. Then you essentially use the axiom of choice there, because you need to choose an enumeration for $Q_n$ in order to do this. Commented Oct 23, 2014 at 19:09
• @AsafKaragila The argument may have failed, but my intuition for choice is much improved now. Commented Oct 23, 2014 at 19:33
• For future reference, the usual term for what you’ve called a cover by independent sets is irreducible cover. Commented Oct 23, 2014 at 20:03

All three points you suspect choice are using choice. Although in the third one you can perhaps remove it.

1. There might be many finite subcovers at each step, and you have to choose one each time. How do you choose it?

2. There might be many candidates at each time. How do you choose them? Ideally, you have a finite enumeration of $$Q_n$$, and you choose from it. But how do you choose the enumeration of $$Q_n$$? Choice hides right there.

The same use of the axiom of choice essentially comes into play when you create $$Q_0$$. In order to do this, you need to enumerate the finite subcover and go over the enumeration, but different enumerations give different $$Q_0$$'s, so you need the axiom of choice once you do this infinitely many times.

3. If you mean one upper bound for each sequence, you might have to resort to the axiom of choice; if you take all of them, then it's probably fine.

Upon re-reading, I think this trick is not applicable here.

In either case, in the general case, I see absolutely no way of removing the need for the axiom of choice here. I'm not even sure that you can bound the amount of choice needed for the first issue, let alone for the third. In the second issue you only need to be able and choose finite numerations, that's not "that bad", but it's still something.

• For the second, isn't it weaker than full choice? For the third, I think I would need an upper bound for each sequence, because I'm not guaranteed one for all of the sequences (it would be a maximum of $P$). Commented Oct 23, 2014 at 19:09
• Yes, the second one only requires choice from families of finite sets. For the third one, do you want a unique upper bound for each sequence, or do you want all upper bound for each sequence, that's my point: in the former choice is needed, in the latter probably not. Commented Oct 23, 2014 at 19:11
• For each sequence, I want to append an upper bound to it, so that I can continue going up. Commented Oct 23, 2014 at 19:12
• You keep not answering my question. Suppose that a sequence has infinitely many upper bounds. Do you want just one of them, or do you want all of them? I get that you one an upper bound, but you keep not answering me whether or not it's just that one, or you are willing to allow other upper bounds as well. Commented Oct 23, 2014 at 19:15
• To append an upper bound to it, I would need to choose a particular upper bound, no? Are you asking if I want the least one? I'm not sure what you mean by "allow". Commented Oct 23, 2014 at 19:16