Set algebra

Set algebra

Set union and intersection

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.

Union function

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

Intersection function

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

Distribution of union and intersection

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

Complements and disjoint sets

Disjoint sets

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

Complement function

\(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.

Existence of the complement

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\).

Boolean algebra

Boolean algebra in propositional logic

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.

Sets satisfy the definitions of a boolean algebra

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.

Algebra on a set

Standard algebra

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.