Search⌘ K
Home
Courses
An Introduction to Basic Set Theory

Bijective Functions

Explore bijective functions, which are both injective and surjective, forming one-to-one correspondences between sets. Learn how to identify and verify these functions with practical Python examples. Understand how bijective functions differ from other function types and gain clarity on their role in set theory and mathematics.

We'll cover the following...

Bijective functions

If a function is both injective and surjective, it is called a bijective function— also called a one-to-one correspondence or simply a correspondence. In a bijective function, every element of the domain maps to a unique element of the codomain, and every element in the codomain has a preimage. This means a bijective function pairs up all the domain and codomain elements.

Examples

Take the following sets:

Using these sets, we define the following function:

Because the function f1f_1 is both injective and surjective, it is a bijective function. The following function is another example of a bijective function:

The illustration given below shows the f2f_2 function in which we can observe that each domain element is connected to exactly one outgoing arrow, and each codomain element is connected to exactly one incoming arrow.

Example of a bijective function from the set A to the set B
Example of a bijective function from the set A to the set B

Here are a few more examples of bijective functions:

Checking if a function is bijective using Python

Let’s explore the following code to check if a given function is a bijective function. Please feel free to make changes and experiment with the given code.

Python 3.8
def is_function(domain, codomain, function):
    # Check that the image of every element in the domain is defined.
    for element in domain:
        # Check if there exists an image of the element
        if not any(pair[0] == element for pair in function):
            # If the image of element does not exist, return False 
            return False
    
    # Check if each element of the domain has only one image
    preimages = set()
    for pair in function:
        if pair[0] in preimages:
            return False
        preimages.add(pair[0])
    
    # Check that the range is a subset of the codomain. 
    for pair in function: # pair = (element, image)
        # Check if every element has an image in the codomain 
        if pair[1] not in codomain:
            # If the image of any element is not in the codomain, return False
            return False  
    return True
def is_injective(domain, codomain, function):
    # Check if every domain element has a unique image.
    image = set()
    for pair in function:
        if pair[1] in image:
            # A codmain element is an image of more than one domain elements.
            return False
        image.add(pair[1])    
    return True
def is_surjective(domain, codomain, function):
    # Check if every element of the codomain has a preimage.
    for element in codomain:
        if not any(pair[1] == element for pair in function):
            return False
    # If the function is surjective
    return True
def is_bijective(domain, codomain, function):
    return is_injective(domain, codomain, function) and is_surjective(domain, codomain, function)
# Define the domain
domain = {1, 2, 3, 4, 5}
# Define the codomain
codomain = {6, 7, 8, 9, 10}
# Define the function
f = {(1, 7), (2, 6), (3, 9), (4, 8), (5, 10)}
#check if f is a valid function
if is_function(domain, codomain, f):
    #check if f is a bijective function
    if is_bijective(domain, codomain, f):
        print('The function is bijective.')
    else:
        print('The function is not bijective.')
else:
    print('Use a valid function.')

Code explanation

  • Lines 1–22: We define a is_function function that takes three arguments, i.e., domain, codomain, and function. It checks if the argument function is a valid function with the domain and the codomain. It returns False if function is not a valid function.

  • Lines 24–32: We define a is_injective function that takes three arguments, i.e., domain, codomain, and function. It checks if the passed function is injective by checking if every domain element has a unique image. It returns True if the function is injective and returns False otherwise.

  • Lines 34–41: We define a is_surjective function that takes three arguments, i.e., domain, codomain, and function. It checks if the passed function is surjective or not by checking if every codomain element has a preimage. It returns True if the function is surjective and returns False otherwise.

  • Lines 43–44: We define a is_bijective function that takes three arguments, i.e., domain, codomain, and function. It checks if the passed function is bijective.

  • Lines 46–50: We define the sets domain, codomain, and f.

  • Lines 52–59: We check if f is a valid function from the domain to the codomain, and if it is, we check if f is a bijective function. We print messages according to each situation.

Types of functions

A function is always one of the four types listed below:

  • Neither injective nor surjective

  • Only injective but not surjective

  • Only surjective and not injective

  • Both injective and surjective, which means bijective

Let’s look at a few examples of functions showing each of these cases. These functions are defined using the following sets:

An example of all four types of functions is given in the following table.

Type Function
Neither injective nor surjective f5:B→C={(j,u),(k,z),(l,z),(m,u),(n,z)}.f_5:B\to C = \{(j,
...