MTH 325 Guided Practice 6.3: Properties of Relations

Overview

We've learned what relations on a set are, and we've learned how to represent relations as sets of ordered pairs, as verbal descriptions, as schematic diagrams, and as directed graphs. With these representations we can now study the properties that relations may or may not have. There are four main properties that we'll study: reflexive, symmetric, antisymmetric, and transitive. These properties describe information about the relation and can have useful real-world implications, as we'll see. We also learn about two important kinds of relations: partial orderings and equivalence relations.

Learning objectives

Basic objectives: Each student is responsible for gaining proficiency with each of these tasks prior to engaging in class discussions, through the use of the learning resources (below) and through the working of exercises (also below).

Advanced objectives: The following objectives are the subject of class discussion and further work; they should be mastered by each student during and following class discussions.

Learning resources

To gain proficiency in the learning objectives, use the following resources. You may include other resources if you wish, in addition to or in replacement of the following.

Textbook: In Applied Discrete Structures, read Section 6.3. Make sure to read actively, working through examples and activities as you go.

Video: Watch the following videos:

Exercises

The following exercises are to be done during and following your reading and viewing of the resources. Work these out on paper and then enter the responses into the appropriate submission form (see Submission Instructions) by the deadline. You will receive a mark of Pass if each item response shows a good-faith effort to be right and is submitted prior to the deadline.

  1. Consider the relation on the set \(\{1, 2, \dots, 10\}\) given by the following directed graph:

(Direct link: http://www.screencast.com/t/cLfZFBzW) At the submission form, check EACH statement about this relation that is true.

  1. Give an example of a relation on the set \(\{1, 2, 3, 4\}\) that is reflexive and symmetric, but not transitive. State your relation as a set of ordered pairs (although, you can use any representation you wish to start with).
  2. If you find antisymmetry to be somewhat difficult to understand, you're in good company. To help us grasp this concept better, we'll use Sage to help us. Below is an interactive Sage cell with some code in it. The first line of code generates a random directed graph on five vertices, and for each pair \((a,b)\) of vertices there is a 0.25 probability (25% chance) of an edge pointing from \(a\) to \(b\). The second line visualizes the graph. The third line prints out a Boolean (TRUE or FALSE) telling whether the relation represented by the digraph is antisymmetric or not. When you click EVALUATE you'll see the graph that is generated as well as the output for whether the relation is antisymmetric. You can also change the number of vertices and the probability of a connection and rerun the code.

Run this code several times -- dozens of times! -- and make a note of your observations of the directed graph and whether it is antisymmetric. What patterns do you notice, and how might one tell whether a relation is antisymmetric just by looking at its directed graph?

NOTE: To reset the code back to its original state, just refresh the page. If you cannot run the code in the embedded cell, copy it and then paste it into the cell found at https://sagecell.sagemath.org.


There is a final item at the response form that solicits any specific mathematical questions or comments you may have about the material in the reading or viewing. If you have any specific mathematical questions, leave them in the blank. Frequently occurring questions will be addressed during the discussion time in class. Other questions (good but not frequently occurring) will be replied to in person on through email. If you have no questions, just leave that item blank.


Submission instructions

Submit your responses using the form at this link: http://bit.ly/1NH7yRE