Re: MY LIST of the subsets of N

From: Jim Ferry (corklebath_at_hotmail.com)
Date: 07/01/04 

Date: 1 Jul 2004 13:04:33 -0700

Wow! This is really cool, David!

I haven't gone through all the details of your algorithm, but what
strikes me is that you've implicitly defined a function f that assigns
a natural number to every subset of the natural numbers. For example,

f({1}) = 1,
f({2}) = 2,
f({1,2}) = 3,
f({3}) = 4.

The function f (let's call it Ferguson's function) simply assigns to
each subset S of the natural numbers the location at which it appears
in the list your algorithm generates.

I believe that you've shown, for example, that f({n}) = 2^(n-1).

I'm curious about the value of f(S) when S is the set of (positive)
odd numbers. Can you work out what that would be? It's probably
pretty big, but I wonder of it's odd or even.

For that matter, what is f(S) when S is the set of (positive) prime
numbers? Oooh, I wonder if it is itself prime!

You know, I sense a more general question here. For which subsets
S is the number f(S) itself a member of S? Hmmm . . .

Well 1 is a member of {1}, and 2 is a member of {2}, certainly, but
3 is not a member of {1,2}, and 4 is not a member of {3}.

Let T be the set of numbers f(S) such that f(S) is not a member of S.
So T = {3,4,...}. What is T exactly? Could someone figure this out?
And what is f(T)? And is f(T) a member of T?

Let's see . . . if f(T) were a member of T then, wait a minute . . .
but if f(T) were not a member of T then . . . ummm.

Very curious function this f.

Relevant Pages

  • Re: MY LIST of the subsets of N
    ... > in the list your algorithm generates. ... but I wonder of it's odd or even. ... And is fa member of T? ... > Very curious function this f. ...
    (sci.math)
  • Re: decidable
    ... a proof of A, then the algorithm verifies that there is a proof of A, ... axiomatized by itself, i.e., every member of the theory is an axiom for ... The only theory that has as members only valid sentences is indeed the ...
    (sci.logic)
  • Re: Recursively enumerable sets
    ... If n is not a member of the ... If an r.e. set happens to have the property that its complement is also ... exactly one of the two lists. ... this algorithm may run forever." ...
    (comp.theory)
  • Re: Recursively enumerable sets
    ... If n is not a member of the ... If an r.e. set happens to have the property that its complement is also ... this algorithm may run forever." ... I know you already wrote me that the algorithm may run forever. ...
    (comp.theory)
  • Re: Recursively enumerable sets
    ... If n is not a member of the ... this algorithm may run forever." ... I know you already wrote me that the algorithm may run forever. ... What about evens plus "3"? ...
    (comp.theory)