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, $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:

[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 $\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:

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

We can then state the following definition: For a set $A$, the union $\bigcup A$ of $A$ 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 $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:

[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 $A$, there exists a set $B$ whose members are the same elements of the elements of $A$. 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 $\bigcup A$ 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 $\{a, b, c, d\}$:

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

[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.