¿Pueden definirse las funciones mediante relaciones?

Question

Digamos entonces que, por las razones que sean, no se nos permite utilizar símbolos de función en la lógica de primer orden. Entonces, ¿podemos definir y utilizar una función sólo mediante relaciones?

Answer 1

Sí, sólo hay que añadir un axioma que indique que la relación es una función: $$\forall x\forall y\forall z(R(x,y)\land R(x,z)\rightarrow y=z)$$

Y es posible que quieras exigir que el dominio sea todo el universo.

Answer 2

Sí, una función de $A$ a $B$ es una relación entre A y B tal que cualquier elemento x del dominio no puede estar relacionado con dos elementos diferentes $y$ y $z$ de $B$ ("esto es lo que queremos decir cuando decimos bien definido"). También cada elemento del dominio $A$ debe estar relacionado con algún elemento del objetivo $B$ .

En una frase, cada elemento del dominio debe estar relacionado con exactamente uno del objetivo.

Answer 3

Gran pregunta. Sí. De hecho, todas las funciones son relaciones: el conjunto de todas las funciones es un subconjunto del conjunto de todas las relaciones.

Piénsalo: toma dos juegos $A = \{a,b,c\},B = \{1,2,3\}$ . Crea una función entre ellos. Recuerda la definición formal de una función: una función no es más que un conjunto de pares ordenados $(x,y)$ por lo que nos gusta decir que $x \in X$ se asigna a $y \in Y$ . Así que nuestra función entre los dos conjuntos $A$ y $B$ será un subconjunto del producto cartesiano $A \times B$ por ejemplo: $f = \{(a,2),(c,1)\}$ .

¿Le resulta familiar? Así es. Una relación entre dos conjuntos $A,B$ es siempre un subconjunto del producto cartesiano $A \times B$ . (Nótese que aquí, un relación no es lo mismo que un relación de equivalencia que son mucho más estrictas, y de las que probablemente acabas de enterarte).

Hasta ahora parece que son lo mismo. Entonces, ¿cuál es la gran diferencia? Bueno, recuerda que una función asigna cada entrada a sólo un de salida. No se puede tener $f(x) = 5$ y $f(x) = 3$ porque entonces $5=3$ . Ya lo sabes. Así que para su conjunto que representa una función --- tomar nuestro ejemplo de antes, $f = \{(a,2),(c,1)\}$ --- tenemos que para cada elemento de $f$ (un par ordenado $(x,y)$ ), la primera coordenada de la tupla (en este ejemplo, es $x$ ) es único . Esto significa que no se puede tener una función como $g = \{(a,2),(c,1),(a,3)\}$ porque $a$ aparece dos veces como primera coordenada de una tupla --- significaría que $g(a) = 2$ y $g(a)=3$ Y no podemos permitirlo.

Y esa es la condición que hace que las funciones sean un subconjunto de las relaciones. En una relación, la primera coordenada de la tupla no tiene por qué ser única. La relación $R = \{(a,2),(c,1),(a,3)\}$ es perfectamente válido. Pero ese conjunto no es una función válida. Así que aunque toda función es una relación, no toda relación es una función.

Answer 4

Normalmente, las funciones se definen en el lenguaje de la teoría de conjuntos. He aquí una posible definición utilizando sólo FOL:

Dejemos que $D$ y $C$ sean predicados unarios. Sea $F$ por un predicado binario.

$F$ se dice que es un relación funcional con dominio predicado $D$ y codominio predicado $C$ si y sólo si:

1. $\forall x,y:[F(x,y)\implies D(x)\land C(y)]$

2. $\forall x:[D(x)\implies \exists y:[F(x,y)]$

3. $\forall x,y_1,y_2:[F(x,y_1)\land F(x,y_2)\implies y_1=y_2]$