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$.

  • $\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 '15 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$ – Pace Nielsen Jul 7 '15 at 18:41
  • $\begingroup$ Yes, that sounds reasonable. $\endgroup$ – Nik Weaver Jul 7 '15 at 23:16
  • $\begingroup$ I think these can be seen as special cases of Kruskal's Tree Theorem. $\endgroup$ – Christoph-Simon Senjak Jul 8 '15 at 3:38
  • $\begingroup$ I would not be surprised if these facts turned out to originate with Georg Cantor. $\endgroup$ – Johan Wästlund Jul 8 '15 at 6:51

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).

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

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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