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

Thread: Set proofs

  1. #1
    Super Member
    Joined
    Oct 2012
    From
    Ireland
    Posts
    751
    Thanks
    533

    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
    387
    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 $\displaystyle \leq $ and $\displaystyle 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 $\displaystyle \in A $ and $\displaystyle j \not \in B $, $\displaystyle B \cup \{j\} $ has a minimum element, since $\displaystyle j \leq p $ or $\displaystyle p \leq j $, so either p or j is the minimum element. Since |$\displaystyle B \cup \{j\}$| = n+1, the induction on the size of the set is complete.
    Last edited by jakncoke; Feb 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
    21,742
    Thanks
    2814
    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
    387
    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 $\displaystyle \mathbb{R} $ with an upperbound and no LUB

    Let U be an upperbound for A. Then pick an $\displaystyle x \in A $. The interval $\displaystyle I_1$ = (x, U) contains other upper bounds, either in $\displaystyle I_2$ = $\displaystyle (x,\frac{U}{2})$ or $\displaystyle (\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 $\displaystyle I_2$ = $\displaystyle (x, \frac{U}{2}) $ contains the smaller upperbound, so either $\displaystyle (x,\frac{U}{4})$ or $\displaystyle (\frac{U}{4}, \frac{U}{2}) $ contains a upper bound, again pick the follow the same rules to pick the interval.Let $\displaystyle I_n$ denote the sequence obtained from this construction.

    Now the sequence of lengths of intervals $\displaystyle |I_n| < \frac{|x-U|}{2^n} $ converges as $\displaystyle n \to \infty $. It follows that there exists a sequence $\displaystyle S_n = x \in I_{n} $ which is monotonously decreasing and since it is bounded, it converges to a limit L in $\displaystyle (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: Jul 12th 2010, 06:52 PM
  2. Two proofs I've done...
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Apr 11th 2010, 02:30 PM
  3. Proofs
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Mar 24th 2009, 01:09 PM
  4. Proofs
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Dec 12th 2007, 02:19 AM
  5. Replies: 3
    Last Post: Oct 6th 2007, 02:01 PM

Search Tags


/mathhelpforum @mathhelpforum