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

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

Copyright © 1996-2017 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 _{1}, n_{2}, ..., n_{k})*lexicographic order* is defined for some k-tuples. More accurately, we say that

(n_{1}, n_{2}, ..., n_{k}) < (m_{1}, m_{2}, ..., 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_{1}, n_{2}, ..., n_{k}) < (m_{1}, m_{2}, ..., m_{k}) nor _{1}, n_{2}, ..., n_{k}) > (m_{1}, m_{2}, ..., m_{k})*incomparable*. An *antichain* is a collection of pairwise incomparable tuples.

Assume there exists an infinite antichain a = (a_{1}, a_{2}, ..., 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}. Then eventually it would also exist for ^{1} = N,

### Reference

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

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

Copyright © 1996-2017 Alexander Bogomolny62040685 |