¿Qué es una prueba de que un conjunto de ciclos disjuntos es un bijection?

Question

Considere una función de $f : D \to D$ (donde $D$ es un conjunto finito) de modo que para cada $d \in D$, no es un número entero $n$, de modo que $f(f(...(n\text{ times})...f(d)...) = d$.

1. Demostrar que $f$ es un bijection.
2. Probar que si $f : D \to D$ (donde $D$ es un conjunto finito) es un bijection, a continuación, para cada $d \in D$, no es un número entero $n$, de modo que $f(f(...(n\text{ times})...f(d)...) = d$.

Sé que esta proposición es verdadera (porque un bijection más de un conjunto finito es sólo una permutación que siempre es representable mediante ciclos), solo estoy teniendo un tiempo difícil formular una prueba de que en el primer año álgebra el estudiante pueda entender.

Answer 1

Si desea utilizar un mínimo de maquinaria, no creo que usted puede conseguir mucho más simple que el de estos:

(2) Fix $d\in D$ y considerar la secuencia $\langle d,f(d),f^2(d),f^3(d),\dots\rangle$; $D$ es finito, por lo que no deben ser diferenciadas $i,k\in\Bbb N$ tal que $i<k$$f^i(d)=f^k(d)$. Desde $f$ es un bijection, tiene un inverso $g$. Deje $n=k-i$, por lo que el $f^k(d)=f^i\big(f^n(d)\big)$. A continuación, $$d=g^i\big(f^i(d)\big)=g^i\big(f^k(d)\big)=g^i\big(f^i\big(f^n(d)\big)\big)=f^n(d)\;.$$

(1) Para mostrar que el $f$ es inyectiva, supongamos que $f(d)=f(e)$ algunos $d,e\in D$. Existen enteros positivos $m$ $n$ tal que $f^m(d)=d$$f^n(e)=e$. Pero, a continuación, por un fácil de inducción $f^{km}(d)=d$ $f^{kn}(e)=e$ todos los $k\in\Bbb N$, y por lo tanto $d=f^{mn}(d)=f^{mn}(e)=e$.

Para mostrar que $f$ es surjective, simplemente a observar que si $d\in D$, entonces no es $n\in\Bbb Z^+$ tal que $d=f^n(d)=f\big(f^{n-1}(d)\big)\in\operatorname{ran}f$.

Answer 2

Para "demostrar $f$ es un bijection" (es decir, #1): en primer lugar, mostrar $f$ es inyectiva. Así, supongamos $f(a) = f(b)$ donde $a, b \in D$. Ahora, para $a$ $b$ existen enteros positivos $n$ $m$ tal que $f^n(a) = a$ $f^m(b) = b$ (donde $f^n$ es la notación estándar para la iteración: $f^n = f \circ f \circ f \circ \cdots \circ f\ (n\ \mathrm{times})$, e $f^0 = \mathrm{id}$, la función identidad.). Estas ecuaciones dan $f^{n-1}(f(a)) = a$$f^{m-1}(f(b)) = b$. Ahora, desde la $f(a) = f(b)$,$f^{m-1}(f(a)) = b$. Es decir, $f^m(a) = b$. Ahora también, $f^{n-1}(f(b)) = a$$f^n(b) = a$. Lo $f^m(a) = b$ muestra es que el ciclo que contiene a $a$ también contiene $b$, así que los dos ciclos no son disjuntas, y de hecho son el mismo ciclo. Por lo tanto, $f^n(b) = b$ (tenga en cuenta que un periodo de un punto en un ciclo es un período de cada punto), y por lo $a = b$.

Ahora a $f$ es surjective. Supongamos $a$ es un elemento de $D$. A continuación, queremos encontrar una $b$ que $f(b) = a$. Desde $f^n(a) = a$ algunos $n$,$f(f^{n-1}(a)) = a$, y por lo $b = f^{n-1}(a)$ va a trabajar.

Por eso, $f$ es tanto inyectiva y surjective. Por lo tanto, $f$ es bijective.

Para el "conversar" (es decir, #2): Supongamos $f$ es bijective. Ahora, considere la posibilidad de $f^n(a)$ algunos $a \in D$ y enteros positivos $n$. Ahora, hay sólo un número finito de posibilidades para $f^n(a)$, por lo que debe haber algo de n para el cual $f^n(a) = f^m(a)$ para algunos m <= n. Entonces, desde el $f$ es bijective, es invertible, y tenemos la existencia de la negativa recorrer $f^{-m} = (f^{-1})^m$, que es la inversa de a $f^m$, y podemos aplicar eso a ambos lados para obtener $f^{n-m}(a) = a$.

Q. E. D.

Answer 3

(1) Primero vamos a comprobar que $f$ es surjective.

deje $d \in A$. Sabemos que $f[ f(f...f(d)))]=d$. Deje $y=$dentro de la $[ ...]$$f(y)=d$.

Ahora podemos demostrar que cualquier surjection $f:A \to A$ también es inyectiva.

Supongamos por contradicción que $f(a)=f(b)$ algunos $a,b$. Deje $n$ el número de elementos de a$A$, $A \backslash \{ a, b\}$ $n-2$ elementos.

Por lo tanto $f(A \backslash \{ a, b\} )$ tiene más de $n-2$ elementos. Por lo tanto $f(A)=f(A \backslash \{ a, b\} ) \cup \{ f(a) \}$ tiene más de $n-1$ elementos, lo que contradice el hecho de que $f$ es sobre.

2 ver el $f^n(d)$. Entonces, hay dos elementos $n <m$, de modo que

$$f^n(d)=f^m(d) \,.$$

Así

$$f^n(d)= f^n(f^{m-n}(d)) \,.$$

Desde $f^n$ es inyectiva, tenemos $d=f^{m-n}(d)$.

Answer 4

1)Claramente, $f$ es un surjection. Ahora vamos a comprobar que $f$ es inyectiva. Primero nos tenga en cuenta que si $f^{n}(x)$, entonces para cualquier entero positivo $k$ ,$f^{kn}(x)=x$.

Deje $f(d_1)=f(d_2)$. Nos encontramos con que no existe $m,n$ tal que $f^{m}(d_1)=d_1,f^{n}(d_2)=d_2$$f^{mn}(d_1)=d_1,f^{mn}(d_2)=d_2$. Desde $f(d_!)=f(d_2)$, por lo $f^{mn}(d_1)=f^{mn-1}(f(d_1))=f^{mn-1}(f(d_2))=f^{mn}(d_2)$

Answer 5

Para (1), es más fácil probar que si $f$ no es inyectiva, entonces tampoco es $f^{n}$ e si $f$ no es surjective ninguno de los dos es $f^n$, para cualquier $n \ge 1$. Usted sabe que $f^n$ es bijective, y por lo tanto así debe de $f$.

Para (2), tenga en cuenta que el bijections en un conjunto forma un grupo en la composición, y que si $D$ es finito, entonces este grupo es finito, así que todos sus elementos finitos de orden.