## Set Theory Ordered Pairs and Cartesian Product with R

- Introduction to Set Theory and Sets with R
- Set Operations Unions and Intersections in R
- Set Theory Arbitrary Union and Intersection Operations with R
- Algebra of Sets in R
- Set Theory Ordered Pairs and Cartesian Product with R

###### Ordered and Unordered Pairs

A pair set is a set with two members, for example, [latex]\{2, 3\}[/latex], which can also be thought of as an unordered pair, in that [latex]\{2, 3\} = \{3, 2\}[/latex]. 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 [latex]\langle2, 3\rangle[/latex], which specifies that [latex]2[/latex] is the first component and [latex]3[/latex] is the second component. We also make the requirement that [latex]\langle2, 3\rangle \neq \langle3, 2\rangle[/latex]. We can also represent this object, generalized as [latex]\langle x, y\rangle[/latex], as:

[latex display=”true”] \large{\langle x, y\rangle = \langle u, v \rangle} [/latex]

Therefore [latex]x = u[/latex] and [latex]y = v[/latex]. 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.

[latex display=”true”] \large{\langle x, y \rangle = \big\{\{x\}, \{x, y\} \big\}} [/latex]

The pair [latex]\langle x, y \rangle[/latex] can be represented as a point on a Cartesian coordinate plane.

###### Cartesian Product

The Cartesian product [latex]A \times B[/latex] of two sets [latex]A[/latex] and [latex]B[/latex] is the collection of all ordered pairs [latex]\langle x, y \rangle[/latex] with [latex]x \in A[/latex] and [latex]y \in B[/latex]. 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 [latex]A = \{1, 2, 3\}[/latex] and [latex]B = \{2, 4, 6\}[/latex]. The Cartesian product [latex]A \times B[/latex] is then:

[latex display=”true”] A \times B = \big\{\{1,2\}, \{1,4\}, \{1,6\}, \{2,2\}, \{2,4\},\{2,6\},\{3,2\},\{3,4\},\{3,6\}\big\}[/latex]

Whereas the Cartesian product [latex]B \times A[/latex] is:

[latex display=”true”] B \times A = \big\{\{2,1\}, \{2,2\}, \{2,3\}, \{4,1\}, \{4,2\},\{4,3\},\{6,1\},\{6,2\},\{6,3\}\big\}[/latex]

The following function implements computing the Cartesian product of two sets [latex]A[/latex] and [latex]B[/latex].

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 [latex]A \times B[/latex] and [latex]B \times A[/latex] 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. One could also simply use the `expand.grid()`

function like so to get the same result for the Cartesian product. Thanks a lot to Jeff in the comments for reminding me about the `expand.grid()`

function.

t(expand.grid(a, b)) ## [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] ## Var1 1 2 3 1 2 3 1 2 3 ## Var2 2 2 2 4 4 4 6 6 6

###### Some Cartesian Product Theorems

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

If [latex]A[/latex] is a set, then [latex]A \times \varnothing = \varnothing[/latex] and [latex]\varnothing \times A = \varnothing[/latex].

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 [latex]\varnothing[/latex] for our purposes of demonstration.

The next theorem involves three sets [latex]A, B, C[/latex].

- [latex]A \times (B \cap C) = (A \times B) \cap (A \times C)[/latex]
- [latex]A \times (B \cup C) = (A \times B) \cup (A \times C)[/latex]
- [latex](A \cap B) \times C = (A \times C) \cap (B \times C)[/latex]
- [latex](A \cup B) \times C = (A \times C) \cup (B \times C)[/latex]

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 [latex]A \times (B \cap C) = (A \times B) \cap (A \times C)[/latex].

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) ## [1] 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 [latex]A \times (B \cup C) = (A \times B) \cup (A \times C)[/latex].

ident2.rhs <- cartesian(a, set.union(b, c)) ident2.lhs <- set.union(cartesian(a, b), cartesian(a, c)) isequalset(ident2.rhs, ident2.lhs) ## [1] 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 [latex](A \cap B) \times C = (A \times C) \cap (B \times C)[/latex].

ident3.rhs <- cartesian(set.intersection(a, b), c) ident3.lhs <- set.intersection(cartesian(a, c), cartesian(b, c)) isequalset(ident3.rhs, ident3.lhs) ## [1] 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 [latex](A \cup B) \times C = (A \times C) \cup (B \times C)[/latex].

ident4.rhs <- cartesian(set.union(a,b), c) ident4.lhs <- set.union(cartesian(a,c), cartesian(b,c)) isequalset(ident4.rhs, ident4.lhs) ## [1] 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.

MacGillivray, G. Cartesian Products and Relations. Victoria, BC. Retrieved from http://www.math.uvic.ca/faculty/gmacgill/guide/RF.pdf

Stacho, Juraj (n.d.). Cartesian Product [PowerPoint slides]. Retrieved from http://www.cs.toronto.edu/~stacho/macm101.pdf

## Set Theory Ordered Pairs and Cartesian Product with R | A bunch of data

July 6, 2017 at 3:43 pm[…] article was first published on R – Aaron Schlegel, and kindly contributed to R-bloggers) Part 5 of 5 in the series Set […]

## Set Theory Ordered Pairs and Cartesian Product with R – Mubashir Qasim

July 6, 2017 at 8:19 pm[…] article was first published on R – Aaron Schlegel, and kindly contributed to R-bloggers) Part 5 of 5 in the series Set […]

## Jeff Newmiller

July 7, 2017 at 7:51 pmNot even a mention of the expand.grid function? Long vectors are much more practical for large problems than short ones.

## Aaron Schlegel

July 11, 2017 at 6:49 amHi Jeff,

Thank you very much for your comment! I completely spaced on the expand.grid function. I updated the post to include a short mention of the function and how one can get the same result as the written function much more simply (and as you call out, much more efficient for larger vectors). The function in the post is meant to be more pedagogical (for myself as well) than practical. Thanks again!