Unit 6: Relations and Functions
In this unit, you will learn about binary relations from a set to a set
. Some of these relations are functions from
to
. Restricting our attention to relations from a set
to the set
, this unit discusses the properties of reflexivity(R), symmetry(S), anti-symmetry(A), and transitivity(T). Relations that satisfy R, S, and T are called equivalence relations, and those satisfying R, A, and T are called partial orderings.
Completing this unit should take you approximately 4 hours.
Upon successful completion of this unit, you will be able to:
- determine if a relation possesses certain properties, including reflexivity, symmetry, antisymmetry, and transitivity;
- recognize and prove that certain relations are equivalence relations;
- recognize and prove that certain relations are partial orderings and/or total orderings;
- recognize when a relation is a function; and
- determine when a function is one-to one and when it is onto.
6.1: Binary Relations on a Set A
Watch this video. It may be worth spending some time watching this video twice. The examples he provides exhibit several properties. These are the defining properties of an equivalence relation (see subunit 6.4) and Partial Ordering (see subunit 6.5).
6.2: Binary Relations from A to B
6.2.1: Relations that Are Functions
Watch this video, which illustrates the notions of relations and functions. This video also provides examples of relations that are functions and some that are not.
6.2.2: Injections, Surjections, and Bijections
Watch these videos.
6.3: Equivalence Relations
Watch the last 10 minutes of this video again. It is especially important that you understand the relationship between an equivalence relation and the partition it induces.
Read this page on equivalence relations. Then, answer the four questions at the bottom of the page.
6.4: Partial Orderings
Watch this lecture. When you have finished, read the lecture notes and attempt the problems in the problem set.
Unit 6 Assessment
- Receive a grade
Take this assessment to see how well you understood this unit.
- This assessment does not count towards your grade. It is just for practice!
- You will see the correct answers when you submit your answers. Use this to help you study for the final exam!
- You can take this assessment as many times as you want, whenever you want.
- Receive a grade
Take this assessment to see how well you understood this unit.
- This assessment does not count towards your grade. It is just for practice!
- You will see the correct answers when you submit your answers. Use this to help you study for the final exam!
- You can take this assessment as many times as you want, whenever you want.