Una observacion importante es que los conceptos de funcion \(\Sigma\)-efectivamente computable, de conjunto \(\Sigma\)-efectvamente computable y de conjunto \(\Sigma\)-efectivamente enumerable, no dependen del alfabeto \(\Sigma\). Esto lo establecemos formalmente en los dos siguientes lemas.
3.13. Sean \(\Sigma\) y \(\Gamma\) alfabetos cualesquiera. Supongamos una funcion \(f\) es \(\Sigma\)-mixta y \(\Gamma\)-mixta, entonces \(f\) es \(\Sigma\)-efectivamente computable sii \(f\) es \(\Gamma\)-efectivamente computable.
3.14. Sean \(\Sigma\) y \(\Gamma\) alfabetos cualesquiera. Supongamos un conjunto \(S\) es \(\Sigma\)-mixto y \(\Gamma\)-mixto, entonces \(S\) es \(\Sigma\)-efectivamente computable (resp. \(\Sigma\)-efectivamente enumerable) sii \(S\) es \(\Gamma\)-efectivamente computable (resp. \(\Gamma\)-efectivamente enumerable).
Dejamos al lector los detalles de las rutinarias pruebas de estos dos lemas.