X is the smallest set of polynomials p(x) such that: (1) p(x) = x belongs to X; and (2) if r(x) belongs to X, then x r(x) and (x + (1 - x) r(x) ) both belong to X. Show that if r(x) and s(x) are distinct elements of X, then r(x) ≠ s(x) for any 0 < x < 1.
Solution
If they are never equal, then we must be able to order them, so that r(x) > s(x) for all x in (0, 1) or s(x) > r(x) for all x in (0, 1). Let us use the notation [+ - - + ... ]. The operation r(x) to x r(x) is denoted as - , and the operation r(x) to x + (1 - x) r(x) is denoted as + . Then the operations are listed in reverse order with the last carried out put first. So for example [ + - ] means we first apply - to get x2, then + to get x + (1 - x)x2 = x + x2 - x3. We claim that we have the ordering + > nothing > - , which we apply starting with the first term. So looking at the first few polynomials we have: [ + + ] > [ + ], because we compare the first terms which are equal, then we compare the second terms. We regard [ + ] as having nothing for the second term, so + > nothing. Then [ + ] > [ + - ], because they have equal first terms, but unequal second terms (nothing > - ). The starting polynomial is represented as [ ]. So we have [ + - ] > [ ] because + > nothing. Then [ ] > [ - + ] > [ - ] > [ - - ]. Clearly this ordering, which is a type of lexicographic ordering is a total order, that is, for any two distinct polynomials in X we will find that one is larger than the other.
So suppose r(x) belongs to the set X. We have to establish that + > nothing > - . In other words, that x + (1 - x) r(x) > x and that x > x r(x). But that is obvious, because by a trivial induction we have 0 < r(x) < 1 for all r(x) in X and x in (0, 1). So, if follows that if r(x) and s(x) are in X then x + (1 - x) r(x) > x s(x). It is also obvious that if [ a ] > [ b ], where a and b are some strings of + and - , then [ + a ] > [ + b ] and [ - a ] > [ - b ]. But that is sufficient to establish the ordering.
© John Scholes
jscholes@kalva.demon.co.uk
26 Aug 2002