## Elements, sets, and membership

### Elements

• Foundation, building blocks of sets
• Can be anything
• Structured
• Numbers

### Sets

• Collection of elements
• Define : {specify elements}

### Specification

• Explicit
• 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 numbers
Usually, 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
{...} or set({...})

• For empty set
set() 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

S = set()
not S

True
T = {1, 2}
not T

False
len(S)

0
len(T)

2

## Some simple sets

### Sets within Sets

Specify 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 \}$$

### Divisibility

In $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)

set(range(3))

{0, 1, 2}
set(range(2, 5))

{2, 3, 4}
set(range(2, 12, 3))

{2, 5, 8, 11}

## Visualizing Sets

### Venn Diagram

• Developed by John Venn
• Used to visualize Sets, Regions, Elements, Points

### Ven Diagram in Python

!pip install matplotlib_venn

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'));


## 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

S1 = {0, 1}
S2 = set({0, 1})
S3 = {1, 0, 1}
T = {0, 2}

print(S1 == T)

print(S1 == S2)

print(S1 == S3)

False
True
True


#### Inequality

print(S1 != S2)
print(S1 != T)

False
True


#### Disjoint

S1.isdisjoint(T)

False
S1.isdisjoint({2})

True

### Subsets and Supersets

zero = {0}
zplus = {0, 1}
zminus = {0, -1}


#### subset

zminus <= zplus

False
zero.issubset(zminus)

True

#### Strict subset

zplus < zminus

False
zero < zminus

True

#### Superset

zplus >= zminus

False
zplus.issuperset(zero)

True

#### Strict superset

zminus > zminus

False
zplus > zero

True

## 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 Python

Use product function in itertools library

from itertools import product

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

for i in product(Faces, Suits):
print(i)

('K', '♠️')
('K', '♦️')
('Q', '♠️')
('Q', '♦️')
('J', '♠️')
('J', '♦️')


### 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\}$)

• 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 1

De 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.1

Write 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**

A = {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})
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)

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})  )


### Exercise 1.2

Write 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**

A = {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})
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)

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})  )


## Exercise 2

This 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.1

Write 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**

A = {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)})
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):

return (union_a_b, product_a_b_s_t)

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)})   )


### Exercise 2.2

Write 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**

A = {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)})
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)

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)})  \
)