[Question]
  [
This construction is a way of representing the Natural Numbers.
In this representation, 0 is defined as the empty set and for all other numbers, n is the union of {0} and {n-1}.
For example to construct 3 we can follow the algorithm: 
```
3 =
{ø, 2} =
{ø, {ø, 1}} =
{ø, {ø, {ø}}}
```
# Task
As you may have guessed your task is to take in a natural number (including zero) and output its construction.
You may output as a either a string or as a set object if your language of choice supports such objects.
If you choose to output as a string you should represent a set with curly braces (`{}`). You may optionally represent the empty set as `ø` (otherwise it should be a set with no entries `{}`). You may also choose to add commas and whitespace between and after entries in the set.
Order is not important, however you may ***not*** have any repeated elements in the sets you output (e.g. `{ø,ø}`)
This is [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'") so the goal is to have the fewest bytes
# Test cases
Here are some test cases with some example outputs.
```
0 -> {}
1 -> {{}}
2 -> {{}{{}}}
3 -> {{}{{}{{}}}}
4 -> {{}{{}{{}{{}}}}}
```
  
[Answer]
# [Python](https://docs.python.org/), 28 bytes
```
lambda x:"{{}"*x+x*"}"or"{}"
```
[Try it online!](https://tio.run/nexus/python2#S7PV@J@TmJuUkqhQYaVUXV2rpFWhXaGlVKuUX6QE5P3X5CooyswrUUjTMDTQ/A8A "Python 2 – TIO Nexus")
This is a pretty bland solution to the problem. For numbers greater than zero you can get the representation with the string formula `"{{}"*x+"}"*x`. However this doesn't work for zero where this is the empty string. We can use this fact to short circuit an `or` to return the empty set.
I wanted to use python's builtin set objects to solve this problem but unfortunately:
```
TypeError: unhashable type: 'set'
```
You cannot put sets inside of sets in python.
[Answer]
# [Haskell](https://www.haskell.org/), 37 bytes
```
f 0="{}"
f n=([1..n]>>)=<<["{{}","}"]
```
[Try it online!](https://tio.run/nexus/haskell#@5@mYGCrVF2rxJWmkGerEW2op5cXa2enaWtjE61UDRTXUapViv2fm5iZZ5uZV5JalJhcolKal5OZl1qsp5GbWKCRpleUmpiiqakHFvtvwGXIZcRlzGUCAA "Haskell – TIO Nexus")
Until 10 minutes ago an answer like this would have made no sense to me. All credits go to [this tips answer](https://codegolf.stackexchange.com/a/52945/62393).
Basically, we use `>>` as `concat $ replicate` (but passing it a list of n elements instead of simply n), and `=<<` as `concatMap`, replicating then n times each of the strings in the list and concatenating the result into a single string.
The `0` case is treated separately as it would return an empty string.
[Answer]
## JavaScript, 28 bytes
```
f=n=>n?--n?[[],f(n)]:[[]]:[]
```
Represents sets using arrays. 38-byte nonrecursive solution:
```
n=>'{{}'.repeat(n)+'}'.repeat(n)||'{}'
```
Returns the example output strings.
[Answer]
## Mathematica, 27 bytes
I've got two solutions at this byte count:
```
Nest[{{}}~Union~{#}&,{},#]&
Union//@Nest[{{},#}&,{},#]&
```
[Answer]
# [Perl 6](https://perl6.org), 37 bytes
```
{('{}','{{}}',{q:s'{{}$_}'}...*)[$_]}
```
[Try it](https://tio.run/nexus/perl6#VY/RaoNAEEXf5ysuQbq7dbNJ2tIHbaQf0bcYQtAtCNGYrJaWZfrrVjeV0qc7c4Z7Z6Z3Fh/Ppkip/sJdcS4ttoOXwrPQwnsexV8SN5XRgQUbY@7VLjrseRgNr511ncMWp6qxTipTH9sEHnXiVjIvYwWxzATky87zPovVKkUcrTW@ow2YqB@Xv40JKbWnY4P4FpcSvZ@vc/Yyg0ReNW3faeT2s7VFZ0soeAIqh@lkGcZKYx5rLHxgPPn9jHmREg/rwJg2QccX6eG3mhqmx78uAKanf@QG@Qc "Perl 6 – TIO Nexus")
## Expanded:
```
{   # bare block lambda with implicit parameter ｢$_｣
  (
    # generate a sequence
    '{}',   # seed it with the first two values
    '{{}}',
    {   # bare block lambda with implicit parameter ｢$_｣
      q         # quote
      :scalar   # allow scalar values
      '{{}$_}'  # embed the previous value ｢$_｣ in a new string
    }
    ...         # keep using that code block to generate values
    *           # never stop
  )[ $_ ] # get the value at the given position in the sequence
}
```
[Answer]
# [Röda](https://github.com/fergusq/roda), 37 bytes
```
f n{[[[],f(n-1)]]if[n>1]else[[[]]*n]}
```
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E), ~~6~~ 5 bytes
### Code
```
ƒ)¯sÙ
```
Uses the **CP-1252** encoding. [Try it online!](https://tio.run/nexus/05ab1e#@39skuah9cWHZ/7/bwIA "05AB1E – TIO Nexus") or [Verify all test cases!](https://tio.run/nexus/05ab1e#JY0/CsIwGMXneopHtkItKbg46KI4Fg/QJUjaBtNEkk/q0ku4eQqPULDgtepHfduP96@QpxKsJBFHD2o1am@t741rUEiQ6XTM0BtqUWIHmedbUc3fZ/p5x@k1A8MK7IhpxHqPaRQZL52DcbSMBR3vluDrhW7BN0F1ouJOWiWcPFitwuJFUpcrn//J6QfBkA6KjHdcGObNDw).
### Explanation
```
ƒ       # For N in range(0, input + 1)..
 )      #   Wrap the entire stack into an array
  ¯     #   Push []
   s    #   Swap the two top elements
    Ù   #   Uniquify the array
```
[Answer]
## [Retina](https://github.com/m-ender/retina), 22 bytes
```
.+
$*
\`.
{{}
{
^$
{}
```
[Try it online!](https://tio.run/nexus/retina#U9VwT/ivp82losUVk6DHVV1dy1XNxRWnwlVd@/@/AZchlxGXMZcJAA "Retina – TIO Nexus")
### Explanation
```
.+
$*
```
Convert the input to unary.
```
\`.
{{}
```
Replace each unary digit with `{{}` and print the result without a trailing linefeed (`\`).
```
{
```
Remove the opening `{`s, so that the remaining `}` are exactly those we still need to print to close all the sets. However, the above procedure fails for input `0`, where we wouldn't print anything. So...
```
^$
{}
```
If the string is empty, replace it with the empty set.
[Answer]
# [Brain-Flak](https://github.com/DJMcMayhem/Brain-Flak), 135 bytes
Includes +1 for `-A`
```
(({}())<{({}[()]<((((((()()()()()){}){}){}())()){}{})>)}{}({}[()()])>)(({})<{({}[()]<(((({}()())[()()])))>)}{}>[()]){(<{}{}{}>)}{}{}{}
```
[Try it online!](https://tio.run/nexus/brain-flak#XUwxDoBACPtOO7g4k0t8h/ElhLdjsboIBNrQtoEskJG6J3gFXPyaWR7Bh4ksatsgi@ik/DLGIP0roT1r3kzExIiyDLr33o4b "Brain-Flak – TIO Nexus")
```
(({}())<                 # Replace Input with input + 1 and save for later
  {({}[()]<              # For input .. 0
    (...)                # Push '}'
  >)}{}                  # End for and pop counter
  ({}[()()])             # change the top '}' to '{'. This helps the next stage
                         # and removes the extra '}' that we got from incrementing input
>)                       # Put the input back on
(({})<                   # Save input
  {({}[()]<              # For input .. 0
    (((({}()())[()()]))) # Replace the top '{' with "{{{}"
  >)}{}                  # end for and pop the counter
>[()])                   # Put down input - 1
{(<{}{}{}>)}             # If not 0, remove the extra "{{}"
{}{}{}                   # remove some more extras
```
[Answer]
# [CJam](https://sourceforge.net/p/cjam), 11 bytes
```
Lri{]La|}*p
```
Prints a set-like object consisting of lists of lists. CJam prints empty lists as empty strings, since lists and strings are almost interchangeable.
[Try it online!](https://tio.run/nexus/cjam#@@9TlFkd65NYU6tV8P@/MQA "CJam – TIO Nexus")
**Explanation**
```
L            Push an empty array 
 ri          Read an integer from input
   {    }*   Run this block that many times:
    ]          Wrap the entire stack in an array
     La        Wrap an empty list in an array, i.e. [[]]
       |       Set union of the two arrays
          p  Print the result
```
# Old answer, ~~21~~ 18 bytes
This was before it was confirmed that it was OK to print a nested list structure. Uses the string repetition algorithm.
*Saved 3 bytes thanks to Martin Ender!*
```
ri{{}}`3/f*~_{{}}|
```
**Explanation**
```
ri                  Read an integer from input
  {{}}`             Push the string "{{}}"
       3/           Split it into length-3 subtrings, gives ["{{}" "}"]
         f*         Repeat each element of that array a number of times equal to the input
           ~_       Dump the array on the stack, duplicate the second element
             {{}}|  Pop the top element, if it's false, push an empty block, which gets 
                      printed as "{}". An input of 0 gives two empty strings on the 
                      repetition step. Since empty strings are falsy, we can correct the 
                      special case of 0 with this step.
```
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 6 bytes
```
⁸,⁸Q$¡
```
This is a niladic link that reads an integer from STDIN and returns a ragged array.
[Try it online!](https://tio.run/nexus/jelly#@/@ocYcOEAeqHFr4/9Cio5Me7pyh8HDH9kcNcxScE3NyFBLzUhSS8/PKUotKFEryFQIqSzLy8xSKK/NKEiv0/psAAA "Jelly – TIO Nexus")
### How it works
```
⁸,⁸Q$¡  Niladic link.
⁸       Set the return value to [].
    $   Combine the three links to the left into a monadic chain.
 ,⁸     Pair the previous return value with the empty array.
   Q    Unique; deduplicate the result.
     ¡  Read an integer n from STDIN and call the chain to the left n times.
```
[Answer]
# [Python 3](https://docs.python.org/3/), 32 bytes
```
f=lambda n:[[],n and f(n-1)][:n]
```
Not the shortest way, but I just *had to* do this with recursion.
[Try it online!](https://tio.run/nexus/python3#@59mm5OYm5SSqJBnFR0dq5OnkJiXopCmkadrqBkbbZUX@z8tv0ghTyEzT6EoMS89VcNU04qLs6AoM69EI09HQV3XTl0HpFxT8z8A "Python 3 – TIO Nexus")
[Answer]
# [Cardinal](https://www.esolangs.org/wiki/Cardinal), ~~51~~ 50 bytes
```
%:#>"{"#? v
x  ^?-"}{"<
v <8/ ?<
>  8\
v"}"<
>?-?^
```
[Try it online!](https://tio.run/nexus/cardinal#@69qpWynVK2kbK9QxlWhoBBnr6tUW61kw1WmYGOhr2Bvw2WnoGARw1WmVAsUtLPXtY/7/98EAA "Cardinal – TIO Nexus")
## Explanation
```
%:#
x
```
Receive input and send down and left from the #
```
   >"{" ? v
   ^?-"}{"<
```
Print "{" one time then print "{}{" n-1 times if n>1 then print "{}" if n>0
```
       #
v <8/ ?<
>  8\
```
Hold onto the input value until the first loop completes
```
v"}"<
>?-?^
```
Print "}" once then repeat n-1 times if n>1
[Answer]
# AHK, 55 bytes
```
IfEqual,1,0
s={{}{}}
Loop,%1%
s={{ 2}{}}%s%{}}
Send,%s%
```
It's not the shortest answer but I enjoyed this because the idiosyncrasies of AutoHotkey make this recursion method look *super* wrong. `If` and `Loop` statements assume the next line is the only thing included if brackets aren't used. Curly brackets are escape characters so you have to escape them with other curly brackets to use them as text. Also, the variable `1` is the first passed argument. When I read the code without knowing those tidbits, the logic *looks* like this:
* If 1=0, then set `s` equal to the wrong answer
* Loop and add a bunch of brackets to the beginning and a few to the end every time
* Return by sending the resulting string to the current window
Without all the bracket escape characters, it would look like this:
```
IfEqual,1,0
   s={}
Loop,%1%
   s={{}%s%}
Send,%s%
```
[Answer]
# JavaScript 50 bytes
```
g=n=>n==0?"":"{{}"+g(n-1)+"}"
z=m=>m==0?"{}":g(m)
```
[Answer]
# [tinylisp](https://github.com/dloscutoff/Esolangs/tree/master/tinylisp), 52 bytes
```
(d f(q((n)(i n(i(e n 1)(c()())(c()(c(f(s n 1))())))(
```
[Try it online!](https://tio.run/nexus/tinylisp#LYo5DoAwDMB2XpHRGRl4UOiBKkGAMvH6ci62ZLkRJbODK0WcQhKXXgko@imQOd76pB/amFeLMpexWj21Y7FNslDNpyTDPVw "tinylisp – TIO Nexus") (test harness).
### Explanation
Note that `(cons x (cons y nil))` is how you build a list containing `x` and `y` in Lisp.
```
(d f           Define f to be
 (q(           a quoted list of two items (which acts as a function):
  (n)           Arglist is a single argument n
  (i n          Function body: if n is truthy (i.e. nonzero)
   (i(e n 1)     then if n equals 1
    (c()())       then cons nil to nil, resulting in (())
    (c            else (if n > 1) cons
     ()            nil to
     (c            cons
      (f(s n 1))    (recursive call with n-1) to
      ())))         nil
   ()))))        else (if n is 0) nil
```
[Answer]
# [C (gcc)](https://gcc.gnu.org/), 52 bytes
```
n(i){putchar(123);i>1&&n(0);i&&n(i-1);putchar(125);}
```
Taking advantage of some short circuit evaluation and recursion.
[Try it online!](https://tio.run/nexus/c-gcc#dY4xDsIwDEX3nMJTGyOQmhamSFwEGKKAwAMuSpMuVc8ekhbEgOLFX35P1o8sCadX8PZhnFRth5qOqqpYNinlTTuF@iccUM9x7OkKLrDESUCaxYavVJ@5Rv0BqgTaEuhKYP8PZiGIPTwNpaIpGHe3W7A9Dx6yB5t8Gk8XhLXpUnp96G4@OIYmfYlv "C (gcc) – TIO Nexus")
[Answer]
# Pure [Bash](https://www.gnu.org/software/bash/), ~~49~~ ~~48~~ 41 bytes
```
for((;k++<$1;)){ s={{}$s};};echo ${s-{\}}
```
[Try it online!](https://tio.run/nexus/bash#@5@WX6ShYZ2trW2jYmitqVmtUGxbXV2rUlxrXWudmpyRr6BSXaxbHVNb@///fwMA "Bash – TIO Nexus")
[Answer]
# [dc](https://www.gnu.org/software/bc/manual/dc-1.05/html_mono/dc.html), 46 bytes
```
[[{}]]sx256?^dd3^8d^1-/8092541**r255/BF*+d0=xP
```
[Try it online!](https://tio.run/nexus/dc#@x8dXV0bG1tcYWRqZh@XkmIcZ5ESZ6irb2FgaWRqYqilVWRkaqrv5KalnWJgWxHw/78xAA "dc – TIO Nexus")
Input on stdin, output on stdout.
This works by computing a formula for the desired output as a base-256 number. The P command in dc is then used to print the base-256 number as a string.
---
Further explanation: 
Let n be the input n. The dc program computes the sum of
A = floor(256^n / 255) \* 125     (BF is interpreted by dc as 11\*10+15 = 125)
and
B = floor((256^n)^3 / (8^8-1)) \* 8092541 \* (256^n).
 
For A:
Observe that 1 + 256 + 256^2 + ... + 256^(n-1) equals (256^n-1)/255, by the formula for a geometric progression, and this equals floor(256^n / 255). So this is the number consisting of n 1's in base 256.
When you multiply it by 125 to get A, the result is the number consisting of n 125's in base 256 (125 is a single digit in base 256, of course). It's probably better to write the digits in base 256 as hex numbers; 125 is hex 7D, so A is the base-256 number consisting of n 7D's in a row.
 
B is similar:
This time observe that 1 + 16777216 + 16777216^2 + ... + 16777216^(n-1) equals (16777216^n - 1)/16777215, and this equals floor(16777216^n/16777215). 
Now, 256^3 = 16777216, and 8^8-1 = 16777215, so this is what we're computing as floor((256^n)^3 / (8^8-1)).
From the geometric series representation, this number in base 256 is 100100100...1001 with n of the digits being 1 and the rest of the digits being 0.
This is multiplied by 8092541, which is 7B7B7D in hexadecimal. In base 256, this is a three-digit number consisting of the digits 7B, 7B, and 7D (writing those digits in hex for convenience).
It follows that the product written in base 256 is a 3n-digit number consisting of the 3 digits 7B 7B 7D repeated n times.
This is multiplied by 256^n, resulting in a 4n-digit base-256 number, consisting of the 3 digits 7B 7B 7D repeated n times, followed by n 0's. That's B.
 
Adding A + B now yields the 4n-digit base-256 number consisting of the 3 digits 7B 7B 7D repeated n times, followed by n 7D's. Since 7B and 7D are the ASCII codes for `{` and `}`, respectively, this is the string consisting of n copies of `{{}` followed by n copies of `}`, which is exactly what we want for n > 0. The P command in dc prints a base-256 number as a string, just as we need.
Unfortunately, n=0 has to be treated as a special case. The computation above happens to yield a result of 0 for n=0; in that case, I've just hard-coded the printing of the string `{}`.
[Answer]
# Java 7, 61 bytes
```
String p(int p){return p<1?"{}":p<2?"{{}}":"{{}"+p(p-1)+"}";}
```
[Try it online!](https://tio.run/nexus/java-openjdk#JY6xDoIwFEV3vuKlU5sGIg4OFvQLnBiNQ0E0L4Hy0haNafrtWGB59y73nEdzO2AH3aCdg5tGE5bGWzRvII7GA4lgez9bA1SVVxYiO1N1TCXEVNdgkjjlpZAsMhUX2oHOa5/iM@ETxoTlO/X@0CJkqwfa2vTfTcmFyl6T3XxYHxRWJ4VSCmh@zvdjMc2@oLT2g@EIEhjkl3QktEV6UqR1zOLyBw "Java (OpenJDK 8) – TIO Nexus")
[Answer]
## Batch, 88 bytes
```
@set s={}
@if %1 gtr 0 set s=&for /l %%i in (1,1,%1)do @call set s={{}%%s%%}
@echo %s%
```
[Answer]
# [Brainf\*\*\*](https://esolangs.org/wiki/Brainfuck), 99 bytes
```
>+>+>+>+<[>[-<+++++>]<-<]>--[->+>+<<]
>[-<+>]>++<,[[->>+>+<<<]>>[-<<<..>>.>]>[-<<.>>]+[]]<.>>.
```
(newline for aesthetics)
Since it's brainf\*\*\*, it takes input as ascii char codes (input "a" corresponds to 96)
# Braineasy, 60 bytes
Also, in my custom language (brainf\*\* based, interpreter [here](https://github.com/ebomberger23/braineasy-interpreter)):
```
#123#[->+>+<<]>++<,[[-<+<+>>]<[->>>..<.<<]<[->>>.<<<]!]>>.<.
```
You have to hardcode the program input into the interpreter because i'm lazy.
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E), ~~5~~ 3 bytes
```
F¯)
```
[Try it online!](https://tio.run/nexus/05ab1e#@@8WcWiHZu3//0YA "05AB1E – TIO Nexus")
This version is after he clarified that sets are okay.
```
F   # From 1 to input...
 ¯  # Push global array (default value is []).
  ) # Wrap stack to array.
```
---
Old version (that makes use of ø):
# [05AB1E](https://github.com/Adriandmen/05AB1E), ~~5~~ 4 bytes
```
FX¸)
```
[Try it online!](https://tio.run/nexus/05ab1e#@@8WcWiHZu3//0YA "05AB1E – TIO Nexus")
Where `1` is equivalent to `ø`.
```
F    # From 1 to input...
 X   # Push value in register X (default is 1).
  ¸  # Wrap pushed value into an array.
   ) # Wrap whole stack into an array.
     # Implicit loop end (-1 byte).
     # Implicit return.
```
[Answer]
# [dc](https://www.gnu.org/software/bc/manual/dc-1.05/html_mono/dc.html), 33 bytes
```
[[{}]n1-d0<m]sr[[{]nd0<r[}]n]dsmx
```
[Try it online!](https://tio.run/##S0n@b/8/Orq6NjbPUDfFwCY3trgIyI3NA7KLooGisSnFuRX//xsDAA "dc – Try It Online")
Not as clever as the other dc answer, but rather shorter
]