◀ ▲ ▶Branches / Combinatorics / Part: Set-theoretic Prerequisites Needed For Combinatorics
Part: Set-theoretic Prerequisites Needed For Combinatorics
In this part, we will recap some basic results from set theory, which are necessary to really understand combinatorics. First of all, please check if you are already acquainted with the following results:
- basics about sets, including the concepts of a set, subsets and supersets, set operations and power set,
- functions, including their definition, and most important properties,
- equivalence relations and partitions,
- cardinalities, definitions of finite and infinite sets, and simple facts about cardinals,
- ordered pairs and Cartesian product,
- proving principle by induction.
These basics are important for combinatorics because almost all combinatorial results can be derived from them.
Table of Contents
Explanations: 1 2 3
- Proposition: Indicator Function and Set Operations
- Proposition: Fundamental Counting Principle
- Theorem: Inclusion-Exclusion Principle (Sylvester's Formula)
- Proposition: Recursively Defined Arithmetic Functions, Recursion