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

Sets and functions

Functions

Injection, surjection and bijection

Given a function :

Injection (one-to-one)

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

DefinitionDiagramExample

Surjection (onto)

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).

DefinitionDiagramExample

Bijection (one-to-one correspondence)

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).

DefinitionDiagramExamples
Both injective and surjective


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

Sets

Cardinality

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

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.

Finite, countable and uncountable sets

A set is countable either if

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 .

Powerset

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 , .

Example

Relation to binomial theorem

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:

Disjoint sets

Sets and are disjoint iff .

More generally, sets are (pairwise) disjoint iff

Union

Cardinality of unions of disjoint sets

For disjoint sets and , we have .

Arbitrary unions

For a finite union of sets , one often writes:

For an infinite union of sets , one often writes:

Intersection

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

Arbitrary intersections

For a finite union of sets , one often writes:

For an infinite union of sets , one often writes:

Inclusion-Exclusion principle

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.

Set difference

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:

Cartesian product

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

Example: and , then: