What's a good notation to show elements of relation composition? - Mathematics Educators Stack Exchange most recent 30 from matheducators.stackexchange.com 2022-01-27T03:07:03Z https://matheducators.stackexchange.com/feeds/question/20874 https://creativecommons.org/licenses/by-sa/4.0/rdf https://matheducators.stackexchange.com/q/20874 6 What's a good notation to show elements of relation composition? Daniel R. Collins https://matheducators.stackexchange.com/users/5563 2021-05-10T13:19:18Z 2021-05-13T11:23:26Z <p>Teaching discrete mathematics, we pose (from the textbook) questions on finding compositions of relations, notably, relations on very small finite sets with only 3 or 4 elements (as an introductory and tested exercise).</p> <p>I'm searching for some way of being very specific and concrete in pointing out the individual &quot;linkages&quot; that are producing elements in the composition relation. I've been frustrated that none of the textbooks I've checked ever shows an explicit example being worked out like this. It's always definition, boom, final composition relation in its entirety.</p> <p>For example, here's an exercise from the Rosen Discrete Math book:</p> <blockquote> <p>Let <span class="math-container">$R$</span> be the relation <span class="math-container">$\{(1,2),(1,3),(2,3),(2,4),(3,1)\}$</span>, and let <span class="math-container">$S$</span> be the relation <span class="math-container">$\{(2,1),(3,1),(3,2),(4,2)\}$</span>. Find <span class="math-container">$S \circ R$</span>.</p> </blockquote> <p><em>(*) Here's where I want some scratch/explanatory work, resulting in the answer:</em></p> <blockquote> <p><span class="math-container">$\{(1,1),(1,2),(2,1),(2,2)\}$</span></p> </blockquote> <p>Now, my instinct is to start writing something like: <span class="math-container">$(1,2) + (2,1) \implies (1, 1)$</span>, etc., but that's a multifold abuse of notation -- which my students are already greatly struggling with, so I want to set a good example.</p> <p>I really want something that can be written briefly in one line of text per element in the composition (e.g., not converting to a digraph and saying &quot;look at this, it's easy&quot;, or any other trick to make the problem &quot;easier&quot; -- the point is to document production of each individual element).</p> <p><strong>What's the best way to show work in finding elements of a relational composition (at point (*) above)?</strong></p> https://matheducators.stackexchange.com/questions/20874/-/20876#20876 3 Answer by user507 for What's a good notation to show elements of relation composition? user507 https://matheducators.stackexchange.com/users/0 2021-05-10T22:45:57Z 2021-05-10T22:51:31Z <p>Thanks for your feedback on my previous answer, which contained a misunderstanding. Here's a new try. I believe the following is the way to express the thought that you were trying to express as <span class="math-container">$(1,2) + (2,1) \implies (1, 1)$</span>, using only the notation your book seems to be using:</p> <p><span class="math-container">$\{(1,2)\}\circ\{(2,1)\}=\{(1,1)\}.$</span></p> <p>That is, your book defines a relation as a set of ordered pairs. We restrict our attention to one element of S and one element of R, forming singleton sets which represent relations that connect only two things (i.e., each of their graphs would be a single dot). We compose these two singleton relations and get one element of the composition of S with R. The complete composition of S and R would be the union of all such compositions of singletons with singletons.</p> https://matheducators.stackexchange.com/questions/20874/-/20878#20878 6 Answer by Trevor Wilson for What's a good notation to show elements of relation composition? Trevor Wilson https://matheducators.stackexchange.com/users/870 2021-05-12T06:06:18Z 2021-05-12T06:06:18Z <p>To explain why any particular ordered pair is in <span class="math-container">$S \circ R$</span>, you can just show that it satisfies the definition, which says that <span class="math-container">$(a,c)$</span> is in <span class="math-container">$S \circ R$</span> if there exists <span class="math-container">$b$</span> such that <span class="math-container">$(a,b) \in R$</span> and <span class="math-container">$(b,c) \in S$</span>. To show this is true, you can just give an example of such <span class="math-container">$b$</span> and observe that <span class="math-container">$(a,b) \in R$</span> and <span class="math-container">$(b,c) \in S$</span>. The two things here are connected with the word &quot;and&quot;; if you want to use a symbol for that, it should be <span class="math-container">$\wedge$</span> or <span class="math-container">$\And$</span>, not <span class="math-container">$+$</span>.</p> <p>For example, you could write:</p> <p><span class="math-container">$(1,3) \in R \quad \And \quad (3,2) \in S, \quad\text{so} \quad (1,2) \in S \circ R$</span>.</p> <p>This is already quite short, and I don't think you should write anything further removed from the definition of <span class="math-container">$S \circ R$</span> just to shorten it further.</p> https://matheducators.stackexchange.com/questions/20874/-/20881#20881 6 Answer by Massimo Ortolano for What's a good notation to show elements of relation composition? Massimo Ortolano https://matheducators.stackexchange.com/users/5367 2021-05-13T09:00:42Z 2021-05-13T11:23:26Z <p>I'd avoid introducing a new notation for such a limited scope: you won't probably use it elsewhere during the class, and it wouldn't be used elsewhere in the literature.</p> <p>I have three suggestions. The first is a simple variation of <a href="https://matheducators.stackexchange.com/a/20878/5367">Trevor Wilson's answer</a>, which mirrors the first relation sign to keep the bridging elements together:</p> <p><span class="math-container">$$R\ni(1,3) \And (3,2) \in S\Rightarrow (1,2) \in S \circ R$$</span></p> <p>The second is to use a table, structured as follows:</p> <div class="s-table-container"> <table class="s-table"> <thead> <tr> <th><span class="math-container">$(a,b) \in R$</span></th> <th><span class="math-container">$(b,c) \in S$</span></th> <th><span class="math-container">$(a,c) \in S \circ R$</span></th> </tr> </thead> <tbody> <tr> <td><span class="math-container">$(1,3)$</span></td> <td><span class="math-container">$(3,1)$</span></td> <td><span class="math-container">$(1,1)$</span></td> </tr> <tr> <td><span class="math-container">$(1,3)$</span></td> <td><span class="math-container">$(3,2)$</span></td> <td><span class="math-container">$(1,2)$</span></td> </tr> <tr> <td>...</td> <td>...</td> <td>...</td> </tr> </tbody> </table> </div> <p>The third is another table, where the first column lists the pairs from <span class="math-container">$R$</span>, and the first row lists the pairs from <span class="math-container">$S$</span>. Then, you mark the intersections which have an element in common (this might possibly reduce mistakes from the students):</p> <div class="s-table-container"> <table class="s-table"> <thead> <tr> <th></th> <th><span class="math-container">$(2,1)$</span></th> <th><span class="math-container">$(3,1)$</span></th> <th><span class="math-container">$(3,2)$</span></th> <th><span class="math-container">$(4,2)$</span></th> </tr> </thead> <tbody> <tr> <td><span class="math-container">$(1,2)$</span></td> <td><span class="math-container">$(1,1)$</span></td> <td></td> <td></td> <td></td> </tr> <tr> <td><span class="math-container">$(1,3)$</span></td> <td></td> <td><span class="math-container">$(1,1)$</span></td> <td><span class="math-container">$(1,2)$</span></td> <td></td> </tr> <tr> <td><span class="math-container">$(2,3)$</span></td> <td></td> <td><span class="math-container">$(2,1)$</span></td> <td><span class="math-container">$(2,2)$</span></td> <td></td> </tr> <tr> <td>...</td> <td>...</td> <td>...</td> <td>...</td> <td>...</td> </tr> </tbody> </table> </div>