[Question]
  [
In set theory, the natural numbers \$\mathbb{N} = \{0, 1, 2, 3, ...\}\$ are usually encoded as [pure sets](https://en.wikipedia.org/wiki/Hereditary_set), that is sets which only contain the empty set or other sets that are pure. However, not all pure sets represent natural numbers. This challenge is about deciding whether a given pure set represents an encoding of natural number or not.
The encoding of natural numbers works in the following way1:
* Zero is the empty set: \$ \text{Set}(0) = \{\} \$
* For a number \$n > 0\$: \$ \text{Set}(n) = \text{Set}(n-1) \cup \{\text{Set}(n-1)\}\$
Thus, the encodings of the first few natural numbers are
* \$ 0 \leadsto \{\}\$
* \$ 1 \leadsto \{0\} \leadsto \{\{\}\}\$
* \$ 2 \leadsto \{0,1\} \leadsto \{\{\},\{\{\}\}\}\$
* \$ 3 \leadsto \{0,1,2\} \leadsto \{\{\},\{\{\}\},\{\{\},\{\{\}\}\}\}\$
* \$ 4 \leadsto \{0,1,2,3\} \leadsto \{\{\},\{\{\}\},\{\{\},\{\{\}\}\},\{\{\},\{\{\}\},\{\{\},\{\{\}\}\}\}\}\$
## The Task
* Given a string representing a pure set, determine whether this set encodes a natural number according to the above construction.
* Note, however, that the elements of a set are not ordered, so \$\{\{\},\{\{\}\},\{\{\},\{\{\}\}\}\}\$ is not the only valid representation of \$3\$ as e.g. \$\{\{\{\}\},\{\},\{\{\{\}\},\{\}\}\}\$ represents the same set.
* You may use `[]`, `()` or `<>` instead of `{}`.
* You may assume the sets are given without the `,` as separator.
* You can assume there won't be any duplicate elements in the input, e.g. `{{},{}}` is not a valid input, and that the input is well-formed, e.g. no `{{},`, `{,{}}` or similar.
## Test Cases
True:
```
{}
{{}}
{{},{{}}}
{{{}},{}}
{{},{{}},{{},{{}}}}
{{{},{{}}},{},{{}}}
{{{{}},{}},{{}},{}}
{{},{{}},{{},{{}}},{{},{{}},{{},{{}}}}}
{{{{{}},{}},{{}},{}},{{}},{},{{},{{}}}}
{{},{{}},{{},{{}},{{},{{}}},{{},{{}},{{},{{}}}}},{{{}},{}},{{},{{}},{{},{{}}}}}
{{{{{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}}
```
False:
```
{{{}}}
{{{{}}}}
{{{{}},{}}}
{{},{{}},{{{}}}}
{{{},{{}}},{{}}}
{{{{{}}},{}},{{}},{}}
{{},{{}},{{},{{}}},{{},{{}},{{{}}}}}
{{{{{}},{}},{{{}}},{}},{{}},{},{{},{{}}}}
{{{{{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{{}},{}},{{}},{}},{{{}},{}},{{}}},{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}}
```
---
Related: [Natural Construction](https://codegolf.stackexchange.com/q/95035/56433) (Output the set encoding of a given natural number.)  
1 See <https://en.wikipedia.org/wiki/Set-theoretic_definition_of_natural_numbers> 
  
[Answer]
# [JavaScript (Node.js)](https://nodejs.org), ~~53~~ ~~48~~ 44 bytes
```
f=a=>(a=eval(a)).every(e=>a[e.length]&&f(e))
```
[Try it online!](https://tio.run/##7VO9DoIwGNx5EGiTyhuUxEEnJ3@mytBgQQ1pDRASn76WiEZqaUt0cHBr7r7eXb7cd6YtrbPqdGlmXByYlDmmOAEUs5aWgEIYs5ZVV8BwQgmLS8aL5piGYQ4YhDITvBalgkUBIrJd7xZpBIPgFc4VoUD4BpJ0BEYdZeYUgez/0FNgTOHOIrtPb4QmOSJDiDF93eDxcOXXDBzmaGDknc0YzwT5jn1b7mfjdRsdrDTac7KcrzbmwyC2pvaSjh74VJ1Ye/hh0z1rrhs5D/VfQ21uQgflDQ "JavaScript (Node.js) – Try It Online") Test cases mostly shamelessly stolen from @Arnauld's answer. Explanation: If a set represents a natural number, then the natural number it represents must be equal to the size of the set, and (given that the elements are guaranteed distinct) the elements must be the representations of the natural numbers less than it, and these must therefore have shorter lengths. This is trivially true of the empty set of course. Edit: Saved 5 bytes thanks to @Arnauld. Saved 4 bytes thanks to @Cowsquack.
[Answer]
# [Python 3](https://docs.python.org/3/), ~~69~~ ~~58~~ 44 bytes
11 bytes thanks to Erik the Outgolfer.
14 bytes thanks to Mr. Xcoder.
```
f=lambda s:all(len(e)<len(s)*f(e)for e in s)
```
[Try it online!](https://tio.run/##7VSxDsIgFNz5CkYwbG5N@yXIgAqxCdKmj8Wvx2JpI4haEwcHF7g83t0jeZfrL@7U2a33ujHyvD9KDJU0hhhliaJ1uIBu9Ih1N2CFW4uBeqfAHSQoaPgOccEQ52I6WUA3GCpJlS3P8T32JqSZ9YrOCoqR/UCPIJud0d9JJ7rPJheHl0pr274t97vfm9ySGCBdU8E0/H7nn3mmbJhcJrfrf8NZ31otgVDIDgjZsQRH1Q@tdUSP6UL9FQ "Python 3 – Try It Online")
[Answer]
# [Wolfram Language (Mathematica)](https://www.wolfram.com/wolframscript/), ~~60~~ 59 bytes
```
E!=(If[Sort@#===Range[t=Tr[1^#]]-1,t,E]&//@ToExpression@#)&
```
[Try it online!](https://tio.run/##y00syUjNTSzJTE78H1CUmVcS/d9V0VbDMy06OL@oxEHZ1tY2KDEvPTW6xDakKNowTjk2VtdQp0THNVZNX98hJN@1oqAotbg4Mz/PQVlT7b@CvoNCtYJSda2SDpCsrtUB4looB8jSqUZwIFJoCmqVFGpj/wMA "Wolfram Language (Mathematica) – Try It Online")
The core of this solution is the function
```
If[Sort@#===Range[t=Tr[1^#]]-1,t,E]&
```
which converts a list of the form `{0,1,2,...,n-1}` in any order into the output `n` (in particular, it converts `{}` to `0`), and converts anything else into the real number `E`.
Call this function `f`. Given an input such as `"{{{}},{}}"`, we do the following:
1. Convert the string into a Mathematica expression.
2. Apply `f` at every level, getting `f[{f[{f[{}]}], f[{}]}]`.
3. Evaluating all the `f`'s will produce a natural number for an input representing it. For example, `f[{f[{f[{}]}], f[{}]}]` = `f[{f[{0}], 0}]` = `f[{1, 0}]` = `2`. Anything else will produce `E`.
4. We test if the result is a natural number by checking if it's not `E`.
[Answer]
# [Brachylog](https://github.com/JCumin/Brachylog) (v2), 9 bytes
```
↰ᵐo.t~k|Ė
```
[Try it online!](https://tio.run/##SypKTM6ozMlPN/r//1HbhodbJ@TrldRl1xyZ9v9/dHR0bKwOkABhECs2FgA "Brachylog – Try It Online")
As usual for a [decision-problem](/questions/tagged/decision-problem "show questions tagged 'decision-problem'"), this is a full program. Input from standard input, using square brackets. Output to standard output as `true.` versus `false.`.
## Explanation
Although I said above that this is a full program, it's actually more interesting than that; it's *both* a full program and a function. When used as a full program, it prints `true.` if the set is a natural number, or `false.` if it isn't. When used as a function, it "normalizes" a natural number (i.e. normalizes all its elements and sorts them into order by value; this program uses lists internally, not sets), or "throws an exception" (actually a failure, as this is Prolog) if the input isn't a natural number.
The full program behaviour is easy enough to explain: it's purely implicit in Brachylog's treatment of full programs that don't contain I/O instructions. The behaviour in question is "run the function, taking its input from standard input, and asserting that its output matches the description given by the first command-line argument; if the assertion fails or the program throws an exception, print `false.`, otherwise print `true.`". In this case, the command-line argument is missing (i.e. "anything goes"), so the exception/no-exception behaviour of the function gives the output.
As for the function behaviour:
```
↰ᵐo.t~k|Ė
↰ᵐ          Map a recursive call to this function over the list
  o         Sort the list
   .   |    Assert that the following operation need not change the list:
    t         Take the last (i.e. greatest) element of the list
     ~k       Append an arbitrary element to the resulting list
   .   |    Output the unchanged list
       |    Exception handler: if the above threw an exception,
        Ė     Assert that the input is empty, and output an empty list
```
A natural number is defined as containing two parts: the elements of the natural number below, unioned with the number itself. Thus, all its elements are also natural numbers. We can recognise a natural number by a) verifying that all its elements are natural numbers, b) verifying that the set's largest element is identical to the set without its largest element.
When we're using lists rather than sets (thus the square brackets), we need to put them into a consistent order for equality comparisons to work (in this case, sorted by "value"). Brachylog's default sort order will sort a prefix of a list before the list itself, which conveniently means that it'll sort natural numbers by numerical value. So we can just recursively sort all our numbers to get them into a consistent order. In fact, via the function we're defining recursively, we can achieve both results at the same time: recursively sorting the number's elements, and verifying that it's a natural number.
The function thus has four main parts. `↰ᵐ` is the recursive call, ensuring that each element is a natural number, and converting it each element to a normalized form. `o` the normalizes the number itself (its elements are already normalized, so all we have to do is to sort it). Then `.t~k|` ensures we have the structure we want by checking that the largest element and other elements are the same. An empty list (i.e. 0) doesn't have a last element, so will get an assertion failure with `t`; the `|Ė` handles this case, via giving an explicit fallback in the case where the input list is empty.
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 8 bytes
```
ß€Ṣ
ÇṖƤƑ
```
Since the input has to be a string, this submission is only valid as a full program.
[Try it online!](https://tio.run/##y0rNyan8///w/EdNax7uXMR1uP3hzmnHlhyb@P///2goiI3VAWMEA5sQscqobdygdR4A "Jelly – Try It Online") or [verify all test cases](https://tio.run/##y0rNyan8///w/EdNax7uXMR1uP3hzmnHlhyb@P9wO1AIiBTc///X0OBSUIiO1QGR0bEwWgfEhnJAomgyOnAlcDVQHWhaYXrxG6KDxVy4CRhGQBkYbkAzgpDxKCbjth2rA7AJEauM2sYNXudxaepowFIQWoJAjzKsSSkaNRWQmpJwJSN0ozAT82iso6kjIco1AQ "Jelly – Try It Online")
### How it works
```
ß€Ṣ   Helper link. Argument: A (array)
ß€    Recursively map the helper link over A.
  Ṣ   Sort the result.
```
This yields a canonical representation of the input, consisting solely of sorted arrays.
```
ÇṖƤƑ  Main link. Argument: A (array)
Ç     Call the helper link to canonicalize the array.
   Ƒ  Fixed; call the link to the left and test if it returns its argument unchanged.
 ṖƤ       Pop prefix; for each non-empty prefix of the result, remove its last element.
```
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 7 bytes
```
Ẉ<Laß€Ạ
```
This is a port of [Leaky Nun's Python answer](https://codegolf.stackexchange.com/a/177874/12012).
Since the input has to be a string, this submission is only valid as a full program.
[Try it online!](https://tio.run/##y0rNyan8///hrg4bn8TD8x81rXm4a8H///@joSA2VgeMEQxsQsQqo7Zxg9Z5AA "Jelly – Try It Online") or [verify all test cases](https://tio.run/##y0rNyan8///hrg4bn8TD8x81rXm4a8H/w@1ABhApuP//r6HBpaAQHasDIqNjYbQOiA3lgETRZHTgSuBqoDrQtML04jdEB4u5cBMwjIAyMNyAZgQh41FMxm07VgdgEyJWGbWNG7zO49LU0YClILQEgR5lWJNSNGoqIDUl4UpG6EZhJubRWEdTR0KUawIA "Jelly – Try It Online")
### How it works
```
Ẉ<Laß€Ạ  Main link. Argument: A (array)
Ẉ        Width; compute the length of A's elements.
  L      Yield the length of A.
 <       Compare them, yielding an array of Booleans.
    ß€   Recursively map the main link over A.
   a     Take the logical AND of the Booleans and the results of the map.
      Ạ  All; yield 1 if and only if all ANDs yielded 1.
```
[Answer]
# [Wolfram Language (Mathematica)](https://www.wolfram.com/wolframscript/), ~~36~~ 40 bytes
```
(Sort//@#//.{a__,{a__}}:>{a})!={}!={{}}&
```
[Try it online!](https://tio.run/##y00syUjNTSzJTE78n2b7XyM4v6hEX99BWV9frzoxPl4HRNTWWtlVJ9ZqKtpW1wJxdW2t2v/A0szUEoeAosy8kmhlXbs0B@VYtbrg5MS8umqu6lodLpAqMKkDYoGZIBEUUR24NFQeqhZFE0wXPu06WEyE6sbQDmWg2Y2mnZDRKObishmr5diEiFVGbeMGr/O4IMkFngJQ0wJqjGFJP9XI0U9a8sGedtCNQU@5o5GNpo5Ys7hq/wMA "Wolfram Language (Mathematica) – Try It Online")
[Answer]
# [K (ngn/k)](https://codeberg.org/ngn/k), ~~26~~ ~~24~~ 27 bytes
```
{{o'!x}[#x]~{x@<x:o'x}x}`j?
```
[Try it online!](https://ngn.bitbucket.io/k#eJy1lMsKgzAURPf5CmsLtpBFu00K7X+EgN0IfYCgLiIhfnu1akx84CO3rkQuJ+Nk7kREyjjYCcX2ghdS3K+CxIFQQoWvG0IZkQeWFwmJPEHD+E2PYfR4fqigOU1OXKGM+Yz7HuRDL/yHZRwU3GFxhYZia2zJxHCSe2qxlu12gKG2xmEQOzps4wIGsWPSBDziy/KjDLV9ue3LFr+n1M7IxpaK4V9V2JTUakcFj32aGfNRiomvhwGgNdEcdqXWxP6wC7Qh2vksryzdls4lAYPrmQp77m0ZDFtjdfjce8ZSa6QfEtv2F0jZDE0Y2dmVPTNQ2wXWsWwqLHAn2MsBAW0qAbATjJJZ0QnriP8phPK+viWXHTQ=)
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 10 bytes
```
ẈṢ‘⁼Jȧ@ßƇƑ
```
[Try it online!](https://tio.run/##y0rNyan8///hro6HOxc9apjxqHGP14nlDofnH2s/NvH////RUBAbqwPGCAY2IWKVUdu4Qes8AA "Jelly – Try It Online")
[Answer]
# [Japt](https://github.com/ETHproductions/japt), 9 bytes
Port of [Neil's JS solution](https://codegolf.stackexchange.com/a/177882/58974). Please upvote that if you're upvoting this.
```
e@Ê>XÊ©ßX
```
[Try it](https://ethproductions.github.io/japt/?v=1.4.6&code=ZUDKPljKqd9Y&input=W10=) or [run all test cases](https://tio.run/##y0osKPn/P9XhcJddxOGuQysPz4/4/z@aiyskKNSVKzqWKzo6FkzogBggFpDSQRbTgUtCZCFsHWQdUC06ePTqYDEOohddM4yBai@aZgIG66AYi8NerFZjEyJWGbWNG7TO4@Jyc/QJdoUkFuQUgBJTmEkmGinOSUoxWJMLuiFoCXU0gtHUER@7sVy6uUEA)
```
              :Implicit input of array U
e             :Does every element in U return true
 @            :When passed through the following function as X
  Ê           :Length of U
   >          :Greater than
    XÊ        :Length of X
      ©       :Logical AND with
       ßX     :A recursive call of the programme with X passed as the new value of U
```
[Answer]
# [Red](http://www.red-lang.org), 81 bytes
```
func[a][p: 1 foreach e to-block a[p: p *(pick[1 0](length? e)< length? a)* f e]p]
```
[Try it online!](https://tio.run/##3ZJBCoMwEEX3nmJwpUKhbqXQO3Q7zCKNkyqKBrHnT7Ui1TQaSheFrpL5mbwJ@b/j3Fw4RwpUZtS9kSgIdQYpqLZjIQtg6NvDtW5lBWI80ZBEupQVpnCkqObm1hdn4PgE817ECShg0mR0Vzb9UIRIYfAqkKxyVNbSIDi75ma7@yk6QRPJC7T5NmWFmRb3W5aYTfiCtz/1bbBd@o6/vf678fNXhHYwnAY7TdhOCjod/iwpuzlZ0TZS@8f2es01Dw "Red – Try It Online")
Similar to Leaky Nun's Python 3 answer
[Answer]
# [Wolfram Language (Mathematica)](https://www.wolfram.com/wolframscript/), 52 bytes
```
If[Max[#0/@#]<(l=2Length@#),l]&@*ToExpression/*EvenQ
```
[Try it online!](https://tio.run/##y00syUjNTSzJTE78n6Zgq/DfMy3aN7EiWtlA30E51kYjx9bIJzUvvSTDQVlTJydWzUErJN@1oqAotbg4Mz9PX8u1LDUv8H9AUWZeSbSygq6dQlq0cmysgpqCvoNCcAlQOD24ICezJFqpuparuroWTOiAGCAWkNJBFtOBS0JkIWwdZB1QLTp49OpgMQ6iF10zjIFqL5pmAgbroBiLw16sVmMTIlYZtY0btM6DpBJY1KOkAZS4wkw01UixTlKawZpg0A1BS6qjUYymjlizlGL/AwA "Wolfram Language (Mathematica) – Try It Online")
]