Recently, while trying to understand another result, I began to wonder about the following question:

Given some orderable set $A,$ what (if anything) can we conclude about the order type or cardinality of a (maximal) $\subsetneq$-chain of $\mathcal{P}(A)?$

I was initially only entertaining the notion for a countably-infinite set, and my first idea was good (more on that in a moment), but didn't actually turn out to answer the question. For one thing, I realized that I had subconsciously been treating my $\subsetneq$-chains as well-ordered, which wasn't intended. For another, it gave me no insight into possible cases in which $A$ was orderable, but not well-orderable. (Obviously, I'm talking about $\mathsf{ZF},$ here, not $\mathsf{ZFC}.$)

The upside is that the initial conclusions I came to seem to hold for all well-ordered chains of $\mathcal{P}(A),$ given any well-orderable set $A,$ though they didn't provide a full classification of such chains. Edit: Together with the fourth result (which I wasn't able to prove until later), the well-ordered chains of any well-orderable set's power set can be fully classified, with no need for any Choice.

Given a well-orderable set $A,$ let $|A|$ indicate the cardinal of $A$ (necessarily a natural number or an aleph number), and let $|A|^+$ indicate the least well-ordered cardinal greater than $|A|$ (necessarily a natural/aleph number, respectively, if $|A|$ is a natural\aleph number). Then the following hold:

  1. For any ordinal $\alpha<|A|^+,$ there is a well-ordered chain $\mathcal{C}$ of $\bigl\langle\mathcal{P}(A),\subsetneq\bigr\rangle$ with order type $\alpha.$
  2. For any successor ordinal $\alpha$ such that $|A|<\alpha\le|A|^+,$ there is a well-ordered chain $\mathcal{B}$ of $\bigl\langle\mathcal{P}(A),\subsetneq\bigr\rangle$ with order type $\alpha,$ such that $\mathcal{B}$ is maximal among the well-ordered chains of $\bigl\langle\mathcal{P}(A),\subsetneq\bigr\rangle.$
  3. Given any $\mathcal{B}\subseteq\mathcal{P}(A)$ such that $\mathcal{B}$ is maximal among the well-ordered chains of $\bigl\langle\mathcal{P}(A),\subsetneq\bigr\rangle,$ we have that $|\mathcal{B}|=|A|+1,$ and that the order type of $\mathcal{B}$ is a successor ordinal.
  4. Given any well-ordered chain $\mathcal{C}$ of $\bigl\langle\mathcal{P}(A),\subsetneq\bigr\rangle$ that is non-maximal among such well-ordered chains, we have that $|\mathcal{C}|\le|A|,$ and so the order type of $\mathcal{C}$ is some ordinal $\alpha<|A|^+.$

My proof outlines follow, then I will come back to my central question.

  1. Since $\alpha<|A|^+,$ then $|\alpha|\le|A|$ by trichotomy of well-ordered sets, so there is an injection $f:\alpha\to A.$ Using $f,$ we can define $g:\alpha\to\mathcal{P}(A)$ by $$g(\beta):=\bigl\{f(\gamma)\mid \gamma\in\beta\bigr\}.$$ Readily, $g$ is an injective order-embedding $\langle\alpha,\in\rangle\to\bigl\langle\mathcal{P}(A),\subsetneq\bigr\rangle;$ its range is the desired set $\mathcal{C}.$

  2. Take any successor ordinal $\alpha$ such that $|A|<\alpha\le|A|^+,$ so that there is some ordinal $\beta$ with $|A|\le\beta<|A|^+$ such that $\alpha=\beta\cup\{\beta\}.$ Since we readily have $$|A|\le|\beta|\le \beta<|A|^+,$$ then $|\beta|=|A|.$ Thus, there is a bijection $f:\beta\to A.$ Using $f,$ we can define $g:\alpha\to \mathcal{P}(A)$ by $$g(\gamma):=\bigl\{f(\delta)\mid\delta\in\gamma\bigr\}.$$ Readily, $g$ is an injective order-embedding $\langle\alpha,\in\rangle\to\bigl\langle\mathcal{P}(A),\subsetneq\bigr\rangle;$ its range is the desired set $\mathcal{B}.$

  3. Given any such $\mathcal{B},$ since $A$ is its $\subsetneq$-greatest element, then the order type of $\langle\mathcal{B},\subsetneq\rangle$ is immediately a successor ordinal. Consider the relation $\prec$ on $A$ given by $a\prec b$ if and only if there is some $B\in\mathcal{B}$ such that $a\in B$ and $b\notin B.$ This is trivially irreflexive, and is readily transitive on $A$ by $\subsetneq$-orderedness. Given any non-empty $C\in\mathcal{P}(A),$ we have $C\cap A=C\neq\emptyset,$ so there is a $\subsetneq$-least element $B\in\mathcal{B}$ such that $C\cap B\neq\emptyset.$ By $\subseteq$-maximality of $\mathcal{B},$ we readily have that $B\cap C$ must be a singleton, and its unique element is the $\prec$-least element of $C.$ Thus, $\langle A,\prec\rangle$ is a well-ordering, and moreover, the elements of $\mathcal{B}$ comprise the initial segments of said well-ordering. Since $b\mapsto\{a\in A:a\prec b\}$ is readily an injection $A\to\mathcal{B}$ with range $\mathcal{B}\setminus\{A\},$ then $|\mathcal{B}|=|A|+1,$ as desired.

  4. [Added later] Let $\prec$ be any well-ordering of $A,$ and let $\mathcal{C}$ be any well-ordered chain of $\bigl\langle\mathcal{P}(A),\subsetneq\bigr\rangle$ that is non-maximal among such well-ordered chains. If we have $A\in\mathcal{C},$ then non-maximality lets us construct a well-ordered chain $\mathcal{C}'$ of equal cardinality such that $A\notin\mathcal{C}';$ hence, we may assume without loss of generality that $A\notin\mathcal{C}.$ Thus, given any $D\in\mathcal{C},$ the set $$\bigl\{a\in A:(a\notin D)\wedge\forall E\in\mathcal{C}(D\subsetneq E\implies a\in E)\bigr\}$$ is readily non-empty (dealing separately with the case that $D$ is the greatest element of $\mathcal{C},$ if any such element exists), and we define $a_D$ to be the $\prec$-least element of this set. Then the map $D\mapsto a_D$ is readily an injection $\mathcal{C}\to A.$

Unfortunately, this still doesn't address my original question. If $A$ is an orderable (but not well-orderable) infinite set, then $\mathcal{P}(A)$ necessarily has chains that aren't well-ordered by $\subsetneq,$ since given an order $\prec$ on $A,$ the map $a\mapsto\{b\in A\mid b\preceq a\}$ is an order embedding $\langle A,\prec\rangle\to\bigl\langle\mathcal{P}(A),\subsetneq\bigr\rangle.$ Furthermore, if $A$ is well-orderable and $\prec$ is a well-ordering, then the image of the map $a\mapsto\{b\in A\mid a\prec b\}$ is a chain of $\mathcal{P}(A),$ but isn't well-ordered.

I suspect that something similar to these results can be concluded in terms of cardinality and/or order type, but I have less experience with order types of orders that aren't well-orders, and have no experience talking about cardinalities that are orderable but need not be well-orderable, so I'm struggling to figure out where to begin. The only thought I've had so far in terms of generalization is to use the Hartogs number instead of the successor cardinal, but I don't yet see how this would help.

If anyone can at least get me started on making such a generalization, point me to some models of $\mathsf{ZF}$ to show that it isn't strong enough to let us make such a classification, or even point me to some results along these lines, I'd greatly appreciate it!

Added: I've been able to generalize the first result as follows:

Given any orderable set $A,$ any set $B$ such that $|B|<|A|,$ and any order relation $\prec$ on $A$ (so on $B$), there exists some $\mathcal{C}\subseteq\mathcal{P}(A)$ such that $\langle\mathcal{C},\subsetneq\rangle$ has the same order type as $\langle B,\prec\rangle.$

The proof is straightforward, using the map $B\to\mathcal{P}(A)$ given by $b\mapsto\{a\in A\mid a\preceq b\}.$

Furthermore, recalling my experience with the Dedekind-cut construction of $\Bbb R,$ it's clear that there can be chains of $\mathcal{P}(A)$ of cardinality $\bigl|\mathcal{P}(A)\bigr|,$ which is a notable departure from the prior results. While the cardinality certainly can't be greater than that, it isn't clear whether that bound is non-strict in all cases. I will keep thinking on it, at any rate.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.