Properties of a binary relation
A binary relation on a finite set, given by its pairs, its matrix or its graph: reflexivity, symmetry, antisymmetry, transitivity, the converse relation and the transitive closure.
- 30 cards
- 4 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
- The numbers
A few cards from the deck
Binary relation on E: what is it?
Show the answer
A set of pairs of elements of E: x R y means that the pair (x, y) belongs to it. It is given by the list of its pairs, by a matrix of 0s and 1s, or by an arrow graph.
The order inside a pair matters: (1, 2) can belong to the relation without (2, 1) belonging to it.
On {1, 2, 3}, which properties does the relation R = {(1,1), (2,2), (3,3), (1,2), (2,1), (2,3)} have?
- Reflexive only
- Reflexive and symmetric
- Reflexive and transitive
- Reflexive, symmetric and transitive
Show the answer
Reflexive only
All three (x, x) are there: reflexive. (2,3) is present but not (3,2): not symmetric. (1,2) and (2,1) link two distinct elements: not antisymmetric. (1,2) and (2,3) would force (1,3), which is missing: not transitive.
A relation on E is … when it contains every pair (x, x): in its matrix, the … holds only 1s.
Show the answer
A relation on E is reflexive when it contains every pair (x, x): in its matrix, the diagonal holds only 1s.
A single 0 on the diagonal, that is one element not related to itself, is enough to break reflexivity.
Reflexive: what is it?
Show the answer
Said of a relation on E in which every element is related to itself: the pair (x, x) belongs to it for every x in E.
In the matrix, the diagonal holds only 1s; in the graph, every vertex has a loop. A single x without a loop is enough to break it.