4
$\begingroup$

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.

$\endgroup$

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.