Re: Need hint for simple proof


<agapito6314@xxxxxxx> wrote in message
news:f7d1a333-cf21-4520-b8fc-01f07e980a2d@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
Say E is a non-empty set of natural numbers. Prove there exists an
element k in E such that k<=m for all m in E. Basic fact for the
proof, I believe is

Am An m=n or m<n or n<m

If we assume the negation of the statement above, then for each k in E
some m exists such that k<m. In turn there's an p such that m<p,
and so on. Eventually this leads to a contradiction. Is this the
right approach and if so, how is it formalized? If not, any hint
would be appreciated. Thanks


Simply, suppose n and m are two lowest bounds. By total ordering we have n <
m, m < n, or n = m. This implies that the lowest bound is unique. (if n < m
then m is not a lowest bound as we hypothesised... same for m < n... only
other case is n=m which is saying that the lowest bound is unique).

We just have to prove that such a lowest bound exists. This is actually a
hard problem unless you make some assumptions.

--- conceptualization ---
The problem here is the way the set is defined. Note for the set Z it is not
true. So we have to somehow take into account the special nature of N.

This actually is extremely hard to do without a proper definition of N. In
fact, any finite set of elements does not have a lower bound and in some
sense N is such a set... yet we obviously "believe" such a lower bound to
exist. What makes it different is the ordering that exists. Hence this is
exactly what we need... or at least what we need, to make such a statement.

In any case what you are trying to prove is that the natural numbers are
well-ordered. To do this correctly you cannot use the ordering of the
natural numbers, because, after all, that is what we are trying to prove.

If you assume well-ordered then your hypothesis follows directly. If you
assume total order, which you mention as a "Basic fact", then a proof goes
something like this:

let a, b \in N. Then either a < b, b < a, or b = a. w.l.o.g. assume a < b.
By induction there exists a sequence of elements a_k and an integer n s.t.,
a_0 < a_1 < ... < a_k < n. Since n is finite the sequence is finite and a_0
is finite and the least element. You now only need to prove uniqueness by
showing that the sequences all have the same a_0.

To do this you can assume you have two integers n,m with two sequences a_k
and b_k. Now since a_0 = b_0, a_0 < b_0, or b_0 < a_0, a_0 is a lower bound
of b_0 or vice versa. Hence we either have a_0 < b_0 < b_1 < ... or b_0 <
a_0 < a_1 < ... or a_0 = b_0 < b_1 < ...: In any case we have a lower bound
and since n and m are arbitrary there must be a unique P such that P <= all
sequences. Suppose there wasn't a unique P, say P1 and P2, then P1 <= all
sequences and P2 <= all sequences but P1 < P2, P2 < P1, or P1 = P2. Again,
if P1 = P2 then it is unique and in the other cases we have a contradition
of lower bound since P1 and P2 are both integers.


(it would be more proper to use subsets of N and the set theoretic
definition of N in terms of subsets)

(basically the idea here is if you choose any integer n I can construct a
chain of integers that will always produce the smallest integer. I do this
by inductively choosing smaller and smaller integers. By induction I know
the process is finite since there are at most n-1 smaller integers to choose
from. if you choose n = 28 I can choose 14, 13, 8, 3, 2, 1. The chain must
be finite because of the finiteness of n. By total ordering the chain always
leads to a lowest integer. If you choose any other integer m and n < m then
the same sequence will hold.

Unfortunately this just pushes the work into induction on N. But you you
gotta take something as an axiom.

Conceptually every finite subset of N has a lower bound. The collection of
all lower bounds from these finite sets has a lower bound, the lowest bound.
The question is the lowest bound converging. For the set of integers this is
not true as the lowest bound will just get more negative as we add more and
more finite sets(it would be the lower bound of the set of the union of all
those sets). Similarly for the upper bound on the naturals.

But for the the naturals, the lower bounds actually "converge" to 0 since
that is the lowest element. But this is hard to prove because 0 is precisely
this element we are talking about. In fact all axioms actually are
presupposing this in some sense and this is precisely what makes the
naturals only "one-sided infinite" verses the integers which are "two-sided
infinite".





.

Relevant Pages

  • Re: e^x > x^a , a > 1
    ... where W_0 denotes the principal branch of the Lambert W ... I got that crude lower bound by thinking about the lowest bound, ... Perhaps someone else can provide a sketch without reference to the Lambert ... Or perhaps someone else could find a nicer lower bound. ...
    (sci.math)
  • Re: e^x > x^a , a > 1
    ... where W_0 denotes the principal branch of the Lambert W ... You asked for the lowest bound for x0 and I gave it precisely. ... I got that crude lower bound by thinking about the lowest bound, ... Or perhaps someone else could find a nicer lower bound. ...
    (sci.math)
  • Re: Review of The Extended Phenotype
    ... One way to restrict the definition of gene as nucleotide sequence is to ... What would be an example of a lower bound sequence preventing the ...
    (sci.bio.evolution)
  • Re: .999... = 1
    ... > lower bound for S. The completeness axiom is this: ... If S is a set of reals and S is ... rational can be approached by a sequence of rationals that approach ... I take to be a particular way of 'approaching arbitrarily close'), ...
    (sci.logic)
  • Re: dynamically growable vector?
    ... rank-one array with lower bound 1 by 2 extra values, you can write, e.g., ... but, as has been pointed out by Richard, under the bonnet there is still the ... sequence of operations you describe. ...
    (comp.lang.fortran)
Quantcast