¿Es necesaria la inducción para demostrar que todo mapeo inyectivo de un conjunto finito sobre sí mismo es un mapeo sobre sí mismo?

Question

Tras repasar el teorema básico de que el número de elementos de un conjunto finito fijo es único, he intentado determinar qué parte de esta proposición necesita demostración. En parece axiomático. No obstante, BBFSK tienen un debate muy largo y aparentemente enrevesado sobre esto y otras ideas relacionadas.

Cuando intenté producir mi propio argumento en apoyo de la proposición anterior, la parte que no soy capaz de enunciar puramente en la terminología de los mapeos (biyección, inyección, etc.) es que una inyección de un conjunto finito en sí mismo es un mapeo sobre sí mismo. La prueba que da BBFSK utiliza la inducción. Después de pensarlo un rato, es lo único que se me ha ocurrido.

¿Existe una prueba rigurosa de la proposición de que todo mapeo inyectivo de un conjunto finito en sí mismo es un mapeo del conjunto en sí mismo que no implique inducción?

Answer 1

Dedekind propuso utilizar esta propiedad como el definición de "conjunto finito", así que esa es al menos una alternativa -- muy en línea con tu intuición de declararlo axiomático. Desgraciadamente, este enfoque plantea problemas técnicos. En particular, se necesita el axioma de elección para demostrar que inducción funciona para todas las cardinalidades "finitas", lo cual es cuanto menos desordenado.

(Un conjunto $X$ tal que cada inyección $X\to X$ es una biyección se denomina ahora "Dedekind-finita").

En cambio, en un desarrollo estándar de la teoría de conjuntos, no tienes suerte. Aquí "finito" se define como "que tiene la misma cardinalidad que un elemento de $\omega$ y $\omega$ se define (esencialmente) como el conjunto más grande para el que funciona la inducción matemática. Así que para demostrar cualquier cosa sobre "finito" necesitas tener una inducción en alguna parte, porque es la única manera de conectar con la definición. Esta inducción se puede ocultar en la demostración de otra propiedad de la que dependas, pero eso es básicamente dar palos de ciego. Con el tiempo tiene que parar.

---

Este comentario de Daniel Schepler también es pertinente (pero véase el debate posterior en el hilo de comentarios):

También existe la noción de finitud de Kuratowski, que es esencialmente equivalente a la condición de que el conjunto de potencias de $$ está bien fundada bajo la relación de "extensión estricta por un elemento". Pero entonces, por supuesto, la forma natural de demostrar casi cualquier cosa sobre los conjuntos finitos de Kuratowski es utilizar la inducción sobre la propiedad de bien fundado...