Artículo de Wikipedia sobre notación set-builder explica que el conjunto $\{f(x) : P(x)\}$ es igual a $\{y : \exists x [y=f(x) \land P(x)]\}$ . Por lo que he entendido, $S = \{f(x) : P(x)\}$ puede expresarse en lógica de predicados como $\forall x[f(x) \in S \leftrightarrow P(x)]$ mientras que $S = \{y : \exists x [y=f(x) \land P(x)]\}$ puede escribirse como $\forall y [y \in S \leftrightarrow \exists x[y=f(x) \land P(x)]]$ . Sin embargo, estas dos fórmulas son lógicamente equivalentes, sólo si la función $f$ es invertible. ¿Es correcto?
Respuesta
¿Demasiados anuncios?
Es cierto que, en general (es decir, para una función genérica $f$ ), las frases \begin{align}\tag{1} \forall x \, [f(x) \in S &\leftrightarrow P(x)] \\ \tag{2} \forall y \, [y \in S &\leftrightarrow \exists x [y = f(x) \land P(x)]] \end{align} no son lógicamente equivalentes. Más precisamente:
- $(1)$ no implica $(2)$ pero la implicación se cumple si la función $f$ es suryectiva en $S$ (es decir $S$ se incluye en la imagen de $f$ ).
- $(2)$ no implica $(1)$ pero la implicación se cumple si la función $f$ es inyectiva en $S$ (es decir, para todos $x$ y $x'$ en el ámbito de $f$ si $f(x) = f(x') \in S$ entonces $x = x'$ );
Las sentencias $(1)$ y $(2)$ son lógicamente equivalentes si la función $f$ es invertible en $S$ (es decir, inyectiva en $S$ y suryectiva en $S$ ). Pero aún es posible, a priori que para algunos función $f$ no invertible en $S$ , $(1)$ y $(2)$ son equivalentes.
Sin embargo, la cuestión es que la definición $S = \{f(x) : P(x)\}$ no se expresa en lógica de predicados mediante $(1)$ pero sólo mediante $(2)$ . De hecho, establecer $S = \{f(x) : P(x)\}$ (o equivalentemente, $S = \{y : \exists x \, [y = f(x) \land P(x)]\}$ ) significa que los elementos de $S$ son todas y sólo las imágenes a través de $f$ de los puntos con la propiedad $P$ .
¿Por qué la frase $(1)$ no significa que $S = \{f(x) : P(x)\}$ ?
En primer lugar, la frase $(1)$ no dice nada sobre los elementos de $S$ que no sean de la forma $f(x)$ Por lo tanto $(1)$ no excluye la posibilidad de que $S$ puede tener algunos elementos que no están en la imagen de la función $f$ . Pero la definición $S = \{f(x) : P(x)\}$ y la frase $(2)$ excluyen esta posibilidad. Obsérvese que esa posibilidad queda excluida siempre que $f$ es suryectiva en $S$ es decir, cuando $S$ es un subconjunto de la imagen de $f$ : esta es la razón por la que $(1)$ implica $(2)$ cuando $f$ es suryectiva en $S$ .
Además, la sentencia $(2)$ y la definición $S = \{f(x) : P(x)\}$ no excluyen la posibilidad de que $P(x')$ mantiene pero $P(x)$ no lo hace, para algunos $x \neq x'$ con $f(x) = f(x')$ Por lo tanto, en ese caso $f(x) \in S$ (porque $f(x) = f(x')$ y $P(x')$ se mantiene) pero $P(x)$ no se sostiene. Pero la sentencia $(1)$ excluyen esta posibilidad. Obsérvese que esa posibilidad queda excluida siempre que $f$ es inyectiva en $S$ es decir, cuando cada elemento de $S$ es la imagen a través de $f$ de como máximo un punto en el dominio de $f$ : esta es la razón por la que $(2)$ implica $(1)$ cuando $f$ es inyectiva en $S$ .
Resumiendo, definir $S = \{y : \exists x \, [y = f(x) \land P(x)]\}$ (o equivalentemente $S = \{f(x) : P(x)\}$ que no es más que una notación abreviada de la misma definición) significa lo que se expresa mediante $(2)$ .
