1. 12

  2. 3

    This is super, and it reminds me of Cantor’s diagonal argument. Is there a term for these kind of arguments, where you set up an infinite grid and then show a false statement? The nature of the proof falls under reductio ad absurdum (my favorite kind, since these are often very easy for me to understand) but this setting up of an infinite set seems like it should have a name …

    1. 1

      The guy’s confusion in the comments is exactly what I’m encountering.

      Clearly, \bar{f} is computable, so it should belong in set A (in fact, it should be included by the “infinite function generator”).

      I’m not sure how this post proves anything.

      I want to understand ;_;

      1. 2

        So I think there is a sneaky self-referential bit in there because $ \bar{f}$’s form depends on the input. The form of the input informs the computation.

        The form of the proof is a bit like the “Say P is the largest prime” and then you go on to show, “but wait, if it was, how can I pull this other, bigger, prime out of my back pocket?!”

        Here we start by saying here’s a table of all the possible functions in A and their input values. My table is infinite and I say I have all possible functions in it.

        But then you come in and pull out $\bar{f}$ from your back pocket and say “Is that SO?! Then explain THIS!” and it turns out for some given input $\bar{f}$ is guaranteed to give a different output than ANY function in my INFINITE table, so POOF, it must mean my infinite table is not enough.

        1. 1

          I guess that is the problem I am having. I knew it was self-referential, but…to me, infinity is also somewhat self-referential.

          It is really hard for me to describe it. But, lets say I define an infinity that is the sum of all natural numbers.

          Lets say our “infinity” stopped (I know this is not right to say…) at 3. 1 + 2 = 3. Now lets go 1 step forward. 1 + 2 + 3 = 6. 3, the previous definition of infinite sum, is now part of the sequence.

          This is kind of how I see this example.

          Basically this guy’s table T would be double the size, but really, that’s how it should have always been.