Active domain and range

The active domain contains first coordinates that occur in relation pairs; the range contains second coordinates that occur.

A relation whose domain and codomain are the same set.

A relation in which each domain element is related to at most one codomain element.

Composition of relations

For $R$ from $X$ to $Y$ and $S$ from $Y$ to $Z$, $x(S \circ R)z$ holds when some $y \in Y$ satisfies $xRy$ and $ySz$.

The smallest reflexive relation containing the given relation; it adds any missing pairs $(x,x)$.

Discrete mathematicsLesson 1 of 1 in the course Set theory and relations

Binary Relations: Operations, Properties, Functions, and Applications

5 flashcards · 5 quiz questions · 5 match pairs · 5 fill-in sentences · English

Save course

Lesson progress

0 / 5

Your progress is kept in this browser only.Sign up to save it

Summary

A binary relation is a way to specify which elements of one set are connected to which elements of another set. It formalizes ideas such as “divides,” “is adjacent to,” and “is greater than.”

For sets $X$ and $Y$ , their Cartesian product is

$X \times Y = \{(x,y) \mid x \in X,\ y \in Y\}.$

Thus a relation is simply a selection of pairs from all possible pairs in $X \times Y$ . If $(x,y) \in R$ , we say that $x$ is related to $y$ by $R$ , and write $xRy$ .

All flashcards

Active domain and range: The active domain contains first coordinates that occur in relation pairs; the range contains second coordinates that occur.
Homogeneous relation: A relation whose domain and codomain are the same set.
Functional relation: A relation in which each domain element is related to at most one codomain element.
Composition of relations: For $R$ from $X$ to $Y$ and $S$ from $Y$ to $Z$ , $x(S \circ R)z$ holds when some $y \in Y$ satisfies $xRy$ and $ySz$ .
Reflexive closure: The smallest reflexive relation containing the given relation; it adds any missing pairs $(x,x)$ .

Quiz questions

What does the converse of a relation do to each ordered pair?Answer: It reverses the pair's coordinates.
A relation from $X$ to $Y$ is surjective when which condition holds?Answer: Every element of $Y$ is related to at least one element of $X.
Which properties define an equivalence relation?Answer: Reflexivity, symmetry, and transitivity.
In a Boolean matrix representation of relations, what does Boolean matrix multiplication correspond to?Answer: Composition of relations.
How is an $n$ -ary relation on sets $X_1,\ldots,X_n$ defined?Answer: As a subset of $X_1 \times \cdots \times X_n$ .

Based on the Wikipedia article Binary relation, licensed CC BY-SA 4.0. Adapted into a summary, flashcards and quizzes.

All Discrete mathematics lessons

Discrete mathematicsPigeonhole Principle: Counting, Collisions, and Applications5 flashcards · 5 quiz questions · 4 gamesPlay free →Discrete mathematicsDe Morgan's Laws in Logic, Set Theory, and Boolean Algebra5 flashcards · 5 quiz questions · 4 gamesPlay free →

Summary

All flashcards

Quiz questions

More in Discrete mathematics