Logic and Set Theory/Functions

From Wikibooks, open books for an open world
Jump to navigation Jump to search

Definition, first examples[edit]

Definition (function):

Let be two sets. A function is an object that associates to every a unique element of .

That is, a function is something where you can put in any element and you get a uniquely defined element .

Example (shift function):

Let , the natural numbers (ie. , an infinite set). Define for .

Example (identity function):

Let be any set, and . Then the function defined by for all is called the identity function.


    1. Suppose that are sets and and are functions. Suppose further that is injective. Prove that is injective.
    2. Prove that if is any set, then the identity on is injective.
    3. Conclude that if and are two functions such that , then is injective.
    4. Do an analogous discussion for surjectivity.
    5. Prove that if and are two functions such that and , then is bijective.