1919. Elementary Additions

In today’s environment, students rely on calculators and computers to perform simple arithmetic too much. Sadly, it is not uncommon to see university students who cannot do simple arithmetic without electronic aids. Professor Peano has had enough. He has decided to take the matter into his own hands and force his students to become proficient in the most basic arithmetic skill: addition of non-negative integers. Since the students do not have a good foundation in this skill, he decided to go back to the basics and represent non-negative integers with set theory.

The non-negative integers are represented by the following sets:

• 0 is represented by the empty set {}.

• For any number n > 0, n is represented by a set containing the representations of all non-negative integers smaller than n.

For example, the first 4 non-negative integers are represented by:

0 => {}

1 => {{}}

2 => {{},{{}}}

3 => {{},{{}},{{},{{}}}}

and so on. Notice that the cardinality (size) of the set is exactly the integer it represents. Although the elements of a set are generally unordered, Professor Peano requires that the elements of a set be ordered in increasing cardinality to make the assignments easier to grade. As an added advantage, Professor Peano is sure that there are no calculators or computer programs that can deal with numbers written in this notation.

Not surprisingly, many students cannot cope with this basic task and will fail the course if they do not get help soon. It is up to you, an enterprising computer science student, to help them. You have decided to write a computer program, codenamed Axiomatic Cheating Machine (ACM), to sell to the students and help them perform the additions to pass the course.