<p><div><div><div><div data-show-faces="false" data-height="21" data-width="100" data-layout="button_count" data-send="true" data-href="https://www.r-bloggers.com/set-theory-ordered-pairs-and-cartesian-product-with-r/"></div></div><div></div></div><div></div></div>
<div>
(This article was first published on <strong><a href="http://www.aaronschlegel.com/set-theory-ordered-pairs-and-cartesian-product-with-r/"> R – Aaron Schlegel</a></strong>, and kindly contributed to <a rel="nofollow" href="https://www.r-bloggers.com/">R-bloggers)</a> </div>
<div>Part 5 of 5 in the series <a rel="nofollow" href="http://www.aaronschlegel.com/series/set-theory/" title="Set Theory" target="_blank">Set Theory</a></div>
<h6>Ordered and Unordered Pairs</h6>
<p>A pair set is a set with two members, for example, <img alt="\{2, 3\}" title="\{2, 3\}" src="https://s0.wp.com/latex.php?latex=%5C%7B2%2C+3%5C%7D&bg=ffffff&fg=000&s=0" class="latex">, which can also be thought of as an unordered pair, in that <img alt="\{2, 3\} = \{3, 2\}" title="\{2, 3\} = \{3, 2\}" src="https://s0.wp.com/latex.php?latex=%5C%7B2%2C+3%5C%7D+%3D+%5C%7B3%2C+2%5C%7D&bg=ffffff&fg=000&s=0" class="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 <img alt="\langle2, 3\rangle" title="\langle2, 3\rangle" src="https://s0.wp.com/latex.php?latex=%5Clangle2%2C+3%5Crangle&bg=ffffff&fg=000&s=0" class="latex">, which specifies that <img alt="2" title="2" src="https://s0.wp.com/latex.php?latex=2&bg=ffffff&fg=000&s=0" class="latex"> is the first component and <img alt="3" title="3" src="https://s0.wp.com/latex.php?latex=3&bg=ffffff&fg=000&s=0" class="latex"> is the second component. We also make the requirement that <img alt="\langle2, 3\rangle \neq \langle3, 2\rangle" title="\langle2, 3\rangle \neq \langle3, 2\rangle" src="https://s0.wp.com/latex.php?latex=%5Clangle2%2C+3%5Crangle+%5Cneq+%5Clangle3%2C+2%5Crangle&bg=ffffff&fg=000&s=0" class="latex">. We can also represent this object, generalized as <img alt="\langle x, y\rangle" title="\langle x, y\rangle" src="https://s0.wp.com/latex.php?latex=%5Clangle+x%2C+y%5Crangle&bg=ffffff&fg=000&s=0" class="latex">, as:<br>
<img alt=" \large{\langle x, y\rangle = \langle u, v \rangle} " title=" \large{\langle x, y\rangle = \langle u, v \rangle} " src="https://s0.wp.com/latex.php?latex=+%5Clarge%7B%5Clangle+x%2C+y%5Crangle+%3D+%5Clangle+u%2C+v+%5Crangle%7D+&bg=ffffff&fg=000&s=0" class="latex"></p>
<p>Therefore <img alt="x = u" title="x = u" src="https://s0.wp.com/latex.php?latex=x+%3D+u&bg=ffffff&fg=000&s=0" class="latex"> and <img alt="y = v" title="y = v" src="https://s0.wp.com/latex.php?latex=y+%3D+v&bg=ffffff&fg=000&s=0" class="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.</p>
<img alt=" \large{\langle x, y \rangle = \big\{\{x\}, \{x, y\} \big\}} " title=" \large{\langle x, y \rangle = \big\{\{x\}, \{x, y\} \big\}} " src="https://s0.wp.com/latex.php?latex=+%5Clarge%7B%5Clangle+x%2C+y+%5Crangle+%3D+%5Cbig%5C%7B%5C%7Bx%5C%7D%2C+%5C%7Bx%2C+y%5C%7D+%5Cbig%5C%7D%7D+&bg=ffffff&fg=000&s=0" class="latex">
<p>The pair <img alt="\langle x, y \rangle" title="\langle x, y \rangle" src="https://s0.wp.com/latex.php?latex=%5Clangle+x%2C+y+%5Crangle&bg=ffffff&fg=000&s=0" class="latex"> can be represented as a point on a Cartesian coordinate plane.</p>
<h6>Cartesian Product</h6>
<p>The Cartesian product <img alt="A \times B" title="A \times B" src="https://s0.wp.com/latex.php?latex=A+%5Ctimes+B&bg=ffffff&fg=000&s=0" class="latex"> of two sets <img alt="A" title="A" src="https://s0.wp.com/latex.php?latex=A&bg=ffffff&fg=000&s=0" class="latex"> and <img alt="B" title="B" src="https://s0.wp.com/latex.php?latex=B&bg=ffffff&fg=000&s=0" class="latex"> is the collection of all ordered pairs <img alt="\langle x, y \rangle" title="\langle x, y \rangle" src="https://s0.wp.com/latex.php?latex=%5Clangle+x%2C+y+%5Crangle&bg=ffffff&fg=000&s=0" class="latex"> with <img alt="x \in A" title="x \in A" src="https://s0.wp.com/latex.php?latex=x+%5Cin+A&bg=ffffff&fg=000&s=0" class="latex"> and <img alt="y \in B" title="y \in B" src="https://s0.wp.com/latex.php?latex=y+%5Cin+B&bg=ffffff&fg=000&s=0" class="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.’</p>
<p>For example, consider the sets <img alt="A = \{1, 2, 3\}" title="A = \{1, 2, 3\}" src="https://s0.wp.com/latex.php?latex=A+%3D+%5C%7B1%2C+2%2C+3%5C%7D&bg=ffffff&fg=000&s=0" class="latex"> and <img alt="B = \{2, 4, 6\}" title="B = \{2, 4, 6\}" src="https://s0.wp.com/latex.php?latex=B+%3D+%5C%7B2%2C+4%2C+6%5C%7D&bg=ffffff&fg=000&s=0" class="latex">. The Cartesian product <img alt="A \times B" title="A \times B" src="https://s0.wp.com/latex.php?latex=A+%5Ctimes+B&bg=ffffff&fg=000&s=0" class="latex"> is then:</p>
<img alt=" A \times B = \big\{\{1,2\}, \{1,4\}, \{1,6\}, \{2,2\}, \{2,4\},\{2,6\},\{3,2\},\{3,4\},\{3,6\}\big\}" title=" A \times B = \big\{\{1,2\}, \{1,4\}, \{1,6\}, \{2,2\}, \{2,4\},\{2,6\},\{3,2\},\{3,4\},\{3,6\}\big\}" src="https://s0.wp.com/latex.php?latex=+A+%5Ctimes+B+%3D+%5Cbig%5C%7B%5C%7B1%2C2%5C%7D%2C+%5C%7B1%2C4%5C%7D%2C+%5C%7B1%2C6%5C%7D%2C+%5C%7B2%2C2%5C%7D%2C+%5C%7B2%2C4%5C%7D%2C%5C%7B2%2C6%5C%7D%2C%5C%7B3%2C2%5C%7D%2C%5C%7B3%2C4%5C%7D%2C%5C%7B3%2C6%5C%7D%5Cbig%5C%7D&bg=ffffff&fg=000&s=0" class="latex">
<p>Whereas the Cartesian product <img alt="B \times A" title="B \times A" src="https://s0.wp.com/latex.php?latex=B+%5Ctimes+A&bg=ffffff&fg=000&s=0" class="latex"> is:</p>
<img alt=" B \times A = \big\{\{2,1\}, \{2,2\}, \{2,3\}, \{4,1\}, \{4,2\},\{4,3\},\{6,1\},\{6,2\},\{6,3\}\big\}" title=" B \times A = \big\{\{2,1\}, \{2,2\}, \{2,3\}, \{4,1\}, \{4,2\},\{4,3\},\{6,1\},\{6,2\},\{6,3\}\big\}" src="https://s0.wp.com/latex.php?latex=+B+%5Ctimes+A+%3D+%5Cbig%5C%7B%5C%7B2%2C1%5C%7D%2C+%5C%7B2%2C2%5C%7D%2C+%5C%7B2%2C3%5C%7D%2C+%5C%7B4%2C1%5C%7D%2C+%5C%7B4%2C2%5C%7D%2C%5C%7B4%2C3%5C%7D%2C%5C%7B6%2C1%5C%7D%2C%5C%7B6%2C2%5C%7D%2C%5C%7B6%2C3%5C%7D%5Cbig%5C%7D&bg=ffffff&fg=000&s=0" class="latex">
<p>The following function implements computing the Cartesian product of two sets <img alt="A" title="A" src="https://s0.wp.com/latex.php?latex=A&bg=ffffff&fg=000&s=0" class="latex"> and <img alt="B" title="B" src="https://s0.wp.com/latex.php?latex=B&bg=ffffff&fg=000&s=0" class="latex">.</p>
<pre>
cartesian &lt;- function(a, b) {
  axb &lt;- list()
  k &lt;- 1
  for (i in a) {
    for (j in b) {
      axb[[k]] &lt;- c(i,j)
      k &lt;- k + 1
    }
  }
  return(axb)
}
</pre>
<p>Let’s use the function to calculate the Cartesian product <img alt="A \times B" title="A \times B" src="https://s0.wp.com/latex.php?latex=A+%5Ctimes+B&bg=ffffff&fg=000&s=0" class="latex"> and <img alt="B \times A" title="B \times A" src="https://s0.wp.com/latex.php?latex=B+%5Ctimes+A&bg=ffffff&fg=000&s=0" class="latex"> to see if it aligns with our results above.</p>
<pre>
a &lt;- c(1,2,3)
b &lt;- 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
</pre>
<pre>
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
</pre>
<p>Both outputs agree to our previous results.</p>
<h6>Some Cartesian Product Theorems</h6>
<p>We can state some theorems related to the Cartesian product of two sets. The first theorem states:</p>
<p>If <img alt="A" title="A" src="https://s0.wp.com/latex.php?latex=A&bg=ffffff&fg=000&s=0" class="latex"> is a set, then <img alt="A \times \varnothing = \varnothing" title="A \times \varnothing = \varnothing" src="https://s0.wp.com/latex.php?latex=A+%5Ctimes+%5Cvarnothing+%3D+%5Cvarnothing&bg=ffffff&fg=000&s=0" class="latex"> and <img alt="\varnothing \times A = \varnothing" title="\varnothing \times A = \varnothing" src="https://s0.wp.com/latex.php?latex=%5Cvarnothing+%5Ctimes+A+%3D+%5Cvarnothing&bg=ffffff&fg=000&s=0" class="latex">.</p>
<p>We can demonstrate this theorem with our <code>cartesian()</code> function.</p>
<pre>
cartesian(a, c()) # c() represents the empty set.
## list()
</pre>
<pre>
cartesian(c(), a)
## list()
</pre>
<p>The outputs are an empty list which is equivalent to the empty set <img alt="\varnothing" title="\varnothing" src="https://s0.wp.com/latex.php?latex=%5Cvarnothing&bg=ffffff&fg=000&s=0" class="latex"> for our purposes of demonstration.</p>
<p>The next theorem involves three sets <img alt="A, B, C" title="A, B, C" src="https://s0.wp.com/latex.php?latex=A%2C+B%2C+C&bg=ffffff&fg=000&s=0" class="latex">.</p>
<ul>
<li><img alt="A \times (B \cap C) = (A \times B) \cap (A \times C)" title="A \times (B \cap C) = (A \times B) \cap (A \times C)" src="https://s0.wp.com/latex.php?latex=A+%5Ctimes+%28B+%5Ccap+C%29+%3D+%28A+%5Ctimes+B%29+%5Ccap+%28A+%5Ctimes+C%29&bg=ffffff&fg=000&s=0" class="latex"></li>
<li><img alt="A \times (B \cup C) = (A \times B) \cup (A \times C)" title="A \times (B \cup C) = (A \times B) \cup (A \times C)" src="https://s0.wp.com/latex.php?latex=A+%5Ctimes+%28B+%5Ccup+C%29+%3D+%28A+%5Ctimes+B%29+%5Ccup+%28A+%5Ctimes+C%29&bg=ffffff&fg=000&s=0" class="latex"></li>
<li><img alt="(A \cap B) \times C = (A \times C) \cap (B \times C)" title="(A \cap B) \times C = (A \times C) \cap (B \times C)" src="https://s0.wp.com/latex.php?latex=%28A+%5Ccap+B%29+%5Ctimes+C+%3D+%28A+%5Ctimes+C%29+%5Ccap+%28B+%5Ctimes+C%29&bg=ffffff&fg=000&s=0" class="latex"></li>
<li><img alt="(A \cup B) \times C = (A \times C) \cup (B \times C)" title="(A \cup B) \times C = (A \times C) \cup (B \times C)" src="https://s0.wp.com/latex.php?latex=%28A+%5Ccup+B%29+%5Ctimes+C+%3D+%28A+%5Ctimes+C%29+%5Ccup+%28B+%5Ctimes+C%29&bg=ffffff&fg=000&s=0" class="latex"></li>
</ul>
<p>We can demonstrate each in turn with a combination of our <code>cartesian()</code> from above, and the <code>set.union()</code> and <code>set.intersection()</code> functions from a previous post on <a rel="nofollow" href="http://wp.me/p4aZEo-5Ri" target="_blank">set unions and intersections</a>. The base R functions <code>union()</code> and <code>intersect()</code> can be used instead of the functions we defined previously.</p>
<pre>
a &lt;- c(1,2,3)
b &lt;- c(2,4,6)
c &lt;- c(1,4,7)
</pre>
<p>The first identity <img alt="A \times (B \cap C) = (A \times B) \cap (A \times C)" title="A \times (B \cap C) = (A \times B) \cap (A \times C)" src="https://s0.wp.com/latex.php?latex=A+%5Ctimes+%28B+%5Ccap+C%29+%3D+%28A+%5Ctimes+B%29+%5Ccap+%28A+%5Ctimes+C%29&bg=ffffff&fg=000&s=0" class="latex">.</p>
<pre>
ident1.rhs &lt;- cartesian(a, set.intersection(b, c)) # Right-hand Side
ident1.lhs &lt;- set.intersection(cartesian(a, b), cartesian(a, c)) # Left-hand Side

isequalset(ident1.rhs, ident1.lhs)
## [1] TRUE
</pre>
<pre>
as.data.frame(ident1.rhs)
##   c.1..4. c.2..4. c.3..4.
## 1       1       2       3
## 2       4       4       4
</pre>
<pre>
as.data.frame(ident1.lhs)
##   c.1..4. c.2..4. c.3..4.
## 1       1       2       3
## 2       4       4       4
</pre>
<p>The second identity <img alt="A \times (B \cup C) = (A \times B) \cup (A \times C)" title="A \times (B \cup C) = (A \times B) \cup (A \times C)" src="https://s0.wp.com/latex.php?latex=A+%5Ctimes+%28B+%5Ccup+C%29+%3D+%28A+%5Ctimes+B%29+%5Ccup+%28A+%5Ctimes+C%29&bg=ffffff&fg=000&s=0" class="latex">.</p>
<pre>
ident2.rhs &lt;- cartesian(a, set.union(b, c))
ident2.lhs &lt;- set.union(cartesian(a, b), cartesian(a, c))

isequalset(ident2.rhs, ident2.lhs)
## [1] TRUE
</pre>
<pre>
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
</pre>
<pre>
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
</pre>
<p>The third identity <img alt="(A \cap B) \times C = (A \times C) \cap (B \times C)" title="(A \cap B) \times C = (A \times C) \cap (B \times C)" src="https://s0.wp.com/latex.php?latex=%28A+%5Ccap+B%29+%5Ctimes+C+%3D+%28A+%5Ctimes+C%29+%5Ccap+%28B+%5Ctimes+C%29&bg=ffffff&fg=000&s=0" class="latex">.</p>
<pre>
ident3.rhs &lt;- cartesian(set.intersection(a, b), c)
ident3.lhs &lt;- set.intersection(cartesian(a, c), cartesian(b, c))

isequalset(ident3.rhs, ident3.lhs)
## [1] TRUE
</pre>
<pre>
as.data.frame(ident3.rhs)
##   c.2..1. c.2..4. c.2..7.
## 1       2       2       2
## 2       1       4       7
</pre>
<pre>
as.data.frame(ident3.lhs)
##   c.2..1. c.2..4. c.2..7.
## 1       2       2       2
## 2       1       4       7
</pre>
<p>We finish the post with the fourth identity <img alt="(A \cup B) \times C = (A \times C) \cup (B \times C)" title="(A \cup B) \times C = (A \times C) \cup (B \times C)" src="https://s0.wp.com/latex.php?latex=%28A+%5Ccup+B%29+%5Ctimes+C+%3D+%28A+%5Ctimes+C%29+%5Ccup+%28B+%5Ctimes+C%29&bg=ffffff&fg=000&s=0" class="latex">.</p>
<pre>
ident4.rhs &lt;- cartesian(set.union(a,b), c)
ident4.lhs &lt;- set.union(cartesian(a,c), cartesian(b,c))

isequalset(ident4.rhs, ident4.lhs)
## [1] TRUE
</pre>
<pre>
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
</pre>
<pre>
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
</pre>
<h6>References</h6>
<p>Enderton, H. (1977). Elements of set theory (1st ed.). New York: Academic Press.</p>
<p>MacGillivray, G. Cartesian Products and Relations. Victoria, BC. Retrieved from <a rel="nofollow" href="http://www.math.uvic.ca/faculty/gmacgill/guide/RF.pdf" target="_blank">http://www.math.uvic.ca/faculty/gmacgill/guide/RF.pdf</a></p>
<p>Stacho, Juraj (n.d.). Cartesian Product [PowerPoint slides]. Retrieved from <a rel="nofollow" href="http://www.cs.toronto.edu/~stacho/macm101.pdf" target="_blank">http://www.cs.toronto.edu/~stacho/macm101.pdf</a></p>
<p>The post <a rel="nofollow" href="http://www.aaronschlegel.com/set-theory-ordered-pairs-and-cartesian-product-with-r/" target="_blank">Set Theory Ordered Pairs and Cartesian Product with R</a> appeared first on <a rel="nofollow" href="http://www.aaronschlegel.com/" target="_blank">Aaron Schlegel</a>.</p>
	<p>
<div>
<div>To <strong>leave a comment</strong> for the author, please follow the link and comment on their blog: <strong><a href="http://www.aaronschlegel.com/set-theory-ordered-pairs-and-cartesian-product-with-r/"> R – Aaron Schlegel</a></strong>.</div>
<hr>
<a rel="nofollow" href="https://www.r-bloggers.com/">R-bloggers.com</a> offers <strong><a rel="nofollow" href="https://feedburner.google.com/fb/a/mailverify?uri=RBloggers">daily e-mail updates</a></strong> about <a rel="nofollow" href="https://www.r-project.org/" title="The R Project for Statistical Computing">R</a> news and <a rel="nofollow" href="https://www.r-bloggers.com/search/tutorial" title="R tutorials">tutorials</a> on topics such as: <a rel="nofollow" href="https://www.r-bloggers.com/search/data%20science" title="Data science">Data science</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/Big%20Data" title="Big Data">Big Data, <a rel="nofollow" href="https://www.r-users.com/" title="R jobs">R jobs</a>, visualization (<a rel="nofollow" href="https://www.r-bloggers.com/search/ggplot2" title="ggplot and ggplot2 tutorials">ggplot2</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/boxplot" title="Boxplots using lattice and ggplot2 tutorials">Boxplots</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/map" title="Maps and gis">maps</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/animation" title="Animation in R">animation</a>), programming (<a rel="nofollow" href="https://www.r-bloggers.com/search/RStudio" title="RStudio IDE for R">RStudio</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/sweave" title="Sweave and literate programming">Sweave</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/LaTeX" title="LaTeX in R">LaTeX</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/SQL" title="SQL and databases">SQL</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/eclipse" title="Eclipse IDE for R">Eclipse</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/git" title="git and github, Version Control System">git</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/hadoop" title="Large data in R using Hadoop">hadoop</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/Web+Scraping" title="Web Scraping of google, facebook, yahoo, twitter and more using R">Web Scraping</a>) statistics (<a rel="nofollow" href="https://www.r-bloggers.com/search/regression" title="Regressions and ANOVA analysis tutorials">regression</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/PCA" title="principal component analysis tutorial">PCA</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/time+series" title="Time series">time series</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/trading" title="finance trading">trading</a>) and more...
<img width="1" alt="" src="http://feeds.feedburner.com/~r/RBloggers/~4/kXE5hZOvH34" height="1"></a></div>