{"id":667,"date":"2020-10-23T15:56:10","date_gmt":"2020-10-23T15:56:10","guid":{"rendered":"https:\/\/site.uvm.edu\/tutortips\/?page_id=667"},"modified":"2020-11-23T19:38:55","modified_gmt":"2020-11-23T19:38:55","slug":"mathematics-sample-proofs","status":"publish","type":"page","link":"https:\/\/site.uvm.edu\/tutortips\/?page_id=667","title":{"rendered":"Mathematics – Sample Proofs"},"content":{"rendered":"\n
\n
\n
<\/div><\/div><\/div>\n\n\n\n
\n
\n

Overview<\/a><\/h4>\n\n\n\n

<\/h4>\n<\/div><\/div>\n\n\n\n
\n

Writing Proofs<\/a><\/h4>\n\n\n\n

<\/h4>\n<\/div><\/div>\n\n\n\n
\n

Types of Proofs <\/a><\/h4>\n\n\n\n

<\/p>\n<\/div><\/div>\n\n\n\n

\n

Sample Proofs<\/h4>\n<\/div><\/div>\n<\/div><\/div>\n\n\n\n

<\/p>\n<\/div><\/div>\n<\/div><\/div>\n\n\n\n

<\/div>\n\n\n\n

Annotated Sample Proofs<\/h3>\n\n\n\n

These proofs are annotated to give you an idea of what goes into a proof and what is going on in each of them:<\/p>\n\n\n\n

Corollary to Fermat\u2019s Theorem <\/strong>(from Elementary Number Theory<\/em>, 7th ed., Burton, 2011, p. 88)
If p<\/em> is a prime, then ap<\/sup><\/em> \u2261 a <\/em>(mod p<\/em>) for any integer a<\/em>. <\/p>\n\n\n\n

Proof<\/em>. When1<\/strong><\/span><\/sup> p<\/em>|a<\/em>, the statement obviously holds; for, in this setting, ap<\/sup><\/em> \u2261 0 \u2261 a<\/em> (mod p<\/em>)2<\/span><\/strong><\/sup> . If p<\/em>|a<\/em>, then according to Fermat\u2019s theorem3<\/span><\/strong><\/sup> , we have a<\/em>p\u22121<\/em><\/sup> \u2261 1 (mod p<\/em>). When this congruence is multiplied by a<\/em>, the conclusion ap<\/sup><\/em> \u2261 a<\/em> (mod p<\/em>) follows. <\/p>\n\n\n\n

Annotations of Rationale<\/summary>
\n

1<\/span><\/strong><\/sup>This proof contains an implicit breakdown into two cases: when p<\/em> divides a<\/em>, and when it does not. It is valid because we know for certain one must be true, and we can therefore assume them one by one to complete the proof.
2<\/span><\/strong><\/sup>This illustrates the idea of a direct proof: deriving elementary facts from the given circumstances.
3<\/span><\/strong><\/sup>Another tenet of the direct proof (and most proofs in general) is citing previously established claims and theorems, either to set up the ongoing proof or to \u201dskip\u201d proving something over again.<\/p>\n<\/div><\/details><\/div>\n\n\n\n

Theorem 1.1: Archimedean Property<\/strong> (ibid, p. 2)
If a<\/em> and b<\/em> are any positive integers, then there exists a positive integer n<\/em> such that na<\/em> \u2265 b<\/em>. <\/p>\n\n\n\n

Proof<\/em>. Assume that the statement of the theorem is not true4<\/span><\/sup><\/strong> , so that for some a<\/em> and b<\/em>, na<\/em> < b<\/em> for every5<\/strong><\/span><\/sup> positive integer n<\/em>. Then the set <\/p>\n\n\n\n

S<\/em> = {b<\/em> \u2212 na<\/em>|n<\/em> a positive integer} <\/p>\n\n\n\n

consists entirely of pisitive integers. By the Well-Ordering Principle6<\/span><\/strong><\/sup> , S<\/em> will possess a least element, say, b<\/em> \u2212 ma<\/em>. Notice that b<\/em> \u2212 (m<\/em> + 1)a<\/em> also lies in S<\/em>, because S<\/em> contains all integers of this form. Furthermore, we have <\/p>\n\n\n\n

b<\/em> \u2212 (m <\/em>+ 1)a<\/em> = (b<\/em> \u2212 ma<\/em>) \u2212 a<\/em> < b<\/em> \u2212 ma<\/em><\/p>\n\n\n\n

contrary to the choice of b\u2212ma<\/em> as the smallest integer in S<\/em>7<\/strong><\/span><\/sup> . This contradiction arose out of our original assumption that the Archimedean property did not hold; hence, this property is proven true8<\/sup><\/span><\/strong>. <\/p>\n\n\n\n

Annotations of Rationale<\/summary>
\n

4<\/span><\/sup><\/strong>Here, it is made quite clear this is a proof by contradiction. This is what we do in one of those, precisely: assume the outcome is not true.
5<\/span><\/sup><\/strong>Note that some of the wording changed when we assumed the opposite. A proof by contradiction requires one to assume every piece of the conclusion is false and negate the entirety of the statement.
6<\/strong><\/span><\/sup>Note that, after the key assumption of the statement\u2019s falsehood, the proof continues through a string of true deductions similarly to a direct proof.
7<\/strong><\/span><\/sup>This is the crux of the proof by contradiction: reaching a fundamental, inevitable impossibility from our set of assumptions.
8<\/span><\/sup><\/strong>This review of the contradiction is thorough, but not always necessary<\/p>\n<\/div><\/details><\/div>\n\n\n\n

A False Statement<\/strong> (from the mind of Ian Kimmel for the purposes of this project)
Any one-to-one function f<\/em> : R \u2192 R is also onto.<\/p>\n\n\n\n

Counterexample<\/em>. Consider f<\/em>(x<\/em>) = ex<\/sup><\/em> . This function is one-to-one on R9<\/span><\/strong><\/sup> ; however, it is not onto, as the range of the function does not cover any of (\u2212\u221e, 0]10<\/strong><\/span><\/sup>.<\/p>\n\n\n\n

Annotated Rationale<\/summary>
\n

9<\/span><\/strong><\/sup>A valid counterexample to a statement meets all of its assumptions; here, we want a function from the set of real numbers to the set of real numbers that is one-to-one.
10<\/span><\/sup><\/strong>As one would expect intuitively, a valid counterexample fails to meet the conclusion of the statement; here, our function does not cover the entire set of real numbers in its range. What a shame.<\/p>\n<\/div><\/details><\/div>\n","protected":false},"excerpt":{"rendered":"

Annotated Sample Proofs These proofs are annotated to give you an idea of what goes into a proof and what is going on in each of them: Corollary to Fermat\u2019s Theorem (from Elementary Number Theory, 7th ed., Burton, 2011, p. 88)If p is a prime, then ap \u2261 a (mod p) for any integer a. … Continue reading Mathematics – Sample Proofs<\/span><\/a><\/p>\n","protected":false},"author":6113,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"templates\/full-width-page.php","meta":{"footnotes":""},"tags":[],"class_list":["post-667","page","type-page","status-publish","hentry","no-featured-image"],"featured_image_src":null,"featured_image_src_square":null,"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/site.uvm.edu\/tutortips\/index.php?rest_route=\/wp\/v2\/pages\/667","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/site.uvm.edu\/tutortips\/index.php?rest_route=\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/site.uvm.edu\/tutortips\/index.php?rest_route=\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/site.uvm.edu\/tutortips\/index.php?rest_route=\/wp\/v2\/users\/6113"}],"replies":[{"embeddable":true,"href":"https:\/\/site.uvm.edu\/tutortips\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=667"}],"version-history":[{"count":19,"href":"https:\/\/site.uvm.edu\/tutortips\/index.php?rest_route=\/wp\/v2\/pages\/667\/revisions"}],"predecessor-version":[{"id":2594,"href":"https:\/\/site.uvm.edu\/tutortips\/index.php?rest_route=\/wp\/v2\/pages\/667\/revisions\/2594"}],"wp:attachment":[{"href":"https:\/\/site.uvm.edu\/tutortips\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=667"}],"wp:term":[{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/site.uvm.edu\/tutortips\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=667"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}