Set-theoretic construction of natural numbers

In order to train myself to use the Ruby langage, I undertook to implement the set-theoretic construction of the natural numbers: \[0 = \{\varnothing\}, \quad 1=0 \cup \{0\}= \{\varnothing, \{\varnothing\}\}, \quad 2=1\cup\{1\}=\{\varnothing, \{\varnothing\}, \{\varnothing, \{\varnothing\}\}\}, \quad ...\]

To define \(0\) we can use \(\varnothing\) as a character or as a symbol:

>> puts ["Ø"].to_set.inspect
#<Set: {"Ø"}>
>> puts [:Ø].to_set.inspect
#<Set: {:Ø}>

Now, we define a recursive function calculating the set representation of an integer:

>> def set_representation(n) 
  n == 0 ? ["Ø"].to_set : set_representation(n-1).tap {|x| break x.union([x].to_set)} 
end

See this stackoverflow thread about the usage of tap to map a single object to a function.

The set_representation function works fine:

>> puts set_representation(1).inspect
#<Set: {"Ø", #<Set: {"Ø"}>}>
>> puts set_representation(2).inspect
#<Set: {"Ø", #<Set: {"Ø"}>, #<Set: {"Ø", #<Set: {"Ø"}>}>}>

However, another way consists in using a hash, as I learnt by reading Algorithmic Fun with Ruby Hashes. The code is similar to the one of set_representation, except that the first value must be initialized outside the body:

>> set_hash ||= Hash.new do |hash,n|
  hash[n] =  hash[n-1].tap {|x| break x.union([x].to_set)}
end
>> # initialization:
>> set_hash[0] = ["Ø"].to_set

Results, as expected, are the same:

>> puts set_hash[2].inspect
#<Set: {"Ø", #<Set: {"Ø"}>, #<Set: {"Ø", #<Set: {"Ø"}>}>}>

And the computation times are comparable:

>> # time consumed by the function:
>> start = Time.now; set_representation(15); finish = Time.now
>> puts finish - start
0.083684302
>> # time consumed by the hash:
>> start = Time.now; set_hash[15]; finish = Time.now
>> puts finish - start
0.082218561

But look what happens if I re-run the same code:

>> # time consumed by the function:
>> start = Time.now; set_representation(15); finish = Time.now
>> puts finish - start
0.080877005
>> # time consumed by the hash:
>> start = Time.now; set_hash[15]; finish = Time.now
>> puts finish - start
8.97e-07

Now, the time consumed by set_hash[15] is almost instantaneous! This is due to memoization (see Algorithmic Fun with Ruby Hashes).

Displaying a set

My next goal was to get a better rendering of the sets. Indeed, it is hard to read something like :

>> puts set_hash[2].inspect
#<Set: {"Ø", #<Set: {"Ø"}>, #<Set: {"Ø", #<Set: {"Ø"}>}>}>

as compared to \[\{\varnothing, \{\varnothing\}, \{\varnothing, \{\varnothing\}\}\}\] isn’t it ? Then I defined a recursive hash:

>> display_hash ||= Hash.new do |hash,set|
  if set.inject(true) {|status, x| status and x.class==String}
    display_hash[set] = "{" + set.inject {|union, x| union + "," + x} + "}"
  else 
    set = set.to_a
    for i in 0 .. set.size-1
      if set[i].class == Set 
        set[i] = display_hash[Set.new(set[i])]
      end
    end
    display_hash[set] = display_hash[set.to_set] 
  end
end

The first line checks whether all elements of the set are some strings. If so, it returns the set as a character string with a comma separating the elements and some braces. Otherwise, the hash is calculated for each element of the set which are themselves some sets (the procedure assumes that the set to be displayed consists only of character strings and of sets of such sets). And it works as desired:

>> one = set_hash[1]
>> two = set_hash[2]
>> three = set_hash[3]
>> puts one.inspect # ugly 
#<Set: {"Ø", #<Set: {"Ø"}>}>
>> puts display_hash[one] # beautiful
{Ø,{Ø}}
>> puts two.inspect # ugly
#<Set: {"Ø", #<Set: {"Ø"}>, #<Set: {"Ø", #<Set: {"Ø"}>}>}>
>> puts display_hash[two] # beautiful
{Ø,{Ø},{Ø,{Ø}}}
>> puts three.inspect # ugly 
#<Set: {"Ø", #<Set: {"Ø"}>, #<Set: {"Ø", #<Set: {"Ø"}>}>, #<Set: {"Ø", #<Set: {"Ø"}>, #<Set: {"Ø", #<Set: {"Ø"}>}>}>}>
>> puts display_hash[three] # beautiful
{Ø,{Ø},{Ø,{Ø}},{Ø,{Ø},{Ø,{Ø}}}}

The memoization offered by the hash approach has a great advantage here. Take for example the case of \(2\): \[2 = \{\varnothing, \{\varnothing\}, \{\varnothing, \{\varnothing\}\}\} = \{\varnothing, \{\varnothing\}, 1\},\] and then, when the set representation of \(2\) is generated, the set representation of \(1\) is generated as well, and this one is memoized. For example we can see that the time consumed by set_hash[16] is almost instantaneous once set_hash[17] is calculated:

>> # time consumed by set_hash[17]:
>> start = Time.now; set_hash[17]; finish = Time.now
>> puts finish - start
0.243370526
>> # time consumed by set_hash[16]:
>> start = Time.now; set_hash[16]; finish = Time.now
>> puts finish - start
1.14e-06

Unordered pairs

Finally, I wanted to visualize the iterated unordered pairs of a set. That is, starting for example from the set \(A_1=\{a,b\}\), the set of its unordered pairs is \(A_2 = \{\{a\}, \{a,b\}, \{b\}\}\), then we form the set of unordered pairs of \(A_2\), and so on. A simple function does this job:

>> def pairs(s,n)
  while n > 0 do 
        b = s.to_a
        s = [].to_set
        for i in 0 .. b.size-1
            for j in i .. b.size-1
                s.add([b[i],b[j]].to_set)
            end
        end
        n = n - 1
    end
    return s.to_set
end

And the rendering hash works fine:

>> p1 = pairs(["a","b"].to_set, 1)
>> puts display_hash[p1]
{{a},{a,b},{b}}
>> p2 = pairs(["a","b"].to_set, 2)
>> puts display_hash[p2]
{{{a}},{{a},{a,b}},{{a},{b}},{{a,b}},{{a,b},{b}},{{b}}}

We can also list the iterated pairs using map:

>> p3 = pairs(["a","b"].to_set, 3)
>> puts p3.map {|x| display_hash[x]}
{{{a}}}
{{{a}},{{a},{a,b}}}
{{{a}},{{a},{b}}}
{{{a}},{{a,b}}}
{{{a}},{{a,b},{b}}}
{{{a}},{{b}}}
{{{a},{a,b}}}
{{{a},{a,b}},{{a},{b}}}
{{{a},{a,b}},{{a,b}}}
{{{a},{a,b}},{{a,b},{b}}}
{{{a},{a,b}},{{b}}}
{{{a},{b}}}
{{{a},{b}},{{a,b}}}
{{{a},{b}},{{a,b},{b}}}
{{{a},{b}},{{b}}}
{{{a,b}}}
{{{a,b}},{{a,b},{b}}}
{{{a,b}},{{b}}}
{{{a,b},{b}}}
{{{a,b},{b}},{{b}}}
{{{b}}}

Now, maybe you still think the title is ridiculous. But I hope you believe Ruby is cool.