1. ## 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.

2. ## 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.

3. ## Re: Set proofs

Originally Posted by Shakarri
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.

4. ## 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.