First Concepts
This chapter deals with the basic results needed to solve combinatorics problems. We start with set-theoretic definitions and constructions, and then carry on with the most important results needed to start working in combinatorics. Then, stronger solving
- PDF / 374,619 Bytes
- 16 Pages / 477 x 684 pts Page_size
- 82 Downloads / 218 Views
First Concepts
1.1
Sets and First Countings
A set is defined to be a “collection of elements contained within a whole”. That is, a set is defined only by its elements, which can also be sets. When we write {a, b, c} = S, we mean that S is the set that has the elements a, b, c. Two sets are equal if (and only if) they have the same elements. To indicate that a is an element of S, we write a ∈ S. In a set we never repeat elements, they can just be in the set or not be there. Given a set A and a property ψ, we denote by {a ∈ A | ψ(a)} the set of all elements of A that satisfy property ψ. For example, {a ∈ R | a > 2} is the set of all real numbers that are greater than 2. By convention, there is an empty set. That is, a set with no elements. One usually denotes that set with the symbol ∅. When we say that a set has to be contained within a whole, we mean that it should not be “too big”. This is a very technical detail, but there are collections (such as the collection of all sets) that bring difficulties if we consider them as sets. Throughout this book we will never face this kind of difficulties, even when we talk about infinite sets. However, it is important to know that there are collections that are not sets.1 Given two sets A and B, we say that A is a subset of B, or that A is contained in B, if every element of A is an element of B. We denote this by A ⊂ B. For example {1, 2} ⊂ {1, {1, 3}, 2} since 1 and 2 are elements of the second set. However, {1, 3} ⊂ {1, {1, 3}, 2} since 3 is not an element in the second set. Given two sets A and B, we can use them to generate other sets. • •
A ∩ B, called the intersection of A and B. This is the set that consists of all the elements that are in both A and B. A ∪ B, called the union of A and B. This is the set that consists all the elements that are in at least one of A or B.
1 If you want an example of this, consider Russell’s paradox. Let S be the collection of all sets that do not contain themselves as elements, i.e., all sets A such that A ∈ / A. If S is considered as a set, then S ∈ S if and only if S ∈ / S, a contradiction!
P. Soberón, Problem-Solving Methods in Combinatorics, DOI 10.1007/978-3-0348-0597-1_1, © Springer Basel 2013
1
2
•
1
First Concepts
P(A), called the power set of A. This is the set made by all subsets of A. Using the notation above, we would write P(A) = {B | B ⊂ A}.
In general we have that A ⊂ A and ∅ ⊂ A for any set A, so they are elements of P(A). Notice that P(∅) is not ∅, but rather {∅}. We say that two sets A and B are disjoint if A ∩ B = ∅. In other words, they are disjoint if they have no elements in common. Given a set A, |A| denotes the number of elements of A. This number is called the cardinality of A. Example 1.1.1 Prove that A ∩ B is the largest set that is contained in A and in B. Solution Note that by the definition of A ∩ B, it is contained in both A and B. Consider any set C that is contained both in A and B. Given any x ∈ C, we know that x ∈ A since C is contained in A and x ∈ B since C is contained in B. Thus, x ∈
Data Loading...
