2
$\begingroup$

I'm wondering if there is a standard reference for the following straightforward facts about well-orderings. (They are quite easy to prove, I just need a handy/standard reference.)

  1. Let $(S,<)$ be a well-ordered set. The set $T=\{(s_1,s_2,\ldots, s_k)\ : \ k\in \mathbb{N},s_i\in S\}$, of all ordered finite tuples, is well-ordered in the degree-lexicographical ordering $\prec$. In other words, given different elements $\vec{a}=(a_1,a_2,\ldots, a_m),\vec{b}=(b_1,b_2,\ldots, b_n)\in T$ then we have $\vec{a}\prec \vec{b}$ exactly when either (1) $m<n$ or (2) $m=n$, and if $i$ is the first index where $a_i\neq b_i$, then $a_i<b_i$.

  2. Let $(S,<)$ be a well-ordered set. The set $U$ of all finite subsets of $S$ is well-ordered by the following relation: given different finite subsets $S_1,S_2\subset S$ we say $S_1\prec S_2$ if it happens that the maximal element of (the finite set) $(S_1\cup S_2)\setminus (S_1\cap S_2)$ belongs to $S_2$.

$\endgroup$
5
  • $\begingroup$ Not a set theorist, but I think these are both sufficiently standard that no reference would be needed. By the way, in #2 you can identify finite subsets of $S$ with functions from $S$ into $\{0,1\}$, and what you have described is the ordinal exponent $\{0,1\}^S$. $\endgroup$
    – Nik Weaver
    Jul 7, 2015 at 18:37
  • 2
    $\begingroup$ The referee on a paper I wrote asked me to provide references if they are readily available. I think you are correct that these are both very standard. I did find that in Sierpinski's book "Cardinal and ordinal numbers" he essentially proves 2 on page 309 when he defines ordinal exponenentiation (so I guess I'll go with that). $\endgroup$ Jul 7, 2015 at 18:41
  • $\begingroup$ Yes, that sounds reasonable. $\endgroup$
    – Nik Weaver
    Jul 7, 2015 at 23:16
  • $\begingroup$ I think these can be seen as special cases of Kruskal's Tree Theorem. $\endgroup$ Jul 8, 2015 at 3:38
  • $\begingroup$ I would not be surprised if these facts turned out to originate with Georg Cantor. $\endgroup$ Jul 8, 2015 at 6:51

1 Answer 1

3
$\begingroup$

I'm pretty sure that both of these can be found in the paper

J. B. Kruskal, The theory of well-quasi-ordering: A frequently discovered concept, J. Combinatorial Theory Ser. A 13 (1972), 297–305.

(but I don't have my copy at hand, so I can't check).

$\endgroup$
2
  • 1
    $\begingroup$ That paper has a great title. $\endgroup$
    – Jim Conant
    Jul 8, 2015 at 8:10
  • $\begingroup$ It is implicitly in there, so I've added this reference too. Thanks! $\endgroup$ Jul 8, 2015 at 15:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.