Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

Part 5 of 5 in the series Set Theory
###### Ordered and Unordered Pairs

A pair set is a set with two members, for example, $$\{2, 3\}$$, which can also be thought of as an unordered pair, in that $$\{2, 3\} = \{3, 2\}$$. However, we seek a more a strict and rich object that tells us more about two sets and how their elements are ordered. Call this object $$\langle2, 3\rangle$$, which specifies that $$2$$ is the first component and $$3$$ is the second component. We also make the requirement that $$\langle2, 3\rangle \neq \langle3, 2\rangle$$. We can also represent this object, generalized as $$\langle x, y\rangle$$, as:
$$\large{\langle x, y\rangle = \langle u, v \rangle}$$

Therefore $$x = u$$ and $$y = v$$. This property is useful in the formal definition of an ordered pair, which is stated here but not explored in-depth. The currently accepted definition of an ordered pair was given by Kuratowski in 1921 (Enderton, 1977, pp. 36), though there exist several other definitions.

$$\large{\langle x, y \rangle = \big\{\{x\}, \{x, y\} \big\}}$$

The pair $$\langle x, y \rangle$$ can be represented as a point on a Cartesian coordinate plane.

###### Cartesian Product

The Cartesian product $$A \times B$$ of two sets $$A$$ and $$B$$ is the collection of all ordered pairs $$\langle x, y \rangle$$ with $$x \in A$$ and $$y \in B$$. Therefore, the Cartesian product of two sets is a set itself consisting of ordered pair members. A set of ordered pairs is defined as a ‘relation.’

For example, consider the sets $$A = \{1, 2, 3\}$$ and $$B = \{2, 4, 6\}$$. The Cartesian product $$A \times B$$ is then:

$$A \times B = \big\{\{1,2\}, \{1,4\}, \{1,6\}, \{2,2\}, \{2,4\},\{2,6\},\{3,2\},\{3,4\},\{3,6\}\big\}$$

Whereas the Cartesian product $$B \times A$$ is:

$$B \times A = \big\{\{2,1\}, \{2,2\}, \{2,3\}, \{4,1\}, \{4,2\},\{4,3\},\{6,1\},\{6,2\},\{6,3\}\big\}$$

The following function implements computing the Cartesian product of two sets $$A$$ and $$B$$.

cartesian <- function(a, b) {
axb <- list()
k <- 1
for (i in a) {
for (j in b) {
axb[[k]] <- c(i,j)
k <- k + 1
}
}
return(axb)
}


Let’s use the function to calculate the Cartesian product $$A \times B$$ and $$B \times A$$ to see if it aligns with our results above.

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

as.data.frame(cartesian(a, b))
##   c.1..2. c.1..4. c.1..6. c.2..2. c.2..4. c.2..6. c.3..2. c.3..4. c.3..6.
## 1       1       1       1       2       2       2       3       3       3
## 2       2       4       6       2       4       6       2       4       6

as.data.frame(cartesian(b, a))
##   c.2..1. c.2..2. c.2..3. c.4..1. c.4..2. c.4..3. c.6..1. c.6..2. c.6..3.
## 1       2       2       2       4       4       4       6       6       6
## 2       1       2       3       1       2       3       1       2       3


Both outputs agree to our previous results.

###### Some Cartesian Product Theorems

We can state some theorems related to the Cartesian product of two sets. The first theorem states:

If $$A$$ is a set, then $$A \times \varnothing = \varnothing$$ and $$\varnothing \times A = \varnothing$$.

We can demonstrate this theorem with our cartesian() function.

cartesian(a, c()) # c() represents the empty set.
## list()

cartesian(c(), a)
## list()


The outputs are an empty list which is equivalent to the empty set $$\varnothing$$ for our purposes of demonstration.

The next theorem involves three sets $$A, B, C$$.

• $$A \times (B \cap C) = (A \times B) \cap (A \times C)$$
• $$A \times (B \cup C) = (A \times B) \cup (A \times C)$$
• $$(A \cap B) \times C = (A \times C) \cap (B \times C)$$
• $$(A \cup B) \times C = (A \times C) \cup (B \times C)$$

We can demonstrate each in turn with a combination of our cartesian() from above, and the set.union() and set.intersection() functions from a previous post on set unions and intersections. The base R functions union() and intersect() can be used instead of the functions we defined previously.

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


The first identity $$A \times (B \cap C) = (A \times B) \cap (A \times C)$$.

ident1.rhs <- cartesian(a, set.intersection(b, c)) # Right-hand Side
ident1.lhs <- set.intersection(cartesian(a, b), cartesian(a, c)) # Left-hand Side

isequalset(ident1.rhs, ident1.lhs)
##  TRUE

as.data.frame(ident1.rhs)
##   c.1..4. c.2..4. c.3..4.
## 1       1       2       3
## 2       4       4       4

as.data.frame(ident1.lhs)
##   c.1..4. c.2..4. c.3..4.
## 1       1       2       3
## 2       4       4       4


The second identity $$A \times (B \cup C) = (A \times B) \cup (A \times C)$$.

ident2.rhs <- cartesian(a, set.union(b, c))
ident2.lhs <- set.union(cartesian(a, b), cartesian(a, c))

isequalset(ident2.rhs, ident2.lhs)
##  TRUE

as.data.frame(ident2.rhs)
##   c.1..2. c.1..4. c.1..6. c.1..1. c.1..7. c.2..2. c.2..4. c.2..6. c.2..1.
## 1       1       1       1       1       1       2       2       2       2
## 2       2       4       6       1       7       2       4       6       1
##   c.2..7. c.3..2. c.3..4. c.3..6. c.3..1. c.3..7.
## 1       2       3       3       3       3       3
## 2       7       2       4       6       1       7

as.data.frame(ident2.lhs)
##   c.1..2. c.1..4. c.1..6. c.2..2. c.2..4. c.2..6. c.3..2. c.3..4. c.3..6.
## 1       1       1       1       2       2       2       3       3       3
## 2       2       4       6       2       4       6       2       4       6
##   c.1..1. c.1..7. c.2..1. c.2..7. c.3..1. c.3..7.
## 1       1       1       2       2       3       3
## 2       1       7       1       7       1       7


The third identity $$(A \cap B) \times C = (A \times C) \cap (B \times C)$$.

ident3.rhs <- cartesian(set.intersection(a, b), c)
ident3.lhs <- set.intersection(cartesian(a, c), cartesian(b, c))

isequalset(ident3.rhs, ident3.lhs)
##  TRUE

as.data.frame(ident3.rhs)
##   c.2..1. c.2..4. c.2..7.
## 1       2       2       2
## 2       1       4       7

as.data.frame(ident3.lhs)
##   c.2..1. c.2..4. c.2..7.
## 1       2       2       2
## 2       1       4       7


We finish the post with the fourth identity $$(A \cup B) \times C = (A \times C) \cup (B \times C)$$.

ident4.rhs <- cartesian(set.union(a,b), c)
ident4.lhs <- set.union(cartesian(a,c), cartesian(b,c))

isequalset(ident4.rhs, ident4.lhs)
##  TRUE

as.data.frame(ident4.rhs)
##   c.1..1. c.1..4. c.1..7. c.2..1. c.2..4. c.2..7. c.3..1. c.3..4. c.3..7.
## 1       1       1       1       2       2       2       3       3       3
## 2       1       4       7       1       4       7       1       4       7
##   c.4..1. c.4..4. c.4..7. c.6..1. c.6..4. c.6..7.
## 1       4       4       4       6       6       6
## 2       1       4       7       1       4       7

as.data.frame(ident4.lhs)
##   c.1..1. c.1..4. c.1..7. c.2..1. c.2..4. c.2..7. c.3..1. c.3..4. c.3..7.
## 1       1       1       1       2       2       2       3       3       3
## 2       1       4       7       1       4       7       1       4       7
##   c.4..1. c.4..4. c.4..7. c.6..1. c.6..4. c.6..7.
## 1       4       4       4       6       6       6
## 2       1       4       7       1       4       7

###### References

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