How to implement set-theoretic definition of natural numbers?

Question

How can I pass the following unit test?

fenc(4)==[[[[[], [[]]], [[[], [[]]]]], [[[[], [[]]], [[[], [[]]]]]]], [[[[[], [[]]], [[[], [[]]]]], [[[[], [[]]], [[[], [[]]]]]]]]]

This is my only context.

f(0) = [] (0 maps to the empty list)
f(n+1) = [f(n),[f(n)]] (n+1 maps to the list that contains f(n) and singleton f(n))

I've tried the following:

def fenc(i):
    arr = []
    if i > 1:
        arr.append([])
        arr.append(fenc(i - 1))
    return arr

fenc(4) outputs:

[[], [[], [[], []]]]

I'm not looking for a complete solution, just some strong pointers.

I think you're overcomplicated the problem. Have you tried rewriting the problem statement as `f(0) = []` and `f(n) = [f(n-1), [f(n-1)]]`, and then literally implementing that in a simple `if i = 0: ... else:`? — Green Cloak Guy, Oct 25 '21 at 15:46
Yeah ive butchered it, with what youve suggested however it comes out with ```None``` like this ```[[[[None, [None]], [[None, [None]]]]...```. Any idea what would cause this? — chas108, Oct 25 '21 at 15:51
Are you returning `[]` in the case where `i = 0`, or are you not returning anything (which results in returning `None`)? — Green Cloak Guy, Oct 25 '21 at 15:56
just in case for `i=4` the corresponding natural number should look like this `[ [], [[]], [[], [[]]], [[], [[]], [[], [[]]]] ] `. Are you sure that you are not looking for the *unnatural* ones? — cards, Oct 25 '21 at 16:57

score 1 · Answer 1 · edited Feb 17 '22 at 20:30

1

Figured it out, actually quite simple.

def fenc(i):
    if i == 0:
        return []
    else:
        return [fenc(i-1), [fenc(i-1)]]

edited Feb 17 '22 at 20:30

marc_s

732,580
175
1,330
1,459

answered Oct 25 '21 at 15:58

chas108

29
8

1

are you sure about the result? I think that the recursion rule (in the question) maybe wrong. Check with `i=4`... – cards Oct 25 '21 at 16:26
The test i was given as part of the assignemnt passes for ```i=4```. Im actually unsure how much the question has to do with natural numbers as im not overly familair with the maths there, but as i said it passes the test given. I dont have another way to check so im going to assume this is the implementation wanted as it passes the test without "gutting the question" @cards – chas108 Oct 25 '21 at 16:59
You can explain a little bit the code so others can understand it better – Repky Oct 25 '21 at 17:01
@Charlie Francis ok, but then you shouldn't talk about natural numbers it is misleading. The words *natural* refers to a specific recursion used to construct them, [wiki](https://en.wikipedia.org/wiki/Set-theoretic_definition_of_natural_numbers) – cards Oct 25 '21 at 17:03
@cards sorry I'm really unfamiliar with the maths so didn't mean to mislead. https://en.wikipedia.org/wiki/Set-theoretic_definition_of_natural_numbers was givien this link and assumed (incorrectly) thats what i was wanting to know my bad – chas108 Oct 26 '21 at 12:35

score 1 · Accepted Answer · answered Oct 25 '21 at 19:03

A recursive approach is suggested if you want follow the truth mathematical definition of natural number. My implementation uses strings and not lists.

Generating natural numbers:

following the mathematical set-theoretical definition

def natural_number(n):
    def natural_number_(n):    
        if n == 0: return '[]'
        return '{N}, [{N}]'.format(N=natural_number_(n-1))
    return '[{}]'.format(natural_number_(n))

for i in range(4):
    print(i, natural_number(i))

Output

   0 []
   1 [[]]
   2 [[], [[]]]
   3 [[], [[]], [[], [[]]]]
   4 [[], [[]], [[], [[]]], [[], [[]], [[], [[]]]]]

following the unit test ( the unnatural natural numbers):

def unnatural_number(n):    
    if n == 0: return '[]'
    return '[{N}, [{N}]]'.format(N=unnatural_number(n-1))

for i in range(4):
    print(i, unnatural_number(i))

Output

   0 []
   1 [[], [[]]]
   2 [[[], [[]]], [[[], [[]]]]]
   3 [[[[], [[]]], [[[], [[]]]]], [[[[], [[]]], [[[], [[]]]]]]]
   4 [[[[[], [[]]], [[[], [[]]]]], [[[[], [[]]], [[[], [[]]]]]]], [[[[[], [[]]], [[[], [[]]]]], [[[[], [[]]], [[[], [[]]]]]]]]]

Check if the unnatural_number satisfies the requirements

check = unnatural_number(4) == '[[[[[], [[]]], [[[], [[]]]]], [[[[], [[]]], [[[], [[]]]]]]], [[[[[], [[]]], [[[], [[]]]]], [[[[], [[]]], [[[], [[]]]]]]]]]'
print(check)
# True

Considerations

the difference between the natural_number and unnatural_number is the most outside bracket:
- '{N}, [{N}]'
- '[{N}, [{N}]]' <- not really natural!
such construction of natural numbers was originally pointed out by von Neumann

How to implement set-theoretic definition of natural numbers?

2 Answers2

Linked