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 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', '♦️')

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 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):
        product_a_b_s_t.add(i)
        
    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)})  \
      )