Skip to content

11.13 Relation

  1. \(\forall m,d\in \Z,d\neq0,\) then there exists \(q,r\in\Z\) such that \(m=d\cdot q+r~\text{with}~0\leq r<\left|d\right|\)

    \(d\) is divisor \(q\) is quotient \(r\) is reminder

    Proof

    First, uniqueness

    Suppose \(m>0,d>0\) and

    \(m=d\times q+r\) and also \(m=d\times q\prime+r\prime\) \(0\leq r<d\), \(0\leq r\prime<d\)

    (Two different integer divisions)

    Note that: if \(q=q\prime\Rightarrow r=r\prime\)

    Since \(d\times q+r=d\times q\prime+r\prime\)

    ‍

    Suppose \(q\neq q\prime\) then \(q>q\prime\) or \(q<q\prime\)

    Suppose \(q<q\prime\) Write

    \(r=m-dq=m-dq\prime+dq\prime-dq=r\prime+d(q\prime-q)\geq r\prime+d\geq d\)

    Contradiction! Then \(q=q\prime\)

    We have proved uniqueness.

    Now the existence: \(m>0,d>0\)

    Consider the set \(A=\{x\in\N:m=d\times q+x~for~some~q\in\Z\}\)

    Note that \(A\neq \emptyset\), since \(m=d\times 0+m\Rightarrow m\in A\)

    By W.O.P. A has a first element: \(r=min(A)\)

    Since \(r\in A\), we have \(m=d\times q+r\) ,\(r\geq 0\)

    We still need to prove that \(0\leq r<d\)

    Suppose not : \(r\geq d\)

    \(m=dq+r=d(q+1)+r-d\Rightarrow r-d\in A,r-d<r\)

    Contradiction

    So, \(0\leq r<d\)

  2. Prove \(T \circ (S \circ R) = (T \circ S) \circ R\) for \(R \subseteq A \times B\), \(S \subseteq B \times C\), \(T \subseteq C \times D\).

    Solution:
    If \((a,d) \in T \circ (S \circ R)\), then that means by definition that \(\exists \, c \in C\) such that \((a, c) \in S \circ R\) and \((c, d) \in T\), and \(a \in A\).

    So I know that:
    If \((a, d) \in T \circ (S \circ R)\) then: \(a \in A\), \(\exists \, c \in C\) such that \((\exists \, b \in B \text{ such that } (a, b) \in R \text{ and } (b, c) \in S)\), and \((c, d) \in T\).

    If \((a, d) \in (T \circ S) \circ R \Rightarrow a \in A\) and \(\exists \, b \in B\) such that \((a, b) \in R\) and \((b, d) \in T \circ S\).

    If \((a, d) \in (T \circ S) \circ R \Rightarrow a \in A\) and \(\exists \, b \in B\) such that \((a, b) \in R\) and \(\exists \, c \in C\) such that \((b, c) \in S\) and \((c, d) \in T\).