Inicio · Parte 04 — Matemática discreta para computación
funciones totales de A a B: |B|^|A|
biyecciones de A en A: |A|!Sobre conjuntos finitos, las tres propiedades se cuentan. Una función es inyectiva si no repite salidas, sobreyectiva si alcanza todo el codominio y biyectiva si ambas. Entre conjuntos del mismo tamaño finito, inyectiva y sobreyectiva son equivalentes —hecho que falla en conjuntos infinitos y da lugar a las paradojas de Hilbert—.
El conteo de funciones ilustra la regla del producto: cada uno de los |A| elementos puede ir a cualquiera de los |B| destinos, luego hay |B|^|A| funciones. Las biyecciones de un conjunto en sí mismo son |A|!, que es el conteo de permutaciones de la clase 088.
La inyectividad es la condición que hace invertible una función (clase 058) y la que define una función hash perfecta. Como una función hash mapea un dominio enorme en un rango pequeño, no puede ser inyectiva, y de ahí las colisiones que el palomar garantiza en la clase 090.
En machine learning, la pérdida de inyectividad es lo que hace que una capa no sea invertible: si la dimensión de salida es menor que la de entrada, información se pierde irremediablemente. Los normalizing flows se construyen precisamente con capas biyectivas para poder invertirlas y calcular densidades exactas.
Dos funciones sobre un dominio de tres elementos.
dominio = {1,2,3}, codominio = {a,b,c}
f = {1→a, 2→b, 3→c}
inyectiva: 3 salidas distintas ✓
sobreyectiva: alcanza a, b y c ✓
biyectiva ✓
g = {1→a, 2→a, 3→b}
inyectiva: 1 y 2 comparten salida ✗
sobreyectiva: no alcanza c ✗
Conteo:
funciones totales posibles: 3³ = 27
biyecciones posibles: 3! = 6Inyectiva, sobreyectiva y biyectiva sobre conjuntos finitos.
python classes/part-04-matematica-discreta-para-computacion/086-funciones-discretas/lab.py
compmath run 086ff_inyectivaf_sobreyectivaf_biyectivagg_inyectivafunciones_totales_posiblesbiyecciones_posibles{
"f": {
"1": "a",
"2": "b",
"3": "c"
},
"f_inyectiva": true,
"f_sobreyectiva": true,
"f_biyectiva": true,
"g": {
"1": "a",
"2": "a",
"3": "b"
},
"g_inyectiva": false
}Funciones hash y colisiones, invertibilidad de capas, codificación sin pérdida y normalizing flows.
Los grafos de cómputo, la búsqueda en árbol y las GNN son estructuras discretas; el conteo sostiene la probabilidad que después usa todo modelo generativo.