﻿ Injections, Surjections, and Bijections
HOME Mathematics Computer Science
Injections, Surjections, and Bijections
Prerequisites
Show All
Hide All
Sets
Show/Hide
﻿
Introduction
• A set is a collection of elements, such as:
• A = {1, 2, 3, 4, 5}
• A set does not have order:
• {1, 2, 3, 4, 5} is the same as {5, 4, 3, 2, 1}
• It is convenient to write the elements of a set in consecutive order, but this is only for convenience.
• Every element in a set is unique, multiples of the same element are ignored:
• The set {1, 2, 2} has a size of 2, and is the same as {1, 2}
Notation
• It is common for sets to be denoted by a uppercase letter, and for its elements to be wrapped in curly braces:k

LaTeX: \mathbf{A} = \{ 1, 2, 3, 4, 5 \}
• Sets can also be defined using set builder notation:
• A rule is used to show which elements are members of the set:
• The set A defined above would contain all even integers between 0 and 2000.
• The format of the rule is: (formula: conditions) or (formula| conditions).
• If it is not specified as a condition, then it is assumed that a is a real number.
Elements in a set
• Elements in a set are usually represented by a lowercase letter.
• To demonstrate that an element is part of a set, we use the set membership symbol:

LaTeX: \mathbf{a} \in \mathbf{A}
• This can also be done with proper elements:

LaTeX: \1 \in \{ 1, 2, 3, 4, 5 \}
• To show that an element is not part of a set, we use the 'not member of' symbol:

LaTeX: 6 \notin \{ 1, 2, 3, 4, 5 \}
The Empty Set

The Empty Set (or Null Set) is a set containing no items. It is represented by the empty set symbol:

LaTeX: \varnothing = \{\}
Code
A = frozenset([1, 2, 3, 4, 5])

print(1 in A) # prints 'True'
print(6 not in A) # prints 'True'

Ordered Pairs
Show/Hide
﻿
Introduction
• An ordered pair is simply a pair of objects, e.g. (a, b)
• In an ordered pair, the order matters:
LaTeX:
(\mathbf{a}, \mathbf{b})\neq (\mathbf{b}, \mathbf{a})
\text{ unless }
\mathbf{a} = \mathbf{b}

• This contrasts with the unordered pair, in which (a, b) = (b, a) regardless of the values of a and b.
• An ordered pair is not a type of set. An ordered pair may contain duplicate elements, and its order is important.
Notation
Ordered Pairs are represented by a comma separated pair of elements wrapped in brackets:
a = (1, 2)
LaTeX: \mathbf{a} = (1, 2)
Code
a = (1, 2)
print(a)

Functions
Show/Hide
﻿
Introduction
• A function is mapping between two sets:
• The first set (denoted by X) is called the domain.
• The second set (denoted by Y) is called the codomain.
• Each mapping can be represented as an ordered pair, e.g. (a, 1). The set of all ordered pairs for the entire function is called the graph of the function, and is given the name G.
• For each element x in X, there exists a unique y in Y.
• X is called the 'argument', 'input', or 'preimage'
• y is called the 'value', 'ouput', or 'image'
• In the above example, not all elements of Y were mapped to from X. The subset of Y that has mappings from X is called the range.
• This is also called the image of the function, and is denoted:
Functional Notation
• One common way to denote functions is using the functional notation.

LaTeX: \mathbf{y} = f(\mathbf{x})
• This is pronounced 'F of X'
• It is commonly used in areas of Mathematics which do not have a basis in set theory (such as calculus).
Arrow Notation
• Another way to denote functions is using arrow notation.

LaTeX: f\colon \mathbf{X} \to \mathbf Y
• This is pronounced 'the function f from set X to set Y.
• It is commonly used in areas of Mathematics which have a basis in set theory.
Code
def f(x):
graph = {
'a': 1,
'b': 3,
'c': 1
}

return graph.get(x)

y = f('a')
print(y)


Injections, Surjections, and Bijections
﻿
Introduction
• Functions can be classified by how they map elements between the domain and codomain.
• Three types of mappings are:
• Injective
• Surjective
• Bijective
Injective Mapping
• An injective mapping is when each element in the codomain is mapped to by at most one element from the domain.
• Another way of saying this is that no two elements in the domain map to the same element in the codomain.
• Example of an injective mapping:
• This type of mapping is also called 'one-to-one'.
Surjective Mapping
• A surjective mapping is when each element in the codomain is mapped to by at least one element from the domain.
• Another way of saying this is that the codomain and image (range) of the function are the same.
• Example of a surjective mapping:
• This type of mapping is also called 'onto'.
Bijective Mapping
• A bijective mapping is when the mapping is both injective and surjective.
• Another way of saying this is that each element in the codomain is mapped to by exactly one element in the domain.
• Example of a bijective mapping:
• This type of mapping is also called a 'one-to-one correspondence'.
Related