Hay algunas funciones f que puede ser compuesta con ellos mismos. ¿Pero hay una función que puede aplicarse a sí mismo? ¿En otras palabras, existe una función f tales que f es un elemento de Domain(f)?
Respuestas
¿Demasiados anuncios?
Dave
Puntos
1459
La respuesta es no, si el axioma de Fundación es aceptado como parte de la teoría de conjuntos. (Si no es así, entonces esta pregunta posiblemente se convierte mucho más difícil e interesante y muy difícil para mí.)
Para asumir que tenemos un par $(f,y)$ que pertenece a $f$. Tenemos $(f,y) = \{ \{f\},\{f,y\} \}$ a continuación:
$$f \in \{ f \} \in (f,y) \in f$$
Así el conjunto no vacío $C = \{ f, \{f\}, (f,y) \}$ no tiene un $\in$-elemento mínimo. Es decir, no es ningún elemento $x$ $C$ tal que $x \cap C = \emptyset$. Esto contradice el axioma de Fundación.
Como varias personas han señalado, esto es imposible cuando vemos a una función como un "conjunto de pares ordenados". Pero, si queremos ver una función en lugar de como un algoritmo, entonces es perfectamente posible. Por ejemplo, puedo escribir un programa en python que toma una cadena de caracteres como entrada y devuelve el número de caracteres de la cadena. Entonces puede que este programa se aplique a sí mismo para determinar la cantidad de caracteres que tiene.
Este concepto es llevada al límite en lenguajes de programación funcional, tales como el Esquema y en el tipo $\lambda$ cálculo. Estos lenguajes de eliminar la diferencia entre el "código" y "datos".
Uno de los retos en la búsqueda de modelos semánticos de estos idiomas es el conjunto teórico de las dificultades mencionadas anteriormente. Pero hay, de hecho, la semántica de los modelos para estos idiomas. Esto es lo que user322483 que se refiere en su respuesta.
user322483
Puntos
31
Sí, ver http://en.wikipedia.org/wiki/Domain_theory .
No va a funcionar para el sistema definición teórica de una función $f: A\to B \in B^A$ desde $B^A \cap A = \emptyset$ cuando en la categoría $\cal Set$. Esta construcción es posible en la categoría de dominios, aunque.
Joel Bosveld
Puntos
662
Una función $f:A\to B$ puede verse como un elemento del conjunto $B^A$. Para que una función actuar sobre sí mismo, necesitamos un mapa $g:B^A\to A$. También queremos que este mapa sea una biyección, para que elementos de $B^A$ se identifican con elementos de $A$.
Esto requeriría $|B|^{|A|}=|A|$, tan $|A|=1$y $|B|\in\{0,1\}$.
Si tenemos $\mathbb{id}:\{\mathbb{1}\}\to\{\mathbb{1}\}$, dado en $\mathbb{1}\mapsto\mathbb{id}(\mathbb{1})=\mathbb{1}$. Si identificamos $\mathbb{id}$ $\mathbb{1}$, $\mathbb{1}(\mathbb{1})=\mathbb{1}$ hace cierta cantidad de sentido.
Entonces la respuesta es no, excepto en alguna manera para los casos triviales.
