Computer Science Canada Mathematical Foundations Help? |
| Author: | rar [ Mon Mar 29, 2010 9:18 pm ] |
| Post subject: | Mathematical Foundations Help? |
I'm in a Mathematical Foundations course and I'm having trouble figuring out how to do this proof. I have to prove that (for all x in the set of the Natural Numbers excluding 1) if (there exists a t) where 10 = xt and (there exists an s) where 15 = xs then (there exists a q) where 5 = xq. Does anyone have any idea of how I could do this? If so, help would be GREATLY appreciated. |
|
| Author: | A.J [ Mon Mar 29, 2010 9:39 pm ] |
| Post subject: | RE:Mathematical Foundations Help? |
Well, this problem can be restated as follows: If x|a and x|b, then x|gcd(a, b) (for positive integers x, a, and b, naturally). [edit]solution redacted[/edit] [edit2]A.J. suggested proof-by-contradiction[/edit] I hope this helps. |
|
| Author: | rar [ Mon Mar 29, 2010 9:55 pm ] |
| Post subject: | Re: RE:Mathematical Foundations Help? |
A.J @ Mon Mar 29, 2010 9:39 pm wrote: Well, this problem can be restated as follows:
If x|a and x|b, then x|gcd(a, b) (for positive integers x, a, and b, naturally). [edit]solution redacted[/edit] [edit2]A.J. suggested proof-by-contradiction[/edit] I hope this helps. Whoa what happened here lol Alright I'll try it out thanks. |
|
| Author: | Brightguy [ Mon Mar 29, 2010 10:16 pm ] |
| Post subject: | Re: Mathematical Foundations Help? |
Technically you didn't state the universe for s, t, q. But the point is that you can exhibit q using s and t. Hint: 5=15-10. |
|
| Author: | rar [ Mon Mar 29, 2010 10:20 pm ] |
| Post subject: | RE:Mathematical Foundations Help? |
Brightguy @ Mon Mar 29, 2010 10:16 pm wrote: Technically you didn't state the universe for s, t, q. But the point is that you can exhibit q using s and t. Hint: 5=15-10.
I figured this out before reading your post, so I'm guessing I got it right! 
My next question has to do with proving: If a - b is an element of the Natural Numbers (including 0) and b - a is an element of the Natural Numbers (including 0) then a = b Advice on proving this? |
|
| Author: | Tony [ Mon Mar 29, 2010 10:29 pm ] |
| Post subject: | RE:Mathematical Foundations Help? |
What's awesome about proves by contradiction is that you simply negate the conclusion that you are trying to prove, and you get a free piece of information. |
|
| Author: | Brightguy [ Mon Mar 29, 2010 10:29 pm ] |
| Post subject: | Re: Mathematical Foundations Help? |
Show a>=b and b<=a. One line and I miss LaTeX already.  |
|
| Author: | rar [ Mon Mar 29, 2010 10:29 pm ] |
| Post subject: | RE:Mathematical Foundations Help? |
I do like proofs by contradiction for that reason. Sometimes I fail to see where it helps though.. |
|
| Author: | rar [ Mon Mar 29, 2010 10:37 pm ] |
| Post subject: | RE:Mathematical Foundations Help? |
I ended up with Assume (looking for a contradiction, so a - b is an element of Naturals, or 0, and b - a same thing, but a != b) therefore a - b != 0 and b - a != 0 therefore a - b element of naturals (same with b - a) therefore a - b + b - a element of naturals (adding 2 naturals, still an element of naturals) therefore 0 element of naturals however, 0 is NOT an element of naturals (stated above, since a - b != 0 and b - a != 0) Contradiction Valid?? |
|
| Author: | Tony [ Mon Mar 29, 2010 10:37 pm ] |
| Post subject: | RE:Mathematical Foundations Help? |
Write out all the information that you have, and see what you can do with it a != b a - b >= 0 b - a >= 0 what is another way of saying a != b ? |
|
| Author: | rar [ Mon Mar 29, 2010 10:39 pm ] |
| Post subject: | RE:Mathematical Foundations Help? |
and one more question Prove 2 and 3 are minimal in N - {1} under the partial ordering given by a|b provided (there exists a t in naturals) such that b = at. So prove if there exists a natural number 't' such that 2 = xt then x = 2 (then the same for 3) |
|
| Author: | rar [ Mon Mar 29, 2010 10:40 pm ] |
| Post subject: | Re: RE:Mathematical Foundations Help? |
Tony @ Mon Mar 29, 2010 10:37 pm wrote: Write out all the information that you have, and see what you can do with it
a != b a - b >= 0 b - a >= 0 what is another way of saying a != b ? Wouldn't that be a - b != 0? |
|
| Author: | A.J [ Mon Mar 29, 2010 10:44 pm ] | ||
| Post subject: | Re: RE:Mathematical Foundations Help? | ||
rar @ Mon Mar 29, 2010 9:55 pm wrote: A.J @ Mon Mar 29, 2010 9:39 pm wrote: Well, this problem can be restated as follows:
If x|a and x|b, then x|gcd(a, b) (for positive integers x, a, and b, naturally). [edit]solution redacted[/edit] [edit2]A.J. suggested proof-by-contradiction[/edit] I hope this helps. Whoa what happened here lol Alright I'll try it out thanks. [edit] whoops...I just realized that my post was edited for giving too much away...my bad[/edit] Basically, try assuming the opposite of what you want to prove, and see if you reach a contradictory statement later on. For example, if you want to prove that there are infinitely many prime numbers, you could start by assuming that there are a finite number of them. So, assume {p_1, p_2, p_3, ..., p_n} are all the prime numbers there are. Now consider the number q = [p_1 * p_2 * p_3 * ... * p_n] + 1. Now q is either prime or composite. Dividing q by any of the primes p_1 -> p_n yields a remainder of 1. Thus, q isn't composite, so it is a prime that isn't listed in the above list (or is factored by a prime not in the above list) contradicting the fact that this list contains all the primes that exist. Thus, there are infinitely many primes. Try something like that:
|
|||