Demostrar que cada sistema con más de un elemento tiene una permutación sin puntos fijos

Question

No puedo probar esta afirmación, por lo que necesitan ayuda. Este problema es uno de los ejercicios de la derecha después de que el capítulo acerca de Hausdorff máxima del principio y el Lema de Zorn. Por lo tanto, usted no puede utilizar el concepto de número cardinal. He encontrado exactamente la misma pregunta en este sitio web, pero la prueba se realiza mediante el concepto de número cardinal. Por favor, asegúrese de que esta pregunta es a la derecha, después de introducir el axioma de elección y el lema de Zorn.

Deje $A$ ser cualquier conjunto con más de un elemento. Demostrar que existe un bijective función de $f:A \to A$ tal que $f(x)\neq x$ por cada elemento de a$x$$A$.

Answer 1

El fin de la bijective funciones de $f\colon A\to A$ tal que $f\le g$ si todos los puntos fijos de $g$ son puntos fijos de $f$ $f$ $g$ está de acuerdo en todos los elementos que no son puntos fijos de $f$. Dada una cadena con respecto a este orden parcial, un límite superior está dado por la función que tiene puntos fijos donde todos los elementos de la cadena de tener puntos fijos y los mapas de cada otro elemento que el único elemento que algunos de los elementos de la cadena de mapa. Por lo tanto, por el lema de Zorn hay un elemento maximal con respecto a este orden parcial. Si este elemento maximal había al menos dos puntos fijos, podríamos trazar esos dos puntos fijos el uno al otro para crear un mayor elemento. Por lo tanto el elemento maximal $f$ tiene más de un punto fijo $x$, y si es así se puede elegir algún otro elemento $a$ y definen $g$, coincidiendo con $f$ con la excepción de$g(a)=x$$g(x)=f(a)$. A continuación, $g$ no tiene puntos fijos.

Answer 2

Si $A$ es infinito es equipotente a $A\times\mathbb F_2$, e $(a,x)\mapsto(a,1+x)$ que hace el trabajo.

Answer 3

He aquí otra prueba para la diversión. Puede ser fácilmente demostrado que el axioma de elección es equivalente a la afirmación de que cada conjunto no vacío admite una estructura de grupo. Dar $A$ una estructura de grupo, y vamos a $f:A \to A$ ser a la izquierda de la multiplicación por un no-elemento de identidad de $A$.

Answer 4

Sugerencia: considerar las colecciones $\{S_i: i \in I\}$ de los subconjuntos de a $A$ cada uno contiene dos elementos. El uso de Zorn para conseguir una colección en la que es máxima.

Answer 5

Aquí es un poco complicado de la prueba que voy a añadir, ya que podría tener algún valor de a es:

Si $A$ es finito, entonces es obvio cómo hacerlo a través de la combinatoria finita. Supongamos que $A$ es infinito.

Lema: Para cada elemento $a\in A$ hay un bijection entre el$A$$A\setminus\{a\}$.

Es suficiente para demostrar que $A$ contiene un countably subconjunto infinito, si no podemos escribir $A=\{a_i\mid i\in\mathbb N\}\cup A'$ y sin pérdida de generalidad $a=a_0$ ahora tome $a_i\mapsto a_{i+1}$ y la identidad en $A'$, este sería nuestro querido bijection.

Prueba. Considere la posibilidad de $A_n = \{X\subseteq A\mid X\text{ has exactly }n\text{ members}\}$, ya que el $A$ es infinito todos los que son no vacíos. Usando el axioma de la opción de elegir, exactamente uno de cada $A_n$, que se denota por a$X_n$, y para cada una de las $X_n$ elegir un bijection con $\{0,\ldots,n-1\}$. Ahora la unión de $\bigcup X_n$ pueden ser enumerados por los números naturales y no es finito. $\square$

Ahora para probar realmente la reclamación queremos demostrar:

Se define un conjunto parcialmente ordenado $(P,\leq)$. Deje $P$ el conjunto de los trillizos $\langle X,Y,f\rangle$ tal que $X,Y$ son distintos subconjuntos de a $A$ $f\colon X\to Y$ es un bijection. Decimos que $\langle X,Y,f\rangle\leq\langle X',Y',f'\rangle$ si y sólo si $X\subseteq X'$, $Y\subseteq Y'$, y $f\subseteq f'$.

Si $\{\langle X_i, Y_i, f_i\rangle\mid i\in I\}$ es una cadena, a continuación, $\langle\bigcup X_i,\bigcup Y_i,\bigcup f_i\rangle$ es un límite superior de esta cadena. Hay detalles a verificar (disjointness, el hecho de que la unión de la $f_i$ es todavía un bijection), pero los siguen desde el hecho de que esto es una cadena. Os dejo estos detalles para que usted pueda verificar.

Deje $\langle X,Y,f\rangle$ ser un elemento maximal, cuya existencia está garantizada por el lema de Zorn. Si $A\setminus (X\cup Y)$ contiene al menos dos elementos que podemos agregar de una a $X$ y otro a $Y$ y extender $f$ respectivamente y por lo tanto contradice el hecho de que tenemos un elemento maximal.

Si sólo hay un elemento $a$ por el lema podemos encontrar un bijection $g\colon X\cup Y\to A$, ya que el $g$ es un bijection tenemos que $g[X]\cup g[Y]=A$$g[X]\cap g[Y]=\varnothing$. También tenga en cuenta que $g\circ f\circ g^{-1}$ es un bijection entre el$g[X]$$g[Y]$. Así que podemos suponer sin pérdida de generalidad que $X\cup Y=A$.

Ahora vamos a $h\colon A\to A$ ser la función de $f\cup f^{-1}$. Para ver que esto es una función de la nota primero que $f^{-1}$ es una función desde $f$ es un bijection entre el $X$ $Y$ y los dominios de $f$ y su inversa son distintos, por lo tanto, la unión es una función. No es muy difícil comprobar que $h$ es de hecho un bijection de $A$ a sí mismo y que para cada $a\in A$ tenemos $h(a)\neq a$ desde el si $a\in X$ $h(a)\in Y$ y viceversa.

---

Otra observación es que Sageev demostrado en los años 70 que la suposición de que para cada conjunto infinito $A$ tenemos un bijection de $A$ $A\times\{0,1\}$( $|A|=2|A|$ ) es estrictamente más débil que el axioma de elección. Uno puede ver de inmediato que esta suposición es, de hecho, suficiente para garantizar una alteración existe.