Here we introduce mappings, look at their properties and introduce operations. At the end of this section we look at comparing sizes of sets.

Definition.

Consider setsAandB. By atransformationor amappingfromAtoBwe mean any subsetTof the Cartesian productthat satisfies the following condition: A×BFor every

afromAthere is a uniquebfromBsuch that( a,b)∈T.We write

T:A↦B.

**Example:** Consider sets *A* = {a,b,c}*B* = {1,2}.

*T* = {(*a*,1),(*b*,1),(*c*,2)}

is a mapping from *A* to *B*.

We view such a mapping as a black box that sends elements from one set to
another set, for instance the element *a* is sent to 1. The condition
from the definition essentially means that one element from *A* cannot
be sent to two (or more) different places in *B*. On the other hand,
there is no problem in sending two elements to
the same place, as you can see in the example. Note that it is not necessary
to use up all elements from the target set *B* in the mapping.

This idea of sending is also reflected in a special notation we use for
mappings. Instead of saying that, say, *a*,1)*T*, we would write
*T* (*a*) = 1.**image** of *a* under *T* or that 1 is the **value** of
*T* at *a*. Sometimes we also use the notation

*T* : *a* ↦ *T*(*a*).

The starting set *A* is called the **domain** of *T*, denoted
*D*(*T* ).*D*_{T} or *T* ).*B* is less important as such than the domain, in particular
because it may contain extra points not involved in the given mapping. Of
interest is the **range** of *T*, which is the set of all elements
of *B* that are images of some elements of *A* under *T*. We
denote it *R*(*T* ),*R*_{T} or *T* ).*D*(*T* ) = *A**R*(*T* ) = *B*,

Once we can send elements, we can also send sets. If *D* is a subset of
*A*, the the image of *D* under *T* is the set

*T* [*D*] = {*T*(*d*); *d*∈*D*}.

For instance,
*R*(*T* ) = *T* [*A*].

**Remark.**
Some authors also use the name *function* as an equivalent for a
mapping. However, other authors reserve this name only for mappings that work
with numbers, whereas the names *mapping* and *transformation*
suggest a more general framework. This is the approach we adopt here, but
since it is not a universally accepted convention, we will not make a big
deal out of it.

There are two popular ways to draw mappings. One is the **graph** of
*T*, when we somehow mark which elements of the Cartesian product
*A*×*B**T*.
For instance, for the above example we could draw this:

In practice we usually do not bother drawing the unused elements of the product and use this picture instead.

Drawing such a graph is probably the most popular visualization, but sometimes a different kind of a picture is more telling and therefore more useful.

For ordered sets (especially sets of numbers) we often prefer this picture.

Before we move on we introduce one mapping that is always defined when we have a set.

Definition.

Consider a setA. We define theidentity mappingonA, denotedas a mapping from Id_{A},AtoAdefined byfor every Id_{A}(a) =aafromA.

There are two important properties of mappings.

Definition.

Consider a mappingTfromAtoB.

We say thatTisone-to-one(1-1), orinjective, or that it is aninjection, if for every two non-equal elementsa_{1},a_{2}fromAalso their imagesT(a_{1}),are not equal. T(a_{2})We say that

Tisonto, orsurjective, or that it is ansurjection, ifWe say that R(T) =B.Tis a mapping "fromAontoB".

The condition for injectivity says that two distinct elements cannot be sent to the same place. We have an advantage here that we do not pretend to be formally perfect, so we could say it this way. However, if we wanted to write it precisely and correctly using logical language, the definition would be more complicated than an alternative definition that goes like this. A mapping is 1-1 if the following condition is true: If two element are sent to the same place, then they must have been the same in the first place.

*T*(*a*_{1}) = *T*(*a*_{2}) ↦ *a*_{1} = *a*_{2}.

To a mathematician this statement is way neater, so it is used very often. It is also more convenient for practical work, since working with the relation "not equal" can get tricky, while we know how to deal with equalities.

**Examples:** In the following picture, the two examples of mappings in
the first row are 1-1, while the three examples in the next two rows are not.

Now concerning surjectivity, the two examples of mappings in the first row are onto, while the three examples in the next two rows are not.

Note that sometimes these properties are determined by number of elements in
the two sets. In the picture about injectivity, note that in the very last
example we have no chance of creating a 1-1 mapping from *A* to
*B*, simply because there are not enough elements in the target set.
Similarly, in the picture about surjectivity, there is no way we can make a
mapping onto *B* in the last example, since we cannot reach four
elements with just three arrows. In general, if *A* and *B* are
finite sets and the size of *A* is greater (sharply) then the size of
*B*, then we cannot make a 1-1 mapping from *A* to *B*; on the
other hand, there is no chance of surjectivity if the size of *A* is
(sharply) smaller than that of *B*. We can also pass to
counterpositives. If there exists a 1-1 mapping from *A* to *B*,
then *B* must have at least as many elements as *A*.
If there exists a mapping from *A* onto *B*,
then *A* must have at least as many elements as *B*.

The above two properties combine into a very useful notion.

Definition.

Consider a mappingTfromAtoB.

We say thatTisbijective, or that it is abijection, if it is one-to-one and onto.

Among all the above examples there is just one bijection, namely the upper left example in the last (and second last) picture. Bijections are very useful, since they allow us to compare sets. For instance, from the above remark concerning sizes we should guess that for two finite sets, unless they have the same number of elements, they cannot be connected by a bijection; conversely, if there is some bijection, then the two sets must have the same number of elements. We look closer at this in the last part of this section.

Intuitively, if we have two sets and a bijection between them, then we have a pairing of elements of the two sets, and it seems that the direction of the arrows is no longer important. This is true, we will look at this in the next part.

We start with something very simple, it does not count as an operation, but it is something we can do to mappings.

Definition.

Consider a mappingTfromAtoB. LetDbe a subset ofA. We define therestrictionofTtoDas the mappingSfromDtoBdefined byfor all S(d) =T(d)dfromD.

Intuitively, we simply pretend that *T* does not exist outside *D*
and we have the restriction. We denote it
*T* |_{D}.

Since the sets we work with here are general, there are no operations (like addition etc.) available. Thus the only thing we can try in general is to look at composition of mappings.

Definition.

LetTbe a mapping fromAtoBand letSbe a mapping fromBtoC. By thecompositionof these two mappings we mean the mappingfrom S○TAtoCdefined by

S○T:a↦S(T(a))for afromA.

That is, we first find the image of *a* under *T* and then we
substitute this image into *S*. The picture shows that it makes sense,
since the images under *T* are exactly in the space where *S*
works; precisely, the range of *T* is a subset of the domain of *S*.

For instance, *S* ○ *T* )(*a*) = *S*(*T*(*a*)) = ½.*A* gets sent twice in a row and then we consider it
just one sending, thus obtaining a new mapping.

Note that the notation for composition is read "right to left", that
is, when substituting, we first use the function on the right and then the
one on the left. This may be unusual at first and beginners occasionally mix
it up, but it makes sense, since the order is the same as the alternative
notation *S*(*T* ).*T* ○ *S* = *T*(*S* )*B* into *S*, we get an element
from *C*, but *T* does not act on *C*.

Note also that in such a composition the second mapping *S* only matters
at places where one can get to it using *T*; in other words, values of
*S* at elements of *B* that are not parts of
*R*(*T* )

Fact.

LetTbe a mapping fromAtoBand letSbe a mapping fromBtoC.

If bothTandSare1-1, thenis also S○T1-1.

IfTis not1-1, thenis also not S○T1-1.

If bothTandSare onto, thenis also onto. S○T

IfSis not onto, thenis also not onto. S○T

If bothTandSare bijections, thenis also a bijection. S○T

It might be interesting to think of some implications that suggest themselves
but are not listed above, obviously because they are not true. For instance,
the following picture shows that it can happen that *S* is not

On the other hand, in the previous picture *S* was not injective and nor
was the composition. This shows that if the injectivity fails for *S*,
then the injectivity of the composition
*S* ○ *T**S*. Similar observation works
for surjectivity. Try to think of an example where *T* is not onto, but
the composition is; or an example when both *T* and *S* are not
bijective, but *S* ○ *T*

Once we have composition, we can pass to another important definition.

Definition.

LetTbe a mapping fromAtoB. We say that a mappingSfromBtoAis theinverse mappingtoT, denotedT^{−1}, if

and S(T(a)) =afor everyafromA

T(S(b)) =bfor everybfromB.If such an inverse mapping exists, then we say that

Tisinvertible.

Intuitively, these two mappings cancel each other's effect. If *T* sends
*a* someplace, then *S* sends it back where it came from, and vice
versa.

The symmetry in the above picture means that being inverse is in a sense a
symmetric notion, that is, also *T* is an inverse to
*T* ^{−1}, we can write it as follows:
*T* ^{−1})^{−1} = *T*.

Note that
*D*( *T* ^{−1}) = *R*( *T* )*R*( *T* ^{−1}) = *D*( *T* ).

Above we had lots of pictures with examples of mappings that were or where
not 1-1/onto. If you think about them for a while, you should start having a
feeling that it is not possible to "undo" action of a mapping if it is not
one-to one or onto. In the first case two arrows go to the same place, so
obviously it is not possible to create an arrow in the "opposite direction"
for the inverse mapping and the first equality in the definition is not true.
If *T* is not onto, then there is an element in *B* that is not a
target for any arrow, thus making it impossible again to do an "opposite"
arrow, this time the second condition in the definition fails.

Theorem.

LetTbe a mapping fromAtoB. It is invertible if and only if it is a bijection.

Remark: If a mapping is a bijection, then it is invertible, by the above observation also its inverse is invertible and thus the inverse mapping is a bijection.

It is interesting to put the notion of inverse together with the composition. The condition in the definition of the inverse function can be rewritten as follows:

*T* ^{−1} ○ *T* = *Id*_{A}*T* ○ *T* ^{−1} = *Id*_{B}.

This suggests an interesting structure for the operation composition. If you are curious, look at this note.

Note that if a mapping from *A* to *B* is not onto, then there are
some unused elements in *B*. In many situations we can disregard them,
thus we get the following statement.

Theorem.

LetTbe a mapping fromAtoB. If we consider it as a mapping fromAtothen it is bijective (and therefore invertible) if and only if it is 1-1. Then it also has an inverse R(T),T^{−1}fromto R(T)A.

If two sets are finite, we can compare their sizes by simply counting numbers
of elements in each of them. As we saw above, we can also determine equality
of their sizes by asking the following question: Does there exist a bijection
from one set to another? This other way is used as a definition, since it
works not only for finite sets, but also for infinite sets. Then we do
not talk about sizes, but about *cardinalities*.

Definition.

Consider two setsAandB. We say that they have the same cardinality, denoted| if there exists a bijection fromA| = |B|,AontoB.We say that the cardinality of

Ais less than or equal to the cardinality ofB, denoted| if there exists an injective mapping fromA| ≤ |B|,AtoB.

Equivalently, *A*| ≤ |*B*|*B*
onto *A*. This comparison of sizes behaves very reasonably, for
instance every set *A* satisfies
*A*| ≤ |*A*|*A*| = |*A*|,*A*,
*B* on has *A*| ≤ |*B*|*B*| ≤ |*A*|.

This feeling that things work "normally" is further strengthened by
a statement called the Cantor-Bernstein theorem: If
*A*| ≤ |*B*|*B*| ≤ |*A*|,*A*| = |*B*|.*A*| < |*B*|*A*| ≤ |*B*|,*A*| = |*B*|

We say that a set *A* is **finite** if either it is empty (then it
has cardinality 0) or there exists a positive integer *n* such that
*A* has the same cardinality as the set
*n*},*A* has cardinality *n*. We denote it
*A*| = *n**A* = *n*.*A*| = ∞.

As we observed above, for finite sets the notion of cardinality agrees with the intuitive notion of size. It gets more interesting when sets are infinite, since it turns out that there are many "sizes" of infinity. One of the most important "sizes" is the cardinality of the set of all natural numbers (see the next section).

Definition.

Consider a setA. We say that this set iscountableif it has the same cardinality as the set ℕ of all natural numbers.

Countable sets are those sets whose elements can be "indexed" or
"enumerated". Indeed, consider a set *A* that is countable. By
definition, there must be some bijection *T* from *A* onto the set
ℕ. Now we can order
elements of *A* according to the number they are assigned via *T*.
First we take the element *a* such that
*T*(*a*) = 1,*a*_{1}, then we take the element *a* such
that *T*(*a*) = 2,*a*_{2},
and so on, and since *T* assigns a number (an "index") to every element
of *A*, we eventually get the whole set *A* in this way.

This property of being "indexable" is very useful, so countable sets are
very welcome, in particular such a set can be exhausted by induction.
By the way, countability is the smallest size of infinite sets. What
sets are countable? It turns out that quite a lot, since the "countable" size
of infinity can take quite a lot. We start with a simple observation that
adding one element to a countable set does not change its size. To prove
this, it is enough to show that the set of natural numbers has the same
cardinality as the set of natural numbers enriched by 0. The bijection we use
is *T*(*n*) = *n* − 1,*T* ) and so they are of
the same "size".

We see that adding one element to an infinite set does not change its size. We can do even better. If we enlarge a countable set by another set of the same size, it will still be countable. One way to see this is to prove that

*integers form a countable set*,

since we know that integers are formed by taking natural numbers and adding natural numbers with minus signs (cf. the next section). Intuitively we would say that there must be twice as many integers as there is naturals, but infinities are tricky.

First we need to make infinitely many holes in natural numbers to make room
for negative integers. Consider the mapping
*T*(*n*) = 2*n*

This actually shows that the set of natural numbers has the same size as the set of even natural numbers, but for us the important thing is the holes on the right. There is obviously infinitely many of them, so they offer places where we can send negative numbers.

This particular *T* is defined as follows:
*T*(*n*) = 2*n**T*(*n*) = 1 − 2*n*

We index by keeping going left and right, obviously we will eventually index all integers in this way. By the way, this indexing exactly corresponds to the bijection above. We introduce this alternative reasoning here, because we will use it in proving the most outrageous claim so far: If we add infinitely many copies of natural numbers to this set, we again get a countable set. In other words, the Cartesian product of natural numbers with natural numbers has the same size as the original set. We will prove it by coming up with a way to enumerate all pairs. We will indicate the first few indexed pairs and then show the general pattern.

It seems clear that if we follow the pattern, we eventually index all the
pairs. We will now look at this result from two different points of view.
First, if we think of countable infinity as an abstract element, then the
first fact concerning countability shows that actually
*n* ⋅ ∞ = ∞*n*.
The last (so far) fact (on Cartesian product) says that also
^{2} = ∞.^{n} = ∞*n*. However, that's where things stop, since
^{∞}^{∞}

We claim that

*rational numbers form a countable set*.

First, since
rational numbers include natural numbers, it is clear that they are at least
countable. Thus the more difficult part is in proving that they are also at
most countable. Recall that we proved that the set of all pairs
(*a*,*b*) of natural numbers is countable. Since we know that
doubling does not change size of infinite sets, it follows that also the set

*M* = {(*a*,*b*); *a* an integer, *b*
a natural number}

is countable. The mapping *S* defined by
*S*(*a*,*b*) = *a*/*b**M* onto rationals, which means that the size of rational numbers is at
most the same as the size of *M*, that is, rationals are at most
countable. The proof is finished.

Thus we see that all sets that we obtained by trying to fix some algebraic problems (cf. the next section) are countable. However, this is not true for real numbers.

Real numbers is not a countable set.

The classical proof of this fact shows that no matter how we try to enumerate real numbers, there will always be some left, and it is surprisingly simple, but still too long for this section; you have to take our word for it. Since connecting two countable sets yields a countable set and rationals are countable, it follows that there is uncountably many irrational numbers. In other words, when we look at a line in the plane, mark some point as origin and then mark all points whose distance from the origin is a rational number, then there will be substantially more holes than points on this line.

Cardinality of sets has been studied thoroughly for quite some time, there are sets that are even bigger than the set of real numbers and even bigger and so on (there is an infinite chain of infinite sizes), but one seemingly simple question remains open: Is the cardinality of real numbers the next after countability, or is there a set whose cardinality is strictly larger than countability but strictly smaller than cardinality of real numbers? Most mathematicians think that there is no intermediate size, which is called the Continuum Hypothesis, but nobody could prove it so far. If you happen to have an idea concerning this, you have a good chance to get some major math prize.