EDB — 20Q

[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}

  193

  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}

  194

  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 . \]