Elementary Set Theory#
[SET]
A set is a collection of mathematical objects called elements (or members, points, etc.).
Curly braces are used to indicate a set specified by explicitly enumerating its elements.
\( \{1,2,3,4\} \)
print( {1,2,3,4} )
print( len({1,2,3,4}))
print(type({1,2,3,4}))
{1, 2, 3, 4}
4
<class 'set'>
\( \{\heartsuit,\spadesuit,\clubsuit,\diamondsuit\} \)
s = {
'♡', # '\u2661', # white heart
'♠', # '\u2660', # black spade
'♣', # '\u2663', # black club
'♢', # '\u2662', # white diamond
}
print( s )
print( len(s))
print(type(s))
{'♠', '♢', '♣', '♡'}
4
<class 'set'>
Each element of some set is considered to occur at most once (i.e., repetition does not matter).
\( \{1,1,2,2,3,3,4,4\} =\{1,2,3,4\} \)
assert {1,1,2,2,3,3,4,4} == {1,2,3,4}
print( {1,1,2,2,3,3,4,4} )
print( len({1,1,2,2,3,3,4,4}))
print(type({1,1,2,2,3,3,4,4}))
{1, 2, 3, 4}
4
<class 'set'>
\( \{\heartsuit,\heartsuit,\heartsuit,\spadesuit,\clubsuit,\diamondsuit\} =\{\heartsuit,\spadesuit,\clubsuit,\diamondsuit\} \)
assert {'♡','♡','♡','♠','♣','♢'} == {'♡','♠','♣','♢'}
print( {'♡','♡','♡','♠','♣','♢'})
print( len({'♡','♡','♡','♠','♣','♢'}))
print(type({'♡','♡','♡','♠','♣','♢'}))
{'♠', '♢', '♣', '♡'}
4
<class 'set'>
A set does not impose an order onto its elements (i.e., order does not matter).
\( \{\heartsuit,\spadesuit,\clubsuit,\diamondsuit\} =\{\clubsuit,\diamondsuit,\heartsuit,\spadesuit\} \)
assert {'♡','♠','♣','♢'} == {'♣','♢','♡','♠'}
[SET CONTAINS ELEMENT]
The symbol \(\in\) is used to indicate that an object belongs to a set (equivalently, that the set contains the object).
\(1\in\{1,2,3,4\}\)
print(1 in {1,2,3,4})
print(2 in {1,2,3,4})
print(3 in {1,2,3,4})
print(4 in {1,2,3,4})
print(5 in {1,2,3,4})
True
True
True
True
False
\(\heartsuit\in\{\heartsuit,\spadesuit,\clubsuit,\diamondsuit\}\)
print('♡' in {'♡','♠','♣','♢'})
print('♠' in {'♡','♠','♣','♢'})
print('♣' in {'♡','♠','♣','♢'})
print('♢' in {'♡','♠','♣','♢'})
print('♦' in {'♡','♠','♣','♢'})
True
True
True
True
False
[SET CONTAINS OTHER SET]
One set \(S_1\) is contained in another set \(S_2\) if every element of \(S_1\) is an element of \(S_2\).
\( S_1\subseteq S_2 \)
[SET EQUALITY]
Two sets \(S_1\) and \(S_2\) are equal if and only if they contain the same elements. In other words, two sets \(S_1\) and \(S_2\) are equal if and only if all the elements that belong to \(S_1\) belong to \(S_2\) and all the elements that belong to \(S_2\) belong to \(S_1\).
The equality of two sets \(S_1\) and \(S_2\) is written \(S_1=S_2\).
Proof procedure
Prove \(S_1\subseteq S_2\)
Prove \(S_2\subseteq S_1\)
[FINITE SET]
\(\{0, 1\}^n\) the set of \(n\)-bit binary strings
[INFINITE SET]
Examples
\(\mathbb{N}\) the set of natural numbers
\(\mathbb{N} \cup \{0\} \overset{\text{def}}= \{0, 1, 2, ...\}\) the set of natural numbers including zero
\(\mathbb{N} - \{0\} \overset{\text{def}}= \{1, 2, ...\}\) the set of natural numbers excluding zero
\(\mathbb{Z} \overset{\text{def}}= \{..., -2, -1, 0, 1, 2, ...\}\) the set of integers
\(\mathbb{Z}^+\) the set of positive integers (equivalent to \(\mathbb{N} - \{0\}\))
\(\mathbb{Z}^+ \cup \{0\}\) the set of nonnegative integers (equivalent to \(\mathbb{N} \cup \{0\}\))
\(\mathbb{E} \overset{\text{def}}= \{..., -2, 0, 2 ...\}\) the set of even integers
\(\mathbb{Q} \overset{\text{def}}= \{\frac{p}{q} : p, q \in \mathbb{Z}, q \ne 0\}\) the set of rational numbers
\(\mathbb{R}\) the set of real numbers
\(\mathbb{R}^-\) the set of negative numbers
\(\mathbb{C} \overset{\text{def}}= \{a + bi : a, b \in \mathbb{R}, i \overset{\text{def}}= \sqrt{-1}\}\) the set of complex numbers
[SET CARDINALITY]
If a set \(S\) is finite, the cardinality of \(S\) is the number of elements that belong to \(S\).
The cardinality of \(S\) is written \(|S|\).
[CARTESIAN PRODUCT]
The Cartesian product of two sets \(A\) and \(B\) is the set of all pairs \((a,b)\) where \(a\in A\) and \(b\in B\).
The Cartesian product of two sets \(A\) and \(B\) is written \(A\times B\).
[Example]
\( \begin{aligned} A&=\{1,2,3\}\\ B&=\{\heartsuit,\spadesuit,\clubsuit,\diamondsuit\}\\ A\times B&=\{(1,\heartsuit),(2,\heartsuit),(3,\heartsuit),(1,\spadesuit),(2,\spadesuit),(3,\spadesuit),(1,\clubsuit),(2,\clubsuit),(3,\clubsuit),(1,\diamondsuit),(2,\diamondsuit),(3,\diamondsuit)\}\\ |A|&=3\\ |B|&=4\\ |A\times B|&=12\\ \end{aligned} \)
from itertools import product
ab = list(product((1,2,3),('♡','♠','♣','♢')))
print( ab )
print(len(ab))
[(1, '♡'), (1, '♠'), (1, '♣'), (1, '♢'), (2, '♡'), (2, '♠'), (2, '♣'), (2, '♢'), (3, '♡'), (3, '♠'), (3, '♣'), (3, '♢')]
12
[PROPOSITION]
For finite sets \(A\) and \(B\), \(|A\times B|=|A|\times|B|\).
[Example]
\( \begin{aligned} A&=\{A,2,3,4,5,6,7,8,9,10,J,Q,K\}\\ B&=\{\heartsuit,\spadesuit,\clubsuit,\diamondsuit\}\\ |A\times B|&=|A|\times|B|=13\times4=52\\ \end{aligned} \)
Figures#
Terms#
[ s ] Category Theory
[ s ] Continuity and Infinitesimals
[ s ] Continuum Hypothesis
[ s ] Large Cardinals and Determinacy
[ s ] Large Cardinals and Independence
[ s ] Set Theory
[ s ] Set Theory, Alternative Axiomatic
[ s ] Set Theory, Early Development
[ s ] Set Theory, Zermelo’s Axiomatization
[ w ] Algebra of Sets
[ w ] Axiom of Choice
[ w ] Burali-Forti Paradox
[ w ] Cantor’s Diagonal Argument
[ w ] Cantor’s Paradise
[ w ] Cantor’s Paradox
[ w ] Cardinal Number
[ w ] Cartesian Product
[ w ] Class
[ w ] Complement of a Set
[ w ] Dedekind-Infinite Set
[ w ] Disjoint Sets
[ w ] Disjoint Union
[ w ] Element
[ w ] Empty Set
[ w ] Equinumerosity
[ w ] Equivalence Class
[ w ] Family of Sets
[ w ] Finite Set
[ w ] Infinite Set
[ w ] Intersection
[ w ] Large Cardinal Property
[ w ] Naive Set Theory
[ w ] Paradoxes of Set Theory
[ w ] Partition of a Set
[ w ] Power Set
[ w ] Russell’s Paradox
[ w ] Set
[ w ] Set Builder Notation
[ w ] Set Theory
[ w ] Singleton
[ w ] Subset
[ w ] Symmetric Difference
[ w ] Transfinite Number
[ w ] Union
[ w ] Universe
[ w ] Zermelo-Fraenkel Set Theory
Bibliography#
Klein, Philip N. (2013). Coding the Matrix: Linear Algebra through Computer Science Applications. 1st Ed. Newtonian Press.