computabilitycountable

How to prove set of all two argument functions cannot be countable


We can prove that set of all one argument functions cannot be countable using the cantor's diagonal. for example

     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 .....   
.
.
.

for all functions f1 to fn we can pass all the arguments and 1 to n for some n. then by taking the diagonal values and add 1 to diagonal values and we can prove that we can't count all the one argument functions.(since change the diagonal values will produce a row unique which haven't listed)

Wonder is there a particular method to count two argument functions also??..

Thanks..


Solution

  • I think I've found an answer. I'm writing the answer in case anyone is interested.

    we can prove than all the pairs of positive integers can be countable. see below

    (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).....
     .
     .
     .
    

    so from the cantor's zig zag we can prove that they can be countable.. see page 8 on this book http://www.scribd.com/doc/51068193/3/Enumerable-Sets

    (1,1) (1,2) (2,1) (1,3) (2,2) (3,1) ....
    

    so we can write our problem as below.

        (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    ......   
    .
    .
    .
    

    Now by the knowledge of cantor's diagonal.. we can argue that all the two argument functions can't be countable.