All antichains in Nk with the lexicographic order are finite.

Solution


|Contact| |Front page| |Contents| |Up|

Copyright © 1996-2018 Alexander Bogomolny

All antichains in Nk with the lexicographic order are finite.

Let's start with a few clarifications. Nk is the set of all k-tuples (n1, n2, ..., nk) with integer components. N = {1, 2, 3, ...}. The lexicographic order is defined for some k-tuples. More accurately, we say that

(n1, n2, ..., nk) < (m1, m2, ..., mk)

if for some index j (which may be 1) the following holds:

ni = mi, for i < j, and ni < mi, otherwise.

If neither (n1, n2, ..., nk) < (m1, m2, ..., mk) nor (n1, n2, ..., nk) > (m1, m2, ..., mk) the two tuples are said to be incomparable. An antichain is a collection of pairwise incomparable tuples.

Assume there exists an infinite antichain a = (a1, a2, ..., ak), b, c, etc. Since b, c, ... are incomparable with a, each of them has a coordinate which is less than the corresponding coordinate in a. Thus some coordinates in a have the property that there are terms among b, c, etc. whose corresponding coordinate is less than that in a. Since, by assumption, the antichain is infinite, at least one coordinate in a has the property of being greater than the corresponding coordinate in an infinite number of terms b, c, etc. Without loss of generality we may assume that the first coordinate possesses this property: there is an infinite number of terms among k-tuples b, c, etc. whose first coordinate is less than that of a. Since there are only finitely many integers less than the first coordinate of a, there bound to be infinitely many terms among k-tuples b, c, etc. with equal first coordinate. Consider such an infinite collection of k-tuples with equal first coordinate.

If we omit the first coordinates in all terms of that collection, we'll get a collection of incomparable (k-1)-tuples, i.e., an infinite antichain in Nk-1.

Thus, we see that, if an infinite antichain existed in Nk for some k > 1, an infinite antichain would also exist in Nk-1. Then eventually it would also exist for N1 = N, which is absurd.

Reference

  1. J.-P. Allouche & J. Shallit, Automatic Sequences, Cambridge University Press, 2003, p. 64.

Related material
Read more...

  • Six integers out of 10: Pigeonhole Principle
  • Pigeonhole Principle (Same sum)
  • Pigeonhole in a Matrix
  • Pigeonhole in Calendar
  • A nice puzzle modeled on the Petersen graph
  • Proizvolov's identity in a game format
  • Pigeonhole with Disjoint Intervals
  • Euclid via Pigeonhole
  • Light Bulbs in a Circle (an Interactive Gizmo)
  • Seven integers under 127 and their Ratios
  • |Contact| |Front page| |Contents| |Up|

    Copyright © 1996-2018 Alexander Bogomolny

    71471326