[Question]
  [
From Wikipedia [Set-theoretic definition of natural numbers](http://en.wikipedia.org/wiki/Set-theoretic_definition_of_natural_numbers)
> 
> The set N of natural numbers is defined as the smallest set containing
>  0 and closed under the successor function S defined by S(n) = n ∪ {n}.
> 
> 
> The first few numbers defined this way are 0 = {}, 1 = {0} = {{}}, 2 = {0,1} = {{},{{}}}, 3 = {0,1,2} = {{},{{}},{{},{{}}}}.
> 
> 
> 
Using this definition of natural numbers count the length of a string.
**Input** a string of characters from a-zA-Z of any length
**Output** the length of the string in set notation without separators
**Examples** 
**Input** Empty string
**Output** {}
**Input** a
**Output** {{}}
**Input** aaaa
**Output** {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}
For readability output for 'aaaa' with separators is
```
{ 
    {} 
    {{}} 
    {{} {{}} } 
    {{}   {{}}   {{} {{} } }   }
}
```
Conditions
1. No digits 0 to 9 to appear in the code;
2. No use of character code conversion to generate numbers;
3. No use of +-\*/ for arithmetic calculations including increment and decrement;
4. No mathematical operations other than Boolean Logic;
5. Input string does not count in determining byte length;
**Winner** Shortest code length in bytes.
As this is my first question I hope I have made it clear and rigorous enough. Friendly advice accepted. 
  
[Answer]
# Haskell function, ~~35~~ 34 characters
```
f[]="{}";f(_:x)='{':f x++tail(f x)
```
# Haskell program with hardcoded input, ~~48 or 49~~ 47 or 48 characters
```
 f[]="{}";f(_:x)='{':f x++tail(f x);main=print$f"aaaa"
```
(47 characters if you don't mind extra quotes around the output; if you do, use `putStr` instead of `print` for a total of 48 characters)
# Haskell program, ~~51~~ 50 characters
```
f[]="{}";f(_:x)='{':f x++tail(f x);main=interact f
```
[Answer]
## GolfScript (18 17 bytes)
```
'{'\{;.'}'++}/'}'
```
Takes input on the stack (so if run as a program, via stdin). Leaves the output as two strings on the stack (so if run as a program, the correct output is sent to stdout).
To leave a single string on the stack, either append `+` to concat, or use the alternative
```
'{}'\{;.);\'}'++}/
```
### Dissection
```
# Stack: input-str
'{'\
# Stack: <0< input-str  where <0< means the string representing 0 without its final }
# Loop over each character of the input string
{
    # Stack: <n< char
    # Discard the input character
    ;
    # Concatenate two copies of <n< and a }
    .'}'++
}/
# Push the final } to the stack
'}'
```
Alternative:
```
# Stack: input-str
'{}'\
# Stack: <0> input-str  (where <0> means the string representing 0)
# Loop over each character of the input string
{
    # Stack: <n> char
    # Discard the input character
    ;
    # Duplicate <n> and remove the final '}'
    .);
    # Stack manipulations
    \'}'
    # Stack: <n>-less-final-'}' <n> '}'
    # Concatenate the three strings to get <n+1>
    ++
}/
```
### Impact of the restrictions
If decrement were allowed, it would permit the 15-byte solution
```
'{}'\{;..,(/*}/
```
[Answer]
# Python 3 - 64
```
o=['{}']
for a in input():o+=['{'+''.join(o)+'}']
print(o.pop())
```
If inlining the input is allowed:
# Python 2 - 54
```
o=['{}']
for a in'whatever':o+=['{'+''.join(o)+'}']
print o.pop()
```
[Answer]
# Javascript 70 (chars)
```
s='';c=prompt().split('');while(c.pop()){s+='{'+s+'}'}alert('{'+s+'}')
```
This was my effort before setting the question. I would assume someone with more knowledge of Javascript than me can probably beat it.
Thank you Jan Dvorak and Peter Taylor for further reductions
# now 62
```
s='{';c=prompt().split('');while(c.pop())s+=s+'}';alert(s+'}')
```
# and now 61
```
s='{';for(c=prompt().split('');c.pop();)s+=s+'}';alert(s+'}')
```
**Explanation of Original Code**
set s to be empty
input string into c and split into an array
while it is possible to pop() a character from c do so and reset s=s{s} as successor
output current s but need to surround with set brackets.
[Answer]
# J - ~~22~~ 20 char
```
'{','}' '{'&(,,~)~#
```
How this can be derived:
```
   #'123'                      NB. string length
3
   'Left' (,,~) 'Right'        NB. dyad to concat L,R,R
LeftRightRight
   '{' (,,~) '}'               NB. using braces
{}}
   '{'&(,,~) '}'               NB. bind left argument, now it's a monad
{}}
   '{'&(,,~) '{'&(,,~) '}'     NB. twice
{{}}{}}
   '{'&(,,~)^:2 '}'            NB. ^: is monad functional power
{{}}{}}
   '{'&(,,~)^:3 '}'            NB. any integer
{{{}}{}}{{}}{}}
   3 '{'&(,,~) '}'             NB. convenient feature of dyadic &
{{{}}{}}{{}}{}}
   '}' '{'&(,,~)~ 3            NB. swap argument order
{{{}}{}}{{}}{}}
   '}' '{'&(,,~)~ #'123'       NB. using string length
{{{}}{}}{{}}{}}
   '{', '}' '{'&(,,~)~ #'123'  NB. add final brace
{{{{}}{}}{{}}{}}
   ('{','}' '{'&(,,~)~#) '123' NB. works as a verb
{{{{}}{}}{{}}{}}
```
Alternatively, this can be written `'{','{'&(,,~)&'}'@#`, meaning the same thing.
Usage:
```
   '{','}' '{'&(,,~)~# 'aaaa'
{{{{{}}{}}{{}}{}}{{{}}{}}{{}}{}}
   f =: '{','}' '{'&(,,~)~#  NB. can be assigned to a function
   f 'VeryBig'
{{{{{{{{}}{}}{{}}{}}{{{}}{}}{{}}{}}{{{{}}{}}{{}}{}}{{{}}{}}{{}}{}}{{{{{}}{}}{{}}{}}{{{}}{}}{{}}{}}{{{{}}{}}{{}}{}}{{{}}{}}{{}}{}}{{{{{{}}{}}{{}}{}}{{{}}{}}{{}}{}}{{{{}}{}}{{}}{}}{{{}}{}}{{}}{}}{{{{{}}{}}{{}}{}}{{{}}{}}{{}}{}}{{{{}}{}}{{}}{}}{{{}}{}}{{}}{}}
```
[Answer]
**Haskell - 35 charactes**
```
g[]="{}";g(_:x)=(init.g)x++g x++"}"
```
Solution is influenced by Jan Dvorak's one, but without reversing the order.
[Answer]
# Scala, 64 characters
```
def f(s:String):String=s"{${s.tails.toSeq.tail.map(f)mkString}}"
```
Note the dual roles that both the braces and `s` play in this code.
EDIT: removed a digit
[Answer]
# Python 3 (44)
```
s='{'
for _ in input():s+=s+'}'
print(s+'}')
```
At each step, `s` is the string representing the set with the final `}` removed. We create the set representing `n+1` from the set representing `n` via the relationship f(n+1) = f(n) ∪ {f(n)}. To implement the union with strings, we append the string for {f(n)}, which is exactly `s` but with the final `}` returned, and neglect to include the final `}` in the result. Finally, we add back a final `'}'` before printing.
If I may hardcode the string, the character count cuts down to 35 character, switching to Python 2 to save parantheses on the `print`.
```
s='{'
for _ in'string':s+=s+'}'
print s+'}'
```
There might be a way to save the space after the `print` by doing something like `print'{'+s` with a reversed `s`, but this messes up with the `+=` appending on the right.
[Answer]
# gs2, 12 bytes
```
7b 7d 05 27 a0 42 30 30 e4 43 2e 32
```
mnemonics:
```
"{}"
right-uncons @0 swap + + b5
rot length times
```
[Answer]
# Mathematica, 115 characters
```
StringReplace[ToString@Function[s,NestWhile[#~Append~#&,{},(s~Read~Character//StringQ)&]]@StringToStream@"test",", "->""]
```
The complete code as shown has 121 characters, but 6 of them are used for the input string (`"test"`) which, according to the rules, doesn't count.
Without the requirement that there are no delimiters, the code length could be reduced further by 24 characters; without explicit conversion to string then another 9 characters could be removed.
[Answer]
# Ruby, 27, kind of cheating
```
a=*a
gets.chars{a=*a,a}
p a
```
Questionable things:
1. Output looks like `[[], [[]], [[], [[]]], [[], [[]], [[], [[]]]]]`
2. Most methods of input to ruby will include a trailing newline, which inflates the count by 1.
[Answer]
# Pure Bash, 54
```
f()([ $@ ]&&(a=`f ${@%?}`
echo $a{$a}))
echo {`f $@`}
```
Output:
```
$ ./strlenset.sh
{}
$ ./strlenset.sh a
{{}}
$ ./strlenset.sh aa
{{}{{}}}
$ ./strlenset.sh aaa
{{}{{}}{{}{{}}}}
$ ./strlenset.sh aaaa
{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}
$ 
```
[Answer]
# Julia 43
```
f(z)="{"foldl((x,y)->"$x{$x}","",{z...})"}"
```
The construct **{z...}** expands the string z into an array. Fold loops over all elements of the array ignoring the contents and instead building up from the empty string. The function **foldl** is available in Julia 0.30.
Sample Output
```
julia> f("")
"{}"
julia> f("aa")
"{{}{{}}}"
julia> f("aaaa")
"{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}"
julia> f("aaaaaa")
"{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}}"
```
[Answer]
# Haskell, 31 bytes
```
foldl(\s _->init s++s++"}")"{}"
```
[Answer]
# Mathematica, ~~45~~ ~~57~~ 48 bytes
```
"{"~~Fold[#~~"{"~~#~~"}"&,"",Characters@#]~~"}"&
```
---
A 36 bytes solution:
```
Fold[{##{##}}&@@#&,{},Characters@#]&
```
However, it uses some arithmetic calculations.
[Answer]
# Delphi XE3 (264)
Ok I dont even come close to the other but it was fun to do :)  
Probably overthinking it. Going to see if there is a better way to do this.
### Golfed
```
uses System.SysUtils;var s,f:string;a:TArray<char>;b:TArray<string>;i,x:integer;begin readln(s);a:=s.ToCharArray;f:='{';setlength(b,Length(a));for I:=Low(a)to High(a) do begin s:='{';for x:=Low(b)to High(b)do s:=s+b[x];b[i]:=s+'}';f:=f+b[i];end;writeln(f+'}');end.
```
### Ungolfed
```
uses
  System.SysUtils;
var
  s,f:string;
  a:TArray<char>;
  b:TArray<string>;
  i,x:integer;
begin
    readln(s);
    a:=s.ToCharArray;
    f:='{';
    setlength(b,Length(a));
    for I:=Low(a)to High(a) do
    begin
      s:='{';
      for x:=Low(b)to High(b)do
        s:=s+b[x];
      b[i]:=s+'}';
      f:=f+b[i];
    end;
    writeln(f+'}');
end.
```
### Testing results
Tested strings with length 0..10
```
{}
{{} }
{{} {{}} }
{{} {{}} {{}{{}}} }
{{} {{}} {{}{{}}} {{}{{}}{{}{{}}}} }
{{} {{}} {{}{{}}} {{}{{}}{{}{{}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}} }
{{} {{}} {{}{{}}} {{}{{}}{{}{{}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}} }
{{} {{}} {{}{{}}} {{}{{}}{{}{{}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}} }
{{} {{}} {{}{{}}} {{}{{}}{{}{{}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}}} }
{{} {{}} {{}{{}}} {{}{{}}{{}{{}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}}}} }
{{} {{}} {{}{{}}} {{}{{}}{{}{{}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}}}}} }
```
[Answer]
**Perl 5: 33 characters**
It's not quite clear which characters I should count as part of the solution. Probably not the `echo ... |` part because that's just used to feed a line in to stdin. Probably not the name of the perl binary, because you could rename that whatever you wanted.
So I've counted the command-line switches passed to perl, the quote marks wrapped around the Perl code, and the Perl code itself.
```
#                                1         2         3
#                     12  3456789012345678901234567890123
$ echo "aaaa" | perl -ple'$s.="{$s}"while s/.//;$_="{$s}"'
```
Also, [related](https://metacpan.org/pod/Number%3a%3aNatural%3a%3aSetTheory).
[Answer]
# Perl 6: 37 characters
```
say ({"\{@_.join()\}"}...*)["(input string)".chars]
```
or from STDIN:
```
say ({"\{@_.join()\}"}...*)[get.chars]
```
`{"\{@_.join()\}"}...*` makes a lazy list of the set forms of the natural numbers, and we just grab the one we need with `get.chars`.
The lazy list might be more readably written:
```
-> *@prev { '{'~ @prev.join ~'}' } ... *
```
Which reads pretty similarly to the definition.
[Answer]
## Dart: 85 characters
```
a(p,i)=>(--i).isNegative?p:a("$p{$p}",i);
main(s){print("{${a("",s.first.length)}}");}
```
(with extra newline for readability).
The requirement of not using "0" really bites, otherwise `.first` would be `[0]` and `(..).isNegative` would be `..<0`.
[Answer]
# Pyth, 13 bytes
```
+u++GG\}z\{\}
```
This is the golfed Pyth equivalent of @xnor's Python answer. Note that Pyth is newer than this question, so this answer is not eligible to win this challenge.
[Demonstration.](https://pyth.herokuapp.com/?code=%2Bu%2B%2BGG%5C%7Dz%5C%7B%5C%7D&input=aaaa&debug=0)
[Answer]
# Javascript, ~~171~~ ~~149~~ ~~147~~ 142 bytes
(Will likely be golfed further later)
```
n=prompt().split("");for(a=[];n.pop();)a.push(a.slice());alert(JSON.stringify({a:a})[R="replace"](/[^\[\]]/g,"")[R](/\[/g,"{")[R](/\]/g,"}"));
```
]