Przedstawiłeś zapis w prostej notacji, a nie mamy tutaj LaTeX-a, więc nie mam pewności czy o to chodzi. Mamy wykazać, że oba zbiory mają taką samą moc. Pierwszy zbiór jest skojarzony z parami liczb nieparzystych, mogą być to na przykład elementy:
(1,3), (7,3), (13,13), ...
Gdyby tak wypisać wszystkie kombinacje, potem podliczyć ile ich jest, to otrzymalibyśmy wartość:
|N x N|
Drugi zbiór skojarzony jest też z parami liczb. Jedną z nich są liczby parzyste, drugą iloczyn liczby parzystej i nieparzystej. Sprawdźmy czym jest iloczyn liczby parzystej i nieparzystej:
n = 2i
m = 2j + 1
i, j e N
n * m = 2i(2j + 1) = 2(2ij + i)
Widzimy więc, że iloczyn da nam zawsze liczbę parzystą, a więc aby policzyć moc:
|P x P|
musi zliczyć wszystkie pary:
(2,4), (10,10), (4,32), ...
Jednak zbiory liczb parzystych i nieparzystych to zbiory nieskończone. Oba są jednak zbiorami przeliczalnymi, bo:
N x N = 2n + 1 x 2n + 1
P x P = 2n x 2n
co dowodzi, że istnieje funkcja wzajemnie jednoznaczna, przekształcająca liczby naturalne na iloczyny kartezjańskie:
n --> N x N
n --> P x P
a to z kolei oznacza, że oba zbiory są równoliczne ze zbiorem liczb naturalnych. Skoro tak to na mocy przechodniości zbiory mają taką samą moc:
|N x N| = |P x NP|