Set Theory

Given sets $A$ and $B$, $A$ equals $B$, written $A = B$, if, and only if, every element of $A$ is in $B$ and every element in $B$ is in $A$.

Symbolically:

Let $A$ and $B$ be subsets of a universal set $U$.

1. The union of $A$ and $B$, denoted $A \cup B$, is the set of all elements that are in at least one of $A$ or $B$. Symbolically:

2. The intersection of $A$ and $B$, denoted $A \cap B$, is the set of all elements that are common to both $A$ and $B$. Symbolically:

3. The difference of $B$ minus $A$ (or relative complement of $A$ in $B$), denoted $B - A$, is the set of all elements that are in $B$ and not in $A$. Symbolically:

4. The complement of $A$, denoted $A^C$, is the set of all elements in $U$ that are not in $A$. Symbolically:

The empty set (or null set), denoted by $\empty$, is a unique set whith no elements.

Two sets are called disjoint if, and only if, they have no elements in common. Symbolically:

Sets $A_1, A_2, A_3, \cdots$ are mutually disjoint (or pairwise disjoint or nonoverlapping) if, and only if, not two sets $A_i$ and $A_j$ with distinct subscripts have any elements in common. More precisely, for all integers $i$ and $j$:

A finite or infinite collection of nonempty sets ${A_1, A_2, A_3, \cdots}$ is a partition of a set $A$ if, and only if:

1. $A$ is the union of all the $A_i$;
2. the sets $A_1, A_2, A_3, \cdots$ are mutually disjoint.

Given a set $A$, the power set of $A$, denoted by $\mathcal{P}(A)$ is the set of all subsets of $A$.

An identitity is and equation that is universally true for all elements in some set.

Let all sets referred to below be subsets of a universal set $U$:

1. Commutative Laws: For all sets $A$ and $B$:

$A \cup B = B \cup A$ and $A \cap B = B \cap B$

2. Associative Laws: For all sets $A$, $B$ and $C$:

3. Distributive Laws: For all sets $A$, $B$ and $C$:

4. Identity Laws: For every set $A$:

$A \cup \emptyset = A$ and $A \cap U = A$

5. Complement Laws: For every set $A$:

$A \cup A^{C} = U$ and $A \cap A^{C} = \emptyset$

6. Double Complement Laws: For every set $A$:

7. Idempotent Laws: For every set $A$:

$A \cup A = A$ and $A \cap A = A$

8. Universal Bound Laws: For every set $A$:

$A \cup U = U$ and $A \cap \emptyset = \emptyset$

9. De Morgan’s Laws: For all sets $A$ and $B$:

10. Absorption Laws: For all sets $A$ and $B$:

11. Complements of $U$ and $\emptyset$:

12. Set Difference Laws: For all sets $A$ and $B$:

If $E$ is a set with not elements and $A$ is any set, then $E \subseteq A$

Proof (by contradiction): Suppose not, suppose there exists a set $E$ with not elements and a set $A$, such that $E \subseteq A$.

Then, by definition of subset, there would be an element of $E$ that is not an element of $A$. But there can be no such element since $E$ has no elements. Thus this line of reasoning resuls in a contradiction and the supposition must be false.

There is only one set with no elements

Proof: Suppose $E_1$ and $E_2$ are both sets with no elements. By the previous Theorem $E_1 \subseteq E_2$ since $E_1$ has no elements. Also $E_2 \subseteq E_1$, since $E_2$ has no elements. Thus $E_1 = E_2$ by definition of set equality.

For every integer $n \geq 0$, if a set $X$ has $n$ elements, then $\mathcal{P}(X)$ has $2^n$ elements.

Proof (by mathematical indcution): Let the property $P(n)$ be:

Any set with $n$ elements has $2^n$ subsets.

Show that $P(0)$ is true. We must show that:

Any set with $0$ eleemnts ahs $2^0$ subsets.

The only set with zero elements is the empty set, and the only subset of the empty set is itself. Thus a set with zero elements has one subset.

Show that for every integer $k \geq 0$, if $P(k)$ is strue then $P(k + 1)$ is also true. Suppose that $k$ is any integer with $k \geq 0$, such that:

Any set with $k$ elements has $2^k$ subsets.

We must show that:

Any set with $k + 1$ elements has $2^{k + 1}$ subsets.

Let $X$ be a set with $k + 1$ elements. Since $k + 1 \geq 1$, we may pick an element $z$ in X. Observe that any subset of $X$ either contains $z$ or does not.

1. Any subset of $X$ that does not contain $z$ is a subset of $X - {z}$.
2. Any subset $A$ of $X - {z}$ can be matched up with a subset $B$ equal to $A \cup {z}$ of $X$ that contains $z$.

Consequently, there are as many subset of $X$ that contain $z$ as do not, and thus there are twice as many subsets of $X$ as there are subsets of $X - {z}$. If follows that since $X - {z}$ has $k$ elements, then, by inductive hypothesis, the number of subsets of $X - {z}$ is $2^k$.

Therefore the number of subsets of $X$ is $2 \cdot 2^k = 2^{k + 1}$.

A Boolean algebra is a set $B$ together with two operations, generally denoted $+$ and $\cdot$, such that for all $a$ and $b$ in $B$ both $a + b$ and $a \cdot b$ are in $B$ and the following axioms are assumed to hold:

1. Commutative Laws: For all $a$ and $b$ in $B$,

2. Associative Laws: For all $a$, $b$ and $c$ in $B$,

3. Distributive Laws: For all $a$, $b$ and $c$ in $B$,

4. Identity Laws: There exist distint elements $0$ and $1$ in $B$ such that for each $a$ in $B$,

5. Complement Laws: For each $a$ in $B$, there exists an element in $B$, denoted $\bar{a}$ and called the complement or negation of f$a$, such taht:

Let $B$ be any Boolean algebra:

1. Uniqueness of the Complement Laws: For all $a$ and $x$ in $B$, if $a + x = 1$ and $a \cdot x = 0$, then $x = \bar{a}$.

2. Uniqueness of $0$ and $1$:

• If there exists $x$ in $B$ such that $a + x = a$ for every $a$ in $B$, then $x = 0$
• If there exists $y$ in $B$ such that $a \cdot y = a$ for every $a$ in $B$, then $y = 1$

3. Double Complement Law: For every $a \in B, \bar{(\bar{a})} = a$

4. Idempotent Laws: For every $a \in B$,

5. Universal Bound Laws: For every $a \in B$,

6. De Morgan’s Laws: For all $a, b \in B$,

7. Absorption Laws: For all $a, b \in B$,

8. Complements of $0$ and $1$:

There is no computer algorithm that will accept any algorithm $X$ and data set $D$ as input and then will output “halts” or “loops forever” to indicate whether or not $X$ terminates in a finite number of steps when $X$ is run with data set $D$.

Proof (by contradiction): Suppose there is an algorithm, CheckHalt, such that if an algorithm $X$ and a data set $D$ are input, then

$\text{CheckHalt}(X, D)$ prints

• “halts” if $X$ terminates in a finite number of steps when run with dataset $D$.
• “loops forever” if $X$ does not terminate in a finite number of steps when run with dataset $D$.

Observe that the sequence of characters making up an algorithm $X$ can be regarded as a data set itself. Thus it is possible to consider running CheckHalt with input $(X, X)$. Define a new algorithm, Test, as follows: For any input algorithm $X$,

• $\text{Test}(X)$ loops forever if $\text{CheckHalt}(X, X)$ prints “halts” or
• $\text{Test}(X)$ steps if $\text{CheckHalt}(X, X)$ prints “loops forever”

Now run algorithm Test with input Test.

• If $\text{Test}(\text{Test})$ terminates after a finite number of steps, then the value of $\text{CheckHalt}(\text{Test}, \text{Test})$ is “halts” and so $\text{Test}(\text{Test})$ loops forever.
• If $\text{Test}(\text{Test})$ does not terminate after a finite number of steps, then the value of $\text{CheckHalt}(\text{Test}, \text{Test})$ is “loops forever” and so $\text{Test}(\text{Test})$ terminates.

This shows a contradiction, therefore the supposition must be false and there is no such algorithm like CheckHalt.