<jupyter_start><jupyter_text>Sets> A summary of "Probability and Statistics in Data Science using Python", offered from UCSD DSE210x- toc: true - badges: true- comments: true- author: <NAME>- categories: [Python, edX, Data_Science, Statistics, Probability]- image: images/venn_example.png  Elements, sets, and membership  Elements- Foundation, building blocks of sets- Can be anything- Structured- Numbers  Sets- Collection of elements- Define : `{specify elements}`  Specification- Explicit    - Coin = {heads, tails}    - Bits = {0, 1}    - Die = {1, 2, 3, 4, 5, 6}- Implicit    - Digits = {0, 1, $\dots$ 9}    - Letters = {a, b, $\dots$, z}    - Days = {Monday, $\dots$, Sunday}- Descriptive     - {4-letter words} = {love, like, dear, $\dots$}  Common Sets| Sets | | Notation || ---- | ----- | ---- || Integers | {$\dots$, -2, -1, 0, 1, 2, $\dots$} | $\mathbb{Z}$ || Naturals | {0, 1, 2, $\dots$ }| $\mathbb{N}$ || Positives | {1, 2, 3, $\dots$} | $\mathbb{P}$ || Rationals | {interger ratio m / n, n $\neq 0$} | $\mathbb{Q}$ || Reals | { whole number } | $\mathbb{R}$ |> Note: $\mathbb{Z}$ comes from german word `Zahl`, meaning numbersUsually, Sets are expressed with Upper case (A, B, etc), and Elements are expressed with Lower case (a, b, etc), as a convention.  Membership- If element $x$ is in a set $A$, it is a member of, or belongs to $A$, denoted $x$ $\in$ $A$.  $$ 0 \in \{0, 1\} \qquad 1 \in \{0, 1\} \qquad \pi \in \mathbb{R} $$ - Equivalently, $A$ contains $x$, written $A$ $\ni$ $x$. $$ \{0, 1\} \ni 0  \qquad \{0, 1\} \ni 1 \qquad \mathbb{R} \in \pi $$- If $x$ is not in $A$, then $x$ is not a member, or does not belong to $A$, denoted $x$ $\notin$ $A$.- Equivalently, $A$ does not contain $x$, $A$ $\not\owns$ $x$.  Doesn't Matter- Order: {0, 1} = {1, 0}- Repetition: {0, 1} = {0, 1, 1, 1}If you want to consider:- Order matters: use ordered tuples ((0, 1) $\neq$ (1, 0))- Repetition matters: use  multisets or bags  Special Sets- Empty set: contains no elements ($\emptyset$ or {}, $\forall x, x \notin \emptyset$)> Note: $\forall$ means 'all', or 'every'- Universal set: all possible elements ($\Omega$, $\forall x, x \in \Omega$)- $\Omega$ lets us consider only relevant elements. $\Omega$ can be $\mathbb{Z}$ (the integer) or "prime number"- $\Omega$ depends on application (temperature, text, etc...)- $\emptyset$ is only one in whole case, this is the set with no elements.  Set Definition in python- Define a set```python{...} or set({...})```- For empty set```pythonset() or set({})```> Note: In python, `{}` is not a empty set, it is dictionary.  Membership in python- $\in \quad \rightarrow$ `in`- $\notin \quad \rightarrow$ `not in`  Testing if Empty, Size<jupyter_code># Empty set
S = set()
not S
# Set
T = {1, 2}
not T
len(S)
len(T)<jupyter_output><empty_output><jupyter_text>Some simple sets  Sets within SetsSpecify a set within a universe, or any other set,$$ \{x \in A \vert \dots \} $$means elements $x$ in $A$ such that. Sometimes it expresses like this,$$ \{x \in A : \dots \} $$For example,$$ \mathbb{N} = \{x \in \mathbb{Z} \vert x \geq 0 \} $$$$ \mathbb{P} = \{x \in \mathbb{N} \vert x \gt 0 \} $$It usually express the solution to equations,$$ \{ x \in \mathbb{R} \vert x^2 \geq 0\} = \mathbb{R} $$$$ \{ x \in \mathbb{R} : x^2 = 1 \} = \{-1, 1\} $$$$ \{ x \in \mathbb{R} \vert x^2 = 0 \} = \{0\} $$> Note: a single-element set is called **singleton**$$ \{ x \in \mathbb{R} \vert x^2 = -1 \} = \emptyset $$$$ \{ x \in \mathbb{C} \vert x^2 = -1 \} = \{i, -i\} $$  Integer intervals$$ \{m, \dots n\} = \{i \in \mathbb{Z} \vert m \leq i \leq n \} $$It is a set of integers from $m$ to $n$, inclusively.$$ \{3, \dots, 5\} = \{i \in \mathbb{Z} \vert 3 \leq i \leq 5 \} = \{3, 4, 5\} $$ $$ \{3, \dots, 4\} = \{i \in \mathbb{Z} \vert 3 \leq i \leq 4 \} = \{3, 4\} $$$$ \{3, \dots, 3\} = \{i \in \mathbb{Z} \vert 3 \leq i \leq 3 \} = \{3\} $$$$ \{3, \dots, 2\} = \{i \in \mathbb{Z} \vert 3 \leq i \leq 2 \} = \emptyset $$For convention, $[n] = \{1, \dots, n\}$  Real intervals$$[a, b] \qquad \rightarrow \{x \in \mathbb{R} \vert a \leq x \leq b \} $$$$(a, b) \qquad \rightarrow \{x \in \mathbb{R} \vert a \lt x \lt b \} $$$$[a, b) \qquad \rightarrow \{x \in \mathbb{R} \vert a \leq x \lt b \} $$$$(a, b] \qquad \rightarrow \{x \in \mathbb{R} \vert a \lt x \leq b \} $$  DivisibilityIn $m, n \in \mathbb{Z}$, if $n = c \dot m$ for some $c \in \mathbb{Z}$, we say that n is a multiple of m, or $m$ divides $n$, and write $m \vert n$If no such $c$ exists, $m$ does not divide $n$, or $n$ is not a multiple of $m$ denoted $m \not\vert n$.For example,$$\text{There is no } c \in \mathbb{Z} \quad \text{such that} \quad 4 = c \cdot 3 \quad \rightarrow 3 \not\vert 4 $$$$ 0 \not\vert n \quad \text{for any } n \neq 0 $$  Set of Multiples- Integer multiples of $m$$$ m \in \mathbb{Z} \qquad {}_m\mathbb{Z} \overset{\underset{\mathrm{def}}{}}{=} \{i \in \mathbb{Z} : m \vert i \}$$    - Example$$ \begin{aligned} {}_2\mathbb{Z} &= \{\dots, -4, -2, 0, 2, 4, \dots \} \overset{\underset{\mathrm{def}}{}}{=} \mathbb{E} \quad \rightarrow \text{even number} \\ {}_1\mathbb{Z} &= \{\dots , -2, -1, 0, 1, 2, \dots \} = \mathbb{Z} \\ {}_0\mathbb{Z} &= \{0\} \end{aligned} $$- Multiples of $m$ in $\{1..n\}$$$ m \in \mathbb{Z}, n \in \mathbb{P} \qquad {}_m[n] \overset{\underset{\mathrm{def}}{}}{=} \{i \in [n] : m \vert i\}$$    - Example    $$ \begin{aligned} {}_3[13] &= \{i \in \{1, \dots, 13\} : 3 \vert i \} = \{3, 6, 9, 12\} \\{}_7[13] &= \{7\} \\ {}_1[13] &= [13] \\ {}_{14}[13] &= {}_0[13] = \emptyset \end{aligned} $$  Intervals, Multiples in python$\{0,\dots, n-1\} \quad \rightarrow$ `range(n)`$\{m, \dots, n-1\} \quad \rightarrow$ `range(m, n)`$\{m, m+d, m+2d, \dots \} \leq n - 1 \quad \rightarrow$ `range(m, n, d)`<jupyter_code>set(range(3))
set(range(2, 5))
set(range(2, 12, 3))<jupyter_output><empty_output><jupyter_text>Visualizing Sets  Venn Diagram- Developed by <NAME>- Used to visualize Sets, Regions, Elements, Points  Ven Diagram in Python```python!pip install matplotlib_venn```<jupyter_code>import matplotlib.pyplot as plt
import matplotlib_venn as venn

S = {1, 2, 3}
T = {0, 2, -1, 5}

venn.venn2([S, T], set_labels=('S', 'T'));
U = { 10, 8, 0, 2, -1}

venn.venn3([S, T, U], set_labels=('S', 'T', 'U'));<jupyter_output><empty_output><jupyter_text>Set Relations  Relation Types- Set $A$ and $B$ are equal, denoted $A = B$, if they have exactly the same elements$$\{0, 1\} = \{1, 0\}$$- If $A$ and $B$ are not equal, they are **different**, denoted $A \neq B$$$\{0, 1\} \neq \{1, 2\}$$- **All** elements must be identical: $\{1, 2, 4\} = \{4, 1, 2\}$- **One different** element enough: $\{1, 2, 4\} \neq \{1, 2, 4, 8\}$  Intersection- Two sets **intersect** if they share at least one common element. Mathematically, it can express like this,$$ \exists x, \quad x \in A \wedge x \in B $$- Two sets are **disjoint** if they share no elements.$$ \neg \exists x, \quad x \in A \wedge x \in B $$- $\emptyset$ disjoint from any set- Non-empty $\Omega$ intersects every set- A set intersects itself if and only if it is not-empty.- Several sets    - intersect if all share a common element    - mutually disjoint if every two are disjoint  Subsets- It generalizes $\leq$- If every element in $A$ is also in $B$, then $A$ is a **subset of** $B$, denoted $A \subseteq B$$$ \{0\} \subseteq \{0, 1\} \\ \{0\} \subseteq \{0\}$$- Equivalently, $B$ is a **superset** of, or contains, $A$, denoted $B \supseteq A$$$ \{0, 1\} \supseteq \{0\} $$- If $A$ has an element that's not in $B$, then $A$ is **not a subset** of $B$, denoted $A \not \subseteq B$, or $B \not \supseteq A$$$ \{0, 1\} \not \subseteq \{1, 2\} \\ \{1, 2\} \not \supseteq \{0, 1\} $$- $\mathbb{P} \subseteq \mathbb{N} \subseteq \mathbb{Z} \subseteq \mathbb{Q} \subseteq \mathbb{R}$- $\emptyset \subseteq A \subseteq A \subseteq \Omega$- (transitivity) $A \subseteq B$ and  $B \subseteq C \rightarrow A \subseteq C$> Note: $\subseteq$ is called **transitive**- $A \subseteq B$ and $B \subseteq A \rightarrow A = B$  Strict Subsets- It generalizes $\gt$- If $A \subseteq B$ and $A \neq B$, $A$ is a **strict subset** of $B$, denoted $A \subset B$ and $B$ is a **strict superset** of $A$, denoted $B \supset A$.$$ \{0\} \subset \{0, 1\} \\ \{0, 1\} \supset \{0\} $$- If $A$ is not a strict subset of $B$, we write $A \not \subset B$ or $B \not \supset A$    - Reason: $ A \not \subseteq B$ , $A = B$  Belongs to vs. Subset of- $\in$ (Belongs to)    - Relation between an element and a set    - $x \in A$: element $x$ belongs to, or is contained in, set $A$     - ex) $\{0, 1\}$ has two elements: 0 and 1     $$ \rightarrow 0 \in \{0, 1\} , \{0\} \not \in \{0, 1\} $$     - $\subseteq$    - Relation between two sets    - $A \subseteq B$ : $A$ is a subset of set $B$    - ex) $\{0, 1\}$ has two elements: 0 and 1     $$ \{0\} \subseteq \{0, 1\} $$    - 0 is an element of $\{0, 1\}$, but 0 is not a set. ($0 \not \subseteq \{0, 1\}$)  Set relations in python Equality<jupyter_code>S1 = {0, 1}
S2 = set({0, 1})
S3 = {1, 0, 1}
T = {0, 2}
print(S1 == T)

print(S1 == S2)

print(S1 == S3)<jupyter_output>False
True
True<jupyter_text>Inequality<jupyter_code>print(S1 != S2)
print(S1 != T)<jupyter_output>False
True<jupyter_text>Disjoint<jupyter_code>S1.isdisjoint(T)
S1.isdisjoint({2})<jupyter_output><empty_output><jupyter_text>Subsets and Supersets<jupyter_code>zero = {0}
zplus = {0, 1}
zminus = {0, -1}<jupyter_output><empty_output><jupyter_text>subset<jupyter_code>zminus <= zplus
zero.issubset(zminus)<jupyter_output><empty_output><jupyter_text>Strict subset<jupyter_code>zplus < zminus
zero < zminus<jupyter_output><empty_output><jupyter_text>Superset<jupyter_code>zplus >= zminus
zplus.issuperset(zero)<jupyter_output><empty_output><jupyter_text>Strict superset<jupyter_code>zminus > zminus
zplus > zero<jupyter_output><empty_output><jupyter_text>Tuples and products  Tuples and Ordered Pairs- Set    - Order and repetition do not matter$$ \{a, b, c\} = \{b, c, a\} $$- Tuple    - Both order and repetition matter$$ (a, b, c) \neq (b, c, a) \\ (a, a, a) \neq (a) $$- $n$-tuple    - Tuple with $n$ elements$$ (a_1, a_2, \dots, a_n) $$- 2-tuple    - Ordered pair$$ (3, 7) $$  Cartesian Products- The cartesian product of $A$ and $B$ is the set $A \times B$ of ordered pairs $(a, b)$ where $a \in A$ and $b \in B$. Mathematically,$$ A \times B = \{(a, b): a \in A, b \in B\} $$- $A \times A = A^2$- $\mathbb{R}^2 = \{(x, y): x, y \in \mathbb{R}\} \quad \rightarrow$ Cartesian Plane- $A, B \subseteq \mathbb{R} \quad \rightarrow A \times B \subseteq \mathbb{R}^2$    - For example,$$ A = [0, 2], B=[1, 4] \\ A \times B = \{(x, y): x \in [0, 2], y \in [1, 4]\} $$  Discrete Sets- Similar, simpler- For example,$$ \begin{aligned} \{a, b\} \times \{1, 2, 3\} &= \{(x, y): x \in \{a, b\}, y \in \{1, 2, 3\}\} \\ &= \{ (a, 1), (a, 2), (a, 3), (b, 1), (b, 2), (b, 3)\} \end{aligned}$$- 1st coordinate: vertical, 2nd coordinate: horizontal  Identities- $A \times \emptyset = \emptyset \times A = \emptyset$- $A \times (B \cup C) = A \times B \cup A \times C$- $A \times (B \cap C) = A \times B \cap A \times C$- $A \times (B - C) = A \times B - A \times C$  Cartesian products in PythonUse **product** function in **itertools** library<jupyter_code>from itertools import product

Faces = set({'J', 'Q', 'K'})
Suits = {'\u2666\uFE0F', '\u2660\uFE0F'}

for i in product(Faces, Suits):
    print(i)<jupyter_output>('K', '♠️')
('K', '♦️')
('Q', '♠️')
('Q', '♦️')
('J', '♠️')
('J', '♦️')<jupyter_text>Russell's Paradox  Sets in Sets- Sets can be elements- Every set is a subset of itself$$ \{0\} \subseteq \{0\} $$- Can a set belong to (be an element of) itself? $ \rightarrow S \in S$    - Typically, sets do not belong to themselves $\quad \{0\} \not \in \{0\} , \emptyset \not \in \emptyset $        - But some sets do belong to themselves! (infinite recursion)        - Some sets $\in$ themselves, others don't ($\{0\}$)  Russell's Paradox- Define a set that cannot exist- For example,$$ R = \{\text{sets that don't belong to themselves}\} = \{S: S \not \in S\} $$- If    - $R \in R \quad \rightarrow R \not \in R$ (contradiciton)    - $R \not \in R \quad \rightarrow R \in R$ (contradiction)    - If R existed, then both $R \in R$ and $R \not \in R$ would hold- R defined but cannot exist!!- ex) The set that contains only the empty set $\emptyset$ is not empty  Exercise 1De Morgan's first law states the following for any two sets $A$ and $B$$$(A\cup B)^c = A^c\cap B^c$$In the following two exercises we calculate $(A\cup B)^c$ in two different ways. Both functions must take $A$, $B$ and the universal set $U$ as their inputs.  Exercise 1.1Write the function **complement_of_union** that first determines $A\cup B$ and then evaluates the complement of this set. Output the tuple: $\begin{pmatrix}A\cup B,\, (A\cup B)^c\end{pmatrix}$. **Code**```pythonA = {1, 2, 3}B = {3, -6, 2, 0}U = {-10, -9, -8, -7, -6, 0, 1, 2, 3, 4}complement_of_union(A, B, U)``` **Output**```({-6, 0, 1, 2, 3}, {-10, -9, -8, -7, 4})```<jupyter_code>def complement_of_union(A, B, U):
    # inputs: A, B and U are of type 'set'
    # output: a tuple of the type (set, set)
    
    union = A.union(B)
    complement_union = U.difference(union)
    return (union, complement_union)
# Check Function

A = {1, 2, 3, 4, 5}
B = {0, 2, -6, 5, 8, 9}
U = A|B|{-3, 7, 10, -4}
assert( complement_of_union(A, B, U) == ({-6, 0, 1, 2, 3, 4, 5, 8, 9}, {-4, -3, 7, 10})  )<jupyter_output><empty_output><jupyter_text>Exercise 1.2Write the function **intersection_of_complements** that first determines $A^c$ and $B^c$ and then evaluates the intersection of their complements. Output the tuple: $\begin{pmatrix}A^c, \,  A^c\cap B^c\end{pmatrix}$ **Code**```pythonA = {1, 2, 3}B = {3, -6, 2, 0}U = {-10, -9, -8, -7, -6, 0, 1, 2, 3, 4}intersection_of_complements(A, B, U)``` **Output**```({-10, -9, -8, -7, -6, 0, 4}, {-10, -9, -8, -7, 4})```<jupyter_code>def intersection_of_complements(A, B, U):
    # inputs: A, B and U are of type 'set'
    # output: a tuple of the form (set, set)
    
    complement_a = U.difference(A)
    complement_b = U.difference(B)
    complement_intersect = complement_a.intersection(complement_b)
    return (complement_a, complement_intersect)
# Check Function

A = {1, 2, 3, 4, 5}
B = {0, 2, -6, 5, 8, 9}
U = A|B|{-3, 7, 10, -4}
assert(  intersection_of_complements(A, B, U) == ({-6, -4, -3, 0, 7, 8, 9, 10}, {-4, -3, 7, 10})  )<jupyter_output><empty_output><jupyter_text>Exercise 2This problem illustrates a property of cartesian products of unions of two or more sets. For four sets $A$, $B$, $S$ and $T$, the following holds:$$(A\cup B)\times(S\cup T) = (A\times S)\cup(A\times T)\cup(B\times S)\cup(B\times T)$$Write the following functions to determine $(A\cup B)\times(S\cup T)$ in two different ways.  Exercies 2.1Write function **product_of_unions** that first determines $(A\cup B)$ and $(S\cup T)$ and then evaluates the cartesian products of these unions. Output the tuple $\begin{pmatrix}(A\cup B),\,  (A\cup B)\times(S\cup T)\end{pmatrix}$. **Code**```pythonA = {1, 2}B = {1, 3}S = {-1, 0}T = {0, 10}product_of_unions(A, B, S, T)``` **Output**```({1, 2, 3}, {(1, -1),  (1, 0),  (1, 10),  (2, -1),  (2, 0),  (2, 10),  (3, -1),  (3, 0),  (3, 10)})```<jupyter_code>def product_of_unions(A, B, S, T):
    # inputs: A, B, S and T are sets
    # output: a tuple of the type (set, set)
    
    union_a_b = A.union(B)
    union_s_t = S.union(T)
    
    product_a_b_s_t = set()
    
    for i in product(union_a_b, union_s_t):
        product_a_b_s_t.add(i)
        
    return (union_a_b, product_a_b_s_t)
# Check Function

A = {5}
B = {5, 6}
S = {-1, 0, 1}
T = {1, 2}
assert( product_of_unions(A, B, S, T) == \
       ({5, 6}, {(5, -1), (5, 0), (5, 1), (5, 2), (6, -1), (6, 0), (6, 1), (6, 2)})   )<jupyter_output><empty_output><jupyter_text>Exercise 2.2Write a function **union_of_products** that first determines $(A\times S)$ and the other three cartesian products that appear on the right hand side of the identity above, then evaluates the union of these cartesian products. Output the tuple $\begin{pmatrix}(A\times S),\,  (A\times S)\cup(A\times T)\cup(B\times S)\cup(B\times T)\end{pmatrix}$. **Code**```pythonA = {1, 2}B = {1, 3}S = {-1, 0}T = {0, 10}union_of_products(A, B, S, T)``` **Output**```({(1, -1), (1, 0), (2, -1), (2, 0)}, {(1, -1),  (1, 0),  (1, 10),  (2, -1),  (2, 0),  (2, 10),  (3, -1),  (3, 0),  (3, 10)})```<jupyter_code>def union_of_products(A, B, S, T):
    # inputs: A, B, S and T are sets
    # output: a tuple of the type (set, set)
    product_a_s = set(x for x in product(A, S))
    product_a_t = set(x for x in product(A, T))
    product_b_s = set(x for x in product(B, S))
    product_b_t = set(x for x in product(B, T))
    
    union_all = product_a_s.union(product_a_t).union(product_b_s).union(product_b_t)
    
    return (product_a_s, union_all)
# Check Function

A = {5}
B = {5, 6}
S = {-1, 0, 1}
T = {1, 2}
assert( union_of_products(A, B, S, T) == \
        ({(5, -1), (5, 0), (5, 1)}, \
         {(5, -1), (5, 0), (5, 1), (5, 2), (6, -1), (6, 0), (6, 1), (6, 2)})  \
      )<jupyter_output><empty_output>
StarcoderdataJupyterStructuredCleanDedup