All antichains in N^k with the lexicographic order are finite.

Solution

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

Copyright © 1996-2018 Alexander Bogomolny

All antichains in N^k with the lexicographic order are finite.

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

(n₁, n₂, ..., n_k) < (m₁, m₂, ..., m_k)

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

n_i = m_i, for i < j, and n_i < m_i, otherwise.

If neither (n₁, n₂, ..., n_k) < (m₁, m₂, ..., m_k) nor (n₁, n₂, ..., n_k) > (m₁, m₂, ..., m_k) the two tuples are said to be incomparable. An antichain is a collection of pairwise incomparable tuples.

Assume there exists an infinite antichain a = (a₁, a₂, ..., a_k), 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 N^k-1.

Thus, we see that, if an infinite antichain existed in N^k for some k > 1, an infinite antichain would also exist in N^k-1. Then eventually it would also exist for N¹ = 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