Monthly Archives: January 2014

by

No increasing functions in the long line

For our purposes, let’s define the “long line” as the set L = (0, 1) \times [0, 1) together with a lexicographic ordering:

\displaystyle (a, b) \prec (c, d) \Leftrightarrow (a < c) \vee (a = c) \wedge (b < d).

We want to prove that we cannot have a strictly increasing real-valued function in L, meaning that there is no function f: L \to \mathbb{R} such that

\displaystyle f((a, b)) < f((c, d)) \Leftrightarrow (a, b) \prec (c, d).

To start with the proof we are going to require a lemma.

Between two different real numbers there is at least one rational number

The basic idea (lifted from this math.SE answer) is to define “a grid” of rationals that is thick enough to be sure we have at least one rational between the two reals. So, if a < b are the two real numbers, we can use as denominator

\displaystyle n = \left\lceil \frac{2}{b - a}\right\rceil

and as numerator

\displaystyle m = \lfloor n a + 1 \rfloor.

Now we need to prove that m/n is always strictly between a and b.

It’s easy to see that is bigger than a,

\displaystyle \frac{m}{n} = \frac{\lfloor n a + 1 \rfloor}{n} > \frac{n a}{n} = a,

and that (m-1)/n is less than or equal to a:

\displaystyle \frac{m-1}{n} = \frac{\lfloor n a + 1 \rfloor - 1}{n} \le \frac{n a + 1 - 1}{n} = a.

As we know that 1/n is smaller than b - a because

\displaystyle \frac{b - a}{1 / n} = n(b - a) = \left\lceil \frac{2}{b - a}\right\rceil (b - a) > \frac{2}{b - a}(b - a) = 2,

we have

\displaystyle \frac{m}{n} = \frac{m-1}{n} + \frac{1}{n} < a + (b - a) = b.

Building an impossible one-to-one function

Using g as a name for the previously defined function that takes a pair of reals and returns a rational between them and f for an increasing function in L, we can define h: (0, 1) \to \mathbb{Q} by the following expression:

\displaystyle h(x) = g(f((x, 0)), f((x, 0.5))).

We know that is one-to-one because if x \ne y, assuming WLOG that x < y,

\displaystyle h(x) = g(f((x, 0)), f((x, 0.5)))
\displaystyle < f((x, 0.5))
\displaystyle < f((y, 0))
\displaystyle < g(f((y, 0)), f((y, 0.5))) = h(y).

But this result would imply that the cardinality of (0, 1) is smaller than the cardinality of a subset of \mathbb{Q} and that is absurd.

Conclusions

This result would seem a random trivia, but it has an important consequence for microeconomics: lexicographic preferences cannot be described by (real-valued) utility functions.

Advertisement