### Create a StudySoup account

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

Already have a StudySoup account? Login here

# EXAMS GUIDE IN MATHS MATH 1009

CSU - Dominguez hills

### View Full Document

## 64

## 0

## Popular in Mathematical Ideals I

## Popular in Department

This 592 page Study Guide was uploaded by Akwasi johon on Thursday June 2, 2016. The Study Guide belongs to MATH 1009 at California State University - Dominguez Hills taught by in Summer 2016. Since its upload, it has received 64 views.

## Reviews for EXAMS GUIDE IN MATHS

### 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: 06/02/16

L Y N N H. L 0 0 MISand S H L 0 M S T ERN B ERG Departmenof MathematiHarvardUniversity ADVANCED CALCULUS REVISED EDITION JONES AND BARTLETT PUBLISHERS Boston London ~"\' , ~ ", :,i.;J) Editorial, Sales, and Customer Service Offices: Jones and Bartlett Publishers, Inc, One Exeter Plaza Boston, MA 02116 Jones and Bartlett Publishers International POBox 1498 London W6 7RS England Copyright © 1990 by Jones and Bartlett Publishers, Inc. Copyright © 1968 by Addison-Wesley Publishing Company, Inc. All rights reserved. No part of the material protected by this copyright notice may be reproduced or utilized in any form, electronic or mechanical, including photocopying, recording, or by any information storage and retrieval system, without written permission from the copyright owner. Printed in the United States of America. 10 9 8 7 6 5 4 3 2 Library of Congress Cataloging-in-Publication Data Loomis, Lynn H. Advanced calculus / Lynn H. Loomis and Shlomo Sternberg. -Rev. ed. p. cm. Originally published: Reading, Mass. : Addison-Wesley Pub. Co., 1968. ISBN 0-86720-122-3 1. Calculus. I. Sternberg, Shlomo. II. Title. QA303.L87 1990 515--dc20 89-15620 CIP 'I '. , PREFACE This book is based on an honors course in advanced calculus that we gave in the 1960's.The foundational material, presented in the unstarred sections of Chap ters 1 through 11,was normally covered, but different applications of this basic material were stressed from year to year, and the book therefore contains more material than was covered in anyone year. It can accordingly be used (with omissions) as a text for a year's course in advanced calculus, or as a text for a three-semester introduction to analysis. These prerequisites are a good grounding in the calculus of one variable from a mathematically rigorous point of view, together with some acquaintance with linear algebra. The reader should be familiar with limit and continuity type arguments and have a certain amount of mathematical sophistication. ABpossi ble introductory texts, we mention Differential and Integral Calculus by R. Cou rant, Calculus by T. Apostol, Calculus by M. Spivak, and Pure Mathematics by G.Hardy. The reader should also have some experience with partial derivatives. In overall plan the book divides roughly into a first half which develops the calculus (principally the differential calculus) in the setting of normed vector spaces,and a secondhalfwhichdealswith the calculusofdifferentiablemanifolds. Vector space calculus is treated in two chapters, the differential calculus in Chapter 3, and the basic theory of ordinary differential equations in Chapter 6. The other early chapters are auxiliary. The first two chapters develop the neces sary purely algebraic theory of vector spaces, Chapter 4 presents the material on compactness and completeness needed for the more substantive results of the calculus, and Chapter 5 contains a brief account of the extra structure en countered in scalar product spaces. Chapter 7 is devoted to multilinear (tensor) algebra and is, in the main, a reference chapter for later use. Chapter 8 deals with the theory of (Riemann) integration on Euclidean spaces and includes (in exercise form) the fundamental facts about the Fourier transform. Chapters 9 and 10developthe differential and integral calculus onmanifolds, while Chapter 11treats the exterior calculus ofE. Cartan. The first eleven chapters form a logical unit, each chapter depending on the results of the preceding chapters. (Of course, many chapters contain material that can be omitted on first reading; this is generally found in starred sections.) On the other hand, Chapters 12, 13, and the latter parts of Chapters 6 and 11 are independent of each other, and are to be regarded as illustrative applications of the methods developed in the earlier chapters. Presented here are elementary Sturm-Liouville theory and Fourier series, elementary differential geometry, potential theory, and classical mechanics. We usually covered only one or two of these topics in our one-year course. We have not hesitated to present the same material more than once from different points of view. For example, although we have selected the contraction mapping fixed-point theorem as our basic approach to the in1plicit-function theorem, we have also outlined a "Newton's method" proof in the text and have sketched still a third proof in the exercises.Similarly, the calculus of variations is encountered twice-once in the context of the differential calculus of an infinite-dimensional vector space and later in the context of classical mechanics. The notion of a submanifold of a vector space isintroduced in the early ohapters, while the invariant definition of a manifold is given later on. In the introductory treatment of vector space theory, we are more careful and precise than is customary. In fact, this level of precision of language is not maintained in the later chapters. Our feeling is that in linear algebra, where the concepts are so clear and the axioms so familiar, it is pedagogically sound to illustrate various subtle points, such as distinguishing between spaces that are normally identified, discussing the naturality of various maps, and so on. Later on, when overly precise language would be more cumbersome, the reader should be able to produce for hin1selfa more precise version of any assertions that he finds to be formulated too loosely. Similarly, the proofs in the first few chapters are presented in more formal detail. Again, the philosophy is that once the student has mastered the notion of what constitutes a fonnal mathematical proof, it is safe and more convenient to present arguments in the usual mathe matical colloquialisms. While the level of formality decreases, the level of mathematical sophisti cation does not. Thus increasingly abstract and sophisticated mathematical objects are introduced. It has been our experience that Chapter 9 contains the concepts most difficult for students to absorb, especially the notions of the tangent space to a manifold and the Lie derivative of various objects with respect to a vector field. There are exercises of many different kinds spread throughout the book. Some are in the nature of routine applications. Others ask the r~ade tr fill in or extend various proofs of results presented in the text. Sometimes whole topics, such as the Fourier transform or the residue calculus, are presented in exercise form. Due to the rather abstract nature of the textual material, the stu dent is strongly advised to work out as many of the exercises as he possibly can. Any enterprise ofthisnature owes much to many people besides the authors, but we particularly wish to acknowledge the help of L. Ahlfors, A. Gleason, R. Kulkarni, R. Rasala, and G. Mackey and the general influence of the book by Dieudonne. We also wish to thank the staff ofJones and Bartlett for their invaluable help in preparing this revised edition. Cambridge, Massachusetts L.H.L. 1968, 1989 S.S. CONTENTS Chapter 0 In trod uction 1 Logic: quantifiers 1 2 The logical connectives 3 3 Negations of quantifiers 6 4 Sets 6 5 Restricted variables. 8 6 Ordered pairs and relations. 9 7 Functions and mappings 10 Product sets; index notation 8 12 9 Composition 14 10 Duality 15 11 The Boolean operations . 17 12 Partitions and equivalence relations 19 Chapter 1 Vector Spaces 1 Fundamental notions 21 2 Vector spaces and geometry 36 3 Product spaces and Hom(V, TV) 43 4 Affine subspaces and quotient spaces 52 5 Direct sums 56 6 Bilinearity 67 Chapter 2 Finite-Dimensional Vector Spaces 1 Bases 71 2 Dimension 77 3 The dual space 81 4 .Matrices 88 5 Trace and determinant 99 6 Matrix computations 102 *7 The diagonalization of a quadratic form 111 Chapter 3 The DifferentialCalculus 1 Review in IR 117 2 Norms. 121 3 Continuity 126 4 Equivalent norms 132 5 Infinitesimals . 136 6 The differential 140 7 Directional derivativesthe mean-value theorem 146 8 The differential and nroduct spaces 152 9 The differential and IR• 156 10 Elementary applications 161 11 The implicit-function theorem 164 12 Submanifolds and Lagrange multipliers 172 *13 Functional dependence 175 *14 Uniform continuity and function-valued mappings 179 *15 The calculus of variations 182 *16 The second differential and the classification of critical point186 *17 The Taylor formula . 191 Chapter 4 Compactness and Completeness 1 Metric spaces; open and closed sets 195 *2 Topology 201 3 Sequential convergence . 202 4 Sequential compactness. 205 5 Compactness and uniformity 210 6 Equicontinuity 215 7 Completeness. 216 8 A first look at Banach algebras 223 9 The contraction mapping fixed-point theorem 228 10 The integral of a parametrized arc 236 11 The complex number system 240 *12 Weak methods 245 Chapter 5 Scalar Product Spaces 1 Scalar products 248 2 Orthogonal projection 252 3 Self-adjoint transformations 257 4 Orthogonal transformations 262 5 Compact transformations 264 Chapter 6 DifferentiaEquations 1 The fundamental theorem 266 2 Differentiable dependence on parameters . 274 3 The linear equation 276 4 The nth-order linear equation 281 5 Solving the inhomogeneous equation 288 6 The boundary-value problem 294 7 Fourier series . 301 Chapter 7 Multilinear Functionals 1 Bilinear functionals 305 2 Multilinear functionals 306 3 Permutations. 308 4 The sign of a permutation 309 The subspace an of alternating tensors 5 310 6 The determinant . 312 7 The exterior algebra. 316 8 Exterior powers of scalar product spaces 319 9 The star operator 320 Chapter 8 Integration 1 Introduction 321 2 Axioms 322 3 Rectangles and paved sets 324 4 The minimal theory . 327 5 The minimal theory (continued) 328 6 Contented sets 331 7 When is a set contented? 333 8 Behavior under linear distortions 335 9 Axioms for integration 336 10 Integration of contented functions 338 11 The change of variables formula 342 12 Successive integration 346 13 Absolutely integrable functions 351 14 Problem set: The Fourier transform 355 Chapter 9 DifferentiableManifolds 1 Atlases 364 2 Functions, convergence . 367 3 Differentiable manifolds 369 4 The tangent space 373 5 Flows and vector fields 376 6 Lie derivatives 383 7 Linear differential forms 390 8 Computations with coordinates 393 9 Riemann metrics . 397 Chapter 10 The Integral Calculus on Manifolds 1 Compactness . 403 2 Partitions of unity 405 3 Densities 408 4 Volume density of a Riemann metric 411 5 Pullback and Lie derivatives of densities 416 6 The divergence theorem 419 7 More complicated domains 424 Chapter 11 ExteriorCalculus 1 Exterior differential forms 429 2 Oriented manifolds and the integration of exterior differential f433s 3 The operator d 438 4 Stokes' theorem 442 5 Some illustrations of Stokes' theorem 449 6 The Lie derivative of a differential form 452 Appendix 1. "Vector analysis" . 457 Appendix II. Elementary differential geometry of surfaces [3 459 Chapter 12 PotentialTheory in lEn 1 Solid angle 474 2 Green's formulas . 476 3 The maximum principle 477 4 Green's functions 479 5 The Poisson integral formula 482 6 Consequences of the Poisson integral formula 485 7 Harnack's theorem 487 8 Subharmonic functions 489 9 Dirichlet's problem 491 10 Behavior near the boundary 495 11 Dirichlet's principle 499 12 Physical applications 501 13 Problem set: The calculus of residues 503 Chapter 13 ClassicalMechanics 1 The tangent and cotangent bundles 511 2 Equations of variation 513 3 The fundamental linear differential form T*(M) 515 4 The fundamental exterior two-form onT*(M) 517 5 Hamiltonian mechanics . 520 6 The central-force problem 521 7 The two-body problem 528 8 Lagrange's equations 530 9 Variational principles 532 10 Geodesic coordinates 537 11 Euler's equations 541 12 Rigid-body motion 544 13 Small oscillations 551 14 Small oscillations (continued) 553 15 Canonical transformations 558 Selected References . 569 Notation Index 572 Index 575 CHAPTER 0 INTRODUCTION This preliminary chapter contains a short exposition of the set theory that forms the substratum of mathematical thinking today. Itbegins with a brief discussion of logic, so that set theory can be discussed with some precision, and continues with a review of the way in which mathematical objects can be defined as sets. The chapter ends with four sections which treat specific set-theoretic topics. Itis intended that this material be used mainly for reference. Some of it will be familiar to the reader and some of it will probably be new. We suggest that he read the chapter through "lightly" at first, and then refer back to it for details as needed. 1. LOGIC: QUANTIFIERS A statement is a sentence which is true or false as it stands. Th<s2' and '4+ 3 = 5' are, respectively, true and false mathematical statemenMany sentences occurring in mathematics contain variables and are therefore not true or false as they stand, but become statements when the variables are given values. Simple examples are '< 4', '< 1/'x is an integer', '+xy2 = 10'. Such sentences will be called statementjramIfP(x) is a frame containing the one variable 'x', then P(5) is the statement obtained by replacing 'x' in P(x) by the numeral '5'. For example, if P(x) is <x 4', then P(5) is <5 4', P(0) is'0 < 4', and so on. Another way to obtain a statement from the frame P(x) is to assert that P(x) is always true. We do this by prefixing the phrase 'forx'.Thus, 'forevery x, x< 4' is a false statement, and 'for every x, 1 = (x - 1)(x+ 1)' is a true statement. This prefixing phrase is called a universal quantifiSyn onymous phrases are 'for each x' and 'for all x', and the symbol customarily used is'("Ix)which can be read in any of these ways. One frequently presents sentences containing variables as being always true without explicitly writing the universal quantifiersFor instance, the associative law for the addition of numbers is often written x+ (y+ z)= (x+ y)+ z, where it is understood that the equation is true for aly and z. Thus the 1 2 INTRODUCTION 0.1 actual statement being made is (Vx)(Vy)(Vz)[x+ (y + z)= (x + y)+ z]. Finally, we can convert the frame P(x) into a statement by asserting that it is sometimes true, which we do by writing 'there exists anx such that P(x)'. This process is calledexistential quantificationSynonymous prefixing phrases here are 'there is anxsuch that', 'for somex',and, symbolically, '(::jx)'. The statement '(Vx)(x < 4)' still contains the variable'x',of course, but 'x' is no longer freeto be given values, and is now called a bound variable. Roughly speaking, quantified variables are bound and unquantified variables are free. The notation 'P(x), is used only when 'x'is free in the sentence being discussed. Now suppose that we have a sentence P(x, y) containing two free variables. Clearly, we need two quantifiers to obtain a statement from this sentence. This brings us to a very important observation. If quantifiers of both types are used, then the order in which they are written affects the meaning of the statement; (::jy)(Vx)P(x, yand (Vx)(::jy)P(x, y) say different thiThe first says that ony can be found that works for all x: "there exists ay such that for all x ... ". The second says that for each x a y can be found that works: "for each xthere exists ay such that ... ".~ut in the second case, it may very well happen that when x is changed, the ythat can be found will also have to be changed. The existence of a singley that serves for alx is thus the stronger statement. For example, it is true that (Vx)(::jy)(< y) and false that (::jy)(Vx)(< y). The reader must be absolutely clear on this point; his whole mathematical future is at stake. The second statement says that there exists a y,call itYo,such that (Vx)(x < Yo), that is, such that every number is less than Yo. This is false; Yo + 1, in particular, is not less Yo.nThe first statement says that for eacx we can find a corresponding y. And we can: take y = x + 1. On the other hand, among a group of quantifiers of the same type the order does not affect the meaning. Thus '(Vx)(Vy)'and '(Vy)(Vx),have the same mean ing. We often abbreviate such clumps of similar quantifiers by using the quan tification symbol only once, as i'(Vx, y)'which can be read 'for everyx and y'. Thus the strictly correct'(Vx)(Vy)(Vz)[x+ (y+ z) = (x+ y) + zl'receives the slightly more idiomatic rendition '(Vx, y, z)[+ (y + z)= (x + y)+ zl'. The situation is clearly the same for a group of existential quantifiers. The beginning student generally feels that the prefixing phrases 'for evexy there exists a y such that' and 'there exists ay such that for every x' sound artificial and are unidiomatic. This is indeed the case, but this awkwardness is the price that has to be paid for the order of the quantifiers to be fixed, so that the meaning of the quantified statement is clear and unambiguous. Quantifiers do occur in ordinary idiomatic discourse, but their idiomatic occurrences often house ambiguity. The following two sentences are good examples of such ambiguous idiomatic usage: "Every x is less than somey"and "Some yis greater than every x". If a poll were taken, it would be found that most men on the 0.2 THE LOGICAL CONNECTIVES 3 street feel that these two sentences say the same thing, but half will feel that the common assertion is false and half will think it true! The trouble here is that the matrix is preceded by one quantifier and followed by another, and the poor reader doesn't know which to take as the inside, or first applied, quantifier. The two possible symbolic renditions of our first sentence'[(Vx)(x < y)](3y)' and '(Vx)[(x< y)(3y)1', are respectively false and true. Mathematicians do use hanging quantifiers in the interests of more idiomatic writing, but only if they are sure the reader will understand their order of application, either from the context or by comparison with standard usage. In general, a hanging quantifier would probably be read as the inside, or first applied, quantifier, and with this understanding our two ambiguous sentences become true and false in that order. After this apology the reader should be able to tolerate t.he definit.ion of sequential convergence. Itinvolves three quantifiers and runs as follows: The sequence {xn} converges to x if (Ve)(3N) (Vn)(if n > N then IXn- xl < e). In exactly the same format, we define a function f to be continuous at a if (Ve)(30)(Vx)(ifIx - al < 0 then If(x) - f(aI < e). We often omit an inside universal quantifierby displaying the final frame, so that the universal quanti fication is understood. Thus we define f to be continuous at a if for everye there is a0 such that if Ix - al < 0, then If(x) - f(a)I < E. We shall study these definitions later. We remark only that it is perfectly possible to build up an intuitive understanding of what these and similar quantified statements actually say. 2. TIlE LOGICAL CONNECTIVES When the word 'and' is inserted between two sentences, the resulting sentence is true if both constituent sentences are true and is false otherwise. That is, the "truth value", T or F, of the compound sentence depends only on the truth values of the constituent sentences. We can thus describe the way 'and' acts in compounding sentences in the simple "truth table" P Q P and Q T T T T F F F T F F F F where 'P' and 'Q'stand for arbitrary statement frames. Words like 'and' are called logical connectivesIt is often convenient to use symbols for connectives, and a standard symbol for 'and' is the ampersand '&'. Thus 'P & Q' is read 'P andQ'. 4 INTRODUCTION 0.2 Another logical connective is the word 'or'. Unfortunathis word is used ambiguously in ordinary discourse.Sometimes it is used in the exclusive sense, where 'P orQ' means that one ofP and Q is true, but not both, and sometimes it is used in the inclusive sense that at least one is true, and possibly both are true. Mathematics cannot tolerate any fundamental ambiguity, and in mathe matics 'or' is always used in the latter way. We thus have the truth table P Q P orQ T T T T F T F T T F F Ii' The above two connectives are binary, in the sense that they combine two sentences to form one new sentence. The word 'not' applies to one sentence and really shouldn't be considered a connective at all; nevertheless, it is called a unary connective. A standard symbol for 'not'~'s ts truth table is obviously P ~P T F F T In idiomatic usage the word 'not' is generally buried in the interior of a sentence. We write' x is not equal to y' rather than' no(x is equal to y)'. However, for the purpose of logical manipulatiothe negation sign (the word 'not' or a symbol lik'~' )recedes the sentence being negatedWe shall, of course, continue to write '~ y', but keep in mind that this is idiomatic for 'not (x= y)'or'~(x = y)'. We come now to the troublesome 'if ... ,then ... ' connective, which we writeas either 'iP, thenQ' or 'P==}Q'. This is almost always applied in the universallyquantified context (Vx) (P(x)==Q(x»), and its meaning is best unraveled by a study of this usage. We consider 'i< 3, then x < 5' to be a true sentence.More exactly, it is true for x,so that the universal quantifi cation (Vx)(x< 3==}x < 5) is a true statementThis conclusion forces us to agree that, in particular'2< 3==}2 < 5', '< 3 ==4 < 5', and '6< 3==} 6 < 5' are all true statements.The truth table for '==}thus contains the values entered below. P Q P==}Q T T T T F F T T F F T 0.2 THE LOGICAL CONNECTIVES 5 On the other hand, we consider 'x < 7 ==}x < 5' to be a false sentence, and therefore have to agree that '< 7==}6 < 5' is false. Thus the remaining row in the table above gives the value 'F' fPr==}Q. Combinations of frame variables and logical connectives such as we have been considering are calletruth-functional forms.We can further combine the elementary forms such as 'P==}Q' and '",P' by connectives to constructcom positeforms such as '",(P ==Q)' and '(P ==}Q) & (Q ==}P)'. A sentence has a given (truth-functional) form if it can be obtained from that form by substitution. Thus 'x < y or ",(x< V)'has the form 'P or ",P', since it is obtained from this form by substituting the sentence 'x< y'for the sentence variabl'P'. Com posite truth-functional forms have truth tables that can be worked out by combining the elementary tables. For example,'",(P ==Q)' has the table below, the truth value for the whole form being in the column under the connective which is applied last ('",' in this example). P Q ",(P==}Q) T T F T T F T F F T F T F F F T Thus", (P ==Q) is true only when P is true and Q is false. A truth-functional form such as 'P or (",P), which is always true (i.e., has only 'T'in the final column of its truth table) is catautologor atautologous form. The reader can check that and ((P ==Q) & (Q ==}R)) ==}(P ==}R) are also tautologous. Indeed, any valid principle of reasoning that does not involve quantifiers must be expressed by a tautologous form. The 'if and only if' for'P <=?Q',or 'P if and only iQ',or 'P ifQ', is an abbreviation for'(P ==}Q) & (Q ==}P)'. Its truth table works out to be P Q P<=?Q T T T T F F F T F F F T That is, P <=?Q is true ifP and Q have the same truth values, and is false otherwise. Two truth-functional forms A and B are said to beequivalentif (the final columns of) their truth tables are the same, and, in view of the table '<=?', we see that A and B are equivalent if A<=B is tautologous,and conversely. 6 INTRODUCTION 0.4 Replacing a sentence obtained by substitution in a form A by the equivalent sentence obtained by the same substitutions in an equivalent form B is a device much used in logical reasoning. Thus to prove a statement P true, it sufficesto prove the statement ",P false, since'P' and '",(",P),are equivalent forms. Other important equivalences are ",(P or Q) ~ (",P) & (",Q), (P =>Q) ~ Qor (",P), ",(P => Q) ~ P & (",Q). A bit of conventional sloppiness which we shall indulge in for smoother idiom is the use of 'if'instead of the correct 'if and only if' in definitions. We definefto be continuous atx ifso-and-so, meaning, ofcourse, thatfis continuous at x if and only ifso-and-so. This causes no difficulty, since it is clear that 'if and only if' is meant when a definition is being given. 3. NEGATIONS OF QUANTIFIERS The combinations '",(V'x)and '(3x)",'have the same meanings: something is not always trueif and only if itsometimes false. Similarly,'",(3y)and '(V'y)",' have the same meanings. These equivalences can be applied to move a negation sign past each quantifier in a string of quantifiers, giving the following important practical rule: In taking the negation of a statement beginning with a string of quantifiers, we simply change each quantifier to the opposite kind and move the negation sign to the end of the string. Thus ",(V'x)(3y) (V'z)P(x, y,~z) (3x)(V'y)(3z)",P(x, y, z). There are other principles of quantificational reasoning that can be isolated and which we shall occasionally mention, but none seem worth formalizing here. 4. SETS It is present-day practice to define every mathematical object as a set of some kind or other, and we must examine this fundamental notion, however briefly. A setis a collection of objects that is itself considered an entity. The objects in the collection are called thelementsor members of the set. The symbol for 'is a member of' is'E' (a sort of capital epsilon), so thatE'A' is read "x is a member of A", "x is an element ofA", "x belongs to A", or "x is inA". We use the equals sign '=' in mathematics to mean logical identity; A= B means that A is B. Now a set A is considered to be the same object as a setB if and only if A and B have exactly the same members. That is, 'A = B' means that (V'x)(x E A ~ x E B). 0.4 SETS 7 We say that a set A is asubset of a seB, or that A isincluded in B (or that B is a supersetof A) if every element of A is an element of B. The symbol for inclusion is Ie'. Thus 'A e B' means that (Yx)(x E A =} x E B). Clearly, (A = B) {=}(A e B) and (B e A). This is a frequently used way of establishing set identity: we prove that = B by proving that A e B and that B e A. If the reader thinks about the above equivalence, he will see that it depends first on the equivalence of the truth-func tional forms 'P {=}Q' and '(P=} Q) & (Q =} P)', and then on the obvious quantificational equivalence between '(Yx)(R & S)' and '(Yx)R & (Yx)S'. We define a set by specifying its members. Ifthe set is finite, the members can actually be listed, and the notation used is braces surrounding a member ship list. For example {I, 4, 7} is the set containing the three numbers 1, 4, 7, {x} is theunit set of x (the set having only the one object x as a member), and {x, y}is thepair setof x and y. We can abuse this notation to name some infinite sets. Thus {2, 4, 6, 8, ... } would certainly be considered the set of all even positive integers. But infinite sets are generally defined by statement frames. If P(x)is a frame containing the free variabl'x',then {x : P(x)}is the set of alx such that P(x) is true. In other words, {x : P(x)}is that setA such that yEA {=}P(y). For example, {x: x2 < 9} is the set of all real numbers x such that x2 < 9, that is, the open interval (-3, 3), any E {x : x < 9} {=}y2 < 9. A statement frame P(x) can be thought of as stating apropertythat an object x mayor may not have, and {x : P(x)}is the set of all objects having that property. We need the empty set 0, in much the same way that we need zero in arithmetic. If P(x) isnever true, then {x: P(x)} = 0. For example, {x:x ~ x} = 0. When we said earlier that all mathematical objects are customarily con sidered sets,it was taken for granted that the reader understands the distinction between an object and a name of that object. To be on the safe side, we add a few words. A chair is not the same thing as the word 'chair', and the number 4 is a mathematical object that is not the same thing as the numeral '4'. The numeral '4' is a name of the number 4, as also are 'four', '2 + 2', and 'IV'. According to our present viewpoint, 4 itself is taken to be some specific set. There is no need in this course to carry logical analysis this far,ome readers may be interested to know that we usually define 4 as {O,1, 2, 3}. Similarly, 2 = {O,I}, 1 = {O},and 0 is the empty set 0. It should be clear from the above discussion and our exposition thus far that we are using a symbol surrounded by single quotation marks as a name of that symbol (the symbol itself being a name of something else). Thus' '4', is a name of '4' (which is itself a name of the number 4). This is strictly correct 8 INTRODUCTION 0.5 usage, but mathematicians almost universally mishandle it. It is accurate to write: let x be the number; call this number 'x'. However, the latter is almost always written: call this number x. This imprecision causes no difficulty to the reading mathematician, and it often saves the printed page from a shower of quotation marks. There is, however, a potential victim of such ambiguous treatment of symbols. This is the person who has never realized that mathe matics is not about symbols but about objects to which the symbols refer. Since by now the present reader has safely avoided this pitfall, we can relax and occasionally omit the strictly necessary quotation marks. In order to avoid overworking the word 'set', we use many synonyms, such as 'class','collection', 'family'and 'aggregate'. Thus we might say, "Let a be a family of classesof sets".Ifa shoe store is a collection of pairs of shoes, then a chain of shoe stores is such a three-level object. 5. RESTRICTED VARIABLES A variable used in mathematics is not allowed to take all objects as values; it can only take as values the members of a certain set, called the domain of the variable. The dOInain is sometimes explicitly indicated, but is often only im plied. For example, the letter' n' is customarily used to specify an integer, so that' (Vn)P(n) ,would automatically be read "for every integer n, P(n)". How ever, sometimes n is taken to be a positive integer. In case of possible ambiguity or doubt, we would indicate the restriction explicitly and write' ("In E 71.)P(n)', where' 71.is the standard symbol for the set of all integers. The quantifier is read, literally, "for anlin71."and more freely, "for every integer n". Similarly, '(3n E 71.)P(n),is read "there exists an n in 71.uch that P(n)" or "there exists an integer n such that P(n)". Note that the symbol 'E' is here read as the preposition' in'. The above quantifiers are called restrictedquantifiers. In the same way, we have restricted set formation, both implicit and explicit, as in '{n: P(n)} , and '{nE 71:.pen)}',both of which are read "the set of all integers n such that P(n)". Restricted variables can be defined as abbreviations of unrestricted variables by ("IxE A)P(x) ¢=> ("Ix) (E A => P(x)), (3x E A)P(x) ¢=> (3x) (xE A & P(x)), {x E A :P(x)} = {x:x E A & P(x)}. Although there is never any ambiguity in sentences containing explicitly restricted variables, it sometimes helps the eye to see the structure of the sentence if the restricting phrases are written in superscript position, as in EZ (Ve>o)(3n ). Some restriction was implicit on page 1. Ifthe reader agreed that (Vx)(x 2 - 1 = (x - 1)(x+ 1)) was true, he probably took x to be a real number. 0.6 ORDERED PAIRS AND RELATIONS 9 6. ORDERED PAIRS AND RELATIONS Ordered pairs are basic tools, as the reader knows from analytic geometry. According to our general principle, the ordered pair -a, b> is taken to be a certain set,but here again we don't care which particular set it is so long as it guarantees the crucial characterizing property: -<x,y> = -<a,b> R x = aandy = b. Thus -<1, 3> ~ -<3,1>. The notion of a correspondence, or relation, and the special case of a map ping, or function, is fundamental to mathematics. A correspondence is a pairing of objects such that given any two objectxand y,the pair -x, y> either does or does not correspond. A particular correspondence (relation) is generally presented by a statement frame P(x, y)having two free variables, witx and y corresponding if any only P(x, y)is true. Given any relation (correspondence), the set of all ordered pai-<x, y> of corresponding elements is called graph. Now a relation is a mathematical object, and, as we have said several times, it is current practice to regard every mathematical object as a set of some sort or other. Since the graph of a relation is a set (ofordered pairs), it is efficientand customary to take the graph to bethe relation.Thus a relation (correspondence) is simply a set of ordered pairs. Ifis a relation, then we say thatxhas the relationR to y,and we write 'xRy', if and only if-<x, y> E R. We also say that x corresponds toy under R. The set of allfirselements occurring in the ordered pairs of a relatioR is called thdomain of R and is designated dom R or ~(R). Thus dom R = {x: (~y)- <>x,E R}. The set of second elements is called tmnge ofR: rangeR = {y:(~x)-<x ,R}.> The inverse, R-l,of a relatioR is the set of ordered pairs obtained by reversing those ofR: 1 R- = {-<x, y> : -<y, x> E R}. A statement frame P(x, y)having two free variables actually determinespair of mutually inverse relationR & S, called thegmphs ofP, as follows: R = {-<x, y> : P(x, y)}, S = {-<y, x> : P(x, y)}. A two-variable frame together with a choice of which variable is considered to be first might be called directedframe. Then a directed frame would have a uniquely determined relation for its graph. The relation of strict inequality on the real number system IRwould be considered the set {-<x, y> : x < y}, since the variables in <x y'have a natural order. The set A X B = {-<x, y> : x E A & y E B} of all ordered pairs with first element iA and second element in B is called thCartesian productof the 10 INTRODUCTION 0.7 sets A and B. A relation R is always a subset of dom R X range R. If the two "factor spaces" are the same, we can use exponential notation: 2 = A X A. The Cartesian product R2 = R X R is the "analytic plane". Analytic geometry rests upon the one-to-one coordinate correspondence between R2and the Euclidean plane [2 (determined by an axis system in the latter), which enables us to treat geometric questions algebraically and algebraic questions geometrically. In particular, since a relation between sets of real numbers is a subset of R2,we can "picture" it by the corresponding subset of the Euclidean plane, or of any model of the Euclidean plane, such as this page. A simple Cartesian product is shown in Fig. 0.1 (A UB is thunion of the sets A and B). B I R[AI I I R B I .... 1 I ----------,--I , 1 A A A AXB when A=[l, 2Iu[2t, 31 and B=[1, Itlu{2} Fig. 0.1 Fig. 0.2 If R is a relation and A is any set, then threstrictioof R to A, R r A, is the subset ofR consisting of those pairs with first elementA:n R tA = {-<x, y> : -<x, y>E R and x E A}. Thus R rA = R n (A X range R), where C n D is the intersectioof the sets CandD. If R is a relation and A is any set, then thimageoj A under R, R[A), is the set of second elements of ordered pairs iR whose first elements are inA: R[A} = {y: (3x)(x E A & -<x. y> E R)}. Thus R[A] = range (R rA), as shown in Fig. 0.2. 7. FUNCTIONS AND MAPPINGS A Junction is a relatiJnsuch that each domain element x is paired with exactly one range element y. This property can be expressed as follows: -<x, y> EJ and -<x, Z> EJ =} y = z. 0.7 FUNCTIONS AND MAPPINGS 11 The y which is thus uniquely determined by f and x is designated f(x): y = f(x) ~ <x, y> Ef. One tends to think of a function as being active and a relation which is not a function as being passive. A function f actson an element x in its domain to givef(x). We take x and applyfto it; indeed weoften calla function an operator. On the other hand, if R is a relation but not a function, then there is in general no particular y related to an element x in its domain, and the pairing of x and y is viewed more passively. We often define a function f by specifying its value f(x) for each x in its domain, and in this connection a stopped arrow notation is used to indicate the 2 2 pairing. Thus x 1-+x is the function assigning to each number x its square x • Fig. 0.3 If we want it to be understood that f is this function, we can write "Consider the function f: x 1-+X2l• The domain of f must be understood for this notation to be meaningful. 1 If f is a function, thenr is of course a relation, but in general it is not a function. For example, if fis the function x 1-+ X2,then r 1 contains the pairs <4,2> and <4,-2> and so is not a function (see Fig. 0.3). Ifr 1 isa func tion, we say thatf is one-to-oneand that fis a one-to-one correspondence between its domain and its range. Each x E domf corresponds to only one y E rangef 1 (f is a function), and each yE range f corresponds to only one x E dom f (r is a function). The notation· f:A -tB is read "a (the) function f on A into B" or "the function f from A to B". The notation implies that f is a function, that domf = A, and that range feB. Many people feel that the very notion of function should include all these ingredients; that is,a function should be consideredan ordered triple < f, A, B> , where fis a function according to our more limited definition, A is the domain 12 INTRODUCTION 0.8 of f, and B is a superset of the range of f, which we shall call the codomainof f in this context. We shall use the terms 'map', 'mapping', and 'transformation' for such a triple, sohat the notationf: A --+B in its totality presents a mapping. Moreover, when there is no question about which set is the codomain, we shall often call the function f itself a mapping, since the triple -<f,A,B>- is then determined by f. The two arrow notations can be combined, as in: "Define f:!Fl--+!Flby x1-+ x2". A mapping f: A --+B is said to be injective if f is one-to-one, surjectiveif range f= B, and bijectiveif it is both injective and surjective. A bijective mapping f:A --+B is thus a one-to-one correspondence between its domain A and its codomain B. Of course, a function is always surjective onto its range R, and the statement that f is surjective means that R = B, where B is the under stood codomain. 8. PRODUCT SETS; INDEX NOTATION One of the characteristic habits of the modern mathematician is that as soon as a new kind of object has been defined and discussed a little, he immediately looks at the set of all such objects. With the notion of a function from A to S well in hand, we naturally consider the set of all functions from A to S, which we R designate SA. Thus!Fl is the set of all real-valued functions of one real variable, and sz+ is the set of all infinite sequences in(It is understood that an infinite sequence is nothing but a function whose domain is the set Z+ of all positive integers.) Similarly, if we set n = {I, ... , n}, thenSriis the set of all finite sequences of length n in S. If B isa subset of S, then itRcharacteristicfunction (relative to S) is the func tion on S, usually designated XB, which has the constant value I on B and the constant value 0 off B. The set of all characteristic functions of subsets of S is thus 2 8 (since 2 = {O,I}). But because this collection of functions is in a natural one-to-one correspondence with the collection of all subsets of S, XB 8 corresponding to B, we tend to identify the two collections. Thus 2 is also interpreted as the set of all subsets of S. We shall spend most of the remainder of this section discussing further similar definitional ambiguities which mathe maticians tolerate. The ordered triple -x,y,z>- is usually defined to be the ordered pair -<-<x,y>- ,z>-. The reason for this definition is probably that a function of two variables x and y is ordinarily considered a function of the single ordered pair variable -<x, y>-, so that, for example, a real-valued function of two real variables is a subset of (!FlX !Fl)X !Fl. But we also consider such a function a subset of Cartesian 3-space !Fl• Therefore, we define !Fl as (!FlX !Fl)X !Fl; that is, we define the ordered triple-<x, y,z>- as -<-<x,y>-.z>-. On the other hand, the ordered triple -<x, y,z>- could also be regarded as the finite sequence {-<I, x>-,-< 2,y>-,-< 3, z>}-, which, of course, is a different object. These two models for an ordered triple serve equally well, and, again, 0.8 PRODUCT SETS; INDEX NOTATION 13 mathematicians tend to slur over the distinction. We shall have more to say on this point later when we discuss natural isomorphisms (Section 1.6). For the moment we shall simply regard IRaand 1R"a 3s" being the same; an ordered triple is something which can be "viewed" as being either an ordered pair of which the first element is an ordered pair or as a sequence of length 3 (or, for that matter, as an ordered pair of which the second element is an ordered pair). 4 Similarly, we pretend that Cartesian 4-space 1R4is 1R 1R2X 1R2,or IRIX IRa = IRX ((IR X IR)X IR), etc. Clearly, we are in effect assuming an associative law for ordered pair formation that we don't really have. This kind of ambiguity, where we tend to identify two objects that really are distinct, is a necessary corollary of deciding exactly what things are. It is one of the prices we pay for the precision of set theory; in days when mathematics was vaguer, there would have been a single fuzzy notion. The device of indices, which is used frequently in mathematics, also has am biguous implications which we should examine. An indexed collection, as a set, is nothing but the range set of a function, the indexing function, and a particular indexed object, say Xi,issimply the value of that function at the domain element i. If the set of indices is I, the indexed set is designated {Xi: i E l} or {Xi};EI (or {Xi};:'lin case I = Z+). However, this notation suggests that we view the indexed set as being obtained by letting the index run through the index set I and collecting the indexed objects. That is, an indexed set is viewed as being the set togetherwith the indexing function. This ambivalence is reflected in the fact that the same notation frequently designates the mapping. Thus we refer to the sequence {Xn}:=l, where, of course, the sequence is the mapping n ~ X . n We believe that if the reader examines his idea of a sequence he will find this ambiguity present. He means neither just the set nor just the mapping, but the mapping with emphasis on its range, or the range "together with" the mapping. But since set theory cannot reflect these nuances in any simple and graceful way, we shall take an indexed set to be the indexing function. Of course, the same range object may be repeated with different indices; there is no implication that an indexing is one-to-one. Note also that indexing imposes no restriction on the set being indexed; any set can at least be self-indexed (by the identity function). Except for the ambiguous' {Xi: iE I}', there is no universally used notation for the indexing function. Since Xi is the value of the function at i,we might think of 'x;' as another way of writing 'xCi)',in which case we designate the function 'x' or 'x'. We certainly do this in the case of ordered n-tuplets when we say, "Consider the n-tuplet x = -<XI, •.• ,x n»". On the other hand, there is no compelling reason to use this notation. We can call the indexing function anything we want; if it is j, then of course j( i) = Xi for alli. We come now to the general definition of Cartesian product. Earlier we argued (in a special case) that the Cartesian product A X B X C is the set of all ordered triples x = -<XI,X2, xa» such that Xl E A, X2 E B, and Xa E C. More generally, A I X A 2 X ... X An, or IIi=1 Ai, is the set of ordered n tuples x = -<XI, ... , xn» such that Xi E Ai for i = 1, ... ,n. Ifwe interpret 14 INTRODUCTION 0.9 an ordered n-tuplet as a function on n = {I, ... , n}, we have IIi=l Ai is the set of all functions x with domain n such that Xi.E Ai for alli En. This rephrasal generalizes almost verbatim to give us the notion of the Cartesian product of an arbitrary indexed collection of sets. Definition. The Cartesian product IIiE1Si of the indexed collection of sets {Si: i E I} is the set of all functions fwith domain the index set I such that f(i)E Si for ali E I. We can also use the notation II {Si : E I} for the product and fifor the value f(i). 9. COMPOSITION If we are given maps f:A ~ Band g: B ~ C, then the composition of g with f, g 0f, is the map of A into C defined by (gof)(x) = g(j(x)) for all X E A. This is the function of a function operation of elementary calculusIff and g are the maps from IRto IRdefined by f(x) = Xl/3+ 1 and g(x) = x 2,then f 0g(x) = 2 23 1 3 2 3 (X )1/3+ 1 = X / + 1,and g 0 f(x) = (X / + 1)2 = X / + 2Xl/3 + 1. Note that the codomain of f must be the domain of g in order for go f to be defined. This operation is perhaps the basic binary operation of mathematics. Lemma. Composition satisfies the associative law: f 0 (g0 h) = (f0 g) 0h. P1"OOf.(jo (g 0 h)) (x) = f((g0 h)(x)) = f(g(h(x))) = (fo g)(h(x)) = ((f 0 g)0 h) (x) for all E dom h. 0 If A is a set, the identity map I A: A ~ A is the mapping taking every x E A to itself. Thus I = {-<x, x>- : xE A}. Iff maps A into B, then clearly foIA=f=IBof. If g:B ~ A is such that g0 f= lA, then we say that g is a left inverse of f and that f is a right inverse of g. Lemma. If the mapping f:A ~ B has both a right inverse h and a left inverse g,they must necessarily be equal. Proof. This is just algebraic juggling and works for any associative operation. We have h = IA 0 h = (g 0f) 0h = go (f 0h) = go IB = g. 0 0.10 DUALITY 15 In this case we call the uniquely determined map y:B ---A such that fog = IB and g 0 f= IA the inverseof f. We then have: Theorem. A mapping f: A ---B has an inverse if and only if it is bijective, in which case its inverse is its relational inverf-l. 1 Proof. If fis bijective, then the relational inverser is a function fromB to A, and the equations fori = I Band r 1 0f = I A are obvious. On the other hand, if fog = IB, then f is surjective, since then everyy in B can be written y = f(g(y»). And if g 0f = IA, then f is injective, for then the equation f(x) = f(y) implies that x = y(j(x») = y(j(y») = y. Thus f is bijective if it has an inverse. D Now let ~(A) be the set of all bijectionf: A ---tA. Then ~(A) is closed under the binary operation of composition and 1) f 0(y 0 h) = (f0 y) 0h for allf,g,h E~; 2) there exists a unique I E ~(A) such that f 0I = I 0 f = ffor allfE ~; 3) for each f E ~ there exists a unique yE ~ such that fog = g 0f = I. Any set G closed under a binary operation having these properties is called a group with respect to that operation. Thus ~(A) is a group with respect to composition. Composition can also be defined for relations as follows. If RCA X Band S C B X C, then S 0 RCA X C is defined by -<x,z>- ESoR <=>(3y EB)(-<x,y>- ER& -<y,z>- ES). If Rand S are mappings, this definition agrees with our earlier one. 10. DUALITY There is another elementary but important phenomenon called duality which occurs in practically all branches of mathematics. Let F: A X B ---C be any function of two variables. It is obvious that if x is held fixed, thenF(x, y)is a function of the one variable y. That is, for each fixed x there is a function h : ---C defined by hX(y) = F(x, y). Then x 1-+h is a mapping cpof A into CB. Similarly, each y E B yields a function gy E CA ,where gy(x) = F(x, y), and y1-+ yyis a mapping (Jfrom B to CA. Now suppose conversely that we are given a mapping cpA ---CB. For each x E A we designate the corresponding value of cp in index notation as hX, so that h is a function from B to C, and we define F: A X B ---C by F(x, y) = hX(y). We are now back where we started. Thus the mappings cp:A ---C , A /1':A X B ---C, and (J:B ---C are equivalent, and can be thought of as three different ways of viewing the same phenomenon. The extreme mappings cpand (Jwill be said to bedual to each other. 16 INTRODUCTION 0.10 The mapping I(is the indexed family of functions {hx:x E A} C CB. Now suppose that 5'C C B is an unindexed collection of functions on B into C, and define F: 5'X B -+ C by F(f, y) = f(y). Then 8: B -+ (J'is defined bygll(f)= f(y). What is happening here is simply that in the expressionf(y) we regard both symbols as variables, so that f(y) is a function o5' X B. Then when we hold y fixed, we have a function on 5'mapping 5'into C. Wc shall see some important applications of this duality principle as our subject develops. For example, an m X n matrix is a function t = {tij} in RmXn. We picture the matrix as a rectangular array of numbers, where Ii'is the row index and Ij'is the column index, so that tij is the number at the inter section of the ith row and the jth column. Ifwe hold ifixed, we get the n-tuple forming the ith row, and the matrix can therefore be interpreted as an m-tuple of row n-tuples. Similarly (dually), it can be viewed as an n-tuple of column m-tuples. In the same vein, an n-tuple -<!I,... ,fn> of functions from A to B can be regarded as a single n-tuple-valued function from A to Bn, In a somewhat different application, duality will allow us to regard a finite dimensional vector space V as being its own second conjugate space (V*)*. It is instructive to look at elementary Euclidean geometry from this point of view. Today we regard a straight line as being a set of geometric points. An older and more neutral view is to take points and lines as being two different kinds of primitive objects. Accordingly, letA be the set of all points (so thaA is the Euclidean plane as we now view it), and leB be the set of all straight lines. Let F be the incidence function:F(p, l) = 1 ifp and I are incident(p is "on" l, I is "on"p) and F(p, l)= 0 otherwise. Thus F maps A X B into {O,1}. Then for each IE B the function gl(P) = F(p, I)is the characteristic function of the set of points that we think of as being the linl(gl(P) has the value 1 if p is ol and 0 if pis not on l.)Thus each line determines the set of points that are on it. But, dually, each point p determines the set of lines I"on" it,through itschar acteristic functionhP(I).Thus, in complete duality we can regard a line as being a set of points and a point as being a set of lines. This duality aspect of geometry is basic in projective geometry. It is sometimes awkward to invent new notation for the "partial" function obtained by holding a variable fixed in a function of several variables, as we did above when we setgil(x)= F(x, y),and there is another device that is frequently useful in this situation. This is to put a dot in the position of the "varying variable". Thus F(a,') is the function of one variable obtained from F(x, y) by holding x fixed at the value a, so that in our beginning discussion of duality we have X h = F(x, .), gil= F(·, y). Iff is a function of one variable, we can then write f= f('), and so express the 0.11 THE BOOLEAN OPERATIONS 17 above equations also as h"'=-)F(x, .)gy(-= F( . , yThe flaw in this notation is that we can't indicate substitution without losing meaning. Thus the value of the functionF(x,·) at bis F(x, b)but from this evaluation we cannot read backward and tell what function was evaluated. Weare therefore forced to some such cumbersome notation as F(x,·)/bwhich can get out of hand. Never theless, the dot device is often helpful when can be used without evaluation difficulties.In addition to eliminating the n

### 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!"

#### "Selling my MCAT study guides and notes has been a great source of side revenue while I'm in school. Some months I'm making over $500! Plus, it makes me happy knowing that I'm helping future med students with their MCAT."

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

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### 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.