Тематика: бинарные отношения, счётность, теорема Кантора - Бернштейна.
Уровень: ВУЗ

Задание:

Доказать, что множество бинарных отношений над множеством натуральных чисел которые (отношения) содержат конечное кол-во пар - счётно.

Решил криво, поэтому обращаюсь ).

Решение:
Докажем более общее утверждение, что множество всех бинарных отношений которые содержат конечное кол-во пар счётно. Докажем с помощью теоремы Кантора - Бернштейна. Определим отображение f : N -> A так что для натурального n E N: f(n) = {(n,n)}, и определим отображение g : A -> N следующим образом: пусть a E A это совокупность пар так что (i0, i1), (i2, i3), ... ,(ik, ik+1) E a. Поскольку кол-во пар конечно, отсортируем их по-возрастанию элементов в них и определим образ g(a) так: g(a) = 2^i0*3^i1*...*2^ik*3^ik+1. Далее я показал взимноднозначность для f и g. После чего множество бинарных отношений с конечным кол-вом пар счётно так как оно подмножество всех бинарных отношений с конечным кол-вом пар.

Вопрос следующий:
Насколько правомочно вот это: "отсортируем их по возрастанию элементов в них"? Можно ли считать это корректным ходом в доказательстве? Есть ли более эффективное доказательство? (можно использовать только то что указано в тематике).

Заранее спасибо.