# Verification of a proof involving Hausdorff max. principle and collections

I am given this proposition to prove which is a corollary to HMP(Hausdorff maximality principle). My two concerns are: 1. is my attempted proof correct? and 2. Is HMP applicable even when we're dealing with collections instead of sets? This last point troubles me because after reading Asaf Karagila answer here I try to be more careful when talking about collections.

Here is the corollary:

Proposition: Suppose $X$ is a non-void set and $A$ is some non-void collection of subsets of $X$, and $S$ is a subcollection of $A$ which is monotonic. Then there exists a maximal monotonic subcollection of $A$ which contains $S$.

I have included a proof outline because: 1. I still can't write proofs correctly so my reasoning in the final proof can appear wrong and 2. So that you can figure out where I got things wrong, if i did.

Proof outline: First we define a relation $\leq$ on $A$ given by $A_i \leq A_j$ iff $A_i \subset A_j$ for $A_i, A_j \in A$ and we show that $\leq$ is a partial ordering. Then we find a subcollection $S$ of $A$ such that the ordering is linear on $S$. Finally we apply HMP to show the existence of the subcollection asked in the proposition.

Proof: Let $\leq$ be a relation on $A$ such that $A_i \leq A_j$ iff $A_i \subset A_j$ for $A_i, A_j \in A$. $\leq$ is a partial ordering since it is: 1. reflexive: if $A_i \in A$ then $A_i \leq A_i$, 2. anti-symmetric: if $A_i \leq A_j$ and $A_j \leq A_i$ then $A_i = A_j$ and 3. transitive: if $A_i \leq A_j$ and $A_j \leq A_k$ then $A_i \leq A_k$. Let $S$ be a subcollection of $A$. Since there is a partial ordering on $A$ then there is a partial ordering on $S$. Furthermore let $S$ be the collections of those sets $S_i$ such that $S_1 \subset S_2 \subset S_3 \subset \dots \subset S_n$, for $S = \{S_1, S_2, S_3, \dots, S_n\}$. We can verify that for any two sets $S_i, S_j \in S$; $S_i \leq S_j$ or $S_j \leq S_i$, therefore $\leq$ is a linear ordering on $S$. By HMP, there exists a set $M$ such that it is maximal and $S \subset M$. And since $M \subset A$ and $A$ is monotonic, $M$ is monotonic as well. $\square$

If this proof is correct (or even if not) is there any other proof(s)?

### UPDATE 1:

Here is the statement of HMP I'm using:

Any linearly ordered subset of a partially ordered set is contained in maximal linearly ordered subset.

### UPDATE 2:

As per answer by Asaf Karagila bellow and comments, I have a final proof with minor corrections. It appeared better to leave the original proof for future reference without future readers having to go through revision history to understand what was happening. So here we go:

Proof: Let $\leq$ be a relation on $A$ such that $A_1 \leq A_2$ iff $A_1 \subseteq A_2$ for $A_1, A_2 \in A$. $\leq$ is a partial ordering since it is: 1. reflexive: if $A_1 \in A$ then $A_1 \leq A_1$, 2. anti-symmetric: if $A_1 \leq A_2$ and $A_2 \leq A_1$ then $A_1 = A_2$ and 3. transitive: if $A_1 \leq A_2$ and $A_2 \leq A_3$ then $A_1 \leq A_3$. Let $S$ be a subcollection of $A$. Since there is a partial ordering on $A$ then there is a partial ordering on $S$. Also since $A$ is monotone, $S$ is monotone as well. We then verify that for any two sets $S_1, S_2 \in S$: $S_1 \leq S_2$ or $S_2 \leq S_1$, therefore $\leq$ is a linear ordering on $S$. By HMP, there exists a set $M$ such that it is maximal and $S \subset M$. And since $M \subset A$ and $A$ is monotonic, $M$ is monotonic as well. $\square$

-
Unless you are working in some weak formal system, all the collections in your question are sets. On the other hand, if you are working in some weak axiomatic system, you need to let us know which one, because the correctness of the proof will depend on it. – Andrés E. Caicedo Feb 19 '13 at 2:28
@AndresCaicedo well part of why i have troubles with collections is because i haven't been introduced to the importance of specifying which system i'm working in. Therefore part of the answer will specify in which system the proof is (might be) correct. – nt.bas Feb 19 '13 at 2:39
I do not know how you can be expected to prove something if you have a principle that only applies to sets, and you do not know that certain objects are sets. I would expect you can assume that the collection of all subsets of a set $A$ is a set (the power set $\mathcal P(A)$). I would also expect that you can assume that subcollections of sets are sets. – Andrés E. Caicedo Feb 19 '13 at 2:42
@AndresCaicedo In this case, I assumed that the collection of subsets of $X$ is a set and used HMP. On the other hand, i'm curious to know how HMP behaves with collections, any collection (not just power sets). So if I get your comment right, to work with those collection, we have to be careful about which axiomatic system we're working with. Did i get you right? – nt.bas Feb 19 '13 at 2:50
Yes. In a general setting, to apply something like HMP to an "arbitrary" collection, you will need more, perhaps something like the axiom of foundation, that should allow you to "stratify" your collection into sets. But it is not true that you can just apply HMP in every situation; for example, global choice is not a theorem of the standard system of set theory, but it would follow from something like HMP applied to a proper class. – Andrés E. Caicedo Feb 19 '13 at 2:54

The caveats that Andres Caicedo mentioned in the comments are valid, as is your concern. Generally speaking we cannot apply HMP to collections. In ZFC, however, if we consider any collection of subsets of $X$, where $X$ is a set, then this collection itself is a set as well.

If you are working naively then it usually means that this collection is a set. I can tell that when I was a teaching assistant for the past three years in an intro to set theory course, we mention on the first class that not all collections are sets, but as we work naively we will always treat our collections as sets and it's fine (we never really talk about the collection of "all sets" and so on). Still I suggest you check this with your teachers, couldn't hurt, but be prepared to a possibility they shrug with a surprised look "of course they are sets". It could happen.

As for your proof itself, it seems to me that you are slightly confused with the details. You are given a linearly ordered subset $S$. Furthermore you are not given that it is finite.

Lastly if you are not given that $A,S$ are sets it is probably best to assume that $M$ itself is a collection as well.

Final remark:

I'm not sure how exactly you formulate HMP. If it is the existence of a maximal chain, then you need to somewhat change your proof in order to show that $M$ exists, for example by taking a new partial order - all those monotone subcollections extending $S$, then by HMP there is a maximal chain in that partial order and its union is the wanted $M$.

Edit:

It seems that your proof is correct, in the sense that you really just apply HMP to $A$ with the $\subseteq$ relation. Since $S$ is monotonic it is contained in a maximal chain (which is itself monotonic).

As for the foundational issue, the file you link (in the comments) seems to be approaching to this issue naively. So I feel it is somewhat safe to assume that these collections are sets, because they are all elements of the power set of $X$.

It is true that some caution is required because you can talk about the collection of all sets; or the collection of all definable classes (whatever that means); these cases require careful handling and understanding the fine points between sets, classes and collections.

But sure enough, naively speaking we usually talk about collections of subsets of some set $X$, and these collections themselves are sets so it is all fine.

(There is again the caveat you may run into, that the universe of sets is not a fixed object, and we can add and sometimes remove sets from it; but in the naive approach, and in the basic mathematical introduction to set theory you can be safe in assuming that you have fixed one universe of all the sets you will ever need, and more.)

-
@Andres: Oops! Thanks! – Asaf Karagila Feb 19 '13 at 6:44
Thanks very much! You said [quote] You are given a linearly ordered subset S. Furthermore you are not given that it is finite. In the proposition, $S$ is given as a subcollection of  $A$. Since a $A$ is a collection of sets (here subsets of $X$), one expects $S$ to be a collection of sets as well. For working with it I had to assume it is a set then prove it is linear. What do you think? – nt.bas Feb 19 '13 at 7:22
Also as you mentioned, $S$ is not given finite but I don't think the proof depends on it. Does it? As for the proof, I used HMP after proving $S$ which is subcollection of $A$ to conclude that $M$ which is given to be a subcollection of $A$ as well and also $S \subset M$, is the maximal monotonic subcollection we're looking for. I fail to see where my proof is wrong! :-( And oh i'm teaching myself and this proposition if from this pdf so no teachers to ask. My book of reference is naive set theory by Halmos. Thanks! – nt.bas Feb 19 '13 at 7:29
Hoho, I meant ... used HMP after proving $S$ is a linearly ordered set... (in this case a subcollection but we take it as a set). – nt.bas Feb 19 '13 at 7:37
@nt.bas: I have edited my answer; as for the finiteness of $S$. You are correct, it does not harm the actual proof. But you are giving a needless limitation. This is wrong because later on you may find yourself working with sets which are far from finite, and the rules of finite sets will not apply to the general case. – Asaf Karagila Feb 19 '13 at 8:31