Re: abundance of irrationals!)

Orphan thread discovered while looking for something else...

aeo6 Tony Orlow wrote:
> Randy Poe said:
> > A finite set of numbers, with the usual order relationships,
> > has a definite largest elements. A set without a largest
> > element can not be finite.
> leap alert! Prove your assertion, and define "usual order
relationships",

"Usual order relationships"

Two elements a and b are related by either "<",
"=", or ">". That is, for any pair of elements we
will say that exactly one of "a > b", "a < b" or
"a = b" is true.

> and tell me if that applies to your "set of all finite natural
numbers".

Yes, the finite natural numbers have a complete
order relationship. Take any two and we can establish
whether a<b, a>b or a=b, only one of these is true,
and we know how to determine it from the base-10
representation.

If you like, I'll go into that too.

> Axioms, please, and logic. No leaps.

Now consider a finite set. That means that the elements
are in one-to-one correspondence with the natural numbers
{1,2,3,...,n} for some finite number n. That is
the definition of finite set.

Given any mapping, we can label the elements in our set
as a_1, a_2, a_3, ..., a_n.

Now we can define an algorithm:

1. Let M = a_1.
2. Let i = 1.
3. Let i = i+1. If i > n. Stop.
4. Either M < a_i or M > a_i (M can not be equal
to a_i because the elements of a set are distinct).
If M < a_i, set a_i = M.
5. Goto 3.

Now first of all, this process is guaranteed to stop.
That is because by the definition of "finite n", step
#3, repeated taking of successors of i, will stop.
A finite n will be reached from 1 in a finite number
of steps.

When it stops, M has the property that M >= a_i for
i={1,2,3,...,n}. The proof of this is a finite
induction on iteration number.

P(1): At step 1, M = a_1. So trivially M >= a_i
for i = {1}.

P(m): Suppose M >= a_i for i = {1,2,...,m-1}. If
M < a_m, then we have a_m > M >= a_i, i={1,2,...,m-1}.
So a_m > a_i for i=1,...,m-1 and when we set M = a_m
we have M > a_i for i=1,...,m-1 and M=a_i for i=m.

Thus P(m) is established: M >= a_i for {1,2,...,m}

Since we have proven P(1) and P(m-1) => P(m), the
property is established for P(n) regardless of n.
M >= a_i for i=1,2,...,n. M is the largest member
of our set.

- Randy

P.S. I was looking for your set cardinality definition,
but haven't found it. Please repost and I'll comment.

.

Loading