Lexicographic ordering on ${\cal P}(\kappa)$

Question

How is the "lexicographic ordering" (which is supposed to be a total ordering) on ${\cal P}(\kappa)$ defined, where $\kappa$ is any cardinal?

(I apologize if this question is a bit fuzzy.)

Answer 1

If $(X,\le)$ is any well-ordered set then we can define a linear ordering on the power set $\mathscr P(X)$ as follows:

For $A\ne B$ we say that $A<B$ if $\min A\mathrel{\triangle} B\in A$ (i.e., if the smallest element of the symmetric difference belongs to $A$).

Since every cardinal is a well-ordered set, this applies to your case. (And I suppose that if the text where you stumbled upon this is related to set theory, then this is the most probable meaning of the lexicographic ordering of $\mathscr P(\kappa)$).

For a random sample of some texts where something like this is used you can try to search for lexicographic "symmetric difference" "set theory" in Google Books.

---

As Brian M. Scott says in a comment, the opposite direction (i.e. $A<B \Leftrightarrow \min A\mathrel{\triangle} B\in B$) is used more often. (And I am willing to take his word for it.) Lexicographic order is defined in this way also in Joel David Hamkins' answer to your related question on MathOverflow in the case $X=\omega$.

From the results returned by the above Google search, Jech uses the direction which Brian mentions here. (I did not find lexicographic order on $P(X)$ in the newer edition of Jech's book, only for functions belonging to $\{0,1\}^X$.) On the other hand, Halbeisen on p. 109 uses the definition I mentioned above.

It is true that the ordering mentioned by Brian seems more natural. It corresponds to ordering between characteristic functions $\chi_A$ and $\chi_B$. For two functions $f,g\in\{0,1\}^X$ it is natural to say that $f<g$ if and only if $f(a)<g(a)$ where $a=\min\{x\in X; f(x)<g(x)\}$.

Answer 2

Identify $\wp(\kappa)$ with ${^\kappa2}$, the set of functions from $\kappa$ to $2$ by identifying each subset of $\kappa$ with its indicator function. Now let $\preceq$ be the natural lexicographic order on ${^\kappa2}$: if $f,g\in{^\kappa2}$ and $f\ne g$, let

$$\delta(f,g)=\min\{\xi\in\kappa:f(\xi)\ne g(\xi)\}\;,$$

and set $f\preceq g$ iff

$$f\big(\delta(f,g)\big)=0<1=g\big(\delta(f,g)\big)\;.$$

This is the easiest way to define it so that it’s clearly a lexicographic order. This is equivalent, however, to saying that if $x,y\subseteq\kappa$, and $x\ne y$, then $x\preceq y$ iff

$$\min(x\mathrel{\triangle}y)\in y\;,$$

i.e., the first element of $\kappa$ on which $x$ and $y$ disagree is in $y\setminus x$.