In this post, it will cover the definition of sets and some examples, and shows usage in Python. This post is a summary of "Probability and Statistics in Data Science using Python", offered from UCSD DSE210x
The number of elements in a set $S$ is called its size or cardinality, and denoted $\vert S \vert$ or $\# S$.
For example,
(Countably infinite $\aleph_0$)
(Uncountably infinite $\aleph$)
if $m \leq n, \{m, \dots n\} = \{\text{integers from m to n, inclusive}\}$,
$$ \vert \{m, \dots, n\} \vert = n - m +1 $$For example,
For example,
print(len({-1, 1}))
2
print(sum({-1, 1}))
0
print(min({-1, 1}))
-1
print(max({-1, 1}))
1
A = {1, 2, 3}
print(sum(A))
total = 0
for i in A:
total += i
print(total)
6 6
A union of disjoint sets is called a disjoint union.
For example,
For disjoint sets, the size of the union is the sum of the sizes.
$$ \vert A \cup B \vert = \vert A \vert + \vert B \vert $$Note: In set theory, it is called addition rule
Note: In set theory, it is called subtraction(or complement) rule
This is Principle of Inclusion-Exclusion(or PIE for short)
If $\vert \{a, b\} \vert = 2$ and $\vert \{1, 2, 3\} = 3$, then
$$ \{a, b\} \times \{1, 2, 3\} = \begin{Bmatrix} (a, 1) & (a, 2) & (a, 3) \\ (b, 1) & (b, 2) & (b, 3) \end{Bmatrix} $$And,
$$ \vert \{a, b\} \times \{1, 2, 3\} \vert = 2 \times 3 = 6 $$In general, the size of a Cartesian Product is the product of the set sizes.
$$ \vert A \times B \vert = \vert A \vert \times \vert B \vert $$Note: In set theory, it is called Product Rule
If we have two sets, ($A \times B \quad \{(a, b): a \in A, b \in B \}$), its shape has rectangle, And set size is $\vert A \times B \vert = \vert A \vert \times \vert B \vert$
If we have three sets, ($A \times B \times C \quad \{(a, b, c): a \in A, b \in B c \in C\}$), then its shape has cuboid, and number of element will be
$$ \vert A \times B \times C \vert = \vert A \vert \times \vert B \vert \times \vert C \vert $$For $n$ sets, by Product Rule and induction,
$$ \vert A_1 \times \dots \times A_n \vert = \vert A_1 \vert \times \dots \times \vert A_n \vert $$Cartesian product of a set with ifself is a Cartesian Power
The power set of $S$, denoted $\mathbb{P}(S)$ is the collection of all subsets of $S$,
$$ \mathbb{P}(\{a, b\}) = \Big\{ \{ \}, \{a\}, \{b\}, \{a,b\}\Big\} $$By the 1-1 correspondence betwen $\mathbb{P}(S)$ and $\{0,1\}^{\vert S \vert}$,
$$ \vert \mathbb{P}(S) \vert = \vert \{0, 1\}^{\vert S \vert} \vert = 2^{\vert S \vert} $$The size of the power set is the power of the set size.
A function from $A$ to $B$ maps every element $a \in A$ to an element $f(a) \in B$
import itertools
print(set(itertools.product({2, 5, 9}, repeat=2)))
{(5, 9), (5, 5), (2, 9), (9, 2), (9, 9), (2, 2), (9, 5), (2, 5), (5, 2)}
3 ** 2
9
Consider 3-5 digit PINs.
$$ D = \{0, \dots, 9\}, \{\text{PINs}\} = D^3 \cup D^4 \cup D^5 $$In this case,
$$ \sharp \text{ of PINs} = \vert D^3 \cup D^4 \cup D^5 \vert = \vert D^3 \vert + \vert D^4 \vert + \vert D^5 \vert = 10^3 + 10^4 + 10^5 $$Consider 4 digit PINs with containing zero
Note: $\bar{Z} = Z^c$: set of non-zero digits
$\qquad \rightarrow \exists Z = \{ x^n \in D^n : \exists i x_i \in Z\} $: {$n$-digit PINs containing 0}
$Z_1 = \{x_1 x_2: x_1 = 0\}$
$Z_2 = \{x_1 x_2: x_2 = 0\}$
$\exists Z = Z_1 \cup Z_2$
$\vert \exists Z \vert = \vert Z_1 \vert + \vert Z_2 \vert - \vert Z_1 \cap Z_2 \vert $
$\omega = D^2$
$\bar{\exists Z} = \bar{\{x_1 x_2: \exists i \quad x_i = 0 \}} = \{x_1 x_2: \forall i \quad x_i \neq 0\} = \bar{Z} \times \bar{Z}$
$ \vert \bar{ \exists Z} \vert = \vert \bar{Z} \times \bar{Z} \vert = \vert \bar{Z} \vert^2 $
Write the following functions to determine $|A\cup B|$ in two different ways.
A function union that determines first $A\cup B$ and then evaluates the union's size. Output the ordered pair $(A\cup B, |A\cup B|)$.
* Sample run *
A = {1, 2, 3}
B = {3, -6, 2, 0}
print union(A, B)
* Expected Output *
({-6, 0, 1, 2, 3}, 5)
def union(A, B):
# inputs: A and B are of type 'set'
# output: a tuple of the type (set, set_length)
union_set = A.union(B)
union_size = len(union_set)
return (union_set, union_size)
A = {1,4,-3, "bob"}
B = {2,1,-3,"jill"}
assert union(A,B) == ({-3, 1, 2, 4, 'bob', 'jill'}, 6)
A function inclusion_exclusion that first deterimines $|A|$, $|B|$, $A\cap B$, and $|A\cap B|$, and then uses the inclusion-exclusion formula to determine $|A\cup B|$. Output the tuple $(|A|, |B|, |A\cap B|, |A\cup B|)$.
* **Sample run:** *A = {1, 2, 3}
B = {3, -6, 2, 0}
print inclusion_exclusion(A, B)
print "notice: 3 + 4 - 2 == 5"
* Expected Output: *
(3, 4, 2, 5)
notice: 3 + 4 - 2 == 5
def inclusion_exclusion(A, B):
# inputs: A and B are of type 'set'
# output: a tuple of four integers
union_set = A.union(B)
intersect_set = A.intersection(B)
return (len(A), len(B), len(intersect_set), len(union_set))
# Check Function
A = {1, 2, 3, 4, 5}
B = {0, 2, -6, 5, 8, 9}
assert inclusion_exclusion(A, B) == (5, 6, 2, 9)
The inclusion-exclusion principle says that for three sets $A$, $B$ and $C$,
$$|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|B\cap C|-|C\cap A|+|A\cap B\cap C|$$We will write the following functions to determine $|A\cup B\cup C|$ in two different ways.
Write function union3 that first determines $A\cup B\cup C$ and then evaluates the size of this union. Output the tuple $(A\cup B\cup C, |A\cup B\cup C|)$.
* Sample run: *
A = {1, 2, 3, 4, 5}
B = {0, 2, -6, 5, 8, 9}
C = {2, 10}
union3(A, B, C)
* Expected Output: *
({-6, 0, 1, 2, 3, 4, 5, 8, 9, 10}, 10)
def union3(A, B, C):
# inputs: A, B and C are of type 'set'
# output: a tuple of the type (set, set_length)
union_set = A.union(B).union(C)
return (union_set, len(union_set))
# check Function
A = {1, 2, 4, 5, 10}
B = {5, 2, -6, 5, 8, 9}
C = {2, 10, 13}
assert union3(A,B,C) == ({-6, 1, 2, 4, 5, 8, 9, 10, 13}, 9)
A function inclusion_exclusion3 that first deterimines the sizes of $A$, $B$, $C$ and their mutual intersections, and then uses the inclusion-exclusion principle to determine the size of the union. Output the tuple $(|A\cap B\cap C|, |A\cup B\cup C|)$. Note that for brevity we are asking you to output the intermediate answer just for $A\cap B\cap C$, but you need to calculate all.
* Sample run: *
A = {1, 2, 3, 4, 5}
B = {0, 2, -6, 5, 8, 9}
C = {2, 10}
print inclusion_exclusion3(A, B, C)
* Expected Output: *
(1, 10)
def inclusion_exclusion3(A, B, C):
# inputs: A, B and C are of type 'set'
# output: a tuple of two integers
intersect_set = A.intersection(B).intersection(C)
union_set = A.union(B).union(C)
return (len(intersect_set), len(union_set))
# Check Function
A = {1, 2, 4, 5, 10}
B = {5, 2, -6, 5, 8, 9, 10}
C = {2, 10, 13}
assert inclusion_exclusion3(A,B,C) == (2, 9)