1. | Sets |

2. | Functions |

3. | Introduction to counting |

4. | Counting with bijections |

5. | Generating functions |

6. | Theory of generating functions (Milan Novaković) |

7. | Burnside's lemma |

8. | Polya's theorem |

This is an introductory article to the theory of sets. It is meant to be skipped by those who are experts in sets. If you don’t know whether you should be reading the article or not, please scroll down and take a test that may help you decide on the quantity of attention and respect that you should be giving to this page.

Sets are collections of objects. Here are three examples:

1) The set of all snakes in the world;

2) The set of all leaves in a given forest;

3) The set of all two-digit integers that are divisible by \(3\);

In some cases it is possible to list all elements of the set. One such example is the set \(S\) of all two-digit integers that are divisible by \(17\). We can write \[S=\{17,34,51,68,85\}.\] The order in which we list the elements does not matter. This means that \(\{17,34,51,68,85\}\) is precisely the same set as \(\{34,51,17,68,85\}\). Also, repetitions of elements do not affect sets. The set \(\{17\), \(17\), \(34\), \(34\), \(51\), \(68\), \(85\}\) is the same old \(S\).

Usually we denote sets by capital letters from the alphabet.

If we want to emphasize that something is an **element** of a set we use the symbol \(\in\). In the case of previously defined set \(S\) we write \(34\in S\). We also use \(\not\in\) to emphasize that something is not in the set. This is how we do that: \(23\not\in S\).

A set \(Q\) is a **subset** of a set \(S\) if every element of \(Q\) is also an element of \(S\). The sentence

is written as \(Q\subseteq S\). Example:

\[\{34,68\}\subseteq S.\]Let \(S=\{17,34,51,68,85\}\) and \(T=\{5, 7, 17, 71, 85\}\) be two sets. Then

\[S\cup T=\{5,7,17,34,51,71,58,85\}\;\;\mbox{and}\;\;\; S\cap T=\{17,85\}.\]

The

Then it is easy to prove the following identities: \[(A\cup B)^C=A^C\cap B^C;\] \[(A\cap B)^C=A^C\cup B^C;\] \[A\setminus B=A\cap B^C.\] The above identities are called de Morgan’s laws.

Some books use vertical line \(|\) instead of colon, but you don’t want to do that, because in problem solving vertical line is so precious as it is used for divisibility (we write \(17|85\)). In some cultures, the symbol **:** (colon) is used for division. That should be stopped - using fractions instead is more professional.

The cartesian product \(A\times B\) of sets \(A\) and \(B\) is the set of ordered pairs whose first component is from \(A\) and the second component is from \(B\). For example, if \(A=\{1,2,3,4\}\) and \(B=\{3, a, 9\}\), then their cartesian product is:
\[A\times B=\{(1,3), (1, a), (1,9), (2,3), (2,a), (2,9), (3,3), (3,a), (3,9), (4,3), (4,a), (4,9)\}.\]
We use the notation \(A^2\) for \(A\times A\).

Cartesian product is used to formally define many important concepts in mathematics. For the beginning, you may notice that we can define the two-dimensional plane as the product of the line \(\mathbb R\) with itself. Later on we will see that relations, functions, and graphs can be defined using cartesian product.