DOC PREVIEW
USF MATH 300 - Formal Methods

This preview shows page 1 out of 3 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 3 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 3 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Formal MethodsKey to Homework Assignment 3, Part 2February 12, 2007• Prove that multiplication of rational numbers is well-defined.Proof. Suppose m, n, p, q, r, s, t and u are integers such that n, q, s, and u are nonzero,m/n = r/s, and p/q = t/u. We want to see thatmnpq=rstu,or, equivalentlympnq=rtsu.From the definition of e quality of rational numbers, we need to see thatmpsu = nqr t.But by assumption m/n = r/s and p/q = t/u. So ms = nr and pu = qt. Substitutinginto the left-hand side of the equation mpsu = nqrt, we getnrqt = nqrt.Reversing the steps, then, we see thatmnpq=rstu,and multiplication of rational numbers is well-defined.89. Is the converse of “if n is any prime, then 2n+ 1 prime” true? If your answer is yes,prove the statement. Otherwise find a counterexample.The converse is “if 2n+ 1 is prime, then n is prime.” This is false. For example,24+ 1 = 17, but 4 isn’t prime.94. Prove that if a and b are rational numbers with a < b, then there exists a rationalnumber r such that a < r < b.1Proof. Define r = (a + b)/2. Then if m, n, p, and q are integers with n and q nonzero,such that a = m/n and b = p/q, we haver =mn+pq12=mq + npnq12=mq + np2nq.Since mq + np is an integer and 2nq is a nonzero integer, we see that r is a rationalnumber.To check that a < r < b, we can check that the differences r − a and b − r are bothpositive. We have thatr − a =a + b2− a =a + b − 2a2=b − a2Since a < b, we know that b −a > 0. So r −a > 0 and a < r. The argument that b −ris positive is entirely analogous:b − r = b −a + b2=2b − a − b2=b − a2,which, as we’ve just seen is positive. So r is a rational number such that a < r < b.95. Prove that if x is a positive real number, then x + 1/x ≥ 2.Proof. This is similar to problem 80, which we proved by contradiction. So let’s tryassuming the contrary. That is, we assume that x is a positive real numb er such thatx + 1/x < 2. Since x is positive, we can multiply both sides of this inequality by x andgetx2+ 1 < 2x,or, equivalently,x2− 2x + 1 = (x − 1)2< 0.However, since x is a real number (x − 1)2≥ 0, and this is a contradiction. So theassumption that x + 1/x < 2 must be false, and x + 1/x ≥ 2 for all positive realnumbers x.96. (a) Find positive real numbers x and y such that√x + y 6=√x +√y.If x = y = 1, then x and y are positive, and√x + y =√2 but√x +√y = 2.Since 2 is rational and√2 is irrational, 2 6=√2.(b) Prove that if x and y are positive real numbers, then√x + y ≤√x +√y.First Proof. We’ve proved a number of inequalities involving real numbers byusing contradiction. So let’s try contradiction. So we assume that x and y arepositive real numbers such that√x + y >√x +√y.Since the function f(z) = z2is increasing on the positive reals, we know that if0 < a < b then 0 < a2< b2. So(√x + y)2> (√x +√y)2.2Simplifying, givesx + y > x + 2√xy + y,and subtracting x + y from both sides gives0 > 2√xy,but since x and y are positive reals,√xy > 0. So 2√xy > 0, which is a contra-diction. So the assumption that√x + y >√x +√y must be false, and we havethat√x + y ≤√x +√y, for all positive real numbers x and y.Second Proof. We can reverse the steps in the argument given in the first proofand give a direct proof of the the result. Suppose that x and y are positive realnumbers. Then√xy > 0, and 2√xy > 0. Thusx + y ≤ x + 2√xy + y,or, equivalently,(√x + y)2≤ (√x +√y)2.Since the function g(z) =√z is increasing on the positive reals, we can takesquare roots of both sides of this inequality, and get√x + y ≤√x +√y.Note. Since√xy > 0, this proof actually shows that√x + y <√x


View Full Document

USF MATH 300 - Formal Methods

Download Formal Methods
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Formal Methods and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Formal Methods 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?