Un mapa suryectivo $S \to T$ implica $|S| \geq |T|$

Question

El problema: Supongamos que existe una función que mapea $S$ en $T$ .

Demuestra que $\operatorname{Card}(S)\ge\operatorname{Card}(T)$

Asunto: No puedo encontrar una razón para que esto siga. Si $S$ mapas $T$ entonces esto garantiza que para cualquier elemento en $T$ hay al menos un elemento en $S$ . Por lo tanto, sigo con el hecho de que $\operatorname{Card}(S)\le\operatorname{Card}(T)$ . ¿Me he perdido algo, o hay un error en mi guía de estudio?

Gracias de antemano.

Answer 1

Parece que no entiendes el significado de "función sobreyectiva (o onto)".

Una función de $A$ a $B$ es onto si, para cada elemento $b\in B$ Hay un poco de $a\in A$ tal que $f(a)=b$ . Así, por ejemplo, el mapa $0\mapsto 5, 1\mapsto 5$ es una suryección de $\{0, 1\}$ en $\{5\}$ .

Mientras tanto hay no la sujeción de $\{5\}$ a $\{0, 1\}$ - podemos enviar $5$ a $0$ o podemos enviar $5$ a $1$ pero no podemos hacer ambas cosas (las funciones son un valor único ), y cualquiera de $0$ o $1$ enviamos $5$ a, el otro será "extrañado".

Answer 2

Si, para cada elemento de $T$ hay al menos un elemento en $S$ , seguramente eso significa que hay al menos tantos elementos en $S$ que en $T$ En otras palabras, el tamaño de $S$ es al menos tan grande como $T$ .

Para demostrar una afirmación como ésta, hay un resultado estándar para los conjuntos finitos (a veces se da como una definición) que $|A|\leq|B|$ si y sólo si existe una inyección (una función uno a uno) de $A$ a $B$ . Esto tiene sentido porque dice que hay al menos suficientes elementos en $B$ tal que cada elemento de $A$ puede enviarse a un elemento diferente; no es necesario duplicar el lugar donde van los elementos.

Una vez que se sabe que hay una sobrecarga $S\rightarrow T$ se puede definir una inyección muy directa en la otra dirección. (Técnicamente esto requiere el axioma de elección). En otras palabras, como hay una suryección, para cualquier elemento $t\in T$ hay al menos un elemento $s\in S$ tal $f(s)=t$ . Entonces, defina $g(t)=s$ para uno de esos $s$ 's. Esto es definitivamente una inyección $T\rightarrow S$ (porque $f$ estaba bien definida) y así se puede concluir $|S|\geq|T|$ .

Answer 3

Si una función $f:X\to Y$ es sobreyectiva, sabemos que $\forall y\in Y,\exists x\in X: f(x)=y$ . Así, sabemos que hay al menos un elemento en $X$ para cada elemento de $Y$ . Esto implica que $\lvert X\rvert \ge \lvert Y\rvert$ .

Answer 4

Si para cada elemento de $T$ hay al menos un elemento en $S$ que mapea en él, ¿no significa que hay al menos tantos elementos en $S$ como en $T$ (no olvide un elemento en $S$ puede asignarse a un solo elemento de $T$ ).