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

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

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

If then the

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

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

- (Reflexivity) for all .
- (Symmetry) If , then .
- (Transitivity) If , and , then .

The following are examples of equivalence relations:

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

Summarizing, we have the following result.

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

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.

David Joyner 2007-08-06