Как доказать множество всех двух функций аргумента не может быть исчисляемым
Мы можем доказать, что множество всех функций с одним аргументом не может быть счетным, используя диагональ кантора. например
1 2 3 4 5 6 7 ......
f1 10 12 23 1 3 12 3 ......
f2 15 6 7 8 9 11 4 ......
f3 14 2 4 3 3 4 5 ......
f4 12 2 3 5 1 20 56 .....
.
.
.
для всех функций от f1 до fn мы можем передать все аргументы и от 1 до n для некоторого n. затем, взяв диагональные значения и добавив 1 к диагональным значениям, мы можем доказать, что не можем сосчитать все функции с одним аргументом (поскольку изменение диагональных значений приведет к появлению уникальной строки, которой нет в списке)
Интересно, есть ли конкретный метод для подсчета двух функций аргументов?
Спасибо..
2 ответа
Я думаю, что нашел ответ. Я пишу ответ на случай, если кому-то будет интересно.
мы можем доказать, что все пары натуральных чисел могут быть счетными. увидеть ниже
(1,1) (1,2) (1,3) (1,4) (1,5) (1,6).....
(2,1) (2,2) (2,3) (2,4) (2,5) (2,6).....
(3,1) (3,2) (3,3) (3,4) (3,5) (3,6).....
(4,1) (4,2) (4,3) (4,4) (4,5) (4,6).....
.
.
.
поэтому из зигзага кантора мы можем доказать, что они могут быть исчисляемыми. см. стр. 8 этой книги http://www.scribd.com/doc/51068193/3/Enumerable-Sets
(1,1) (1,2) (2,1) (1,3) (2,2) (3,1) ....
поэтому мы можем написать нашу проблему, как показано ниже.
(1,1) (1,2) (2,1) (1,3) (2,2) (3,1)
f1 10 12 23 1 3 12 ......
f2 15 6 7 8 9 11 ......
f3 14 2 4 3 3 4 ......
f4 12 2 3 5 1 20 ......
.
.
.
Теперь, зная диагональ кантора... мы можем утверждать, что все две функции аргумента не могут быть счетными.
Интересно, есть ли конкретный метод для подсчета двух функций аргументов?
Вы имеете в виду Wonder, есть ли конкретный метод для подсчета двух функций аргумента? ("также" подразумевает, что он существует для функций с одним аргументом).
Если подмножество неисчисляемого множества всегда также неисчисляемо, то вы можете просто использовать подмножество набора всех функций с двумя аргументами, где вы фиксируете второй параметр в константе (делая его по существу равным функции с одним аргументом)). Однако я сомневаюсь, что это предположение верно.
Я думаю, что вы упустили некоторые важные предпосылки для диаграммы (как fn строятся так, как они не выбраны произвольно). Может быть, изучение их приведет вас к разгадке? Я думаю, это домашний вопрос? Разрешено ли в stackru публиковать домашние вопросы, а в вашем университете разрешать их решать кому-то еще?