### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# TRANS HIGHER MATH MATH 074

GPA 3.93

### View Full Document

## 13

## 0

## Popular in Course

## Popular in Mathematics (M)

This 15 page Class Notes was uploaded by Kavon Feest on Thursday October 22, 2015. The Class Notes belongs to MATH 074 at University of California - Berkeley taught by Staff in Fall. Since its upload, it has received 13 views. For similar materials see /class/226598/math-074-university-of-california-berkeley in Mathematics (M) at University of California - Berkeley.

## Reviews for TRANS HIGHER MATH

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/22/15

MATH 74 TRANSITION TO UPPER DIVISION MATHEMATICS LECTURE 14 Spring 2005 MWF 300PM 400PM 6 Evans CON 54789 In this lecture7 we7ll continue with our introduction to number theory by proving the division theorem7 and stating a division theorem for polynomials 01 proving the division theorem Recall that the division theorem says meEZngt03lqr Zmqnr0 rrlt71 The proof uses the well ordering principle7 together with a carefully constructed set A Proof Let mm 6 Z and assume n gt 0 De ne A x E N 3k 6 Zx m 7 Now A Q N by its de nition and A 31 o since choosing k mmm7 7m ensures that m 7 kn E N By the well ordering principle7 A has a least element7 call it 7 Since 7 E A let q be the integer such that r m 7 gm Then we have 1 m qn r subtracting qn from both sides of the equation above 2 0 S 7 since 7 E N 3 r lt 71 since 7 is the least member of A le7 if we had 7 2 717 then we would have T771 6 N7 and r 7 n m 7 q 7 1n7 so that r 7 71 would be in A7 contradicting the choice of r as the least member of A This completes the existence part of the proof Assume m7n7q7r are xed for the remainder of the proof For uniqueness7 let q f E Z and assume that 1 m 1 r 2 0 S r 3 r lt 71 well rst show q 1 Since lt is a total ordering on Z either q lt q or q lt q or q 1 well rule out the rst two of these cases lfq lt q 7 then 11 3 1 So r m7q n S m7q1n r771 lt 0 So r lt 0 This contradicts our second assumption regarding r lfq ltq7 then 1 q71 So r m7q n 2m7q71nrn gt71 So r gt71 This contradicts our third assumption regarding r We conclude that q 1 Now we have m qnr and m q nr So 7 m7qn m7q n r This completes the uniqueness part of the proof D For any integers mm with n gt 07 the division theorem gives us unique integers q and r The integers q and r depend on m and 71 Sometimes to avoid using so many variables7 we7ll write m div n to mean the q we get from the division theorem starting with m and n7 and m mod n to mean the r we get from the division theorem starting with m and So that m div n and m mod n are the unique integers with 1 mm divn nm mod n 2 0 m modnltn Date Friday7 February 187 2005i 2 MATH 74 TRANSITION TO UPPER DIVISION MATHEMATICS LECTURE 14 1 THE DIVISION THEOREM FOR POLYNOMIALS A polynomial with real coef cients is an expression of the form 20 ajzj where z is a variable 10 an are real numbers and an 31 0 Polynomials are often denoted by the letters p or q and sometimes we also write p when we want to reference the name of the variable The degree of a polynomial p is the least natural number n such that the coef cient of x is non zero and is denoted by degp For example 4x3 x2 7 7m 5 has degree 3 15x9 7 2m has degree 9 and the constant polynomial 4 has degree 0 By convention we say that ifp is the constant zero polynomial ie p 0 then degp foo There is a division theorem for polynomials with real coef cients It says that if pd are polyno mials with real coef cients and if d has degree n 2 0 then there are unique polynomials with real coef cients q and 7 with 1 1996 Qd WC 2 deg lt degd The theorem is also true if 77real77 is replaced by 77rational77 or 77complex but not if it is replaced by 77integer The reason integer doesn7t work as you will see from the proof is that you need to be able to divide the coef cients of p by the coef cients of d to get the coef cients of q and 7 and we cannot always divide in the integers The proof of this theorem will be given as an exercise 2 EXERCISES These exercises will be due Wednesday February 23 1 Modify the example in the lecture notes involving the Well Ordering Principle to prove that E is irrational whenever s is not a perfect square ie not the square of any natural number You may assume as hypotheses any of the arithmetic and ordering properties of rational numbers Show that the usual de nition of the choose function in terms of factorials satis es the recursive condition Hint You don7t need to use induction just algebra Various versions of the recursive condition above are often referred to as the Addition Formula for Binomial Coef cients What is the coef cient of x10 in the expansion of x 3 Hint Use the Binomial Theorem Use telescoping sums to derive a formula for the sum of the rst 71 cubes 21j3 Suppose that f N a N is a function satisfying the following two properties o w e Nfa b fa fb o The range of f is nite and contains exactly 71 elements a Show that f0 0 Hint At some point you will need to use the fact that 0 0 0 and also the cancellation law for addition b Show that Haj E Na 31 b fa fb Hint pigeonhole principle c Show that 30 E Nc 31 0 fc 0 Hint Fix ab E N satisfying the property above Either a lt b or b lt 1 Use the c you get from the de nition of lt d How many different natural numbers 0 must satisfy fc 0 Hint lf fc 0 what is fc c and fc c 0 e Show that if fc 0 and b a c then fa fb f Show that if k E N and 0 lt k lt n then fk 31 0 Hint Show that if k gt 0 and fk 0 then the range of f has at most k elements g What must be the value of fn7 Give a proof along with your answer A D V A 0 V AA U 4 VV MATH 747 TRANSITION TO UPPER DIVISION MATHEMATICS LECTURE 14 3 h Suppose that f1 m Give a description of the elements in the range of f in terms of m and n MATH 74 TRANSITION TO UPPER DIVISION MATHEMATICS LECTURE 12 Spring 2005 MWF 300PM 400PM 6 Evans CON 54789 Updated 21605 In this lecture7 well talk about a few more miscellaneous properties of N and some useful proof techniques 1 THE PIGEONHOLE PRINCIPLE One version of the pigeonhole principle says that if you try to cram n1 pigeons into n pigeonholes7 then at least one pigeonhole must have more than one pigeon in it Formally7 in N this version of the principle can be formulated as the rst order statement V71 6 NV lt n 13y lt nPzy thxg lt n 13y lt nz1 31 x2 Pz1y P2y The pigeonhole principle encapsulates a type of counting argument which is dif cult to formulate using a purely direct approach The pigeonhole principle tells us something about what happens when we match up 71 1 items with 71 items To analyze this scenario without using the pigeonhole principle requires that we consider every possible function from a set of n 1 items to a set of n items7 and there are nler1 such functions Without using the pigeonhole principle7 our analysis is forced to take a form similar to the following 77Let7s see7 if we put this pigeon here and that one there7 darn it still doesn7t work If we take a step back for a moment7 and take the time to count the number of pigeons and the number of holes7 we can conclude something that is very dif cult to derive using an up close analysis In the exercises7 you will prove a statement about functions on N that respect addition Using the pigeonhole principle will simplify your proof considerably7 and it is unclear how you would prove this fact at all without using a type of pigonhole principle counting argument 2 RECURSION IN Two VARIABLES l didn7t discuss this much in the lecture7 but here is the information for reference If we want to de ne a function fn in one variable 71 using recursion7 then we just need to specify an initial value and a recurrence relation The function f can then be computed based on two separate cases7 whether 71 07 or whether 71 is the successor of some other natural number If we want to use this same type of recursive approach to de ne a function gmn in two variables m and 717 then a single initial value and a recurrence relation is not suf cient to cover the four possibilities of whether mm are zero or the successor of something We can give analogous recursive de nitions for two variable functions7 but to do so requires giving four recursive conditions instead ofjust two7 as in the one variable case To de ne gm7 n as a recursive function of two variables by general recursion7 we need to specify four conditions I 9070 a single value7 2 071 I in terms of previous values of g of the form kg 9 0kltn1 3 gm 17 0 in terms of previous values of g of thwe form 0g 9 gtgt k ltm1gt m 171 I in terms of previous values of g of the form ltk17k2gk1 k2 k1 kg S m1k1 ltm1Vk2ltn1 4 Date Monday7 February 147 2005i 2 MATH 74 TRANSITION TO UPPER DIVISION MATHEMATICS LECTURE 12 For example suppose that ltajgtj6N is a xed sequence Then we can de ne the function of two variables 17 via the four conditions 1 230 0739 00 2 2201 0739 220 0739 an1 3 23 aa39 0 4 2271 0739 22quot am These four conditions are enough to uniquely determine every value of this summation function for all choices of 77171 6 N We can take the above recursive conditions as a formal de nition for the summation function to be used in subsequent proofs As another example consider the choose function which is usually de ned only when n 2 k by the formula MOE is read as 7771 choose k and corresponds to the number of possible ways to choose k items from a set of 71 items when the order in which the items are chosen does not matter This choose function also appears in a large variety of seemingly unrelated contexts one of which is the binomial theorem discussed below We can actually give a recursive de niton for 2 that extends the usual de nition to all natural numbers n and k Saying the new de nition 77extends the usual de nition77 means that the recursive de nition will correspond to the standard de nition in the restricted case k S You will prove part of this in the homework Here are the recursive conditions lt1 30 1 2 0 lt3 13 1 4 In the homework you will prove that the choose function7s factorial de nition satis es the fourth recursive condition whenever k S n 3 THE BINOMIAL THEOREM The Binomial Theorem tells us how to expand the expression a b as a standard form poly nomial in the two variables a and b One version of the binomial theorem states that for every 1 b E C and for every n E N a b Zn 7an jbj 7390 Now we can also use Pascal7s triangle to nd the coef cients of ab Pascal7s triangle is usually formed by writing down three 17s at the top and lling in the remaining rows by the following two rules 1 Always write a 1 on the outer edge of each row 2 The other integers in each row are the sum of the two integers immediately above The rst several rows of Pascal7s triangle are as follows 1 121 1331 14641 15101051 MATH 747 TRANSITION TO UPPER DIVISION MATHEMATICS LECTURE 12 3 1 6 15 20 15 6 1 172135352171 18285670562881 Long ago Pascal discover that the numbers in row 71 of this triangle correspond to the coef cients in the expansion of a b For exarnple7 we have a b2 112 2ab 1b2 3 1a3 3a2b 3ab2 b3 We can ask two questions 1 Why do we need the binomial theorern when Pascal7s triangle is so easy to construct 2 How does the binonrnial theorem and the choose function trelate to Pascals triangle To answer the rst question is easy Pascal7s triangle requires a recursive construction To compute one coef cient in the expansion of a b L7 for exarnple7 required constructing every term in a huge triangle The binornial theorern gives a closed form formula for each term that can be evaluated with a single cornputation As an exarnple7 we can compute the coef ecient of x14 in the expansion of s 216 easily using the binomial theorern We get the term containing x14 when n 16 andj 2 The term is 1x16 222 and the coef cient is 1 22 Li 4800 If we tried cornputing this value using Pascal7s triangle7 it would probably take us quite a long time How does the binomial theorern relate to Pascal7s triangle This question has a very interesting answer It turns out that the numbers in Pascal7s triangle can be indexed by the choose function The rst few rows look like the following From the rules for constructing Pascal7s triangle7 and from the picture above7 we can see that for j S 717 we have 71 Not surprisingly7 this is exactly the fourth condition in our recursive de nition of the choose function given above The full graph of the recursive choose function is rectangular7 and includes Pascal7s triangle in the upper left diagonal portion 3 3 3 0 2 AAAA 0 0 one No H AAAA H pH 02H NH H AAAA 0 pm mm mm H AAAA a pm one No Ho AAAA p pp on N H 4 MATH 747 TRANSITION TO UPPER DIVISION MATHEMATICS LECTURE 12 10000 11000 12100 13310 14641 Finally7 here is a proof of the binomial theorem Proof Let 11 E C Let Pn say a b 20 a jbj Then Pn is a predicate in the variable 71 1 P0 says a b0 230 3a0 jb7 We have a b0 1 369quotle0 230 ga0 jbj So P0 is true 2 Let n E N and assume Pn is true Then a b 220 a jbj We need to show Pn 1 is true Pn 1 says a b 1 1a 1 7b739 We have a W a W b n a b 2 anijb induction hypothesis 7390 crew rmsMW Z t i 1 a 1 n a 17b7gt b 1 recursive de nition of choose function 7 71 n1 Z n 1an1ijbj J 7390 a 1 11 So Pn 1 is true Since 71 was arbitrary7 V71 6 NPn Pn 1 is true By induction7 V71 6 is true7 ie V71 6 Na b 220 a jbj Since ab were arbitrary cornplex nurnbers7 the binomial theorern follows E MATH 74 TRANSITION TO UPPER DIVISION MATHEMATICS LECTURE 12 5 4 TELESCOPING SUMS A telescoping sum7 is an expresion of the form Egmm l 7 17 If ltajj6N is any sequence of real or complex numbers7 we can prove that me E N m S n Eggnij 7 a7 an 7 am The informal argument is easy to see from writing out the terms of a telescoping sum We have 2maj1 0739 am1 am am2 am1gt am3 am2 39 an1 an eVeTything cancels except for the 7am term and the an term More formally7 the proof goes as follows Proof Let ltajj6N be any sequence from R and let mm 6 N with m S 71 Since m S n7 let k0 be then natural number such that n m k0 well actually prove Vko E NVmn E N n m k0 2maj1 7 a7 an 7 am using induction on k0 Let Pk0 say me E Nn m k0 Egmm l 7 a7 an 7 am 1 P0 says me E N n m0 2maj17aj an17am Let mm 6 N and assume n m 0 Then m 717 so 2maj1 7 a7 Zmaj1 7 a7 am 7 am an 7 am So P0 is true 2 Let kg 6 N and assume Pk0 is true Then me E Nn m k0 Egmm l 7 a7 an17am We need to show Pk01 is true Pk01 says me E Nn mk01 2maj1 7 a7 an 7 am Let mm 6 N and assume n m k0 1 Then we have n mko1 0741 i 0739 Z 0741 i 0739 jm jm mko Z 1741 i 1739 f amko11 0mk01 algebra 0f sums jm amko1 am amko11 amko1 indUCtiOH hYPOtheSiS amko2 am an1 am So 71 m k0 1 i Egmm l 7 a7 an 7 am Since mm were arbitrary7 me E N n m k0 1 i 2maj1 7 a7 an 7 am7 ie7 Pk0 1 is true Since kg was arbitrary7 Vko E NPk0 Pk0 By induction7 Vko E N me E N n m k0 2maj1 7 a7 an 7 am D The telescoping sum formula follows me E N m S n Eggnij 7 a7 an 7 am 5 USING TELESCOPING SUMS One use of telescoping sums is a new method for discovering a formula for the rst 71 consecutive integers7 2211 The way to do this is to evaluate the sum 21j12 772 in two different ways7 once by using the telescoping sum formula with 17 jz and once by simplifying the expression 7 12 7 72 Using the rst method7 telescoping sums7 we have j12j2n121 n J 6 MATH 747 TRANSITION TO UPPER DIVISION MATHEMATICS LECTURE 12 Using the second method7 simplifying j 12 7 jz we have iltltj1gt27j2gt imam 1 lt72 m 1 n 11 11 71 Setting these two expressions equal7 we can solve for 21j Using simple algebra lt2ijgt nn1271 11 jn22n7n M 2 x H in2ninn71 2 7 2 M j m NH We can discover the formula for 21j in a similar manner by evaluating the telescoping sum 221U1L 13 jg in two different ways and setting the results to be equal lN this case7 the telescoping sum formula gives 71 13 7 17 and the simpli cation process gives 3 21j2 3 21j 71 Since we already know 21j M2 substituting this and setting the two above expressions equal allows us to solve for 21j2 in terms of 71 You have already proven nn12n1 6 this well known result 21j2 in a previous Homework In this homework7 you7ll discover and simultaneously prove a formula for 21j3 using the telescoping sum technique One important thing to note about this type of proof is that it does not involve induction lnduction is required in order to prove any suf ciently general formula involving summation7 but the induction argument is hidden in the proof of the telescoping sum formula So when you use the telescoping sum formula7 you bypass the part of the proof that requires induction 6 HERCULES AND THE HYDRA You had to be in class for this one 7 EXERCISES These exercises will be due Wednesday7 February 23 1 Modify the example in the lecture notes involving the Well Ordering Principle7 to prove that E is irrational whenever s is not a perfect square ie not the square of any natural number You may assume as hypotheses any of the arithmetic and ordering properties of rational numbers 2 Show that the usual de nition of the choose function in terms of factorials satis es the recursive condition Hint You don7t need to use induction7 just algebra Various versions of the recursive condition above are often referred to as the Addition Formula for Binomial Coef cients 3 What is the coef cient of x10 in the expansion of z3127 Hint Use the Binomial Theorem 4 Use telescoping sums to derive a formula for the sum of the rst 71 cubes7 21j3 5 Suppose that f N a N is a function satisfying the following two properties o w e Nfa b fa fb o The range of f is nite7 and contains exactly 71 elements a Show that f0 0 Hint At some point7 you will need to use the fact that 0 0 07 and also the cancellation law for addition A MATH 747 TRANSITION TO UPPER DIVISION MATHEMATICS LECTURE 12 7 b Show that Haj E Na 31 b fa fb Hint pigeonhole principle c Show that 30 E Nc 31 0 fc 0 Hint Fix ab 6 N satisfying the property above Either a lt b or b lt 1 Use the c you get from the de nition of lt d How many different natural numbers 0 must satisfy fc 0 Hint lf fc 07 what is fc c and fc c 0 e Show that if fc 0 and b a c then fa fb f Show that if k E N and 0 lt k lt 717 then fk 31 0 Hint you may need to use some form of proof by contradiction here g What must be the value of fn7 Give a proof along with your answer h Suppose that f1 m Give a description of the elements in the range of f in terms of m and n MATH 74 TRANSITION TO UPPER DIVISION MATHEMATICS LECTURE 13 Spring 2005 MWF 300PM 400PM 6 Evans CON 54789 In this lecture we7ll introduce the eld of number theory and the set Z of integers In subsequent lectures we7ll begin to be less formal in our proofs and worry less about making explicit our assumptions regarding the common functions and For example we7ll allow ourselves to write a b c not caring whether the formal expression is really a b c or a b 0 since associativity tells us these two expressions always evaluate in the same way After discussing a variety of properties expressible using integers well then go back and show how these properties can actually be expressed just as well without really using Z at all All theorems about Z can be expressed and proven using only the three initial axioms of N and some carefully chosen de nitions 1 NUMBER THEORY Loosely speaking number theory is the study of the set of integers Many topics in number theory deal only with positive integers but some can be expressed in terms of all integers in a more transparent way Many theorems in the eld of Number theory have two characteristic properties 1 They are very easy to state 2 They are very dif cult to prove Because of these characteristics many mathematicians choose to like number theory and many choose to dislike it In our treatment of number theory in this course we will try to state a lot of theorems and only prove the ones that are relatively easy We7ll also try to give some motivation for why some of the easily expressed statements are so dif cult to prove 2 THE INTEGERS The set of integers Z can be informally de ned as the set 7 3 72 710 1 23 We are all familiar with the set of integers They include the natural numbers together with all the additive inverses of natural numbers Later in the course we7ll show how we can construct a copy of the integers within the structure NNN0N1N For now we7ll just assume that the integers come equipped with the standard binary functions Z Z the additive inverse I ary function 7 and the constants ON IN A list of the properties we7ll assume about Z is given below Later we7ll show how we can avoid assuming these properties and actually prove them from our axioms about N Properties of integers 1 Z Z are associative and commutative and the distributive property holds 3 For every 1 E Z a 0 a 4 For every 1 E Z a1Z a Foreveryabc Zaltblt acltbc 6 For every ab Z and for everyc N a ltblt acltbc l7ll probably need to go back and edit this list later Basically we7ll assume any of the standard properties of 7 0 and 1 with which you are familiar from grade school We will not assume any properties of or admit to the existence of rational numbers everything well do will involve integers Date Wednesday February I6 2005 2 MATH 74 TRANSITION TO UPPER DIVISION MATHEMATICS LECTURE 13 For now well proceed to discussing some real theorems about integers the rst of which is the division theorem 3 THE DIVISION THEOREM The Division theorem is an essential result that is necessary to prove many of the common properties of integers involving any form of divisibility For the next several weeks you will have to use this theorem so it might be a good idea to memorize it The Division Theorem For any m n E Z with n gt 0 there exists unique integers q 7 E Z such that 1 m q n 7 2 0 S 7 lt 71 First well give a motivation for the theorem Then we7ll show how to formalize it Then we7ll prove it 31 motivating the division theorem One way to think of the division theorem is that its just a formalization in Z of the statement in Q that we can always express a fraction uniquely as a mixed number For example we can write as 2 and we can write 7733 as 12 We can also deal with negative numbers since 7 76 There is an algorithm for doing this Its called 3 long division To write 7733 as a mixed number we divide 6 into 73 12 6W 13 12 1 and we get 12 with remainder 1 So 12 If we divide both sides of this equation by 6 we get an expression involving no fractions 73 6 12 1 In the above algorithm the number 73 is called the dividend 6 is called the divisor 12 is called the quotient and 1 is called the remainder The division theorem just says that for any integer dividend m and non zero integer divisor n we can do long division to get a unique quotient q and remainder 7 The equation In qn 7 is just a re wording of the equation q that says how we would write as a mixed number The condition 0 S 7 lt 71 just expresses our halting condition for the long division algorithm that says we are not done until the last number at the bottom is smaller than our dividend When were done the last number at the bottom is 7 and our dividend is n so 0 S 7 lt 71 While our motivation for this theorem involves fractions the division theorem itself does not deal with fractions only with integers and our proof of it will need to use only integers as well 32 formalizing the division theorem Every part of the division theorem is easily expressible in rst order logic except for the part that says 77unique To say that q 7 are unique with respect to the two properties listed above means that if q r are any pair of integers satisfying both properties then 1 q and r 7 We can formulate the division theorem using rst order logic if we introduce the 77 unique exis tential77 quanti er 3 First if P is any predicate in one variable x then 31 6 is an abbreviation for the sentence Hz 6 ZPz Vy E ZPy i y Similarly if P is a predicate in m variables z1 zm then 31 zm E ZPz1 is an abbreviation for 3z1zm E ZPz1zm Vy1ym E ZPy1ym yl zl ym We just gave the de nition for 31 as a quanti er over the set Z but the de nition is analogous for N or any other set X in place of Z MATH 74 TRANSITION TO UPPER DIVISION MATHEMATICS LECTURE 13 3 In this new notation we can formally express the division theorem as the following rst order sentence VmnEZngt03lqr Zmqnr0 rrlt71 4 EXERCISES These exercises will be due Wednesday February 23 1 Modify the example in the lecture notes involving the Well Ordering Principle to prove that E is irrational whenever s is not a perfect square ie not the square of any natural number You may assume as hypotheses any of the arithmetic and ordering properties of rational numbers 2 Show that the usual de nition of the choose function in terms of factorials satis es the recursive condition Hint You don7t need to use induction just algebra Various versions of the recursive condition above are often referred to as the Addition Formula for Binomial Coef cients 3 What is the coef cient of x10 in the expansion of x 3 Hint Use the Binomial Theorem 4 Use telescoping sums to derive a formula for the sum of the rst 71 cubes 21j3 5 Suppose that f N a N is a function satisfying the following two properties o w e Nfa b fa fb o The range of f is nite and contains exactly 71 elements a Show that f0 0 Hint At some point you will need to use the fact that 0 0 0 and also the cancellation law for addition b Show that Haj E Na 31 b fa fb Hint pigeonhole principle c Show that 30 E Nc 31 0 fc 0 Hint Fix ab E N satisfying the property above Either a lt b or b lt 1 Use the c you get from the de nition of lt d How many different natural numbers 0 must satisfy fc 0 Hint lf fc 0 what is fc c and fc c 0 e Show that if fc 0 and b a c then fa fb f Show that if k E N and 0 lt k lt n then fk 31 0 Hint you may need to use some form of proof by contradiction here g What must be the value of fn7 Give a proof along with your answer h Suppose that f1 m Give a description of the elements in the range of f in terms of m and n MATH 74 TRANSITION TO UPPER DIVISION MATHEMATICS LECTURE 39 Spring 2005 MWF 300PM 400PM 6 Evans CON 54789 In this lecture7 we7ll prove my favorite theorem7 the theorem rst proved by George Cantor that says for every set X7 X is strictly dominated by its power set 73X 1 MY FAVORITE THEOREM My favorite theorem is the one by George Cantor that says that every set is strictly dominated by its power set 11 Notation l7ll introduce some notation rst If A and B are sets7 we de ne A 5 B to mean that there exists an injective function f A 4 B Sometimes we say7 in this case7 that A is dominated by B7 or that B dominates A We de ne A 4 B to mean that A 5 B A 99 B In other words7 A 4 B means that there exists an injective function f A a B7 but there does not exist a bijective function f A 4 B Sometimes we say7 in this case7 that A is strictly dominated by B7 or that B strictly dominates A 12 Cantor7s Theorem Cantor7s theorem says that for every set X7 we have X 4 73X Date Wednesday7 May 67 20051 2 MATH 747 TRANSITION TO UPPER DIVISION MATHEMATICS LECTURE 39 Proof Let X be any set De ne the function f X a 73X Via fv Then clearly f is injective This shows X j 73X It remains to show that X 99 73X For this we use proof by contradiction Suppose that f X a 73X were a surjective function Consider the set A 2 E 5 2 A is a non empty subset of X It is non empty7 because7 for example7 if e is the element of X such that fe Q then 6 is a member of A because 6 6 X7 and e Z fe Q It does not really matter that A is non empty7 it only matters that A is well de ned iff exists and that A is a member of 73X since f is surjective7 there is an element 0 E X such that fc A We ask the question 77Is 0 6 A777 The answer must be yes or no 1 If c 6 A7 then c E 2 E X 2 by the de nition of A So 0 E X and c Zfc Since fc A7 this latter condition implies that c Z A This contradicts our assumption that c E A 2 If c Z A7 then c E X because A Q X7 and c Z fc because 0 Z A and fc A so 0 E 2 E X 2 Z So 0 E A by the de nition of A This contradicts our assumption that c Z A In either case7 we get a contradiction So we conclude that no such f can exist In particular7 there does not exist a bijective function f X a 73X This completes the proof that X 4 73X 2 EXERCISES This exercise will be due Monday7 May 9 1 Prove that for every set X7 X 4 73X

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the material...plus I made $280 on my first study guide!"

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.