Set Theory Arbitrary Union and Intersection Operations with R

The union and intersection set operations were introduced in a previous post using two sets, \(a\) and \(b\). These set operations can be generalized to accept any number of sets.

Arbitrary Set Unions Operation

Consider a set of infinitely many sets:

\( A = \large{\{b_0, b_1, b_2, \cdots \} \large} \)

It would be very tedious and unnecessary to repeat the union statement repeatedly for any non-trivial amount of sets, for example, the first few unions would be written as:

\( \large{b_0 \cup b_1 \cup b_2 \cup b_3 \cup b_4 \cup b_5\large} \)

Thus a more general operation for performing unions is needed. This operation is denoted by the \(\bigcup\) symbol. For example, the set \(A\) above and the desired unions of the member sets can be generalized to the following using the new notation:

\( \large{\bigcup A = \bigcup_i b_i} \)

We can then state the following definition: For a set \(A\), the union \(\bigcup A\) of \(A\) is defined by:

\( \large{\bigcup A = \{x \space | \space (\exists b \in A) \space x \in b \} \large} \)

For example, consider the three sets:

\( \large{a = \{2, 4, 6 \} \qquad b = \{3, 5, 7\} \qquad c = \{2, 3, 8 \} \large}\) The union of the three sets is written as:
\( \large{\bigcup \Big\{\{2,4,6\}, \{3,5,7\}, \{2,3,8\} \Big\} = \{2,3,4,5,6,7,8\}} \)

Recalling our union axiom from a previous post, the union axiom states for two sets \(A\) and \(B\), there is a set whose members consist entirely of those belonging to sets \(A\) or \(B\), or both. More formally, the union axiom is stated as:

\( \large{\forall a \space \forall b \space \exists B \space \forall x (x \in B \Leftrightarrow x \in a \space \vee \space x \in b)} \)

As we are now dealing with an arbitrary amount of sets, we need an updated version of the union axiom to account for the change.

Restating the union axiom:

For any set \(A\), there exists a set \(B\) whose members are the same elements of the elements of \(A\). Stated more formally:

\( \large{\forall x \big[ x \in B \space \Leftrightarrow \space (\exists b \in A) \space x \in b \big] }\)

The definition of \(\bigcup A\) can be stated as:

\( \large{x \in \bigcup A \Leftrightarrow (\exists b \in A) \space x \in b} \)

For example, we can demonstrate the updated axiom with the union of four sets \(\{a, b, c, d\}\):

\( \large{\bigcup \{a, b, c, d \} = \big\{(\exists B \in A) \space x \in \{a, b, c, d\}\big\} \large}\)
\( \large{ \bigcup \{a, b, c, d \} = a \cup b \cup c \cup d \large}\)

We can implement the set operation for an arbitrary amount of sets by expanding upon the function we wrote previously.

set.unions <- function(a, b, ...) {
  u <- a
  for (i in 1:length(b)) {
    if (!(b[i] %in% u)) {
      u <- append(u, b[i])
    }
  }
  
  s <- list(...)
  
  for (i in s) {
    for (j in i) {
      if (!(j %in% u)) {
        u <- append(u, j)
      }
    }
  }
  return(u)
}

Perform the set union operation of four sets:

\( \large{a = \{1,2,3\} \qquad b = \{3,4,5\} \qquad c = \{1,4,6\} \qquad d =\{2,5,7\} \large}\)

a <- c(1,2,3)
b <- c(3,4,5)
c <- c(1,4,6)
d <- c(2,5,7)

set.unions(a, b, c, d)
## [1] 1 2 3 4 5 6 7

Intersections of an Arbitrary Number of Sets

The intersection set operation can also be generalized to any number of sets. Consider the previous set containing an infinite number of sets.

\( \large{A = \{b_0, b_1, b_2, \cdots \}} \)

As before, writing out all the intersections would be tedious and not elegant. The intersection can instead be written as:

\( \large{\bigcap A = \bigcap_i b_i} \)

As before in our previous example of set intersections, there is no need for a separate axiom for intersections, unlike unions. Instead, we can state the following theorem, for a nonempty set \(A\), a set \(B\) exists that such for any element \(x\):

\( \large{x \in B \Leftrightarrow x \in \forall A} \)

Consider the following four sets:

\( \large{a = \{1,2,3\} \qquad b = \{1,3,5\} \qquad c = \{1,4,5,3\} \qquad d = \{2,6,1,3\}} \)

The intersection of the sets is written as:

\( \large{\bigcap \big\{\{1,2,3,5\}, \{1,3,5\}, \{1,4,5,3\}, \{2,5,1,3\}\big\}} \) \( = \large{\{1,2,3,5\} \cap \{1,3,5\} \cap \{1,4,5,3\} \cap \{2,5,1,3\} = \{1,3,5\}} \)

We can write another function to implement the set intersection operation given any number of sets.

set.intersections <- function(a, b, ...) {

  intersect <- vector()
  for (i in a) {
    if (i %in% b) {
      intersect <- append(intersect, i)
    }
  }
  
  s <- list(...)
  
  for (i in s) {
    for (j in i) {
      if (j %in% intersect) {
        intersect <- append(intersect, j)
      }
    }
  }
  intersect <- unique(intersect)
  
  return(intersect)
}

Perform set intersections of the four sets specified earlier.

a <- c(1,2,3,5)
b <- c(1,3,5)
c <- c(1,4,5,3)
d <- c(2,5,1,3)

set.intersections(a, b, c, d)
## [1] 1 3 5

References

Enderton, H. (1977). Elements of set theory (1st ed.). New York: Academic Press.

The post Set Theory Arbitrary Union and Intersection Operations with R appeared first on Aaron Schlegel.