Relations are one of the key concepts in set theory and discrete mathematics. Understanding relations is essential for studying functions, graphs, databases, and many other areas. On the YÖS exam, problems on relations test your ability to analyze connections between elements of sets.
Definition: A binary relation on a set $A$ and a set $B$ (or a relation from $A$ to $B$) is any subset of the Cartesian product $A \times B$.
Notation: $R \subseteq A \times B$
If the elements $a$ and $b$ are in the relation $R$, we write: $aRb$ or $(a, b) \in R$
Special case: If $A = B$, we speak of a relation on the set $A$.
Example 1: The relation "greater than" on the set of natural numbers:$$R = \{(a, b) \mid a, b \in \mathbb{N}, a > b\}$$
Examples of pairs belonging to this relation: $(5, 3)$, $(10, 7)$, $(2, 1)$
Example 2: The relation "is the mother of" between the set of all women and the set of all people:$$R = \{(x, y) \mid x \text{ — мать } y\}$$
Example 3: The relation "divides" on the set of natural numbers:$$R = \{(a, b) \mid a, b \in \mathbb{N}, a | b\}$$ (where $a | b$ means "$a$ divides $b$")
Examples of pairs: $(2, 4)$, $(3, 9)$, $(5, 20)$
Example 4: The relation "is a friend of" on the set of students in a group:$$R = \{(x, y) \mid x \text{ и } y \text{ — друзья}\}$$
#### Method 1: Describing a property$$R = \{(a, b) \in A \times B \mid P(a, b)\}$$
where $P(a, b)$ is some logical condition
Example: $R = \{(x, y) \in \mathbb{R} \times \mathbb{R} \mid y = x^2\}$
#### Method 2: Explicit listing of pairs$$R = \{(a_1, b_1), (a_2, b_2), ..., (a_n, b_n)\}$$
Example: $R = \{(1, 1), (1, 2), (2, 2), (2, 3), (3, 3)\}$
#### Method 3: Graph of the relationA relation can be depicted as a graph, where the vertices are elements of the sets, and the arrows are the pairs in the relation.
#### Method 4: Matrix of the relation (table)For finite sets, a relation can be represented by a matrix, where at the intersection of row $a$ and column $b$ we place 1 if $(a, b) \in R$, and 0 otherwise.
Domain: The set of all first components of pairs in the relation $R$.
Notation: $D(R)$ or $Dom(R)$
Formally: $D(R) = \{a \in A \mid \exists b \in B: (a, b) \in R\}$
Range (Codomain/Image): The set of all second components of pairs in the relation $R$.
Notation: $R(B)$ or $Im(R)$
Formally: $R(B) = \{b \in B \mid \exists a \in A: (a, b) \in R\}$
Example 5: Let $A = \{1, 2, 3, 4\}$, $B = \{a, b, c, d\}$ and $R = \{(1, a), (2, b), (2, c), (3, d)\}$
Definition: A relation $R$ on a set $A$ is called reflexive if every element of $A$ is in the relation $R$ with itself.
Formally: $R$ is reflexive $\Leftrightarrow \forall a \in A: (a, a) \in R$
Examples of reflexive relations:- "equals" on the set of numbers: $a = a$ for all $a$- "is at the same latitude as" on the set of cities- "divides" on the set of natural numbers: every number divides itself
Counterexample (not reflexive):- "greater than" on the set of numbers: $a > a$ is false for all $a$
Definition: A relation $R$ on a set $A$ is called symmetric if $(a, b) \in R$ implies $(b, a) \in R$.
Formally: $R$ is symmetric $\Leftrightarrow \forall a, b \in A: (a, b) \in R \Rightarrow (b, a) \in R$
Examples of symmetric relations:- "equals" on the set of numbers: if $a = b$, then $b = a$- "is a friend of" (in the sense of mutual friendship)- "parallel to" for lines
Counterexample (not symmetric):- "greater than" on the set of numbers: $(5, 3) \in R$, but $(3, 5) \notin R$
Definition: A relation $R$ on a set $A$ is called antisymmetric if $(a, b) \in R$ and $(b, a) \in R$ imply $a = b$.
Formally: $R$ is antisymmetric $\Leftrightarrow \forall a, b \in A: ((a, b) \in R \text{ и } (b, a) \in R) \Rightarrow a = b$
Examples of antisymmetric relations:- "greater than or equal to" on the set of numbers: if $a \geq b$ and $b \geq a$, then $a = b$- "subset of" on a set of sets: if $A \subseteq B$ and $B \subseteq A$, then $A = B$- "divides" on the set of natural numbers
Remark: A relation can be both symmetric and antisymmetric only if it contains only pairs of the form $(a, a)$.
Definition: A relation $R$ on a set $A$ is called transitive if $(a, b) \in R$ and $(b, c) \in R$ imply $(a, c) \in R$.
Formally: $R$ is transitive $\Leftrightarrow \forall a, b, c \in A: ((a, b) \in R \text{ и } (b, c) \in R) \Rightarrow (a, c) \in R$
Examples of transitive relations:- "equals" on the set of numbers: if $a = b$ and $b = c$, then $a = c$- "greater than" on the set of numbers: if $a > b$ and $b > c$, then $a > c$- "parallel to" for lines: if line $\ell_1$ is parallel to $\ell_2$, and $\ell_2$ is parallel to $\ell_3$, then $\ell_1$ is parallel to $\ell_3$
Counterexample (not transitive):- "is a parent of": if $a$ is the parent of $b$, and $b$ is the parent of $c$, then $a$ is the grandparent of $c$, but not the parent
Definition: A relation $R$ on a set $A$ is called an equivalence relation if it is simultaneously reflexive, symmetric, and transitive.
Formally: $R$ is an equivalence relation $\Leftrightarrow$- Reflexivity: $\forall a \in A: (a, a) \in R$- Symmetry: $\forall a, b \in A: (a, b) \in R \Rightarrow (b, a) \in R$- Transitivity: $\forall a, b, c \in A: ((a, b) \in R \text{ и } (b, c) \in R) \Rightarrow (a, c) \in R$
Example 6: The relation "has the same remainder when divided by 3" on the set of natural numbers.
Example 7: The relation "is parallel to or coincides with" on the set of lines in a plane.
Example 8: The relation "has the same number of letters" on the set of Russian words.
Definition: The equivalence class of an element $a$ with respect to the relation $R$ is the set of all elements equivalent to $a$.
Notation: $[a]_R$ or $\bar{a}$
Formally: $[a]_R = \{b \in A \mid (a, b) \in R\}$
Properties of equivalence classes:1. An equivalence class is non-empty: $[a]_R \neq \emptyset$ (since $a \in [a]_R$ by reflexivity)2. Two equivalence classes are either equal or disjoint3. The union of all equivalence classes equals the original set $A$
Example 9: The relation "has the same remainder when divided by 3" on the set $\{0, 1, 2, 3, 4, 5, 6, 7, 8\}$.
Equivalence classes:- $[0] = \{0, 3, 6\}$ (remainder 0)- $[1] = \{1, 4, 7\}$ (remainder 1)- $[2] = \{2, 5, 8\}$ (remainder 2)
Definition: A relation $R$ on a set $A$ is called an order relation (or a partial order relation) if it is simultaneously reflexive, antisymmetric, and transitive.
Formally: $R$ is an order relation $\Leftrightarrow$- Reflexivity: $\forall a \in A: (a, a) \in R$- Antisymmetry: $\forall a, b \in A: ((a, b) \in R \text{ и } (b, a) \in R) \Rightarrow a = b$- Transitivity: $\forall a, b, c \in A: ((a, b) \in R \text{ и } (b, c) \in R) \Rightarrow (a, c) \in R$
Definition: A relation $R$ is called a strict order if it is antireflexive ($(a, a) \notin R$ for all $a$), asymmetric, and transitive.
Examples:- The relation "strictly greater than" on the set of numbers- The relation "is a proper subset of" on a set of sets
Definition: An order relation is called total (linear) if for any two elements $a$ and $b$, either $(a, b) \in R$ or $(b, a) \in R$ (or both) holds.
Examples of total order:- "greater than or equal to" on the set of real numbers- Alphabetical order on the set of words
Example of a partial order (not total):- The relation "divides" on the set of natural numbers: the numbers 2 and 3 are incomparable (neither divides the other)
Definition: The inverse relation of a relation $R \subseteq A \times B$ is the relation $R^{-1} \subseteq B \times A$ defined as:
$$R^{-1} = \{(b, a) \mid (a, b) \in R\}$$
Example 10: If $R = \{(1, a), (2, b), (3, c)\}$, then:$$R^{-1} = \{(a, 1), (b, 2), (c, 3)\}$$
Definition: The composition of relations $R_1 \subseteq A \times B$ and $R_2 \subseteq B \times C$ is the relation $R_2 \circ R_1 \subseteq A \times C$ defined as:
$$(R_2 \circ R_1) = \{(a, c) \mid \exists b \in B: (a, b) \in R_1 \text{ и } (b, c) \in R_2\}$$
Read as: "$R_2$ after $R_1$" or "$R_2$ composed with $R_1$"
Important: Order matters! $R_2 \circ R_1 \neq R_1 \circ R_2$ in general.
Example 11: Let:- $R_1$ = "is the father of" (a relation from the set of people to the set of people)- $R_2$ = "is the mother of" (a relation from the set of people to the set of people)
Then $R_2 \circ R_1$ = "is the mother of the father" = "is the grandmother (on the paternal side)"
If $A$ and $B$ are finite sets, then:
$$|A \times B| = |A| \cdot |B|$$
Example 12: If $|A| = 3$ and $|B| = 4$, then $|A \times B| = 3 \cdot 4 = 12$
Since a relation $R$ from $A$ to $B$ is a subset of $A \times B$, the number of all possible relations from $A$ to $B$ is:
$$2^{|A \times B|} = 2^{|A| \cdot |B|}$$
Example 13: From a set of 2 elements to a set of 3 elements, one can define $2^{2 \cdot 3} = 2^6 = 64$ different relations.
On the set $A = \{1, 2, 3, 4\}$, the relation $R = \{(1,1), (1,2), (2,2), (2,3), (3,3), (3,4), (4,4)\}$ is given.
Is this relation:a) reflexive?b) symmetric?c) transitive?d) an equivalence relation?e) an order relation?
Solution:
a) Reflexivity: We check whether the pairs $(a, a)$ are present for all $a \in A$. - $(1, 1) \in R$ ✓ - $(2, 2) \in R$ ✓ - $(3, 3) \in R$ ✓ - $(4, 4) \in R$ ✓
Answer: Yes, reflexive
b) Symmetry: We check whether it is true that if $(a, b) \in R$, then $(b, a) \in R$. - $(1, 2) \in R$, but $(2, 1) \notin R$
Answer: No, not symmetric
c) Transitivity: We check whether it is true that if $(a, b) \in R$ and $(b, c) \in R$, then $(a, c) \in R$. - $(1, 2) \in R$ and $(2, 2) \in R$ $\Rightarrow$ $(1, 2) \in R$ ✓ - $(1, 2) \in R$ and $(2, 3) \in R$ $\Rightarrow$ $(1, 3) \in R$? We check: $(1, 3) \notin R$ ✗
Answer: No, not transitive
d) Equivalence relation: Requires reflexivity, symmetry, and transitivity. Since the relation is not symmetric and not transitive, it is not an equivalence relation.
e) Order relation: Requires reflexivity, antisymmetry, and transitivity. - Reflexive ✓ - Antisymmetric: if $(a, b) \in R$ and $(b, a) \in R$, then $a = b$. We check: the only such pairs are of the form $(a, a)$. ✓ - Not transitive (from part c)
Answer: No, not an order relation (due to the absence of transitivity)
On the set $A = \{-3, -2, -1, 0, 1, 2, 3, 4, 5\}$, the equivalence relation is given:$$R = \{(a, b) \mid a \equiv b \pmod{3}\}$$
(that is, $a$ and $b$ give the same remainder when divided by 3)
Find all equivalence classes.
First, let's find the remainders when dividing by 3 for each element:- $-3 \equiv 0 \pmod{3}$- $-2 \equiv 1 \pmod{3}$- $-1 \equiv 2 \pmod{3}$- $0 \equiv 0 \pmod{3}$- $1 \equiv 1 \pmod{3}$- $2 \equiv 2 \pmod{3}$- $3 \equiv 0 \pmod{3}$- $4 \equiv 1 \pmod{3}$- $5 \equiv 2 \pmod{3}$
Equivalence classes:- $[0] = \{-3, 0, 3\}$ (remainder 0)- $[1] = \{-2, 1, 4\}$ (remainder 1)- $[2] = \{-1, 2, 5\}$ (remainder 2)
Answer: Three equivalence classes: $\{-3, 0, 3\}$, $\{-2, 1, 4\}$, $\{-1, 2, 5\}$
On the set of people, the following relations are defined:- $R$ = "is a child of"- $S$ = "is a spouse of"
Describe the relation $S \circ R$ (composition of $R$ and $S$).
$(S \circ R)(a, c) \Leftrightarrow \exists b: R(a, b) \text{ и } S(b, c)$
This means: there exists a person $b$ such that $a$ is a child of $b$, and $b$ is a spouse of $c$.
Therefore, $a$ is a child of the spouse of $c$, that is, $a$ is the stepson/stepdaughter of $c$.
Answer: $S \circ R$ = "is a stepson/stepdaughter of"
The relation $R = \{(1, 2), (1, 3), (2, 3), (2, 4), (3, 4)\}$ is given.
Find:a) $R^{-1}$b) $D(R)$ and $R(\{1, 2, 3, 4\})$c) $D(R^{-1})$ and $R^{-1}(\{1, 2, 3, 4\})$
a) $R^{-1} = \{(2, 1), (3, 1), (3, 2), (4, 2), (4, 3)\}$
b) $D(R) = \{1, 2, 3\}$ (all first components) $R(\{1, 2, 3, 4\}) = \{2, 3, 4\}$ (all second components)
c) $D(R^{-1}) = \{2, 3, 4\}$ (this is the range of the original relation) $R^{-1}(\{1, 2, 3, 4\}) = \{1, 2, 3\}$ (this is the domain of the original relation)
How many relations can be defined from the set $A = \{a, b\}$ to the set $B = \{1, 2, 3\}$?
$|A| = 2$, $|B| = 3$$|A \times B| = 2 \cdot 3 = 6$
The number of all subsets of $A \times B$:$$2^{|A \times B|} = 2^6 = 64$$
Answer: 64 relations
### Mistake 1: Confusion in the definition of transitivityWrong: If $(a, b) \in R$, then $(b, a) \in R$.Right: Transitivity requires: if $(a, b) \in R$ AND $(b, c) \in R$, then $(a, c) \in R$.
### Mistake 2: Incorrect application of equivalence propertiesWrong: A relation can be symmetric and antisymmetric at the same time.Right: A relation can be both symmetric and antisymmetric only if it contains only pairs of the form $(a, a)$.
### Mistake 3: Forgetting that a relation can be emptyWrong: The empty relation $\emptyset$ does not satisfy any properties.Right: The empty relation is reflexive on the empty set, and on a non-empty set — antireflexive.
### Mistake 4: Wrong order in compositionWrong: $R \circ S$ means first $R$, then $S$.Right: $R \circ S$ means first $S$, then $R$. ($(R \circ S)(a, c) \Leftrightarrow \exists b: S(a, b) \text{ и } R(b, c)$)
### Mistake 5: Confusion between order relation and linear orderWrong: All order relations allow one to compare any two elements.Right: Only a linear (total) order allows this. In a partial order, some elements may be incomparable.
### Mistake 6: Incorrect definition of an equivalence classWrong: The equivalence class of an element $a$ is the set of elements that are not equivalent to $a$.Right: The equivalence class of an element $a$ is the set of all elements that are equivalent to $a$.
### Tip 1: Organized checking of propertiesWhen checking whether a relation has a property, create a table:
| Property | Definition | Result ||----------|-------------|-----------|| Reflexivity | All pairs $(a,a)$ in $R$ | Yes/No || Symmetry | If $(a,b)$ then $(b,a)$ | Yes/No || Antisymmetry | If $(a,b)$ and $(b,a)$ then $a=b$ | Yes/No || Transitivity | If $(a,b)$ and $(b,c)$ then $(a,c)$ | Yes/No |
### Tip 2: Visualization of the relationFor finite sets, draw the graph of the relation. This helps:- To clearly see the loops (reflexivity)- To find two-way arrows (symmetry)- To check chains (transitivity)
Equivalence relations:- Equality- Congruence modulo $n$- "Has the same number of elements" (for sets)
Order relations:- "Greater than or equal to"- "Subset of"- "Divides"
### Tip 4: Checking for counterexamplesFor each property, find a counterexample or verify that there is none:- Reflexivity fails? Find an element without a pair $(a, a)$- Symmetry fails? Find a pair $(a, b) \in R$ with $(b, a) \notin R$
### Tip 5: Using Hasse diagramsFor order relations, use a Hasse diagram to visualize the order structure.
### Tip 6: Attention to wordingIn problems on relations, understand precisely:- Is the relation defined on one set or from one set to another?- Are the pairs ordered?- What universal set is being used?
### Tip 7: Practice with real-world examplesApply the theory of relations to real situations:- Friendship in a social network (symmetric relation)- Rating of athletes (order relation)- Classification of animals (equivalence relation)
### Tip 8: Checking the resultAfter solving a problem, check:- Have all required pairs been found?- Are there no extra pairs?- Does the result satisfy all the requirements of the problem?
---
Conclusion
Relations are a fundamental concept that connects elements of sets. Understanding various types of relations (equivalence, order) and their properties is important for success on the YÖS exam and further mathematical studies.
All course topics · Practice problems
Please enable JavaScript to use the practice app.