# Thread: Set proofs

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 $\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.

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 $\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.