1

For working with countable sets I have to define a coding function of all finite subsets of N (natural numbers). How can I do this? I started with finding a function for all natural numbers: f(n)=1+2+...+(n-1)+n. But how can I express a coding function for all possible subsets of f? And how can I say that f contains all finite natural numbers? I can not say n=infinity-1 because infinity-1 is still infinity. Is there a formal way constitute all finite natural numbers?

user3351676
  • 91
  • 1
  • 1
  • 5

1 Answers1

1

If I understand you correctly, you wish to define a function that would count through all finite subsets of N. One way to achieve this is to use the 1s in the binary representation of a number n to encode the elements of f(n), that is f(n) = {k \in N | the k-th binary digit of n is 1}.

In programming terms, say for instance in Python (here I'm using lists to represent subsets of N) this would look like

def f(n):
    result = []
    k = 1
    while n != 0:
        if n % 2 == 1:
            result.append(k)
        k += 1
        n //= 2
    return result
Cereal
  • 156
  • 7
  • Hello, and thanks for your help. I'm sorry but I don't understand your solution. (Maybe just because I am not so familiar with Python.) As I understood k are the elements of result and the first k = 1. Line 4 checks if n is not equal to zero. Line 5 checks if n is an odd number. If yes, k is added to the results list in line six. Line 7 is clear too. Line 8 redifines n by its floor division by 2. For me is unclear what ensures that all elements of n are listed and where this function counts to all countable elements of natural numbers!? Why just odd numbers are added to the results list? – user3351676 Dec 27 '20 at 14:08
  • From your original phrasing I wasn't actually totally sure what it is you wanted. What I implemented is what's described in the post, i.e. you encode all finite sets of natural numbers via a mapping from the binary representation of a number to a set containing every number that corresponds to a `1` in said representation. I'm not just adding odd numbers, the check is basically "is the lowest binary digit of n a 1". If it is, you add the corresponding k. The integer division by 2 is equivalent to a right shift of n by 1 bit. – Cereal Dec 27 '20 at 14:49
  • Thanks a lot. :-) – user3351676 Jan 04 '21 at 22:43