# Sets and mappings

We begin our discussion with the concept of a set, the notion of which we will assume is intuitively clear; although this is in actuality far from so and an unrestricted use of the set concept has led to contradictions in mathematics. It was for this reason that an axiomatic treatment became necessary.

In this discussion, we will usually designate sets by capital Roman letters such as , , , etc, and elements of sets by small Roman letters. We will also indicate that an element belongs to a set by writing , while if this is not the case, we write , read  does not belong to the set .''

If we have a collection of sets indexed by elements belonging to a set , then this collection will be denoted by . For example, if , the set of positive integers or natural numbers, we could write , meaning that we have a countable number of sets which are being considered. (Note, in general, it is not necessary that be even countable. The set of all real numbers denoted by is an example of an uncountable set as compared to , which is a countable set.)

Let be a collection of sets. The union of these sets, denoted by , is the set of all elements which belong to at least one of the . In case the index set is equal to or is finite, say is equal to , we use the following notations: , , respectively or

Again let be a collection of sets. The intersection of the sets, denoted by , is the set of all elements which belong to all the . Similar notations as for unions are adopted in the case of intersections when the index set is countable or finite.

Next let and be two sets. If every element of is also an element of , one says that is a subset of , denoted (or ). If and , then the sets and are said to be equal, denoted . Finally, if but , then is called a proper subset of , denoted .

If and are two sets, the cartesian product, , is the set of all ordered pairs such that and . Here it is to be emphasized that if and only if and . Similarly we can define the cartesian product of any finite number of sets. For example, ( times), consists of ordered -tuples where each , for .

The set consisting of no elements at all is called the null set or empty set and is designated by . If and are two sets such that , then and are called disjoint sets.

We next introduce a particularly useful notation which will be used throughout: If is a set, we denote by

the set of all elements belonging to for which the proposition is true. For example, the set of even positive integers equals . In the way of notation and abbreviation, we shall also, sometimes, adopt the following convention: If is a finite set consisting of the elements , one writes . In particular if consists of just a single element , we write . A similar notation is frequently adopted in the case where consists of a denumerable or countable number of elements. Finally, we define the order of a finite set , written , to be the number of elements in the set . If is not finite we write, .

We now turn to the next item of business involving sets, namely the notion of a mapping between two sets. Let and be two sets. If for every there is associated a unique , we say that there is a mapping or function from into and we write . Here is called the domain of , is the co-domain of , and if , then is the image of under . We denote this by

Let be a mapping from into . If distinct elements of have distinct images in under , i.e., if and implies , then is called a one-to-one (1-1) (or injective) mapping. Put another way, f is 1-1 if and only if implies . If for every , there is an element such that , then the mapping is said to be onto .

Again, let , and suppose that is a subset of , . The image set is defined by

If then the pre-image is defined by

Notice that an image set can be empty only if is empty, but that a pre-image set can be empty even if is nonempty.

Suppose now that is a 1-1 mapping of onto . Then for each , there exists a unique such that . This allows us to define a mapping called the inverse mapping of , which we denote by , where

is defined by provided is the unique element of such that . It is easy to show that is also one-to-one and onto. This usage of the notation should not be confused with its usage for the pre-image of a set, which is defined even if is NOT one-to-one and onto.

For any set , we define the identity map on , denoted by or simply if the set involved is clear, as that mapping which leaves every element of fixed, i.e., for all .

Next let , and let . The restriction of to is the mapping denoted by , and defined by for all . (Here it is assumed that is non-empty.)

Now let , , and be sets and suppose that is a mapping from into and is a mapping from into . Thus we have

Then the composite map (or product map or composition) is defined as

for all ; thus . Since is uniquely determined by , is indeed a mapping. In the special case of , we speak of powers of : , , etc., and mean , , etc., for all .

Using the notations introduced above and assuming is a 1-1, onto mapping from to , it is easy to see that and .

Let be a set and furthermore let denote a relation defined between ordered pairs of elements of such that given any two elements either (read  is equivalent to b'') is true or it is false. In other words, using the previously introduced terminology and notation, we assume we are given a mapping:

i.e., a mapping of the cartesian product of S with itself into a two-element set consisting of (true'') and (false''). If is mapped into , we write and say that  is equivalent to ''. If is mapped into , we say that  is not equivalent to ''. The relation, , is called an equivalence relation on if it satisfies the following three conditions:
1. (Reflexivity) for all .
2. (Symmetry) If , then .
3. (Transitivity) If , and , then .

The following are examples of equivalence relations:

Example 1.1.1   Take to be the set of all triangles in the plane and take to be the relation of congruence, , or equally well, take to be the relation of similarity.

Example 1.1.2   Take to be the set of all lines in the plane and to be the relation of being parallel. (By convention, a line is parallel to itself.)

Example 1.1.3   Take , the set of all integers, and let be a fixed positive integer. Define if and only if divides . This special equivalence relation is denoted by (mod ), read is congruent to modulo (or just mod) . It will be treated in more detail in the next section.

Now suppose that we have a set and an equivalence relation defined on . We denote by , the set of all elements of S which are equivalent to , i.e.,

Such a set is called an equivalence class. Clearly by the first condition for an equivalence relation, hence , for all . We claim, next, that for either or and are disjoint sets, i.e., . To this end, suppose that . Then there is a such that and . Let be any element in . Then and . Hence . Since also , it follows that , which implies . Thus . Similarly, . We have, therefore shown that either and are disjoint or are equal.

Summarizing, we have the following result.

Theorem 1.1.4   If is a set with an equivalence relation defined on it, then is decomposed into disjoint, nonempty equivalence classes. (We say is partitioned.) This is denoted by , where it is understood that the union is taken over only certain so that the classes are disjoint.

Next, we want to consider one further equivalence relation of great importance. It will occur in more specialized settings latter, and we consider the general case now. For this purpose let and be sets, and let . For define if and only if . It is readily seen that this is an equivalence relation on . Let denote the set of all equivalence classes and consider the following mappings:

where , , and . Clearly is an onto mapping. We claim that is, first of all, well-defined: implies . Indeed, if , then or , because , so ; hence , proving the claim. Moreover, is 1-1. Namely if , then , so and, therefore, . Also is onto; for if , then for some , so . Finally, is clearly a 1-1 mapping, and it is also clear that .

Thus it is seen that an arbitrary mapping of one set into another can be written (factored) as a product of three mappings each of which has certain nice features which in general need not possess.

Subsections

David Joyner 2007-08-06