2.7 Projecting to the quotient [1Z5]

Definition 80

[23M]Let \(A\) be a set and \(\sim \) an equivalence relation. We denote by

\[ \frac A\sim \]

the quotient space, that is, the set of all equivalence classes; the canonical projection is the map \(\pi :A\to \frac A\sim \) that associates each \(x\in A\) with the class \([x]\in A/\sim \).

[20Q]

  • Suppose we have a function \(f:A→ C\); we will say that this is invariant (or ”compatible with \(∼\)”) if

    \begin{equation} ∀ x,y∈ A, \quad x∼ y⇒ f(x)=f(y)\quad .\label{eq:simRRR} \end{equation}
    81

    This implies that \(f\) is constant on each equivalence class; so \(f\) passes to the quotient, that is, there is a well-defined function \(\widetilde f:\frac A∼→ B\) such that \(\widetilde f([x]) = f(x)\) for each \(x∈ A\); i.e. \(\widetilde f◦ 𝜋≡ f\).

    (See PDF for figure)

  • Similarly we will proceed if \(f\) is a multi-argument function \(f:A_ 1× A_ 2× \ldots A_ n→ C\), and on one or more of these sets \(A_ 1\) there are equivalence relations: in this case we can pass the associated variables to the quotients. For example when there is an equivalence relation \(∼\) on \(A_ 1\), we will require that

    \[ ∀ x,y∈ A_ 1,∀ a_ 2∈ A_ 2\ldots ∀ a_ n∈ A_ n\ldots \quad x∼ y⇒ f(x,a_ 2,\ldots a_ n)=f(y,a_ 2,\ldots a_ n) \]

    and then we can switch to the quotient and define the function \(\widetilde f:{\frac{A_ 1}∼ }× A_ 2× \ldots A_ n→ C\) so that

    \[ \widetilde f(𝜋(x),a_ 2,\ldots a_ n)=f(x,a_ 2,\ldots a_ n)\quad . \]

  • Similar reasoning can be made for relation \(R∈ A× B\); formally we can go back to the previous case, thinking of \(R\) as a function that has domain \(A× B\) and the set \(\{ ''\mathrm{true}'' , ''\mathrm{false}''\} \) as image; more explicitly, we will say that \(R\) is invariant with respect to the relation \(∼\) on \(A\) if

    \[ ∀ x,y∈ A,∀ b∈ B \quad x∼ y⇒ ( xRb ⇔ yRb)\quad ; \]

    and in this case we can define the relation \(\widetilde R\) ”projected to quotient” between \(\frac A∼\) and \(B\).

  • In some cases a function can be projected to the quotient in domain and codomain; we present a simple case, with two variables, that will be used in the following. Consider a function \(f:A× A→ A\); it is invariant if
         (See PDF for figure)

    \begin{equation} ∀ x,\tilde x,y,\tilde y∈ A, \quad (x∼ \tilde x ∧ y∼\tilde y)⇒ f(x,y)∼ f(\tilde x,\tilde y)\quad ;\label{eq:sim-AA-A} \end{equation}
    82

    then \(f\) can be projected to the quotient, that is, the function

    \[ \widetilde f: \frac{A}∼ × \frac{A}∼ → \frac{A}∼ \]

    is well defined when abiding to the rule

    \[ ∀ x,y∈ A\quad \widetilde f([x],[y]) = [f(x,y)]\quad . \]

Proposition 83

[1Z6]

  • Suppose that the function \(f:A× A→ A\) is invariant for the equivalence relation \(∼\) in all its variables, in the sense defined in 82 let \(\tilde f\) be the projection to the quotient

    \[ \widetilde f:\frac A∼× \frac A∼→ \frac A∼\quad . \]

    If \(f\) is commutative (resp. associative) then \(\widetilde f\) is commutative (resp. associative).

  • If \(R\) is a relation in \(A× A\) invariant for \(∼\), and \(R\) is reflexive (resp symmetrical, antisymmetric, transitive) then \(\widetilde R\) is reflexive (resp symmetrical, antisymmetric, transitive).

  • Consider the ordered sets \((A,≤_ A)\) and \((B,≤_ B)\), let \(f:A→ B\) be a monotonic function; suppose moreover that \(≤_ A\) is invariant with respect to an equivalence relation \(∼\) on \(A\), e and let \(\widetilde f:{\frac{A}∼ }→ B\) be its projection to the quotient: then \(\widetilde f\) is monotonic.

Proposition 84

[1Z7] (Replaces 06G) (Replaces 06H) Consider \(R\) a transitive and reflexive relation in \(A× A\); such a relation is called a preorder [ 43 ] ; we define \(x ∼ y\iff (xRy ∧ yRx)\) then \(∼\) is an equivalence relation, \(R\) is invariant for \(∼\), and \(\widetilde R\) (defined as in 83) is an order relation.

Proof ▼

  1. \(∼\) is clearly reflexive and symmetrical; is transitive because if \(x∼ y,y∼ z\) then \(xRy∧ yRx∧ yRz∧ zRy\) but being \(R\) transitive you get \(xRz∧ zRx\) i.e. \(x∼ z\)

  2. Let \(x,y,\tilde x,\tilde y∈ X\) be such that \(x∼ \tilde x,y∼ \tilde y\) then we have \(xR\tilde x ∧ \tilde xRx∧ yR\tilde y∧ \tilde yRy\) if we add \(xRy\), by transitivity we get \(\tilde xR\tilde y\); and symmetrically.

  3. Finally, we see that \({\widetilde R}\) is an order relation on \(Y\). Using the (well posed) definition ”\([x]{\widetilde R}[y] \iff xRy\)” we deduce that \({\widetilde R}\) is reflexive and transitive (as indeed stated in the previous proposition). \({\widetilde R}\) is also antisymmetric because if for \(z,w∈ A/∼\) you have \(z{\widetilde R}w∧ w{\widetilde R}z\) then taken \(x∈ z,y∈ w\) we have \(xRy ∧ yRx\) which means \(x∼ y\) and therefore \(z=w\).

E84

[1Z8] \(ℤ\) are the relative integers with the usual operations. Let \(p≥ 1\) a fixed integer. Consider the equivalence relation

\[ n∼ m \iff p | (n-m) \]

that is, they are equivalent when \(n-m\) is divisible by \(p\).

Show that there are \(p\) equivalence classes \([0],[1],\ldots [p-1]\) We indicate the quotient space with \(ℤ/(pℤ)\) or more briefly \(ℤ_ p\).

Show that the usual operations of sum and product in \(ℤ\) are invariant (in the sense defined in 82), hence they pass to the quotient.