Elementary Set Theory

Elementary Set Theory#

\( \begin{aligned} & \mathbb{N}^{+} &&= \{ 1, 2, 3, \dotsc \} && \text{positive integers} \\ & \mathbb{N} &&= \{ 0, 1, 2, 3, \dotsc \} && \text{natural numbers (nonnegative integers)} \\ & \mathbb{Z}^{ -} &&= \{ -1, -2, -3, \dotsc \} && \text{negative numbers} \\ & \mathbb{Z} &&= \{ \dotsc, -3, -2, -1, 0, 1, 2, 3, \dotsc \} && \text{integers} \\ & \mathbb{E} &&= \{ \dotsc, -4, -2, 0, 2, 4, \dotsc \} && \text{even numbers} \\ & \mathbb{O} &&= \{ \dotsc, -3, -1, 1, 3, \dotsc \} && \text{odd numbers} \\ & \mathbb{P} &&= \{ 2, 3, 5, 7, 11, \dotsc \} && \text{primes} \\ & \mathbb{Q} &&= \{ p/q \mid p, q \in \mathbb{Z}, q \ne 0 \} && \text{rational numbers, expressible as the ratio of two integers} \\ & \mathbb{R} && && \text{real numbers, the continuum} \\ & \mathbb{R - Q} &&= \{ x \mid x \in \mathbb{R} \land x \not\in \mathbb{Q} \} && \text{irrational numbers, not expressible as the ratio of two integers (algebraic vs transcendental)} \\ & \mathbb{I} &&= \{ bi \mid b \in \mathbb{R} \land i = \sqrt{-1} \} && \text{imaginary numbers} \\ & \mathbb{C} &&= \{ a + bi \mid a, b \in \mathbb{R} \land i = \sqrt{-1} \} && \text{complex numbers} \\ \end {aligned} \)

\[ \mathbb{N} \subset \mathbb{Z} \subset \mathbb{Q} \subset \mathbb{R} \subset \mathbb{C} \]

\( \begin{aligned} & \mathbb{Z}[x] && \text{the set of polynomials in } x \text{ with integral coefficients} \\ & \mathbb{Q}[x] && \text{the set of polynomials in } x \text{ with rational coefficients} \\ & \mathbb{R}[x] && \text{the set of polynomials in } x \text{ with real coefficients} \\ & \mathbb{Q}[x, y] && \text{the set of polynomials in } x, y \text{ with rational coefficients} \\ & \mathbb{R}[x, y] && \text{the set of polynomials in } x, y \text{ with real coefficients} \\ \end {aligned} \)

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

Figures#

  • [ w ] Cantor, Georg (1845-1918)

    • [ w ] (1874). On a Property of the Collection of All Real Algebraic Numbers.

  • [ w ] Dedekind, Richard (1831-1916)

  • [ w ] Russell, Bertrand (1872-1970)

  • [ w ] Zermelo, Ernst (1871-1953)

Terms#

  • [ 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 ] Multiplicity

  • [ w ] Multiset

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

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

Acknowledgements#

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