Podemos reorganizar todos los números reales entre $0$$1$, denotan $f(x):(0,1) \rightarrow (0,1)$ (un bijection), tal que para $$\forall 0<x_1<x_2<\dots<x_n<1,$$ neither $$f(x_1) <f(x_2) <\dots <f(x_n)$$ nor $$f(x_1)>f(x_2)>\dots>f(x_n)$$ can be hold $(n>3)$. I'd like to see an answer for $n=4$ and $n=5$. Gracias!
Respuestas
¿Demasiados anuncios?
Como deinst link espectacular de la muestra, hay un vínculo directo entre la cuestión de encontrar un adecuado bijection (según sus criterios) y la teoría de Ramsey. Vamos a empezar por responder a la pregunta sobre finito de conjuntos:
Deje $X=\{x_1,\dots ,x_N\}\subset \mathbb R$ $x_i<x_{i+1}$ ser un conjunto de cardinalidad $N\in\mathbb N$, y deje $f:X\to X$ ser un bijection. Deje $G_f$ el gráfico que se define como sigue:
Dibujar un nodo para cada una de las $x_i$. Para cualquier $i< j$$1$$N$, podemos dibujar un borde de $e_{ij}$. Si $f(x_i)<f(x_j)$, el color del borde de color rojo. Si $f(x_i)>f(x_j)$, el color del borde azul.
Nuestra condición es que ni $$ f(x_{i_1}) <f(x_{i_2}) <\dots <f(x_{i_n}) $$ ni $$ f(x_{i_1}) >f(x_{i_2}) >\dots >f(x_{i_n}) $$ es cierto para cualquier selección creciente de los índices de $i_k$. Esta condición tiene iff $G_f$ no tiene monocromática subgrafo completo en $n$ nodos. Por lo tanto, para un determinado $X$, sólo podemos encontrar una adecuada $f$ al $N<R(N,N)$.
Con eso en mente, Ramsey teoría nos da los siguientes resultados:
- si $n=3$, sólo podemos encontrar una adecuada $f$ si $N<6$
- si $n=4$, sólo podemos encontrar una adecuada $f$ si $N<18$
- si $n=5$, sólo podemos encontrar una adecuada $f$ si $N<49$
- si $n=6$, sólo podemos encontrar una adecuada $f$ si $N<165$
y así sucesivamente y así sucesivamente, siguiendo la diagonal de las entradas de esta tabla.
Finalmente, como se señaló en los comentarios: para cualquier $X$ de los no-finito de cardinalidad, el Infinito de Ramsey, el Teorema nos dice que podemos encontrar infinitamente muchos (cada vez mayor) $i_k$, de modo que
$$ f(x_{i_1}) <f(x_{i_2}) <\dots <f(x_{i_k})<\dots $$ o $$ f(x_{i_1}) >f(x_{i_2}) >\dots >f(x_{i_k})>\dots $$
Nota: a pesar de que cada bijection tiene un gráfico correspondiente, que no todos los posibles gráfico en la $N$ nodos, como se define arriba corresponde a una posible bijection $f:X\to X$. Sin embargo, puede ser un bijection para cada gráfico hasta el isomorfismo. En cualquier caso, es que no me queda claro si, por ejemplo, podemos encontrar un bijection $f$ $X$ contiene $5$ elementos en los que se satisface la condición de $n=3$.
Después de algunas investigaciones, resulta que no es adecuado bijection en un conjunto de $5$ elementos. Las condiciones que se dio anteriormente en el número de elementos de un conjunto son necesarios pero insuficientes para establecer la existencia de un adecuado bijection.
6005
Puntos
19982
No es necesario traer en la teoría de Ramsey! Dada una función de $f$, considere la secuencia $$ f\left(1 - \tfrac{1}{2} \right), \left(1 - \tfrac{1}{3} \right), \left(1 - \tfrac{1}{4} \right), \ldots $$ Como cualquier secuencia en la $\mathbb{R}$ tiene una monótona y larga, existe un aumento de la secuencia de los números reales $x_i$, $0 < x_1 < x_3 < x_3 < \cdots$, tal que $$ f(x_1) \le f(x_2) \le f(x_3) \le \cdots \text{ o } f(x_1) \ge f(x_2) \ge f(x_3) \ge \cdots $$ y desde $f$ es un bijection, la igualdad no puede sostener, es decir, $$ f(x_1) < f(x_2) < f(x_3) < \cdots \text{ o } f(x_1) > f(x_2) > f(x_3) > \cdots $$ así que el reordenamiento que le pides es imposible para cualquier $n$.
