$\mathbb{R}$ and $\mathbb{C}$ are uncountable (Cantor's diagonal argument).
$\mathbb{Q}$ is countable — using the table $p/q$ traversed by diagonals.
Python — enumerate Z (bijection with N)def enumerate_integers(n):
# 0,1,-1,2,-2,3,-3,...
return 0 if n == 0 else ((n + 1) // 2) * (1 if n % 2 else -1)
print([enumerate_integers(k) for k in range(8)])
Output[0, 1, -1, 2, -2, 3, -3, 4]
Python — table p/q for Qfrom fractions import Fraction
table = [[Fraction(p, q) for q in range(1, 6)] for p in range(1, 6)]
for row in table:
print(row)
5 / 13
Venn Diagram
Sets can be represented visually using Venn diagrams. Below: $A \cap B$ (orange region).
Python — quick Venn with matplotlib_venn# pip install matplotlib matplotlib_venn
from matplotlib_venn import venn2
import matplotlib.pyplot as plt
A = {1, 2, 3, 4}
B = {3, 4, 5, 6}
venn2([A, B], set_labels=('A', 'B'))
plt.show()
6 / 13
Subset
A subset ($\subset$, $\subseteq$) is a portion of a set. $A \subseteq B$ means every element of $A$ is in $B$.
Python — slice / subset testS = [2, 3, 4, 7, 10]
print(S[2:4]) # [4, 7]
A, B = {4, 7}, set(S)
print(A.issubset(B)) # True
print(A <= B, A < B) # True True
SymPyfrom sympy import FiniteSet
A = FiniteSet(4, 7)
B = FiniteSet(2, 3, 4, 7, 10)
A.is_subset(B) # True
Power Set
The power set $\mathcal{P}(S)$ is the set of all subsets of $S$. If $|S| = n$, then $|\mathcal{P}(S)| = 2^n$.
Python — power setfrom itertools import chain, combinations
def powerset(s):
s = list(s)
return list(chain.from_iterable(combinations(s, r) for r in range(len(s)+1)))
print(powerset({2, 3, 4, 7, 10})) # 2**5 = 32 subsets
A set partition of $S$ is a collection of disjoint subsets of $S$ whose union is $S$.
Python — partition by chunks of size ndef partition(seq, n):
return [list(seq[i:i+n]) for i in range(0, len(seq), n)]
print(partition(range(1, 19), 3))
A cover is the same idea but the subsets may overlap:
Python — overlapping windows (cover)def cover(seq, n, step):
return [list(seq[i:i+n]) for i in range(0, len(seq)-n+1, step)]
print(cover(range(1, 19), 4, 2))
A dataset is a list of structured associations of attributes and data. In Python, this is naturally a list of dictionaries — or a pandas.DataFrame.
Python — list of dictstitanic = [
{"class": "1st", "age": 29, "sex": "female", "survived": True},
{"class": "1st", "age": 2, "sex": "female", "survived": True},
{"class": "1st", "age": 30, "sex": "male", "survived": False},
{"class": "3rd", "age": 27, "sex": "male", "survived": False},
{"class": "3rd", "age": 29, "sex": "male", "survived": False},
]
# survivors only
print([row for row in titanic if row["survived"]])
Python — with pandas# pip install pandas
import pandas as pd
df = pd.DataFrame(titanic)
print(df.head())
print(df.groupby("class")["survived"].mean())
The Mathematica ExampleData["Dataset","Titanic"] idea translates directly to a
Python DataFrame — same tabular structure, same filtering, much faster on real data.
10 / 13
Empty Set
Often, there is a lot of confusion about the empty set $\varnothing = \{\}$.
What is the size of $\varnothing$? What about $\{\varnothing, \{\varnothing\}\}$?
What is the power set of $\varnothing$? Of the power set of $\varnothing$?
What is the Cartesian product of $\varnothing$ with any set?
Python — power setsdef powerset(s):
s = list(s)
return [set(combinations(s, r)[0]) if False else c
for r in range(len(s)+1)
for c in combinations(s, r)]
# P(∅) = {∅}
print(list(powerset(set()))) # [()]
# P(P(∅)) = {∅, {∅}}
print(list(powerset(powerset(set())))) # [(), ((),)]
Python — Cartesian product with ∅print(list(product(set(), {2, 4, 6, 8}))) # [] → ∅ × A = ∅
11 / 13
Summary
Sets are the basis of discrete structures.
Important sets include $\varnothing,\; \mathbb{Z},\; \mathbb{N},\; \mathbb{Q},\; \mathbb{R}$ and $\mathbb{C}$.
Use Venn diagrams to easily visualize sets and their interactions.
Other basic discrete structures include lists, tuples, dictionaries (associations) and datasets.
In Python, the natural set tools are the built-in set, frozenset, dict, and SymPy's FiniteSet / ProductSet for symbolic work.
Now that sets are clearly explained, it is time to do computations on them to fully utilize their versatility.
Python — key imports for this lessonfrom itertools import chain, combinations, product
from fractions import Fraction
from sympy import (FiniteSet, EmptySet, Integers, Naturals0,
Rationals, Reals, Complexes,
Interval, Union, Intersection, Complement, ProductSet)