Elementary Set Theory

Elementary Set Theory#

Contents#

[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

  1. Prove \(S_1\subseteq S_2\)

  2. Prove \(S_2\subseteq S_1\)

[FINITE SET]

  • \(\{0, 1\}^n\) the set of \(n\)-bit binary strings

[INFINITE SET]

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

Acknowledgements#

2013 Klein, Philip N. Coding the Matrix: Linear Algebra through Computer Science Applications. Newtonian Press.

Contents