A function is a special type of relation and, consequently, itself a set.
Definition.
A relation is called a function from to if for all , there is a unique such that .
- I abbreviate these circumstances by the symbol .
- The set is called the domain of , and is called the codomain of .
- The element is called the image of under and always denoted by , and is called a preimage of .
Exercise.
Determine which of these relations is a function from to .
Examples.
Let be a nonempty set.
- A function of the form is called a constant function.
- The identity on is the function . I denote this by .
- If , the function is called the inclusion map from to . I denote this by .
Exercises.
- In the examples above, are 2 and 3 the same? What is the difference?
- Rewrite all the above examples by defining the functions using only their rule of correspondence, that is, exhibiting a formula of the form .
Direct and inverse images
Recall that the symbol represents “exists.” Also, I use the symbol instead of when I want to remind the reader that I am not just claiming the sets are equal, I am declaring it as part of a definition.
Definition.
Let and be any set.
- The direct image of under is the set .
- The inverse image of under is the set .
- The set is called the image of . Some textbooks might use the word range.
My definition does not require any assumptions about the set and still makes perfect sense. However, most textbooks require for the direct image and for the inverse image. How do these definition change in this case?
Warning:
Most textbooks will use the notation to denote the direct image of under . In most cases (e.g., analysis, linear algebra, etc.) this will not cause confusion. But in general, this notation is ambiguous if, for instance, the domain of also consists of sets in the same language as its powerset. In this case, could either mean the image or the direct image, and these could have different values.
Exercises.
For the functions mentioned in the above examples, find the direct and inverse images of the following sets under those functions. Assume that and that . Prove your claims if you want to learn.
- .
- .
- .
- .
- .
Exercises.
Suppose that and . Prove that
Reflect.
Under what conditions can you change for ?
Injectivity and surjectivity
Definition.
A function is called:
- injective, or one-to-one if for all , implies .
- surjective, or onto, if .
- bijective if it is both injective and surjective.
Write the contrapositive statement of the first definition above. When would you use the contrapositive rather than the direct statement? Write out the second definition as a quantified statement.
Exercise.
Out of all the examples mentioned in this page, decide which ones are injective, which ones are surjective? Write a proof for each claim.
Exercise.
Let be a surjective function and define if . Prove that is an equivalence relation on . Where is surjectivity needed?
Conversely, show that if if is an equivalence relation on , then there is a set and a surjective function such that if and only if .
Hard exercise.
I say is a partition of if ( is the union over all sets that are members of ), and the elements of are pairwise disjoint. Prove that any quotient on is a partition of .
Conversely, show that for any partition, there is an equivalence relation whose quotient is equal to the partition.