Tchebysheff proof, help understanding transition to last step

1. Jun 4, 2009

el_llavero

proof attached as pdf in link provided

File size:
37.1 KB
Views:
51
2. Jun 4, 2009

EnumaElish

Using A for |A| and kk for k squared:

1 > Akk/n
1 < n/(Akk)
A < n/kk
A/n < 1/kk
1 - A/n > 1 - 1/kk

So the stated result actually holds with strict equality.

3. Jun 4, 2009

el_llavero

I actually got some help with the algebraic manipulation, which was clouding my conceptual understanding, after looking at this more I realized what it all meant and why the use of >= instead of > at the end

Divide by k^2 results in 1/(k^2)>|A|/n

multiply both sides by -1 (fips inequality) and add 1 to both sides results in 1- 1/k^2 < 1-|A|/n

change from strict inequality to weak inequality to account for proportion of all elements "~A" INTERSECTION "B" results in
1- 1/k^2 <= 1-|A|/n

Last edited: Jun 5, 2009
4. Jun 4, 2009

el_llavero

But the only way 1 - A/n > 1 - 1/kk describes the proportion of measurements in B, i.e. ~A, is to switch to weak inequalitysince strict inquality leaves out part of B, t/f weak inequality is required.

What do you think?

Last edited: Jun 5, 2009
5. Jun 4, 2009

EnumaElish

|A| is a real number, like 2.

If 2/n < 1/kk then 1 - 2/n > 1 - 1/kk. Not so?

6. Jun 4, 2009

el_llavero

the cardinality of A, i.e. |A|, is a natural number, an integer in the set {0,1,2,3,...}

if |A|=1, and k =1 and n = 1 then the equations are equal. thats assuming that there is no restriction on n being equal to 1 and card(A) being equal to 1.

Last edited: Jun 4, 2009
7. Jun 4, 2009

EnumaElish

Of course, if the premise were 2/n < 1/kk then 1 - 2/n > 1 - 1/kk would be the case. But the premise is stated with strict inequality.

8. Jun 4, 2009

el_llavero

yes you're right. So the use of weak inequality may have something to do with describing the complement of A?

Last edited: Jun 5, 2009
9. Jun 4, 2009

EnumaElish

Or what they meant was 2/(n-1) < 1/kk, then they replaced n-1 with n but forgot to change < to <.

10. Jun 5, 2009

el_llavero

Perhaps that's the case, because the strict inequality was used to derive the last line. Moreover, perhaps my set element argument was more of a way to try and rationalize the use of the weak inequality. I'm going to try and get a response from the author of this proof, and see what he says. Thanks for your responses EnumaElish.

11. Jun 6, 2009

el_llavero

If you assume p is true then you may also conclude that ( p OR q) is true, no matter what q is! q doesn't ever have to be true since we've assumed p is. It's a fact in logic referred to as (addition or generalization).

p is LHS > RHS, and q is LHS = RHS.

Last edited: Jun 6, 2009
12. Jun 6, 2009

EnumaElish

I am not saying the proof is wrong; I am saying it can be more definitive.

Last edited: Jun 6, 2009