Skip to content

4 Relation

BCH4.pdf

Homework 4 Basic Concepts in Mathematics - 104002

Guangdong Technion

Yue Shi 999027873

Exercise 1. (25 points) Let \(R \subset A \times B\) and \(S \subset B \times C\) be two relations. Prove that \((S \circ R)^{-1} = R^{-1} \circ S^{-1}\).

Proof

  1. Right hand

    Since \(R^{-1}=\{(b,a)\in B\times A:aRb\}\subset B\times A\) and \(S^{-1}=\{(c,b)\in C\times B:bSc\}\subset C\times B\)​

    Then \(R^{-1}\circ S^{-1}=\{(a,c)\in C\times A:\exists b\in B\text{ such that }aRb\text{ and }bSc\}\subset C\times A\) by definition

  2. Left hand

    Since \(R \subset A \times B\) and \(S \subset B \times C\) are two relations, by definition \(S\circ R=\{(a,c)\in A\times C:\exists b\in B\text{ such that }aRb\text{ and }bSc\}\subset A\times C\)

    Then \((S\circ R)^{-1}=\{(c,a)\in C\times A:\exists b\in B\text{ such that }aRb\text{ and }bSc\}\subset C\times A\)

Thus \((S \circ R)^{-1} = R^{-1} \circ S^{-1}\)

Exercise 2. (25 points) Let \(A = \{a, b, c, d\}\). Find a relation on \(A\) that is

  1. reflexive and symmetric but not transitive.

    \(R=\{\left(a,a\right),\left(b,b\right)\left(c,c\right),\left(d,d\right),\left(a,b\right),\left(b,a\right),\left(b,c\right),\left(c,b\right)\}\)

    • Reflexive: \((a,a),(b,b),(c,c),\left(d,d\right)\)​
    • Symmetric: If \((a,b)∈R\), then \((b,a)∈R\). Similar for others
    • Not transitive: \((a,b)∈R\) and \((b,c)∈R\), but there is no \((a,c)\in R\)

  2. reflexive and transitive but not symmetric.

    \(R=\{\left(a,a\right),\left(b,b\right)\left(c,c\right),\left(d,d\right),\left(a,b\right),\left(b,c\right),\left(a,c\right)\}\)

    • Reflexive: \((a,a),(b,b),(c,c),\left(d,d\right)\)
    • Transitive: \((a,b)∈R\) and \((b,c)∈R\), there is \((a,c)\in R\)
    • Not symmetric: \((a,b)∈R\), but \((b,a)∉R\)

  3. symmetric and transitive but not reflexive.

    \(R=\left\lbrace\left(a,a\right)\right\rbrace\)

    • Symmetric: If \((a,a)\in R\), then \((a,a)\in R\)
    • Transitive: \((a,a)\in R\) and \((a,a)\in R\), there is \((a,a)\in R\)
    • Not reflexive: there is no \((b,b),\left(c,c\right),\left(d,d\right)\in R\)

Exercise 3. (25 points) Define a relation \(\sim\) on \(\mathbb{Z} \times \mathbb{N}\) as follows: \((a, b) \sim (a', b')\) iff \(ab' = a'b\).

Prove that \(\sim\) is an equivalence relation.

  • Reflexive: \((a,b)\sim(a,b)\) iff \(ab=ab\) yes
  • Symmetric: if \((a, b) \sim (a', b')\) iff \(ab' = a'b\), then we have \(a^{\prime}b=b^{\prime}a\), which is \((a^{\prime},b^{\prime})\sim(a,b)\) yes
  • Transitive: if \((a, b) \sim (a', b')\) iff \(ab' = a'b\) and \((a^{\prime},b^{\prime})\sim(a'',b'')\) iff \(a^{\prime}b''=b^{\prime}a''\), then we have \(\frac{a}{b}=\frac{a^{\prime}}{b^{\prime}}\) and \(\frac{a^{\prime}}{b^{\prime}}=\frac{a''}{b''}\).

Thus \(\frac{a}{b}=\frac{a''}{b''}\), then \(ab'' = a''b\), which is \((a, b) \sim (a'', b'')\) yes

Thus \(\sim\) is an equivalence relation.

Exercise 4. (25 points) Name a positive integer and a negative integer that are

If in some case it is not possible, explain why.

  1. congruent to \(0 \pmod{7}\) but not congruent to \(0 \pmod{8}\).

    The number is the multiple of \(7\) but not the multiple of \(8\)​

    Then \(x=7k(k\neq 8n,n\in\N)\)​

    Thus the positive integer is \(7\), the negative number is \(-7\)​

  2. congruent to \(3 \pmod{7}\) and congruent to \(4 \pmod{8}\).

    The number \(x-3\) is the multiple of \(7\) and \(x-4\) is the multiple of \(8\)

    Then \(x-3=7k,x-4=8n\Rightarrow x=7k+3,x=8n+4\)

    Thus \(7k+3=8n+4\Rightarrow8n=7k-1\Rightarrow n=\frac{7k-1}{8}\)

    Thus we can choose \(k=7,n=6\) to get the positive integer

    We can choose \(k=-1,n=-1\) to get the negative integer

    Thus the positive integer is \(52\), the negative number is \(-4\)

  3. congruent to \(0 \pmod{5}\) and congruent to \(2 \pmod{6}\).

    The number \(x\) is the multiple of \(5\) and \(x-2\) is the multiple of \(6\)

    Then \(x=5k,x-2=6n\Rightarrow x=5k,x=6n+2\)

    Thus \(5k=6n+2\Rightarrow6n=5k-2\Rightarrow n=\frac{5k-2}{6}\)

    Thus we can choose \(k=4,n=3\) to get the positive integer

    We can choose \(k=-2,n=-2\) to get the negative integer

    Thus the positive integer is \(20\), the negative number is \(-10\)

  4. congruent to \(3 \pmod{4}\) and congruent to \(4 \pmod{6}\).

    The number \(x-3\) is the multiple of \(4\) and \(x-4\) is the multiple of \(6\)

    Then \(x-3=4k,x-4=6n\Rightarrow x=4k+3,x=6n+4\)

    Thus \(4k+3=6n+4\Rightarrow6n=4k-1\Rightarrow n=\frac{4k-1}{6}\)

    However, \(4k-1\) must be an odd number and \(6n\) must be a even number

    Thus we never can choose a proper integer to satisfy it.

    Thus this statement is impossible

‍