Does this Set Represent a Natural Number?

Question

In set theory, the natural numbers \$\mathbb{N} = \{0, 1, 2, 3, ...\}\$ are usually encoded as pure sets, 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 way¹:

• Zero is the empty set: \$ Set(0) = \{\} \$
• For a number \$n > 0\$: \$ Set(n) = Set(n-1) \cup \{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 (Output the set encoding of a given natural number.)
1 See https://en.wikipedia.org/wiki/Set-theoretic_definition_of_natural_numbers}

Answer 1

JavaScript (Node.js), 53 48 44 bytes

f=a=>(a=eval(a)).every(e=>a[e.length]&&f(e))

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 2

Python 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!

Answer 3

Wolfram Language (Mathematica), 60 59 bytes

E!=(If[Sort@#===Range[t=Tr[1^#]]-1,t,E]&//@ToExpression@#)&

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 4

Brachylog (v2), 9 bytes

↰ᵐo.t~k|Ė

Try it online!

As usual for a 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 5

K (ngn/k), 26 24 27 bytes

~^{$[#(!#x)^o'x;0N;#x]}@`j@

Try it online!

input is a json string parsed by `j@ (syntax specific to ngn/k)

{ } is a recursive function with argument x. it returns the natural number represented by the set x, or null (0N) if it doesn't represent one.

$[ ; ; ] is if-then-else. 0 is falsey, other integers are truthy

!#x the integers from 0 (inclusive) to the length of x (exclusive)

^ without

o'x recursion (o) on each (') element of x

# length

^ is null?

~ not

@ acts as a dummy last verb so that ~ and ^ get composed with { } instead of being applied to it

Answer 6

Jelly, 10 bytes

ẈṢ‘⁼Jȧ@ßƇƑ

Try it online!

Answer 7

Japt, 9 bytes

Port of Neil's JS solution. Please upvote that if you're upvoting this.

e@Ê>XÊ©ßX

Try it or run all test cases

              :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 8

Jelly, 8 bytes

߀Ṣ
ÇṖƤƑ

Since the input has to be a string, this submission is only valid as a full program.

Try it online! or verify all test cases

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 9

Red, 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!

Similar to Leaky Nun's Python 3 answer

Answer 10

Jelly, 7 bytes

Ẉ<La߀Ạ

This is a port of Leaky Nun's Python answer.

Since the input has to be a string, this submission is only valid as a full program.

Try it online! or verify all test cases

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 11

Wolfram Language (Mathematica), 52 bytes

If[Max[#0/@#]<(l=2Length@#),l]&@*ToExpression/*EvenQ

Try it online!