Proofs of irrationality

From Computer Science
Revision as of 12:37, 6 September 2022 by Jkinne (talk | contribs) (Assignment)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

One of the classic proofs in mathematics is that the square root of 2 is irrational. The classic proof of this is the proof by "infinite descent" that is included on wikipedia's page on sqrt(2). CS students who have taken CS 303 or CS 600 should be able to demonstrate this proof on the board, or write it out on paper.

The same basic proof technique can be used to prove that other numbers are irrational - the square root of any number that is not a perfect square, the cube root of any number that is not a perfect cube, etc.


You will be asked to prove that a number is irrational using the same basic strategy as the proof that the square root of 2 is irrational. In general, you will be assigned integers m and n, and asked to show that the m-th root of n is irrational.

Note that doing this for a composite number can be a tiny bit different than a composite number; just pay attention to what you are claiming as you go through the proof. For example, suppose you are in the middle of the proof and have integers a and b such that a2 = 12 b2. This does not imply that 12 must be a factor of a, but it does imply that 2 and 3 must be factors of a. So you would assume a = 6 * k for some integer k, and continue on.

Pass rating check Your proof must satisfy the following.

  • State your claim (e.g., that sqrt(2) is irrational).
  • Proof is by contradiction, and the assumption is given in generality (e.g., if the number is rational, then let it be i/j for some integers i and j).
  • Correct argument is given that the assumption leads to a contradiction, including working through the formulae.
  • Your claim and proof are complete - someone who is not in our class could follow through your argument and validate your proof.
  • You need to both hand in your work, and also check in with the help lab to demonstrate your proofs. You can use your work that you hand in, and should talk the GA through the proof. The GA will make note if you are not able to do this, or if it seems you do not fully understand the process.
  • You should follow the rules of writing good proofs - Proofs

Note - the shared spreadsheet that GAs use for submitting information to Jeff Kinne's courses is this link, which should work only for the current term's GAs.