Set Theory Arbitrary Union and Intersection Operations with R

June 22, 2017
By

(This article was first published on R – Aaron Schlegel, and kindly contributed to R-bloggers)

Part 3 of 3 in the series Set Theory

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.

To leave a comment for the author, please follow the link and comment on their blog: R – Aaron Schlegel.

R-bloggers.com offers daily e-mail updates about R news and tutorials on topics such as: Data science, Big Data, R jobs, visualization (ggplot2, Boxplots, maps, animation), programming (RStudio, Sweave, LaTeX, SQL, Eclipse, git, hadoop, Web Scraping) statistics (regression, PCA, time series, trading) and more...



If you got this far, why not subscribe for updates from the site? Choose your flavor: e-mail, twitter, RSS, or facebook...

Comments are closed.

Sponsors

Never miss an update!
Subscribe to R-bloggers to receive
e-mails with the latest R posts.
(You will not see this message again.)

Click here to close (This popup will not appear again)