I'm currently working my way through Naive Set Theory by Paul Halmos and am confused by what sort of answer might satisfy this exercise on page 23:
Find an intrinsic characterization of those sets of subsets of $A$ that correspond to some order in $A$.
This exercise is in Section 6: Ordered Pairs, and comes after a discussion of how to define the ordering of a quadruplet $\{a, b, c, d\}$ by generating a set where every element is a set that contains
- the element in question along with
- every element that comes before the element in the supplied ordering.
So the set representing the ordering $c, b, d, a$ would be:
$C = \{\{c\}, \{c, b\}, \{c, b, d\}, \{c, b, d, a\}\}$
I can make various statements about this sort of set of subsets, like
- every element of $C$ has an ordering that's a subset of $C$
But I'm sure this doesn't count as an intrinsic characterization.
What does an intrinsic characterization of sets of subsets of $A$ look like? How can I think about the answer to this question?
Thank you!
Best Answer
Halmos mentions that for any $a$ in an ordered set $(A, \le)$ we can construct $\mathcal{O}(a) = \{\,x \in A \mid x \le a\,\}$, and thus the set $\mathcal{O}(A) = \{\,\mathcal{O}(a)\mid a \in A\,\}$. He then describes a process by which we can recover the original order on $A$ by taking the smallest set (by inclusion) of $\mathcal{O}(A)$, extracting the element of $A$ it represents, then taking the next smallest set, which has added one element of $A$, etc. This description of the reverse process implies to me that the order $\le$ he's referring to is actually a well-ordering, where $A$ has a least element and we can remove elements of $A$ and still have a least element.
By a characterization, I think he means a set of properties that is necessary and sufficient for a set $\mathcal{O}$ to have if it is $\mathcal{O}(A)$ for some $A$. By "intrinsic", I think he means this characterization shouldn't reference the order operation $\le$.
I thought about this yesterday, and have got it down to 3 properties:
The first property assures that $\mathcal{O}$ isn't missing any elements of $A$. It's not really necessary if you consider $\bigcup \mathcal{O}$ as an implicit definition of $A$, but you need it if you're matching a given $A$. The second guarantees we can follow the process of successively picking and removing the smallest element of $\mathcal{O}$. And the third guarantees distinct elements of $A$ can be separated by the derived order.
To show that an $\mathcal{O}$ with these properties defines a well-ordering of $A$, I found it easier to work with a strict order $\lt$ on $\bigcup \mathcal{O}$ defined by $x \lt y$ iff there is some set $X \in \mathcal{O}$ that contains $x$ but not $y$. Irreflexivity follows directly from the definition of $\lt$. Asymmetry can be derived by contradiction from property 2 by considering the minimal set between a set in $\mathcal{O}$ that contains $x$ but not $y$ and one that contains $y$ but not $x$. Transitivity is derived by using property 2 to show that a set in $\mathcal{O}$ containing $x$ but not $y$ must be a subset of one containing $y$ but not $z$. Trichotomy ($x \lt y$ or $x = y$ or $y \lt x$) can be derived directly from property 3. And well-ordering requires both 2 and 3. For well-ordering, we get the minimal element of some nonempty $A' \subseteq A$ by finding the minimal $X \in \mathcal{O}$ that contains at least one element of $A'$. If it contains more than one element of $A'$, then property 3 shows it's not minimal, which contradicts property 2, so it must have exactly one element of $A'$, which is then shown to be the minimal element of $A'$.
Whether or not this is the most concise or understandable characterization I don't know (it's why I searched for this question). I'm answering it long after it was asked, since it does come up in searches, and I would have found a different answer useful.