¿Admite todo conjunto una relación binaria rígida? (¿y cómo se relaciona esto con el axioma de elección?)

Question

Digamos que un conjunto B admite una relación binaria rígida, si existe una relación binaria R tal que la estructura (B,R) no tiene automorfismos no triviales.

Según el axioma de elección, todo conjunto es bien ordenable, y como los bien ordenados son rígidos, según AC todo conjunto tiene una relación binaria rígida.

Mis preguntas son: ¿es cierto lo contrario? ¿Se necesita CA para producir estructuras tan rígidas? ¿Se trata de un principio de elección débil? ¿O se puede demostrar simplemente en ZF?

(Esta pregunta se deriva de la pregunta ¿Un tipo de estructura rígida que se puede poner en cada plató? .)

Answer 1

Actualización: Joel y yo hemos escrito un artículo basado en los conceptos introducidos en esta pregunta, que puede verse en http://arxiv.org/abs/1106.4635

Me parece que es coherente con ZF que exista un conjunto sin relación binaria rígida. Utilice la técnica estándar para construir tales conjuntos extraños. Primero construye un modelo de permutación de ZFA donde el conjunto de átomos A tiene la propiedad deseada y luego utilizar el teorema de Jech-Sochor para transferir el resultado a un modelo ZF. Cualquier sentencia que puede ser enunciada simplemente usando cuantificadores sobre alguna iteración fija de la operación powerset sobre A puede ser transferida. En nuestro caso, la sentencia "A no tiene relación binaria sin un automorfismo no trivial" sólo necesita cuantificar sobre, digamos, la quinta iteración del conjunto de potencias de A (probablemente menos). La referencia estándar para estas técnicas es el texto de Jech The Axiom of Choice de 1973. (En él, el teorema de Jech-Sochor se denomina Primer Teorema de Incrustación).

En nuestro caso lo que se llama el modelo básico de Fraenkel es el modelo ZFA deseado. (Este y otros modelos similares se construyen en el capítulo 4). Supongamos que R es una relación binaria en A. Entonces hay un conjunto finito E (llamado el soporte de R en la terminología de Jech) tal que cualquier permutación de A que fije E mapea puntualmente R a sí mismo. En En otras palabras, tales biyecciones son automorfismos de R. Puesto que E es finito, podemos encontrar sin AC tales biyecciones no triviales y se deduce que R no es rígido. se deduce que R no es rígido.

De hecho examinando la demostración del teorema de Jech-Sochor se ve que el hecho de Joel sobre conjuntos de reales es óptimo en el siguiente sentido: los modelos de ZFA son simulados por modelos de ZF transfiriendo el conjunto de átomos a un conjunto de conjuntos de reales y, por tanto, en ZF no se puede ir más arriba en la jerarquía de tipos que la de omega y esperar construir relaciones binarias rígidas.

Answer 2

Como Joel señaló en los comentarios, aunque se aceptó una respuesta a esta pregunta, quedaba la cuestión de si el enunciado en cuestión era equivalente al axioma de elección. Modificando la prueba del teorema de Joel sobre conjuntos de reales que admiten relaciones binarias rígidas, creo que puedo demostrar que en el modelo estándar de Cohen $M$ para el fracaso de AC se cumple la afirmación "todo conjunto admite una relación binaria rígida". En particular, esta afirmación es estrictamente más débil que AC y no implica ninguno de los principios de elección que fallan en ese modelo. Otra cuestión que puede ser interesante es si todos los conjuntos de este modelo admiten un orden lineal rígido.

Teorema. En $M$ todo conjunto admite una relación binaria rígida.

Prueba. En todo momento trabajamos en $M$ . Existe un conjunto de reales $A$ tal que cualquier conjunto $x$ puede inyectarse en $A^{<\omega}\times\gamma$ para algún ordinal $\gamma$ (véase por ejemplo el Lemma 5.25 en The Axiom of Choice de Jech). Por tanto, cualquier conjunto puede inyectarse en $\mathbb{R}^{<\omega}\times\gamma$ y de hecho en $\mathbb{R}\times\gamma$ para algunos $\gamma$ . Así pues, para demostrar el teorema basta con reforzar el teorema de Joel y demostrar que todo subconjunto $X$ de $\mathbb{R}\times\gamma$ admite una relación binaria rígida. La prueba es en realidad sólo un ligero retoque, pero voy a escribirlo. Sea $ < $ denotan la ordenación lexicográfica en $\mathbb{R}\times\gamma$ heredadas de las dos ordenaciones lineales habituales en los conjuntos componentes. (Identifico $\mathbb{R}$ con el espacio de Cantor $2^\omega$ ).

Caso 1: $X$ no tiene ningún subconjunto contablemente infinito. Entonces $ < $ restringido a $X$ es rígido, ya que cualquier permutación no trivial nos permite iterar el mapa contablemente muchas veces sobre algún elemento movido y obtener un subconjunto contable.

Caso 2: $X$ tiene un subconjunto contablemente infinito $z_0,\ldots z_n,\ldots$ (y coger algún otro punto $z^* $ ). Sea $Z=\{z^* ,z_0,\ldots z_n,\ldots\}$ . Definimos una relación binaria rígida $R$ como sigue. Fijamos $R(z^* ,z^* )$ y poner $z_0,\ldots z_n,\ldots$ debajo de $z^* $ en tipo de pedido $\omega$ . Sea $s_0,\ldots s_n\ldots$ enumerar las secuencias binarias finitas. Entonces para $\langle x,\alpha\rangle\not\in Z$ ponemos $R(z_n,\langle x,\alpha\rangle)$ si $s_n\subseteq x$ . Para $\langle x,\alpha\rangle$ y $\langle y,\beta\rangle$ ambos no en $Z$ dejamos que $R(\langle x,\alpha\rangle,\langle y,\beta\rangle)$ se mantiene si $\langle x,\alpha\rangle<\langle y,\beta\rangle$ .

Afirmamos que $R$ es rígido. Sea $\pi:X\rightarrow X$ ser un $R$ -automorfismo. Como en la prueba de Joel, es fácil ver que cada miembro de $Z$ se arregla, y que como resultado siempre que $\pi(x,\alpha)=(y,\beta)$ debemos tener $x=y$ . De ello se deduce fácilmente que $\pi$ fija la segunda coordenada de cada miembro de $X\setminus Z$ también, como ahora $\pi$ restringido a la segunda coordenada es un automorfismo de un subconjunto de $\gamma$ con respecto a la relación bien ordenada habitual en $\gamma$ .

Answer 3

He resuelto el problema afirmativamente al menos para conjuntos de reales.

Teorema. Todo conjunto de reales admite una relación binaria rígida (sin utilizar el axioma de elección). Equivalentemente, todo conjunto de reales es el conjunto de vértices de un grafo dirigido rígido.

Prueba. Supongamos que A es un conjunto de reales. Podemos considerar libremente que A es un subconjunto del espacio de Cantor 2^omega. Vamos a dividirlo en varios casos.

Caso 1. A es contable. Este es el caso fácil, ya que podemos simplemente imponerle una estructura rígida haciéndolo un orden lineal isomorfo a omega (o un orden lineal finito si A es finito).

Caso 2. A es incontable, pero A tiene un subconjunto contablemente infinito. Fijemos tal subconjunto Z={z_0, z_1, ...} y fijemos un punto z* en A-Z. Para cada secuencia binaria finita s, sea U_s la vecindad en 2^omega de todas las secuencias que extienden s, de modo que U_s(x) si x extiende s. Claramente, la estructura (A,U_s)_s es rígida, puesto que si se mueve cualquier punto x en A a otro punto, se moverá fuera de alguna vecindad U_s en la que estaba anteriormente. Ahora reducimos esta estructura a una relación binaria. Sea R una relación sobre A que coloca todos los z_n por debajo de z*, ordenados como omega, y hace que R(z*,z*) sea verdadera. A continuación, enumeramos las secuencias binarias finitas como s_0, s_1, etc., (esto no requiere AC). Definimos R(x,y) si x=z_n para algún n, y no es z_m para cualquier m, y no es z*, y U_{s_n}(y). Es decir, la primera coordenada le da algunos z_n, y por lo tanto algunos s_n, y luego se utiliza esto para determinar qué predicado de vecindad para aplicar a y, pero sólo hacemos esto para y fuera de Z unión {z*}. Afirmo que la estructura (A,R) es rígida. La razón es que z* y los reales z_n son definibles en la estructura (A,R), y por tanto están fijados por todos los automorfismos. (El real z* es el único tal que R(z*,z*), y los z_n son los únicos predecesores de z* wrt R.) Puesto que cada z_n es fijo, se deduce que cada automorfismo debe respetar la vecindad U_{s_n} intersecar A, y por lo tanto fijar todos los reales. Así que no hay automorfismos no triviales.

Caso 3. Raro A. El único caso restante se da cuando A es incontable, pero no tiene ningún subconjunto contablemente infinito. (Se deduce que A será Dedekind finito, pero no finito.) En este caso, cada permutación de A consistirá en órbitas disjuntas de longitud finita, ya que si hubiera una órbita infinita, entonces podríamos construir un subconjunto contablemente infinito de A iterándolo. Pero si toda permutación de A es así, entonces A no tiene permutaciones que respeten el orden lineal habitual < de los reales. Por lo tanto, (A,<) es rígido. QED

En particular, no es cierto que el contraejemplo habitual a AC en los modelos de forzamiento simétrico sea un contraejemplo a esta cuestión de rigidez. Esos conjuntos son conjuntos de reales, y este argumento muestra que tienen relaciones binarias rígidas, sin ser bien ordenables.

No estoy seguro de hasta dónde se puede extender esta idea. ¿Qué tal subconjuntos de 2^kappa para cualquier kappa cardinal? Creo, sin embargo, que incluso esto todavía no dará una respuesta positiva completa para todos los conjuntos.

Answer 4

Todos los conjuntos tienen una relación binaria rígida. Tengo una referencia para esto:

Existe una relación rígida en cada conjunto P. Vopěnka, A. Pultr y Z. Hedrlin, Commentationes Mathematicae Universitatis Carolinae 6(1965), 149-155

Answer 5

Una variante de la respuesta de Justin Palumbo, blackboxing la construcción de forzamiento:

Un conjunto infinito X se denomina amorfo si todos sus subconjuntos son finitos o cofinitos. X se llama fuertemente amorfo (o superamorfo) si toda relación sobre X (es decir, todo subconjunto de $X^n$ para cualquier $n$ ) es definible con un número finito de parámetros en el lenguaje de la igualdad. (En otras palabras, restringiendo a $n=2$ para simplificar: Cada $R \subseteq X^2$ debe estar en el álgebra booleana generada por los conjuntos $X_a:=\{(a,x): x\in X\}$ sus conversos y la diagonal. A menos que haya olvidado algunos generadores más).

(En particular, los conjuntos amorfos son Dedekind finitos).

Es evidente que los conjuntos fuertemente amorfos no tienen ninguna relación rígida. Su coherencia con ZF puede demostrarse (como se ha señalado anteriormente) construyendo primero un modelo ZFA con un conjunto amorfo de átomos y aplicando después el teorema de Jech-Sochor.

Los conjuntos (fuertemente) amorfos X (y las estructuras relacionadas, como el conjunto de potencias de X) pueden utilizarse a menudo como contraejemplos que demuestran que es necesaria alguna elección.