Sets and functionsFunctionsInjection, surjection and bijectionInjection (one-to-one)Surjection (onto)Bijection (one-to-one correspondence)SetsCardinalityCantor's diagonalisation argumentFinite, countable and uncountable setsPowersetExampleRelation to binomial theoremDisjoint setsUnionCardinality of unions of disjoint setsArbitrary unionsIntersectionArbitrary intersectionsInclusion-Exclusion principleSet differenceCartesian product

Given a function :

The function is injective if every element of the codomain is mapped to by at most one element of the domain.

Definition | Diagram | Example |
---|---|---|

The function is surjective if every element of the codomain is mapped to by at least one element of the domain (The image and the codomain of the function are equal).

Definition | Diagram | Example |
---|---|---|

The function is bijective if every element of the codomain is mapped to by exactly one element of the domain (The function is both **injective** and **surjective**).

Definition | Diagram | Examples |
---|---|---|

Both injective and surjective |

Note that a function is bijective if and only if it has an inverse.

For set , its cardinality is denoted as . The cardinality of a set is a measure of the number of elements of the set.

Given two sets and :

The sets and have the same cardinality if there exists a bijection from to .

has cardinality less than or equal to the cardinality of if there exists an injective function from to .

has cardinality strictly less than the cardinality of if there is an injective function, but no bijective function from to .

Example:

This is because the inclusion map is injective (every element of is also in ).

But it can be shown that there does not exist a bijective function from to . This can be proven by Cantor's diagonal argument.

Cantor's diagonalisation argument can be used to prove that the set of all infinite sequences of binary digits is infinite.

First, we make the assumption that we can list **all** of the infinite sequences of binary digits, as shown above.

Then, we construct a new sequence by choosing the th digit of (the digits coloured in red), and taking its complement.

So in this case, we would have formed the new sequence that starts with:

By assumption, this sequence appears in the list of all infinite binary sequences that we made. However this is a contradiction as it can't appear in this list, as it differs from every other sequence by at least one bit.

Therefore, the set of infinite sequences of binary digits is infinite.

Similarly, we can prove that the set of real numbers is not countable. We will show that the set of reals in the interval is not countable.

First, assume that we could list all of the decimal expansions of the reals in :

This sequence can be described as , where (this can be expressed in a simpler way, but it made me feel smart so i'm keeping it).

We need to construct a new real number that wouldn't be listed above. That is, one that differs from every listed number above in at least one digit.

Similarly to the example with binary strings, we can construct a new number that disagrees with every digit , so all of the digits Since we are working in , we can let represent the modular multiplicative inverse of . , so we can use this to construct our new number:

This number differs with every number listed above by at least one digit, and therefore we have a contradiction.

- For any set , if , then is said to be a
**finite**set. - For any set , if , then is said to be a
**countably infinite**set. - For any set , if , then is said to be
**uncountable**.

A set is **countable** either if

- it is finite
- it is infinite there exists a bijection between the elements of the set of natural numbers and the set of . i.e. there exists a function such that is a bijective function.

Example: Prove that the set of rationals is countable.

For this proof, we will first prove that is countable. We must find a bijection . Consider the following function:

It is easy to prove that this function is bijective. Therefore, is countable.

Now since we know that is countable, it is sufficient to find a bijection , since is a bijection between and .

The following diagram depicts such a bijection. Note that we don't count any fractions that can be reduced to a fraction that has already been counted previously. For example is not counted, as this is equivalent to .

The powerset of any set is the set of all subsets of , including the empty set and itself. The power set of the set is denoted as .

For every set , .

The number of subsets with elements in the power set of a set with elements is given by the number of combination .

Example: The power set of a set with three elements has:

- subset with elements (the empty subset)
- subsets with element (the singleton subsets)
- subsets with elements (the complements of the singleton subsets)
- subset with elements (the original set itself)

Sets and are disjoint iff .

More generally, sets are (pairwise) disjoint iff

For disjoint sets and , we have .

For a finite union of sets , one often writes:

For an infinite union of sets , one often writes:

For disjoint sets and , we have . That is, .

For a finite union of sets , one often writes:

For an infinite union of sets , one often writes:

Consider the cardinality of the union of two disjoint finite sets and . Symbolically, this can be expressed as:

The formula expresses the fact that the sum of the sizes of the two sets may be too large since some elements may be counted twice. The double-counted elements are those in the intersection of the two sets and the count is corrected by subtracting the size of the intersection.

The principle is more clearly seen in the case of three sets, which for the sets , and is given by:

This can also be easily seen with a Venn diagram.

If and are sets, then the set difference of in is the set of elements in but not in . The set difference of in is denoted as either .

Example:

- is the set of irrational numbers.

For sets and , the Cartesian product is the set of all ordered pairs where and :

Example: and , then: