Relations- Homogeneous and Heterogeneous
Let’s start with the technical definition of a relation.
A relation \(R\) is nothing more than a subset of all ordered pairs from a given Cartesian Product, where an ordered pair is in the set (i.e. the relation) \(R\) if two elements are related. Note that we do not restrict the symbol used to represent the relation to letters such as \(R\). Often, we use other symbols. Ones you are familiar with? \(\vert,=,\leq, >, \equiv\).
More often than not, relations are defined either using set builder notation or by describing the relation verbally or symbolically.
Quick Example: Let \(M_0=\{1,2,…,10\}\) and let \(M_1=\{11,12,13,…,19,20\}\). We can define a relation \(D\) as the set \(\{(a,b)\vert\ a\in M_0,\ b\in M_1,\ \text{and}\ a\vert b\}\). This relation is the set of all ordered pairs where the first entry is in \(M_0\), and the second entry is in \(M_1\) and \(a\) divides \(b\). So, by how this set/relation is defined, \((2,12),(2,14),(2,16),(2,18),(2,20)\) are elements of \(D\) (but certainly are not all the elements of \(D\)), because \(2\) divides each of \(12,14,16,18\) and \(20\). One could then write (if so desired), \(2D12,2D14,2D16,2D18,2D20\). Note that pairs like \((3,13)\) or \((4,15) \notin D\) (because \(3\) doesn’t divide \(13\) and \(4\) doesn’t divide \(15\)).
In other words, a set is homogeneous if we are relating elements from the same set, and heterogeneous if we are relating elements from different sets.
The example relation given above the last definition is an example of a heterogeneous relation because the sets over which we are relating are different.
Examples of Homogenous Relations (that you’ve seen before)
- Equality of real numbers: \(“=”\) defined as the set \(\{(a,b)|\ a,b\in \mathbb{R}\ \text{and}\ a\ \text{equals}\ b\}\).
- Divides: \(“\vert” =\{(a,b)|\ \text{there exists}\ c\in\mathbb{Z}\ \text{such that}\ b=a\cdot c\}\)
- Equivalence, mod \(m\): \(“\equiv_{mod\ m}” =\{(a,b)\vert\ a,b\in\mathbb{Z},\ \text{and}\ m\vert(b-a)\}\)
- Less than: \(“<” =\{(a,b)|\ a,b\in\mathbb{R}\ \text{and a is strictly less than}\ b\}\).
a.) False
b.) True
c.) True
d.) False
e.) True
For all of these, one could either write out every element in the relation \(D\), or just determine whether or not the \(a\) or \(b\) given meet the conditions specified in the description of the relation (in the second part of set builder notation).
a.) False, because \((0,2)\notin D\). In other words, while \(0\in A\), \(2\notin B\) so \(2\) and \(2\) can’t be related because we needed the second entry \(2\) to be in \(B\), and its not.
b.) True. \((3,4)\in D\). In other words, \(3\in A\) and \(4\in B\) and \(3\leq 4\).
c.) True. Same reason as above.
d.) False. \(6\notin A\), so \((6,7)\notin D\).
e.) True. \(4\) is present in both \(A\) and \(B\), and \(4\) is less than or equal to \(4\).
\(\{10,12,14,16,18,20,22,24,26,28,30\}\)
Our relation, in words, is defined to be the set of all ordered pairs \((x,y)\) such that \(x\) divides \(y\) evenly, and (of course) \(x\) is in the first set \(P\) and \(Y\) is in the second set.
We are looking for the set of all elements \(q\) from the second set such that \(2Rq\), i.e. the set of all second-set-stuff that \(2\) divides. That set is precisely \(\{10,12,14,16,18,20,22,24,26,28,30\}\).
Note that most of these problems really come down to “definition unpacking.”
\(\{2,3,5\}\)
We are looking for the set of all \(p\in P\) such that \(p\) is related to \(30\) via \(S\). everything in \(P\) that divides \(30\).
Note: Be careful to use the definition of the set, and not a verbal interpretation of what might be in the set (i.e. “coprime numbers”). You might miss elements.
\((2,3),(2,5),(3,2),(3,4),(3,5),(4,3),(4,5),(5,2),(5,3),(5,4),(5,6)\)
Yes. It is true that \(aCb\) implies \(bCa\) as well for all \(a,b \in A\).
Here we are looking for the set of all ordered pairs \((a,b)\) where \(\text{gcd}(a,b)=1\), that is, the set of all pairs of numbers (in any order) from \(A\) that share no common factor (i.e. are coprime).
What we are asking for, with determining whether \(aCb\) implies \(bCa\) for all \(a,b \in A\), is whether we can swap the order of the elements of a pair \((a,b)\) in the relation \(C\) and still have an element of \(C\). In this case, the answer is “yes.” Notice that if \((x,y)\) is in the set, so is \((y,x)\). e.g. \((2,3)\in C\) and so is \((3,2)\), \((2,5)\in C\) and so is \((5,2)\), etc… for all pairs.
When a relation has this property, it is called symmetric. More on this later.
\(“\geq”=\{(a,b)|\ a,b\in\mathbb{R}\ \text{and}\ a\ \text{is greater than or equal to}\ b\}\)
Relations are technically just a set of ordered pairs. So here, we are looking for a set of ordered pairs such that a pair \((a,b)\) is in the set if and only if \(a\geq b\). Since we are essentially defining the symbol \(“\geq”\) we don’t want to use it in our set’s definition.