0

This problem involves pointing out the unjustified inference/logic error in the following proof that all positive rational numbers can be written in "lowest terms" that is as a ratio of positive integers with no common prime factor.

Bogus proof:

Suppose to the contrary that there was positive rational, q, such that q cannot be written in lowest terms. Now let C be the set of such rational numbers that cannot be written in lowest terms. Then q belongs in C, so C is nonempty. So there must be a smallest rational, q0 that belongs in C. So since q0=2 < q0, it must be possible to express q0=2 in lowest terms, namely, q0/2 = m/n, for positive integers m, n with no common prime factor. Now we consider two cases: Case 1: [n is odd]. Then 2m and n also have no common prime factor, and therefore q0 = 2 * (m/n) = (2m/n) expresses q0 in lowest terms, a contradiction.

Case 2: [n is even]. Any common prime factor of m and n/2 would also be a common prime factor of m and n. Therefore m and n/2 have no common prime factor, and so q0 = m / (n/2) expresses q0 in lowest terms, a contradiction.

I've been reasoning through each of the cases and the logic makes sense to me. Any hints or guidance?

Thanks.

Git Gud
  • 31,356
user3761743
  • 87
  • 2
    Review the well ordering principle. What does it say exactly? (Pay attention to the set to which it applies). – Git Gud Aug 10 '14 at 17:16
  • 2
    "So there must be a smallest rational, q0 that belongs in C." Really? – Daniel Fischer Aug 10 '14 at 17:16
  • You want to start with a set and assume its non empty to reach a contradiction. Also, you cannot apply WOP for Q generally. For example, what is the minimal element in S = {0< a < 1| a in Q}? One way could be S = {b|a/b can't be written in lowest terms } or something like that. Then by assumption, S is non empty so by WOP, there exists a minimal b. Then by division algorithm, all a can be written as bq+r for 0 <= r < b. Then a/b = (bq+r)/b = (bq/d+r/d)/(b/d) where d = gcd(b,r) which is reduced so we are done. – Sandeep Silwal Aug 10 '14 at 17:54
  • Thank you for pointing out the definition. So the set of positive rationals wouldn't include 0/1 since C is a set of just positive rationals. That means we could have anything from 0.0000001 to etc and so there can't be a smallest rational. – user3761743 Aug 10 '14 at 18:05
  • Yes, WOP is an axiom of Z but not of Q. – Sandeep Silwal Aug 10 '14 at 18:08

0 Answers0