11.1 Relations

Class: CSE 16 Subject: computer-science discrete-math Date: 2024-12-10 Teacher: Prof. Musacchio

Relations

Introduction

• a relation on a set $A$ is a subset $R\subseteq A\times A$. We often abbreviate the statement $(x,y)\in R$ as $xRy$. The statement $(x,y)\notin R$ is abbreviated as $x/Ry$

Example

• Let $A=\{1,2,3,4\}$, and consider the following set: $R=(1,1),(2,1),(2,2),(3,3),(3,2),(3,1),(4,4),(4,3),(4,2),(4,1)\subseteq A\times A$.

• The set $R$ is a relation on $A$, by Definition 11.1.

• Since $(1,1)\in R$, we have $1R1$. Similarly $2R1$ and $2R2$, and so on.

• However, notice that (for example) $(3,4)\notin R$, so $3/R4$. Observe that $R$ is the familiar relation ≥ for the set $A$.