¿En qué conjuntos además de $\mathbb{N}$ ¿podríamos utilizar la prueba por inducción?

Question

Supongamos que tenemos un conjunto $S$ con $s_1\in S$ y $f: S\to S$ y $n\subset S$ tal que $n=\{s_1, f(s_1), f(f(s_1)), \cdots \}$ ( $n$ no necesariamente infinito).

Para establecer las propiedades de $n$ ¿podemos utilizar la prueba por inducción sobre $n$ mismo utilizando $f$ como función sucesora?

---

EDITAR: Supongamos que $f:S\to S$ . Por si sirve de algo, aquí está la mía prueba formal que para cada $s_1\in S$ existe un conjunto $n\subset S$ en la que la inducción se mantiene, con $f$ siendo la función sucesora y $s_1$ siendo el "primer elemento" en $n$ . La clave de la prueba es la construcción del subconjunto $n$ :

$\forall a:[a\in n \iff a\in S\land \forall b\subset S:[s_1\in b\land \forall c\in b : [f(c)\in b]]\implies a\in b]$

Podemos demostrarlo:

(1) $s_1\in n$

(2) $\forall a\in n: f(a)\in n$

(3) $\forall P\subset n:[s_1\in P \land \forall a\in P: [f(a)\in P] \implies \forall a\in n : [a\in P]]$

Estos son el equivalente a 3 de los 5 axiomas de Peano para los números naturales (la versión moderna de la teoría de conjuntos). Sólo falta que $f$ sería inyectiva, y que $s_1$ no tendría ninguna imagen previa en $n$ en $f$ .

Answer 1

Para ampliar mi comentario, el quid de la cuestión no es demostrar que la inducción funciona, sino incluso definir el conjunto $n$ en absoluto (una vez definida, la inducción será trivial a partir de la definición). Su definición $n=\{s_1, f(s_1), f(f(s_1)), \cdots \}$ no es, por supuesto, riguroso, a menos que se explique qué es el " $\cdots$ " se supone que significa.

Hay varias maneras de precisar esta definición, pero la siguiente es una de las más fáciles. Definir $n$ sea el subconjunto más pequeño de $S$ que contiene $s_1$ y se cierra bajo $f$ . Más concretamente, $n$ es la intersección de todos los subconjuntos $A\subseteq S$ tal que $s_1\in A$ y para todos $a\in A$ , $f(a)\in A$ .

A partir de esta definición, la inducción es esencialmente una tautología. La inducción dice que dada una propiedad $P$ de elementos de $n$ , si $P(s_1)$ es verdadera y $P(a)$ implica $P(f(a))$ para todos $a\in n$ entonces $P(a)$ es cierto para todos los $a\in n$ . Pero dada tal $P$ , sólo hay que definir $A=\{a\in n:P(a)\}$ . Entonces $A$ contiene $s_1$ y se cierra bajo $f$ por lo que por definición de $n$ , $n\subseteq A$ . Así, $P(a)$ es cierto para todos los $a\in n$ .

Answer 2

Preveo que lo que se obtendría haciendo algo así se parecería mucho a $\mathbb{N}$ . Es decir, probablemente podrías encontrar una forma de asociar $S$ y $\mathbb{N}$ entre sí. Es decir, se podría escribir $s_{1} = s \in S, s_{n + 1} = f(s_{n})$ pero al hacerlo, realmente no hay mucha diferencia entre "inducir" en $S$ y la inducción en $\mathbb{N}$ en que $s_{1}$ es "básicamente" $1$ , $s_{2}$ es "básicamente" $2$ y así sucesivamente. Así que aunque se puede hacer $S$ diferente de $\mathbb{N}$ No habrá mucha diferencia en cuanto a la inducción (aunque $S$ puede tener otras "características" muy diferentes de $\mathbb{N}$ .

Otras respuestas tienen razón en que habría que dar una definición más formal y rigurosa. Pero creo que para usos "casuales" como el de este foro, creo que el significado es claro; pero como he dicho, creo que lo que se obtendría no sería mucho más que una enumeración básica de $S$ y no comprar nada realmente útil. Al enumerar un conjunto, puedes hacer inducción sobre él, pero todo lo que estás haciendo realmente es inducir sobre $\mathbb{N}$ y pasarlo a su conjunto enumerado.

EDIT: En respuesta a un comentario, el conjunto puede ser finito, por ejemplo, si $f$ es la identidad. En este caso, no es lo mismo que $\mathbb{N}$ pero la "inducción" se repetirá indefinidamente; es decir, habrá algún $k$ tal que $f^{k}(s) = s$ para todos $s$ . La inducción está ahí, y es diferente de $\mathbb{N}$ pero todavía se puede enumerar $S$ aunque de forma redundante (es decir $s_{i} = s_{i + k}$ ).