Linear Algebra/Sets, Functions, Relations

__NOTOC__ Linear Algebra Sets, Functions, Relations Techniques of Proof Licensing And History Sets Mathematicians work with collections called sets. A set can be given as a listing between curly braces as in , or, if that's unwieldy, by using set-builder notation as in (read "the set of all such that \ldots"). We name sets with capital roman letters as with the primes , except for a few special sets such as the real numbers , and the complex numbers . elementTo denote that something is an element (or member) of a set we use "", so that while . What distinguishes a set from any other type of collection is the Principle of Extensionality, that two sets with the same elements are equal. Because of this principle, in a set repeats collapse and order doesn't matter . subsetWe use "" for the subset relationship: and "" for subset or equality (if is a subset of but then is a proper subset of ). These symbols may be flipped, for instance . Because of Extensionality, to prove that two sets are equal , just show that they have the same members. mutual inclusionUsually we show mutual inclusion, that both and . Set operations Venn diagrams are handy here. For instance, can be pictured x200px and "" looks like this. x200px Note that this is a repeat of the diagram for "if \ldots then ..." propositions. That's because "" means "if then ". In general, for every propositional logic operator there is an associated set operator. complementFor instance, the complement of is x200px the union is x200px and the intersection is x200px emptyWhen two sets share no members their intersection is the empty set , symbolized . Any set has the empty set for a subset, by the "vacuously true" property of the definition of implication. Sequences We shall also use collections where order does matter and where repeats do not collapse. These are sequences, denoted with angle brackets: . ordered pairA sequence of length is sometimes called an ordered pair and written with parentheses: . We also sometimes say "ordered triple", "ordered -tuple", etc. The set of ordered -tuples of elements of a set is denoted . Thus the set of pairs of reals is . Functions We first see functions in elementary Algebra, where they are presented as formulas (e.g., ), but progressing to more advanced Mathematics reveals more general functions— trigonometric ones, exponential and logarithmic ones, and even constructs like absolute value that involve piecing together parts— and we see that functions aren't formulas, instead the key idea is that a function associates with its input a single output . functionConsequently, a function or map is defined to be a set of ordered pairs such that suffices to determine , that is: if then (this requirement is referred to by saying a function is well-defined).\footnote{More on this is in the section on isomorphisms} argumentEach input is one of the function's arguments and each output is a value. domainThe set of all arguments is 's domain and the set of output values is its range. codomainUsually we don't need know what is and is not in the range and we instead work with a superset of the range, the codomain. The notation for a function with domain and codomain is . x200px imageWe sometimes instead use the notation , read " maps under to ", or " is the "image of '. Some maps, like , can be thought of as combinations of simple maps, here, applied to the image of . compositionThecomposition of with , is the map sending to . It is denoted . This definition only makes sense if the range of is a subset of the domain of . identityObserve that the identity map defined by has the property that for any , the composition is equal to . So an identity map plays the same role with respect to function composition that the number plays in real number addition, or that the number plays in multiplication. left inverseIn line with that analogy, define aleft inverse of a map to be a function such that is the identity map on . right inverseOf course, a right inverse of is a such that is the identity. inverseA map that is both a left and right inverse of is called simply an inverse. An inverse, if one exists, is unique because if both and are inverses of then (the middle equality comes from the associativity of function composition), so we often call it "the" inverse, written . For instance, the inverse of the function given by is the function given by . The superscript "" notation for function inverse can be confusing— it doesn't mean . It is used because it fits into a larger scheme. Functions that have the same codomain as domain can be iterated, so that where , we can consider the composition of with itself: , and , etc. Naturally enough, we write as and as , etc. Note that the familiar exponent rules for real numbers obviously hold: and . The relationship with the prior paragraph is that, where is invertible, writing for the inverse and for the inverse of , etc., gives that these familiar exponent rules continue to hold, once is defined to be the identity map. ontoIf the codomain equals the range of then we say that the function is onto (or surjective). A function has a right inverse if and only if it is onto (this is not hard to check). injectiveIf no two arguments share an image, if implies that , then the function isone-to-one (or injective). A function has a left inverse if and only if it is one-to-one (this is also not hard to check). bijectionBy the prior paragraph, a map has an inverse if and only if it is both onto and one-to-one; such a function is acorrespondence. It associates one and only one element of the domain with each element of the range (for example, finite sets must have the same number of elements to be matched up in this way). Because a composition of one-to-one maps is one-to-one, and a composition of onto maps is onto, a composition of correspondences is a correspondence. We sometimes want to shrink the domain of a function. For instance, we may take the function given by and, in order to have an inverse, limit input arguments to nonnegative reals . restrictionTechnically, is a different function than ; we call it the restriction of to the smaller domain. A final point on functions: neither nor need be a number. As an example, we can think of as a function that takes the ordered pair as its argument. Relations Some familiar operations are obviously functions: addition maps to . But what of "" or ""? We here take the approach of rephrasing "" to " is in the relation ". binaryThat is, define a binary relation on a set to be a set of ordered pairs of elements of . For example, the relation is the set ; some elements of that set are , , and . Another binary relation on the natural numbers is equality; this relation is formally written as the set . Still another example is "closer than ", the set . Some members of that relation are , , and . Neither nor is a member. Those examples illustrate the generality of the definition. All kinds of relationships (e.g., "both numbers even" or "first number is the second with the digits reversed") are covered under the definition. Equivalence Relations We shall need to say, formally, that two objects are alike in some way. While these alike things aren't identical, they are related (e.g., two integers that "give the same remainder when divided by "). A binary relation is an equivalence relationwhen it satisfies <li> reflexivityreflexivity: any object is related to itself; <li> symmetrysymmetry: if is related to then is related to ; <li> transitivitytransitivity: if is related to and is related to then is related to . (To see that these conditions formalize being the same, read them again, replacing "is related to" with "is like".) Some examples (on the integers): "" is an equivalence relation, "" does not satisfy symmetry, "same sign" is a equivalence, while "nearer than " fails transitivity. Partitions In "same sign" there are two kinds of pairs, the first with both numbers positive and the second with both negative. So integers fall into exactly one of two classes, positive or negative. A partition of a set is a collection of subsets such that every element of is in one and only one : , and if is not equal to then . Picture being decomposed into distinct parts. x200px Thus, the first paragraph says "same sign" partitions the integers into the positives and the negatives. Similarly, the equivalence relation "=" partitions the integers into one-element sets. Another example is the fractions. Of course, and are equivalent fractions. That is, for the set , we define two elements and to be equivalent if . We can check that this is an equivalence relation, that is, that it satisfies the above three conditions. With that, is divided up into parts. x200px Before we show that equivalence relations always give rise to partitions, we first illustrate the argument. Consider the relationship between two integers of "same parity", the set (i.e., "give the same remainder when divided by "). We want to say that the natural numbers split into two pieces, the evens and the odds, and inside a piece each member has the same parity as each other. So for each we define the set of numbers associated with it: . Some examples are , and , and . These are the parts, e.g., is the odds. equiv partitionsTheorem An equivalence relation induces a partition on the underlying set. Proof Call the set and the relation . In line with the illustration in the paragraph above, for each define . Observe that, as is a member if , the union of all these sets is . So we will be done if we show that distinct parts are disjoint: if then . We will verify this through the contrapositive, that is, we wlll assume that in order to deduce that . Let be an element of the intersection. Then by definition of and , the two and are members of , and by symmetry of this relation and are also members of . To show that we will show each is a subset of the other. Assume that so that . Use transitivity along with to conclude that is also an element of . But so another use of transitivity gives that . Thus . Therefore implies , and so . The same argument in the other direction gives the other inclusion, and so the two sets are equal, completing the contrapositive argument. equiv classesWe call each part of a partition an equivalence class(or informally, "part"). representitiveWe somtimes pick a single element of each equivalence class to be theclass representative. x200px Usually when we pick representatives we have some natural scheme in mind. naturalIn that case we call them the canonical' representatives. An example is the simplest form of a fraction. We've defined and to be equivalent fractions. In everyday work we often use the "simplest form" or "reduced form" fraction as the class representatives. x200px Linear Algebra Sets, Functions, Relations Techniques of Proof Licensing And History