¿Son las inyecciones más difíciles de encontrar que las inyecciones?

Question

Dados dos conjuntos finitos $A$ y $B$ con $|A|<|B|$ Hay más funciones de $B$ a $A$ que de $A$ a $B$ excepto cuando $|A|=1$ o $|A|=2,|B|=3,4$ . Vea aquí la prueba .

También es cierto que hay más proyecciones de $B$ a $A$ que las inyecciones de $A$ a $B$ .

Una forma de demostrarlo es la siguiente: Crear un grafo bipartito en el que los vértices de una parte sean las inyecciones de $A$ a $B$ y los vértices de la otra parte son las proyecciones de $B$ a $A$ . Conecta dos vértices si y sólo si son inversos (en los lados apropiados) el uno del otro.

las funciones inyectivas tienen $(|A|)^{|B|-|A|}$ inversos a la izquierda. Por otro lado, el número de inversos a la derecha que puede tener una función suryectiva depende de la propia función. Es el producto del orden de los pullbacks de todos los singletons de la imagen. Entonces es el producto de $A$ números que suman $B$ y por lo tanto por AM-GM está limitado por $(\frac{|B|}{|A|})^{|A|}$ Por lo tanto, tenemos $I(|A|)^{|B|-|A|}\leq S(\frac{|B|}{|A|})^{|A|}$ donde $I$ es el número de funciones inyectivas y $S$ de funciones suryentes. Esto se debe a que la suma de los grados de cada una de las dos partes de un grafo bipartito es igual.

Por lo tanto, $\frac{S}{I}\leq\frac{|A|^{|B-|A|} |A|^{|A|}}{|B|^{|A|}}=\frac{|A|^{|B|}}{|B|^{|A|}}$ .

Por otro lado, las funciones de $B$ a $A$ y de $A$ a $B$ están en proporción $\frac{|A|^{|B|}}{|B|^{|A|}}$ .

Por lo tanto, el número de funciones inyectivas son un porcentaje menor de las funciones de $A$ a $B$ que las funciones surjetivas son de $B$ a $A$ .

Esto me lleva a creer que ser sobreyectivo es más "fácil" que ser inyectivo.

Preguntas de seguimiento:Deja que $|A|<|B|$ para conjuntos arbitrarios $A$ y $B$ .

¿Hay alguna manera de demostrar que hay más funciones inyectivas de $A$ a $B$ que las funciones suryentes de $B$ a $A$ ?

¿Hay alguna manera de probar $|A^B|\geq |B^A|$ ?

¿Existe una forma de expresar el hecho de que las suryecciones son "más fáciles" de encontrar en conjuntos infinitos? ¿Sería esto cierto? Está claro que no podemos utilizar el mismo argumento.

Answer 1

Hay una manera fácil de mostrar la desigualdad para conjuntos infinitos. ¡Aritmética cardinal!

Recordemos que para un cardinal infinito $\kappa$ es cierto que $\kappa^\kappa=2^\kappa$ (ya que $2^\kappa\leq\kappa^\kappa\leq(2^\kappa)^\kappa=2^{\kappa\cdot\kappa}=2^\kappa$ ).

Suponiendo que $|A|>2$ inmediatamente obtenemos que $|A^B|=2^{|B|}$ y $|B^A|\leq|B^B|=2^{|B|}$ Así que, efectivamente, tenemos la desigualdad deseada. Si se toma, por ejemplo $A=\Bbb N$ y $B=\Bbb R$ entonces también se obtiene una desigualdad aguda allí, ya que $A^B$ tiene tamaño $2^{2^{\aleph_0}}$ mientras que $B^A$ tiene tamaño $2^{\aleph_0}$ .

(Nótese que para "conjuntos arbitrarios" es difícil demostrar que hay más funciones inyectivas de $A$ a $B$ ya que si $A$ es vacía no hay funciones surjetivas, y hay una inyección; y si $A$ es un singleton y $B$ no lo es, entonces sólo hay una suryección, pero muchas inyecciones; y si $A$ tiene al menos dos elementos, entonces hay $2^{|B|}$ inyecciones, pero no necesariamente tantas inyecciones. Así que no podemos decir mucho sobre los "conjuntos arbitrarios").

En definitiva, yo diría que es más "fácil" encontrar las suryecciones exactamente expresando este tipo de desigualdades cardinales. El conjunto de proyecciones de $B$ a $A$ no es menor en cardinalidad que el conjunto de inyecciones de $A$ en $B$ (suponiendo, por supuesto, $A$ tiene al menos dos elementos, y $|A|\leq|B|$ ).