# 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 }

```
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
```

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

```
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
```

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$.

```
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]
```

## 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.

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

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

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

Let $B$ and $C$ denote the sets

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

```
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]
```

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.

- The set of
**natural numbers**……….. $N\ =\ \ \{\ 1,2,3,…\ \}$ - The set of
**integers**……………………. $Z\ =\ \ \{\ …,-3,-2,-1,0,1,2,3,…\ \}$ - The set of
**rational numbers**………. $Q\ =\ \ \{\ p\ /\ q\ |\ p\ is\ an\ integer,\ q\ is\ an\ integer,\ q\ \neq\ 0\ \}$

```
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
```

- The set of
**prime numbers**…………… $P\ \ =\ \ \{\ 2,3,4,7,11,…\ \}$ - The set of
**complex numbers**……….. $C\ \ =\ \ \{\ x\ +\ iy\ |\ i_2\ =\ -1,\ x,y\ \in\ R\ \}$ - The set of
**real numbers**……………… $R\ \ =\ \ \{\ all\ decimal\ numbers\ \}$ - The set of
**2-tuples**…………………….. $R^2\ =\ \ \{\ (x,y)\ |\ x,y\ \in\ R\ \}$ - 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$.

```
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)]
```

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$.

```
IsSubset(A,A)
```

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

```
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)]
```

## 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$

```
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)]
```

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

```
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)]
```

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

```
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)]
```

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\ \}$.

```
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))
]
```

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\ \}$

```
U = [1,2,3,4,5]
A = [2,3]
A_c = DifferenceOfSets(U,A)
A_c
```

```
```

- 5,

0.6666666666666666,

0.75,

0.8,

0.8333333333333334,

0.8571428571428571,

0.875,

0.8888888888888888 ↩