Associated Topics || Dr. Math Home || Search Dr. Math

### 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/
```
Associated Topics:
College Logic
High School Logic
High School Sets

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search