We discuss functions. Just because we can write a function of sets which exist, does not mean the results of the functions exist. For that we need axioms discussed later.
We define a function on two sets, \(a\lor b\), such that the result contains all elements from either sets.
\(\forall a \forall x \forall y [a\in (x\lor y) \leftrightarrow (a\in x \lor a\in y)]\)
This is commutative: \(a\lor b = b\lor a\)
This is associative: \((a\lor b)\lor c = a\lor (b\lor c)\)
We define a function, \(a\land b\), on two sets, such that the result contains all elements which are in both.
\(\forall a \forall x \forall y [a\in (x\land y) \leftrightarrow (a\in x \land a\in y)]\)
This is commutative: \(a\land b = b\land a\)
This is associative: \((a\land b)\land c = a\lor (b\land c)\)
Union is distributive over intersection: \(a\lor (b\land c)=(a\lor b)\land (a\lor c)\)
Intersection is distributive over union: \(a\land (b\lor c)=(a\land b)\lor (a\land c)\)
Sets are disjoint is there is no overlap in their elements. Two sets are \(s_i\) and \(s_j\) are mutually exclusive if:
\(s_i\land s_j=\emptyset\)
A collection of events \(s\) are all mutually exclusive if all pairs are mutually exclusive. That is:
\(\forall s_i \in s\forall s_j\in s[s_i\land s_j\ne \emptyset \rightarrow s_i=s_j]\)
\(x^C\) is the completement. It is defined such that:
\(\forall x [x\land x^C=\varnothing ]\)
For a set \(b\), the complement with respect to \(a\) is all elements in \(a\) which are not in \(b\).
\(\forall x \in a \forall y \in b [x \in (a \setminus b) \land y\in (a \setminus b)]\)
\(b\land (a \setminus b)= \varnothing\)
That is, \(b\) and \(a \setminus b\) are disjoint.
For two sets \(a\) and \(b\) we can write \((a \setminus b)\). This is the set of elements of \(a\) which are not in \(b\).
Consider the axiom of specification:
\(\forall x \forall a \exists s[(P(x)\land x\in a )\leftrightarrow (x\in s)]\)
We can also write
\(\forall x \forall a \forall b\exists s[(x\not\in b\land x\in a )\leftrightarrow (x\in s)]\)
Which provides the complement, \(s\).
We previously discussed properties of normal form, and the results from these properties.
If another structure shares these properties then they will also share the results.
If a mathematical structure has the following properties, it shares the results from normal form, and is a boolean algebra.
Both binary operators are commutitive - \(A\land B=B\land A\) and \(A\lor B=B\lor A\)
Both binary operators are associative - \((A\land B)\land C=A\land (B\land C)\) and \((A\lor B)\lor C=A\lor (B\lor C)\)
Completements - \(A\land \neg A=\emptyset\) and \(A\lor \neg A=U\)
Absorption - \(A\land (A\lor B)=A\) and \(A\lor (A\land B)=A\)
Identity - \(A\land U=A\) and \(A\lor \emptyset =A\)
Distributivity - \(A\land (B\lor C)=(A\land B)\lor (A\land C)\) and \(A\lor (B\land C)=(A\lor B)\land(A\lor C)\)
These hold for sets, and so boolean algebra holds for sets.
An algebra, \(\Sigma\), on set \(s\) is a set of subsets of \(s\) such that:
Closed under intersection: If \(a\) and \(b\) are in \(\Sigma\) then \(a\land b\) must also be in \(\Sigma\)
\(\forall ab [(a \in \Sigma \land b \in \Sigma )\rightarrow (a\land b \in \Sigma)]\)
Closed under union: If \(a\) and \(b\) are in \(\Sigma\) then \(a\lor b\) must also be in \(\Sigma\).
\(\forall ab [(a \in \Sigma \land b \in \Sigma )\rightarrow (a\lor b \in \Sigma)]\)
If both of these are true, then the following is also true:
Closed under complement: If \(a\) is in \(\Sigma\) then \(s \backslash a\) must also be in \(\Sigma\)
We also require that the null set (and therefore the original set, null’s complement) is part of the algebra.