20 - Properties of relations

!Screenshot 2023-10-24 at 9.46.44 PM.png
!Screenshot 2023-10-26 at 7.18.32 PM.png

In Class Practice

Def: Let R be a relation on a set A.

FOR ALL they have to hold true

1. We say that R is reflexive if $\mathrm{\forall }a\in A,aRa$
2. We say that R is symmetric if $\mathrm{\forall }a,b\in A,aRb⟹bRa$
3. We say that R is transitive if $\mathrm{\forall }a,b,c\in A,((aRb)\wedge (bRc))⟹(aRc)$
4. We say that R is antisymmetric if $\mathrm{\forall }a,b\in A,((aRb)\wedge (bRa))⟹a=b$

Example:
A = {1,2,3,4}
R =

HW 20

Ben Finch

E 20.1
a) a = 1, b = 2
b) a = 1, b = 5
c) $S_1=\{1,2,3,4\}$
$S_2=\{3,5,6\}$
$S_3=\{5\}$
$S_4=\{5,6\}$
$S_5=\mathrm{\varnothing }$
$S_6=\mathrm{\varnothing }$
d)
$T_1=\{1\}$
$T_2=\{1\}$
$T_3=\{1,2\}$
$T_4=\{1\}$
$T_5=\{2,3,4\}$
$T_6=\{2,4\}$

E 20.2

E 20.3

E 20.4

c)
Reflexive.
Proof. Assume $x\in \mathbb{R}$. Then $x-x=0\in \mathbb{Z}$ so $xRx$. Thus $R$ is reflexive. $◻$

Symmetric.
Proof. Assume $xRy$. Then $x-y\in \mathbb{Z}$. Thus $-(x-y)=y-x\in \mathbb{Z}$. Hence $R$ is symmetric. $◻$

Transitive.
Proof. Assume $xRy$ and $yRz$. Then $x-y\in \mathbb{Z}$ and $y-z\in \mathbb{Z}$.
This implies that $(x-y)+(y-z)=x-z\in \mathbb{Z}$, because the sum of two integers is always an integer. Hence, $xRz$. So, $R$ is transitive. $◻$

Antisymmetric.
Fix $x=-1$ and $y=0$. We have $xRy$ since $-1-0\in \mathbb{Z}$ and $yRx$ since $0-(-1)\in \mathbb{Z}$ but $-1\ne 0$. Thus $R$ is not reflexive.

E 20.5
a) {$(a,b)$ $\in$ ${\mathbb{Z}}^2$ : $a-b=2k$ for some $k\in \mathbb{Z}$}.
b)
Reflexive.
Proof. Assume $x\in \mathbb{Z}$. Then $x-x=2(0)$. Thus $xRx$. Thus $R$ is reflexive. $◻$

Symmetric.
Proof. Assume $aRb$. Then $a-b=2k$ for some $k\in \mathbb{Z}$. Thus $-(a-b)=b-a=2(-k)$. So $bRa$. Hence $R$ is symmetric. $◻$

Transitive.
Lemma. Let $x,y\in EVEN$. Then $x=2k,y=2z$ for some $k,z\in \mathbb{Z}$. Then $x-y=2k-2z=2(k-z)$. Hence the difference of two even integers is even. $◻$

Proof. Assume $aRb$ and $bRc$. Then $a-b\in EVEN$ and $b-c\in EVEN$. Thus $(a-b)-(b-c)=a-c$ is even since the difference of two even integers is even per the lemma. Thus we have $aRc$. Hence $R$ is transitive. $◻$

c)
Fix $a=4$, $b=2$. We have $aRb$ and $bRa$ since $4-2=2\in EVEN$ and $2-4=-2\in EVEN$ but $4\ne 2$. Thus $R$ is not antisymmetric $◻$

d) Any integers such that 1 (mod 2)

E 20.6
a) R =

b) R =

c) R =

d) R =

e) R =

f) R =

g) R =

h) R =

E 20.7
a) $$R ={(1,1), (2, 2), (3, 3), (1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2), (3, 4), (4, 4), (4, 3), (5, 5)}$$
b)
Reflexive.
Proof. R is reflexive since (1,1), (2,2), (3,3), (4,4), and (5, 5) are in R. $◻$

Symmetric.
Proof. Since we find (b, a) for all elements (a, b) in R, R is symmetric. $◻$

Transitive.
Disproof. Fix a = 1, b = 3, c = 4. We have $aRb$ and $bRc$ since $(1,3)\in R$ and $(3,4)\in R$. However $(1,4)\notin R$, so $a\mathrm{R̸}c$. Thus R is not transitive.

E 20.8
a)

b)
Reflexive. Disproof. Fix a = 3. We see $3\in A$ but not $3R3$ since $(3,3)\notin R$. Thus R is not reflexive.

Symmetric.
Proof. Since we find (b, a) for all elements (a, b) in R, R is symmetric. $◻$

Transitive.
Proof. For every pair (a, b) and (b, c) in R, (a, c) is also in R. Thus, we can conclude that R is transitive. $◻$