Elementary Set Theory

A set can be ANY collection of objects.

The notation for specifying a set is:

S = { x | expression about x }

Another way to state this is that S is the set of objects x which make the expression about x true.

Example: S = { x | x – 4 > 0 }

In [20]:
possible_values = [1,2,3,4,5,6,7,8,9,10,11]
S = [x for x in possible_values if x - 4 > 0]
S
Out[20]:
[5, 6, 7, 8, 9, 10, 11]

This of course is pretty universal, let’s try with some non-trivial set of programming language objects.

In [19]:
class O(object):
    ''' Some kind of pythonic nonsense, theres no toString() method to override!'''
    class __metaclass__(type):
        def __repr__(self):
            return "O"
    def __init__(self,t):
        self.t = t
    def getType(self):
        return self.t
U = [O(1),O(2),O(3),O(1)]
S = [x for x in U if x.getType() == 1]
S
Out[19]:
[<O at 0x7fc48b47f910>, <O at 0x7fc48b47e990>]

A set with no elements is denoted by $\emptyset$, and is known as the empty set. Elements within a set are usually selected from the universal set and S is derived or collected from that set via the expression for the $x^{n}$ of S. In this case if x.getType() == 1. The universal set is usually denoted by $U$.

The symbol $\in$ is understood to mean belongs to, or another way to say it is is a member of or in programming speak in array. The symbol $\notin$ denotes that some object is NOT a member of the set.

For instance we can say that $S_1\ =\ \{\ x\ |\ x.type\ =\ 1\ \}$ and $S_2\ =\ \{\ x\ |\ x\ \notin\ S_1\ \}$ where x $\in U$.

Where $U\ =\ \{\ O_1,O_2,…O_n\ \}$ and $O_n$ is an instance of class $O$.

In [27]:
S_1 = [x for x in U if x.getType() == 1]
S_2 = [x for x in U if not x in S_1]
[S_1,S_2]
Out[27]:
[[<O at 0x7fc48b47f910>, <O at 0x7fc48b47e990>],
 [<O at 0x7fc48b47fcd0>, <O at 0x7fc48b47e890>]]

Bounded Sets

Let $S$ denote a non-empty set containing real numbers $x$. This set would be bounded if one can find a number $b$ such that for each $x \in S$, one can find that $x \leq b$ the $b$ is called the upper bound of $S$.

Let $b = 8$ so that $S\ =\ \{\ x\ |\ x\ \in\ U,\ x\ \leq b\ \}$ where $U\ =\ \{\ x\ |\ x\ \leq\ 10,\ x\ \geq\ 1,\ x\ \in\ Z\ \}$. Here $Z$ is all integers from 0 to infinity. We haven’t goen to infinity, just 10.

In [1]:
U = [1,2,3,4,5,6,7,8,9,10]
b = 8
S = [x for x in U if x <= b]
S
Out[1]:
[1, 2, 3, 4, 5, 6, 7, 8]

$\ell$ will denote a lower bound, that is an expression of x >= b.

In [2]:
U = [1,2,3,4,5,6,7,8,9,10]
ell = 5
S = [x for x in U if x >= ell]
S
Out[2]:
[5, 6, 7, 8, 9, 10]

Let $B$ and $C$ denote the sets

$B\ =\ \{\ x\ |\ x\ =\ b\ of\ S\ \}$ and $C\ =\ \{\ x\ =\ \ell\ of\ S\ \}$ then

In [6]:
U = [1,2,3,4,5,6,7,8,9,10]
ell = 5
b = 8
S = [x for x in U if x >= ell and x <= b]
B = [x for x in U if x >= b]
C = [x for x in U if x <= ell]
[S,B,C]
Out[6]:
[[5, 6, 7, 8], [8, 9, 10], [1, 2, 3, 4, 5]]

A set which is bounded above and below (which $S$ is in the above example) is called a bounded set.

There are some well known sets that must, in general characteristics, be memorized.

  1. The set of natural numbers ……….. $N\ =\ \ \{\ 1,2,3,…\ \}$
  2. The set of integers ……………………. $Z\ =\ \ \{\ …,-3,-2,-1,0,1,2,3,…\ \}$
  3. The set of rational numbers ………. $Q\ =\ \ \{\ p\ /\ q\ |\ p\ is\ an\ integer,\ q\ is\ an\ integer,\ q\ \neq\ 0\ \}$
In [15]:
U = [0,1,2,3,4,5,6,7,8,9,10]
Q = [float(U[i]) / float(U[i+1]) for i in range(len(U)) if i < len(U) - 2 and U[i] != 0]
Q
Out[15]:
1
  1. The set of prime numbers …………… $P\ \ =\ \ \{\ 2,3,4,7,11,…\ \}$
  2. The set of complex numbers……….. $C\ \ =\ \ \{\ x\ +\ iy\ |\ i_2\ =\ -1,\ x,y\ \in\ R\ \}$
  3. The set of real numbers ……………… $R\ \ =\ \ \{\ all\ decimal\ numbers\ \}$
  4. The set of 2-tuples …………………….. $R^2\ =\ \ \{\ (x,y)\ |\ x,y\ \in\ R\ \}$
  5. The set of 3-tuples …………………….. $R^3\ =\ \ \{\ (\xi_1,\xi_2,\ \xi_3,…\xi_n)\ |\ \xi_1,\xi_2,\ \xi_3,…\xi_n\ \in\ R\ \}$

It is understood that $i$ is an imaginary unit with the property $i_2 = -1$ and decimal numbers are all terminating and nonterminating decimals. A terminating decimal is one that ends, like 0.25, while a nonterminating decimal is one that can go on forever, like 1/3 which is $0.333 \rightarrow \infty$.

Intervals

When dealing with real numbers, say a,b and x, we would say $x\ \in\ [a,\ b]$ such that { $x \ |\ a\ \leq\ x\ \leq\ b$ } which is to say that at some point during the calculation the $\ell$ and $b$ will need to be decided, but for out purposes it is irrelevant. Such a notation is called a closed interval.

An open interval is denoted $x\ \in\ (a,\ b)$ such that $\{\ x\ |\ a <\ x\ < b\ \}$.

A left closed, right open interval would be $x\ \in\ [a,\ b)$ such that $\{\ x\ |\ a\ \leq x\ <\ b\ \}$ and its opposite, left open, right close interval would be $(a,\ b]$.

In every instance, ( tends to mean open, and [ tends to mean closed, and which way the parenthesis or bracket faces depends which side of the $x$ it appears on. One may have a left closed, right unbounded set notation as such $x\ \in\ [a,\ \infty)$ such that $\{\ x\ |\ x\ >\ a\ \}$. When a side is infinity, it is unbounded “(“. Such a notation can be used to define $R$ in that $x\ \in\ (-\infty,\ \infty)$ such that $R\ =\ \{\ x\ |\ -\infty\ <\ x\ <\ \infty\ \}$.

Subsets

If for every element $x\ \in\ B$ one can demonstrate that $x$ is at the same time an element of $A$, then we can say that $B$ is a subset of $A$. Another way to express this is to say that B is contained by $A$ or that $A$ contains $B$.

In [17]:
A = [1,2,3,4,5,6]
B = [2,3,6]
C = [1.3,2.1,-3.6]
def IsSubset(S1,S2):
    for x in S1:
        if not x in S2:
            return False
    return True
[IsSubset(B,A),IsSubset(C,A)]
Out[17]:
[True, False]

We express this by writing $B\ \subset\ A$. And using the above example that $C\ \not\subset\ A$. An important thing to remember is that every set is a subset of itself, that is $B\ \subset\ B$ and $A\ \subset\ A$.

In [18]:
IsSubset(A,A)
Out[18]:
True

Whenever $B\ \subset\ A$ and $B\ \not=\ A$ Then we say that $B$ is a proper subset of $A$.

In [20]:
def AreEqualSets(S1,S2):
    if len(S1) == len(S2) and IsSubset(S1,S2):
        return True
    return False
def IsProperSubset(S1,S2):
    if AreEqualSets(S1,S2) == False and IsSubset(S1,S2):
        return True
    return False
[IsProperSubset(B,A),IsProperSubset(C,A),IsProperSubset(B,B)]
Out[20]:
[True, False, False]

Set Operations

The union of two sets is a new set where $\{\ x\ |\ x\ \in\ A\ or\ x\ \in\ B\ \}$. This is written as $A\ \cup\ B$

In [33]:
A = [100,200,300]
B = [2,3,6,11]
def UnionOfSets(S1,S2):
    S3 = []
    if len(S1) > len(S2):
        l = S1
        s = S2
    else:
        l = S2
        s = S1
    for x in l:
        S3.append(x)
    for x in s:
        if (x in l or x in s) and x not in S3:
            S3.append(x)
    return S3
            
[UnionOfSets(B,A),UnionOfSets(A,B)]
Out[33]:
[[2, 3, 6, 11, 100, 200, 300], [2, 3, 6, 11, 100, 200, 300]]

The intersection of two sets is when $\{\ x\ |\ x\ \in\ A\ and\ x\ \in\ B\ \}$. This is written $A\ \cap\ B$.

In [34]:
A = [1,2,3,5,7,11]
B = [2,3,6,11,32]
def IntersectionOfSets(S1,S2):
    S3 = []
    if len(S1) > len(S2):
        l = S1
        s = S2
    else:
        l = S2
        s = S1
    for x in s:
        if x in l:
            S3.append(x)
    return S3
            
[IntersectionOfSets(B,A),IntersectionOfSets(A,B)]
Out[34]:
[[2, 3, 11], [2, 3, 11]]

If $A\ \cap\ B\ =\ \emptyset$ we say that A and B are disjoint.

In [35]:
A = [2,4,6,8]
B = [1,3,5,7]
def IsDisjoint(S1,S2):
    S3 = IntersectionOfSets(S1,S2)
    if len(S3) == 0:
        return True
    return False
[IsDisjoint(A,B),IsDisjoint(B,A)]
Out[35]:
[True, True]

The difference between two sets is written $A\ -\ B$ or sometimes $A\ \backslash\ B$. $A\ -\ B\ =\ \{\ x\ |\ x\ \in\ A\ and\ x\ \not\in\ B\ \}$.

In [41]:
A = [1,3,7,11]
B = [1,3,5,7]
def DifferenceOfSets(S1,S2):
    S3 = []
    for x in S1:
        if not x in S2:
            S3.append(x)
    return S3
[
    DifferenceOfSets(A,B),
    DifferenceOfSets(B,A),
    (not DifferenceOfSets(A,B) == DifferenceOfSets(B,A))
]
Out[41]:
[[11], [5], True]

The equality of sets is written $A\ =\ B$ which is hardly surprising. It is true if and only if $A\ \subset\ B\ and\ B\ \subset\ A$.

The complement of a set with respect to the Universal set $U$ is written $A^c$ and defined as $A^c\ =\ \{\ x\ |\ x\ \in\ U\ and\ x\ \not\in\ A\ \}$

In [43]:
U = [1,2,3,4,5]
A = [2,3]
A_c = DifferenceOfSets(U,A)
A_c
Out[43]:
[1, 4, 5]
In [ ]:
 

  1. 5,
    0.6666666666666666,
    0.75,
    0.8,
    0.8333333333333334,
    0.8571428571428571,
    0.875,
    0.8888888888888888