$$\newcommand{\<}{<_{\text{new}}}$$ Un elemento de $\mathbb Z^+\times\mathbb Z^+$ es una tupla de la forma $(a,b)$ donde cada $a,b\in\mathbb Z^+$ . Ha dado una función de $\mathbb Z^+$ a conjuntos de tuplas, por lo que el conjunto de potencia de $\mathbb Z^+\times\mathbb Z^+$ .
Tenga en cuenta que voy a interpretar $\mathbb Z^+$ como $\mathbb Z_{\geq 1}$ . Si te refieres a $\mathbb Z_{\geq 0}$ Esto sólo requiere ligeras modificaciones en el concepto general.
En lugar de encontrar una suryección explícita, daré una ordenación de los elementos de $\mathbb Z^+\times\mathbb Z^+$ . En realidad, esto es suficiente para dar una suryección explícita, pero me resulta más fácil trabajar con ella.
En primer lugar, que el $d$ diagonal de $\mathbb Z^+\times\mathbb Z^+$ sean todos los elementos $(a,b)$ tal que $a+b = d$ . Por lo tanto, el $4$ La diagonal contiene $(3,1),(2,2),(1,3)$ .
Ahora, dados dos elementos cualesquiera $(a_1,b_1),(a_2,b_2)$ diremos que $(a_1,b_1)\<(a_2,b_2)$ si $a_1+b_1<a_2+b_2$ (así, un elemento es menor que otro elemento si forma parte de una diagonal menor). Esto compara toneladas de números diferentes, pero aún no está completo (que es más grande, $(3,1)$ o $(2,2)$ ?).
Para solucionar esto, cambiaremos la ordenación de la siguiente manera. Ahora decimos que $(a_1,b_1)\<(a_2,b_2)$ si se cumple alguna de las siguientes condiciones:
-
$a_1+b_1<a_2+b_2$
-
$a_1+b_1 = a_2+b_2$ y $b_1<b_2$
Esta segunda condición dice esencialmente "si dos elementos están en la misma diagonal, elige el que está más a la izquierda como "más pequeño").
Deberías ser capaz de convencerte de que bajo esta definición, siempre tenemos que $(a_1,a_2)\<(a_2,b_2)$ , $(a_2,b_2)\<(a_1,b_1)$ o tenemos que $(a_1,b_1) = (a_2,b_2)$ .
Esto define algo llamado pedido total en $\mathbb Z^+\times\mathbb Z^+$ (más o menos, en realidad tendría que pasar por desigualdades no estrictas para hacerlo formalmente, pero es muy fácil de hacer). Un orden total en un conjunto $S$ significa esencialmente que, dados dos elementos cualesquiera $u,v\in S$ tenemos que, o bien $u<v$ , $v<u$ o $v = u$ (de lo que nos convencimos antes).
Ahora, como esto define un orden total, si decimos que $(1,1)$ es el elemento más pequeño de $\mathbb Z^+\times\mathbb Z^+$ se deduce que $(2,1)$ es el segundo elemento más pequeño, $(1,2)$ es el tercero más pequeño, etc. Ahora, define $f(t):\mathbb Z^+\to\mathbb Z^+\times\mathbb Z^+$ como $t$ va a la $t$ El elemento más pequeño bajo $\<$ . Esto es una sobreproyección.
Obsérvese que esto funciona, pero si definimos un orden total diferente (donde $(1,x)<(2,x)<(3,x)$ y $(1,x)<(1,y)$ si $x<y$ ), tendríamos problemas. La razón de esto es que bajo el orden total que definí, cualquier $(a,b)$ tiene finamente muchos elementos más pequeños que él. Esto no es cierto para el definido anteriormente en este párrafo.
Como tenemos que cada elemento sólo tiene un número finito de elementos más pequeños que él, podemos averiguar que cada elemento es el $t$ El elemento más pequeño para un elemento finito $t$ y, por tanto, si $u$ es el $t$ El elemento más pequeño, entonces $f(t)= u$ . Podemos hacer esto para cualquier elemento $u$ Así que $f$ es un suryecto.
