2018 | OriginalPaper | Chapter

# 3. Relations and Functions

Published in:
The Discrete Math Workbook

## Abstract

Binary relation between the elements of the sets A and B is the subset R of the direct product \(A\times B\). It is said that R is the relation on A if \(A=B\). If R is some binary relation, then instead of notation \((x, y)\in R\) designation \(x\;R\;y\) is often used.

Let \(A=\{x_1, x_2, \dots , x_n\}\), \(B=\{y_1, y_2, \dots , y_m\}\). Logical matrix of the relation R on \(A\times B\) is defined as matrix M of size \(n\cdot m\), whose elements \(M_{ij}=\text {T}\), if \((x_i, y_j)\in R\), and \(M_{ij}=\text {F}\), if \((x_i, y_j)\notin R\).

A binary relationship between elements of finite sets can be represented by a listing of ordered pairs, using suitable predicates, as well as in the form of a logical matrix or a directed graph (digraph, see chapter “Graphs”). If at least one of the sets A or B is not finite, the relation \(R\subseteq A\times B\) can be specified with the help of predicates.

In this chapter, the equivalence relations of partial and linear order are considered. An important special case of relations are functions. Function from a set A to a set B is a binary relation, for which each element from A is associated with the only element from the set B.

An idea of the types of functions is given:

1.

injection;

2.

surjection;

3.

bijection.

The Pigeonhole Principle is formulated.