Difference between revisions of "Proofs of irrationality"

From Computer Science
Jump to: navigation, search
(Created page with "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 [https://...")
 
(Assignment)
 
(4 intermediate revisions by the same user not shown)
Line 4: Line 4:
  
 
=Assignment=
 
=Assignment=
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.
+
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.
  
''Pass rating check'' Your proof must satisfy the following.
+
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 ''a''<sup>2</sup> = 12 ''b''<sup>2</sup>.  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).
 
* 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).
 
* 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.
 
* 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.
 
* 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 [https://sycamoresindstate-my.sharepoint.com/:x:/g/personal/jeffrey_kinne_indstate_edu/ESbWO8QmBg9Jn9-ufDqR6_EBPzUbhzjVjyyzAPEAcjbMgg?e=XBpLEa this link], which should work only for the current term's GAs.''

Latest revision as of 12:37, 6 September 2022

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.

Assignment

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.