Set Theory Arbitrary Union and Intersection Operations with R

[This article was first published on R – Aaron Schlegel, and kindly contributed to R-bloggers]. (You can report issue about the content on this page here)
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

Part 3 of 3 in the series Set Theory

The union and intersection set operations were introduced in a previous post using two sets, [latex]a[/latex] and [latex]b[/latex]. These set operations can be generalized to accept any number of sets.

Arbitrary Set Unions Operation

Consider a set of infinitely many sets:

[latex display=”true”] A = \large{\{b_0, b_1, b_2, \cdots \} \large} [/latex]

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:

[latex display=”true”] \large{b_0 \cup b_1 \cup b_2 \cup b_3 \cup b_4 \cup b_5\large} [/latex]

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

[latex display=”true”] \large{\bigcup A = \bigcup_i b_i} [/latex]

We can then state the following definition: For a set [latex]A[/latex], the union [latex]\bigcup A[/latex] of [latex]A[/latex] is defined by:

[latex display=”true”] \large{\bigcup A = \{x \space | \space (\exists b \in A) \space x \in b \} \large} [/latex]

For example, consider the three sets:

[latex display=”true”] \large{a = \{2, 4, 6 \} \qquad b = \{3, 5, 7\} \qquad c = \{2, 3, 8 \} \large}[/latex] The union of the three sets is written as:
[latex display=”true”] \large{\bigcup \Big\{\{2,4,6\}, \{3,5,7\}, \{2,3,8\} \Big\} = \{2,3,4,5,6,7,8\}} [/latex]

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

[latex display=”true”] \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)} [/latex]

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 [latex]A[/latex], there exists a set [latex]B[/latex] whose members are the same elements of the elements of [latex]A[/latex]. Stated more formally:

[latex display=”true”] \large{\forall x \big[ x \in B \space \Leftrightarrow \space (\exists b \in A) \space x \in b \big] }[/latex]

The definition of [latex]\bigcup A[/latex] can be stated as:

[latex display=”true”] \large{x \in \bigcup A \Leftrightarrow (\exists b \in A) \space x \in b} [/latex]

For example, we can demonstrate the updated axiom with the union of four sets [latex]\{a, b, c, d\}[/latex]:

[latex display=”true”] \large{\bigcup \{a, b, c, d \} = \big\{(\exists B \in A) \space x \in \{a, b, c, d\}\big\} \large}[/latex]
[latex display=”true”] \large{ \bigcup \{a, b, c, d \} = a \cup b \cup c \cup d \large}[/latex]

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:

[latex display="true"] \large{a = \{1,2,3\} \qquad b = \{3,4,5\} \qquad c = \{1,4,6\} \qquad d =\{2,5,7\} \large}[/latex]

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.

[latex display="true"] \large{A = \{b_0, b_1, b_2, \cdots \}} [/latex]

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

[latex display="true"] \large{\bigcap A = \bigcap_i b_i} [/latex]

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 [latex]A[/latex], a set [latex]B[/latex] exists that such for any element [latex]x[/latex]:

[latex display="true"] \large{x \in B \Leftrightarrow x \in \forall A} [/latex]

Consider the following four sets:

[latex display="true"] \large{a = \{1,2,3\} \qquad b = \{1,3,5\} \qquad c = \{1,4,5,3\} \qquad d = \{2,6,1,3\}} [/latex]

The intersection of the sets is written as:

[latex display="true"] \large{\bigcap \big\{\{1,2,3,5\}, \{1,3,5\}, \{1,4,5,3\}, \{2,5,1,3\}\big\}} [/latex] [latex display="true"] = \large{\{1,2,3,5\} \cap \{1,3,5\} \cap \{1,4,5,3\} \cap \{2,5,1,3\} = \{1,3,5\}} [/latex]

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 about learning R and many other topics. Click here if you're looking to post or find an R/data-science job.
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

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)