Set Theory#
Set theory forms the basis of several other fields of study like counting theory, relations, graph theory and finite state machines.
Set Theory Notation
- \(\{ , \}\)
We use braces to enclose the elements of a set. So \(\{ 1, 2, 3 \}\) is the set containing \(1\), \(2\), and \(3\).
- \(:\)
\(\{ x : x > 2\}\) is the set of all \(x\) such that \(x\) is greater than \(2\).
- \(\in\)
\(2 \in \{ 1, 2, 3 \}\) asserts that \(2\) is an element of the set \(\{ 1, 2, 3 \}\).
- \(\notin\)
\(4 \notin \{ 1, 2, 3 \}\) because \(4\) is not an element of the set \(\{ 1, 2, 3 \}\).
- \(\subseteq\)
\(A \subseteq B\) asserts that \(A\) is a subset of \(B\); every element of \(A\) is also an element of \(B\).
- \(\subset\)
\(A \subset B\) asserts that \(A\) is a proper subset of \(B\); every element of \(A\) is also an element of \(B\), but \(A \neq B\).
- \(\cap\)
\(A \cap B\) is the intersection of \(A\) and \(B\); the set containing all elements which are elements of both \(A\) and \(B\).
- \(\cup\)
\(A \cup B\) is the union of \(A\) and \(B\); the set containing all elements which are elements of \(A\) or \(B\) or both.
- \(\times\)
\(A \times B\) is the Cartesian product of \(A\) and \(B\); the set of all ordered pairs \(( a, b )\) with \(a \in A\) and \(b \in B\).
- \(\setminus\)
\(A \setminus B\) is set difference between \(A\) and \(B\); the set containing all elements of \(A\) which are not elements of \(B\).
- \(\bar{A}\)
The complement of \(A\) is the set of everything which is not an element of \(A\).
- \(|A|\)
The cardinality (or size) of \(A\) is the number of elements in \(A\).
Sets#
A set is an unordered collection of different elements. A set can be written explicitly by listing its elements using set bracket. If the order of the elements is changed or any element of a set is repeated, it does not make any changes in the set.
Examples
A set of all positive integers.
A set of all the planets in the solar system.
A set of all the states in India.
A set of all the lowercase letters of the alphabet.
Set Representations#
Roster or Tabular Form#
The set is represented by listing all the elements comprising it. The elements are enclosed within braces and separated by commas.
Examples
Set of vowels in English alphabet, \(A = \{a, e, i, o, u\}\).
Set of odd numbers less than \(10\), \(B = \{1, 3, 5, 7, 9\}\).
Set Builder Notation#
The set is defined by specifying a property that elements of the set have in common. The set is described as \(A = \{x : p(x)\}\).
Examples
The set \(\{a, e, i, o, u\}\) is written as:
The set \(\{1, 3, 5, 7, 9\}\) is written as:
If an element \(x\) is a member of any set \(S\), it is denoted by \(x \in S\); and if an element \(y\) is not a member of set \(S\), it is denoted by \(y \notin S\).
Example
If \(S = \{1, 1.2, 1.7, 2\}\), \(1 \in S\) but \(1.5 \notin S\).
Some Important Sets
\(N\) – the set of all natural numbers: \(\{ 1, 2, 3, 4, ... \}\).
\(Z\) – the set of all integers: \(\{ ..., -3, -2, -1, 0, 1, 2, 3, ... \}\).
\(Z^+\) – the set of all positive integers: \(\{ 1, 2, 3, ... \}\).
\(Q\) – the set of all rational numbers: \(\{ \frac{p}{q} | p, q \in Z, q \neq 0 \}\).
\(R\) – the set of all real numbers.
\(W\) – the set of all whole numbers: \(\{ 0, 1, 2, 3, ... \}\).
Natural Language Description#
This is often called a semantic description of the set, where a sentence is used to describe the properties of objects contained in a set.
The following are valid semantic descriptions of sets:
Let \(A\) be the set of three primary colors: \(A = \{ \text{red}, \text{blue}, \text{yellow} \}\)
Let \(B\) be the set of five smallest positive integers: \(B = \{ 1, 2, 3, 4, 5 \}\)
Let \(C\) be the set of positive rational numbers with 1 as a numerator: \(C = \{1, \frac{1}{2}, \frac{1}{3}, \frac{1}{4}, \ldots\}\)
Important
When using semantic descriptions, it is important that the sentence be as clear as possible and unambiguous.
Interval Notation#
For sets of real numbers, a particularly useful notation is interval notation. We are probably familiar with this notation from calculus. For two real numbers \(a\) and \(b\), such that \(a < b\), we have the following possible intervals:
The choice of including the end point of an interval or not determines if the interval is closed or open.
A closed interval is the set of all numbers between two end points, including those endpoints. It is denoted by square brackets. \([a, b]\) is all numbers \(x\) such that \(a \leq x \leq b\).
An open interval is the set of all numbers between two end points, excluding those endpoints. It is denoted by parentheses. \((a, b)\) is all numbers \(x\) such that \(a < x < b\).
A half-open or half-closed interval is where one endpoint is included and one endpoint is excluded. To be more precise, we can say left-open or right-closed to mean only the right end point is included, e.g. \(( a, b ]\). We can say left-closed or right-open to mean only the left end point is included, e.g. \([ a, b )\).
When we want to describe intervals which are unbounded on one side (i.e. go until positive or negative infinity), we use a parenthesis and the infinity symbol.
Membership and Equality#
Membership is the basic property of sets from which all other operatiosn and properties can be defined. A set either contains an object or does not contain an object. Sets define a clear and unambiguous description of its members.
We have already seen the notation \(\in\) which is used to say that an element is included in the set. The notation \(\notin\) says an element is not included in a set.
Again, membership is a strict binary—an object is either in a set or is not in a set. Because of that, we have the following results:
Stated in predicate logic, two sets are equal if \(\forall x (x \in A \leftrightarrow x \in B)\).
Because the only basic property of a set is membership, a set does not care about the order in which elements are listed or the number of times each element appears in the set construction. For example, the following sets are equal:
To avoid this awkward and “non-canonical” description of sets, it is often said that sets should only contain unique, distinct, and distinguishable objects. In particular, when using the roster method, one should only write each unique element once. Therefore, \(\{ 1, 2 \}\) or \(\{ 2, 1 \}\) is the most “correct” description of the previous set.
Cardinality of a Set#
Cardinality of a set \(S\), denoted by \(|S|\), is the number of elements of the set. The number is also referred as the cardinal number. If a set has an infinite number of elements, its cardinality is \(\infty\).
Example
\(|\lbrace 1, 4, 3, 5 \rbrace | = 4, | \lbrace 1, 2, 3, 4, 5, \dots \rbrace | = \infty\)
Types of Sets#
Sets can be classified into many types. Some of which are finite, infinite, subset, universal, proper, singleton set, etc.
Finite Set#
A set which contains a definite number of elements is called a finite set.
Example
\(S = \{ x | x \in N \text{and} 70 > x > 50 \}\)
Infinite Set#
A set which contains infinite number of elements is called an infinite set.
Example
\(S = \{ x | x \in N \text{and} x > 10 \}\)
Subset#
A set \(X\) is a subset of set \(Y\) (written as \(X \subseteq Y\)) if every element of \(X\) is an element of set \(Y\).
Examples
Let \(X = \{ 1, 2, 3, 4, 5, 6 \}\) and \(Y = \{ 1, 2 \}\). Here, set \(Y\) is a subset of set \(X\) as all the elements of set \(Y\) is in set \(X\). Hence, we can write \(Y \subseteq X\).
Let \(X = \{ 1, 2, 3 \}\) and \(\{ 1, 2, 3 \}\). Here, set \(Y\) is a subset (not a proper subset) of set \(X\) as all the elements of set \(Y\) is in set \(X\). Hence, we can write \(Y \subseteq X\).
Proper Subset#
The term proper subset can be defined as subset of but not equal to. A set \(X\) is a proper subset of set \(Y\) (written as \(X \subset Y\)) if every element of \(X\) is an element of set \(Y\) and \(|X| < |Y|\).
Example
Let \(X = \{ 1, 2, 3, 4, 5, 6 \}\) and \(Y = \{ 1, 2 \}\). Here, set \(Y \subset X\) since all elmeents in \(Y\) are contained in \(X\) too, and \(X\) has at least one element more than set \(Y\).
Universal Set#
It is a collection of all elements in a particular context or application. All the sets in that context or application are essentially subsets of this universal set. Universal sets are represented as \(U\).
Example
We may define \(U\) as the set of all animals on Earth. In this case, set of all mammals is a subset of \(U\), set of all fishes is a subset of \(U\), set of all insects is a subset of \(U\), and so on.
Empty Set or Null Set#
An empty set contains no elements. It is denoted by \(\emptyset\). As the number of elements in an empty set is finite, empty set is a finite set. The cardinality of empty set or null set is zero.
Example
\(S = \{ x | x \in N \text{and} 7 < x < 8 \} = \emptyset\)
Singleton Set or Unit Set#
Singleton set or unit set contains only one element. A singleton set is denoted by \(\{ s \}\).
Example
\(S = \{ x | x \in N, 7 < x < 9 \} = \{ 8 \}\)
Equal Set#
If two sets contain the same elements, they are said to be equal.
Example
If \(A = \{ 1, 2, 6 \}\) and \(B = \{ 6, 1, 2 \}\), they are equal as every element of set \(A\) is an element of set \(B\), and every element of set \(B\) is an element of set \(A\).
Equivalent Set#
If the cardinalities of two sets are same, they are called equivalent sets.
Example
If \(A = \{ 1, 2, 6 \}\) and \(B = \{ 16, 17, 22 \}\), they are equivalent as cardinality of \(A\) is equal to the cardinality of \(B\), i.e. \(|A| = |B| = 3\).
Overlapping Set#
Two sets that have at least one common element are called overlapping sets.
In case of overlapping sets:
\(n(A \cup B) = n(A) + n(B) - n(A \cap B)\)
\(n(A \cup B) = n(A - B) + n(B - A) + n(A \cap B)\)
\(n(A) = n(A - B) + n(A \cap B)\)
\(n(B) = n(B - A) + n(A \cap B)\)
Example
Let \(A = \{ 1, 2, 6 \}\) and \(B = \{ 6, 12, 42 \}\). There is a common element \(6\), hence these sets are overlapping sets.
Disjoint Set#
Two sets \(A\) and \(B\) are called disjoin sets if they do not have even one element in common. Therefore, disjoint sets have the following properties:
\(n(A \cap B) = \emptyset\)
\(n(A \cup B) = n(A) + n(B)\)
Example
Let \(A = \{ 1, 2, 6 \}\) and \(B = \{ 7, 9, 14 \}\), there is not a single common element, hence these sets are disjoint sets.
Venn Diagrams#
Venn diagram, invented in 1880 by John Venn, is a schematic diagram that shows all possible logical relations between different mathematical sets.
Set Operations#
Set operations include Set Union, Set Intersection, Set Difference, Complement of Set, and Cartesian Product.
Set Union#
The union of sets \(A\) and \(B\) (denoted by \(A \cup B\)) is the set of elements which are in \(A\), in \(B\), or in both \(A\) and \(B\). Hence, \(A \cup B = \lbrace x \:| \: x \in A\ OR\ x \in B \rbrace\).
Example
If \(A = \{ 10, 11, 12, 13 \}\) and \(B = \{ 13, 14, 15 \}\), then \(A \cup B = \{ 10, 11, 12, 13, 14, 15 \}\). (The common element occurs only once.)
Set Intersection#
The intersection of sets \(A\) and \(B\) (denoted by \(A \cap B\)) is the set of elements which are in both \(A\) and \(B\). Hence, \(A \cap B = \{ x | x \in A \text{AND} x \in B \}\).
Example
If \(A = \{ 11, 12, 13 \}\) and \(B = \{ 13, 14, 15 \}\), then \(A \cap B = \{ 13 \}\).
Set Difference#
The set difference of sets \(A\) and \(B\) (denoted by \(A - B\)) is the set of elements which are only in \(A\) but not in \(B\). Hence, \(A - B = \{ x | x \in A \text{AND} x \notin B \}\).
Example
If \(A = \{ 10, 11, 12, 13 \}\) and \(B = \{ 13, 14, 15 \}\), then \(A - B = \{ 10, 11, 12 \}\) and \(B - A = \{ 14, 15 \}\). Here, we can see \(A - B \neq B - A\).
Symmetric Difference#
A special kind of difference is symmetric difference. It is the set-equivalent of “exclusive or” from propositional logic.
The symmetric difference of two sets \(A\) and \(B\) is the set of elements which are members of \(A\) or members of \(B\) but not both. The symmetric difference of \(A\) and \(B\) is denoted \(A \oplus B\).
The “symmetric” in symmetric difference comes from the following identity:
However, a more intuitive way to think about symmetric difference is as the union of two sets minus their intersection.
Which leads to the following Venn diagram.
The symmetric difference of two sets \(A\) and \(B\) is their union minus their intersection.#
Complement of a Set#
The complement of a set \(A\) (denoted by \(A'\)) is the set of elements which are not in set \(A\). Hence, \(A' = \{ x | x \notin A \}\).
More specifically, \(A' = U - A\) where \(U\) is a universal set which contains all objects.
Example
If \(A = \{ x | x \text{belongs to set of odd integers} \}\), then \(A' = \{ y | y \text{does not belong to set of odd integers} \}\).
Cartesian Product#
The Cartesian product of \(n\) number of sets \(A_1, A_2, ..., A_n\) denoted as \(A_1 \times A_2 \times ... \times A_n\) can be defined as all possible oredered pairs \((x_1, x_2, ..., x_n)\) where \(x_1 \in A, x_2 \in A_2, ..., x_n \in A_n\).
Example
If we take two sets \(A = \{ a, b \}\) and \(B = \{ 1, 2 \}\);
The Cartesian product of \(A\) and \(B\) is writted as:
The Cartesian product of \(B\) and \(A\) is writted as:
Power Set#
Power set of a set \(S\) is the set of all subsets of \(S\) including the empty set. The cardinality of a power set of a set \(S\) of cardinality \(n\) is \(2^n\). Power set is denoted as \(P(S)\).
Example
For a set \(S = \{ a, b, c, d \}\), let us calculate the subsets:
Subsets with 0 elements: \(\{ \emptyset \}\)
Subsets with 1 element: \(\lbrace a \rbrace, \lbrace b \rbrace, \lbrace c \rbrace, \lbrace d \rbrace\)
Subsets with 2 elements: \(\lbrace a, b \rbrace, \lbrace a,c \rbrace, \lbrace a, d \rbrace, \lbrace b, c \rbrace, \lbrace b,d \rbrace,\lbrace c,d \rbrace\)
Subsets with 3 elements: \(\lbrace a ,b, c\rbrace,\lbrace a, b, d \rbrace, \lbrace a,c,d \rbrace,\lbrace b,c,d \rbrace\)
Subsets with 4 elements: \(\lbrace a, b, c, d \rbrace\)
Hence, \(P(S) =\)
\(| P(S) | = 2^4 = 16\)
Note
The power set of an empty set is also an empty set.
\(| P (\lbrace \emptyset \rbrace) | = 2^0 = 1\)