Results 1 to 4 of 4
Like Tree2Thanks
  • 2 Post By jakncoke

Math Help - Set proofs

  1. #1
    Super Member
    Joined
    Oct 2012
    From
    Ireland
    Posts
    586
    Thanks
    155

    Set proofs

    I am struggling to start these two proofs, I hope you can point me in the right direction.

    1. Prove by induction on the size of the set that every finite set has a minimum element.

    2. S is a set defined by S= { a + b(2)0.5 } where a and b are rational
    If S has an upper bound does a least upper bound exist? Prove the answer.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member jakncoke's Avatar
    Joined
    May 2010
    Posts
    388
    Thanks
    80

    Re: Set proofs

    "Minimum" would indicate the elements of the set have a total ordering.

    1. Let A be a set with a total order  \leq and  B \subset A be a finite set. If |B| = 1, then the minimum element is the only element in B. Assume for |B| = n contains a minimum element p. Then if an element j  \in A and  j \not \in B , B \cup \{j\} has a minimum element, since  j \leq p or  p \leq j , so either p or j is the minimum element. Since | B \cup \{j\}| = n+1, the induction on the size of the set is complete.
    Last edited by jakncoke; February 25th 2013 at 12:58 PM.
    Thanks from Shakarri and HallsofIvy
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,617
    Thanks
    1581
    Awards
    1

    Re: Set proofs

    Quote Originally Posted by Shakarri View Post
    2. S is a set defined by S= { a + b(2)0.5 } where a and b are rational
    If S has an upper bound does a least upper bound exist? Prove the answer.
    I am confused by why this question is being asked in this forum.

    It is well known that any set of real numbers that has an upper bound has a least upper bound.

    Now the set(sequence) of axioms/definitions may vary, but the result is the same.

    Please 'flesh out' the setting of this question.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member jakncoke's Avatar
    Joined
    May 2010
    Posts
    388
    Thanks
    80

    Re: Set proofs

    For 2, how about we prove that any subset of reals having an upperbound has a LUB.
    Here is a proof by contradiction

    Let A be a non empty subset of  \mathbb{R} with an upperbound and no LUB

    Let U be an upperbound for A. Then pick an  x \in A . The interval I_1 = (x, U) contains other upper bounds, either in I_2 = (x,\frac{U}{2}) or  (\frac{U}{2}, U). for if it does not then by contradiction there exists a LUB. If both the intervals contain atleast one upper bounds p,q take the interval which contains the smaller value of p and q. so for the sake of brevity, say I_2 =  (x, \frac{U}{2}) contains the smaller upperbound, so either (x,\frac{U}{4}) or  (\frac{U}{4}, \frac{U}{2}) contains a upper bound, again pick the follow the same rules to pick the interval.Let I_n denote the sequence obtained from this construction.

    Now the sequence of lengths of intervals  |I_n| < \frac{|x-U|}{2^n} converges as  n \to \infty . It follows that there exists a sequence S_n = x \in I_{n} which is monotonously decreasing and since it is bounded, it converges to a limit L in (x, U) If L is LUB, by contradiction proof is complete. If L is not LUB, then if some R is LUB, it means at some point in the interval sequence picking procedure, we picked the interval containing L instead of R, which would mean L < R. Thus L is LUB.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Need help on proofs
    Posted in the Pre-Calculus Forum
    Replies: 2
    Last Post: July 12th 2010, 06:52 PM
  2. Two proofs I've done...
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: April 11th 2010, 02:30 PM
  3. Proofs
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: March 24th 2009, 01:09 PM
  4. Proofs
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 12th 2007, 02:19 AM
  5. Replies: 3
    Last Post: October 6th 2007, 02:01 PM

Search Tags


/mathhelpforum @mathhelpforum