Linear Topology

Date: 02/09/2003 at 23:54:00
From: Brandon
Subject: Sets and finite (linear topology)

The question is true or false: If a point in set X is finite, then X 
has a first point and a last point. We are to prove by induction if 
true, and give a counterexample if false. We know the definition of 
first point, last point, finite, infinite, and precede, so it is not 
necessary to define these in the proof. 

Date: 02/10/2003 at 03:49:33
From: Doctor Jacques
Subject: Re: Sets and finite (linear topology)

Hi Brandon,

You do not give the definition of "first point" and "last point."

Let us assume that a "first point" means a point x such that, for all 
y different from x, we have x < y.

Note that, if the set X is empty, the proposition is false. As this 
case is not very interesting, let us just add the condition "X is not 
empty" to the hypotheses.

Let us first prove a few useful results.

Proposition 1
-------------

If x and y are distinct, we cannot have both x < y and y < x (axiom 
(a) states that at least one of these relations is true).

Indeed, assume that x < y and y < x. Axiom (c) then implies x < x, 
which is false by axiom (b).

Proposition 2
-------------

x is a first element iff there is no y such that y < x.

Assume that x is a first element. This means that, for all y <> x, we 
have x < y. Proposition 1 then implies that we cannot have y < x.

Conversely, let us assume that there is no y such that y < x. Let y 
be any element different from x. By axiom (a), we have x < y.

Let us now tackle the main part of the proof. You are asked to provide 
a proof by induction. Let n be the number of elements of the set X.

If n = 1, X = {x}, x is a first point (as there is no y <> x, there is 
nothing to prove).

Let us now assume that n > 1, and that the proposition is true for all 
k < n.

Pick a point x, and consider the sets S = {y | y < x} and T = {x} U 
{y | x < y}. Note that, by axiom (a), X = S U T.

If S is empty, x is a first point by proposition 2.

If S is not empty, it contains fewer elements than X, and therefore
has a first point s by the induction hypothesis. Note that, by the 
definition of S, we have s < x.

You should now be able to conclude the proof using axiom (c), as any 
element of X belongs to either S or T.

The proof for a last element is entirely similar.

Please feel free to write back if you are still stuck.

- Doctor Jacques, The Math Forum
  http://mathforum.org/dr.math/