A Primer on Quotient Sets and Stepnumbers

Introduction

The following primer has been assembled from various notes I have collected written by Professor Antal E. Fekete on the subject of quotient sets, and stepnumbers — a new number system invented by Fekete in 1997.

My purpose in assembling this information is twofold:

  1. To whet the reader’s appetite for quotient sets and stepnumbers, two absolutely fascinating subjects that could easily slip by unnoticed;
  2. To serve as a primer for an interview with Prof. Fekete about these subjects.

From here, the interested reader is strongly encouraged to go directly to the source and delve into Fekete’s writings on quotient sets and stepnumbers (and other mathematics subjects) which can be found on his website.

I apologize to the reader and to Prof. Fekete for any injustices to his work that might arise from my liberal rearranging of his writings, and from taking passages out of context. Otherwise the words are his, with only ever-so-slight editing in a few places to help with continuity.   But again, the motivated reader is urged to consult the original material.

Quotient sets

Early in my academic career I [Fekete] became fascinated with what Nicolas Bourbaki has in the first book of his series Elements of Mathematics, first published in 1937, called quotient sets. In particular I was interested in the ‘weak’ duality between the theory of subsets and the theory of quotient sets.

It has been suggested that set theory ought to be supplanted by the quotient-set theory.

In spite of the great popularity of Bourbaki, the subject has failed to stimulate interest in the mathematical community, nor has the term ‘quotient set’ gained currency since its introduction well over half-a-century ago. Equivalent but misleading terms such as “partitions” preferred by set theorists and “block design” preferred by combinatorists still dominate the literature. Unified notation for the number of quotient sets and quotient set types is still wanting. Deplorable as the lack of uniform terminology and symbolism may be, even more serious is the fact that the theory of quotient set is the Cinderella of mathematics, especially of mathematics education. If textbooks and treatises mention it at all, the effort hardly goes beyond paying lip service. A comprehensive bibliography of the subject is still waiting to be compiled. Its classification shows great inconsistency, even confusion. Authors, among others, Gian Carlo Rota, switch allegiance between competing schools with different terminologies, symbolism, and conceptual outlook, making it difficult for the researcher to follow their output. Editors, referees, and reviewers of learned journals are often ignorant about the central importance of the subject. They tend to treat submissions trying to rectify the situation in an offhand fashion.

Yet a quotient set is one of the great unifying ideas in all mathematics.

  • The quotient set concepts cuts through various disciplines as no imposed structure on the underlying set is assumed.
  • Quotient sets, like subsets, are natural in the sense of not being subject to prior choices such as structures (as do most mathematical concepts in the vogue today, causing fragmentation of the discipline).
  • And, above all, set theory is not complete without an explicit recognition of a weak duality between the lattice of subsets and the lattice of quotient sets.
  • Furthermore, we have every reason to believe that, sooner or later, information technology will embrace the concept of quotient sets as a vehicle towards improved information efficiency.

In every day terms, and in practice, every classification of elements of X, e.g., classification according to size, shape, weight, color, taste, odor, etc., gives rise to a quotient set of X, namely the set of sizes, shapes, weights, colors, tastes, odors, etc.

In mathematical terms, a quotient set of a given set is, by definition, the set of all equivalence classes modulo a fixed equivalence relation on the given set.

A familiar example is one where the given set is ℕ, the set of natural numbers including zero, and the equivalence relation is “congruence (mod 2)”. The equivalence classes are the subsets of even and odd natural numbers, so that the quotient set has two elements: {even} and {odd}.

Quotient sets provide a powerful and universal method to build the number concept. (See: Maiming the Mind.) In mathematics, there have been four major upheavals during the evolution of the number concept. Each of them arose because of obstruction to the four inverse operations: subtraction, division, logarithm, and root extraction. The evolution of the number concept through the phases ℕ, ℤ, ℚ, ℝ, ℂ is hereby described through a uniform method: the construction of quotient sets.

  • ℕ is the set of natural numbers.
  • The quotient set ℤ of equivalence classes is the number system that contains positive and negative integers, and zero. (Integers)
  • The quotient set ℚ of equivalence classes is the number system that contains integers as well as fractions. (Rational numbers)
  • The quotient set ℝ of equivalence classes is the number system consisting of rational and irrational numbers. (Real numbers)
  • The quotient set ℂ of equivalence classes – that is, equivalent transformations of the plane – is the number system containing complex numbers.

Again, the method followed in each case above is a quotient set construction. The set of equivalence classes is called a quotient set; it is conceived as a way of “simplifying” a given set. It is akin to the simplification of a fraction via dividing out a common factor of the numerator and the denominator — explaining how quotient sets earn their name (“quotient” is Latin for the result of a division).

Another application of quotient sets is epistemology, that part of philosophy studying the nature and scope of knowledge. In all branches of science we have a hierarchy of concepts determined by generalization or specialization. This corresponds to the relation refinement and rarefaction of quotients sets. In other words, every branch of science is a quotient set the elements of which are objects (or phenomena), and rarefaction is generalization (and refinement is specialization).

From quotient sets to stepnumbers

I took early retirement as professor of mathematics and subsequently decided that I wanted to dedicate myself to the cause of mathematics education of the blind.

While working on the problem to include the quotient sets of the six-cell in order to augment Braille, I stumbled over a novel number system: that of the stepnumbers. These numbers can deputize for quotient sets in exactly the same way as binary numbers do for subsets. Stepnumbers can be used not only to count the number of quotient sets, but also to calculate their superimposition and amalgamation (lattice operations, dual concepts of the union and intersection of subsets under weak duality).

Since the stepnumber system calls for an inventory of infinitely many digits, the problem has arisen how to furnish it in the most efficient way. In searching for a solution I discovered new digits, the so-called rainbow digits obtained by coloring the decimal digits with the standard colors of the rainbow spectrum in the following order:

  1. black
  2. red
  3. brown
  4. orange
  5. yellow
  6. green
  7. viridian
  8. blue
  9. indigo
  10. violet

Further colors are derived from the standard ones by passing to their various shades.

It turns out that Bell numbers are intimately connected with the concept of a quotient set, and with stepnumbers. Stepnumber milestones are Bell numbers. And the Bell number bn+1 counts the number of stepnumbers of at most n digits.

The first b21 = 474,869,816,156,751 stepnumbers involving black and red decimal digits only will admit the writing of stepnumber expansions of very large numbers already. Apparently, there is no practical need to go to the brown color and beyond, at least for the time being.

The rainbow digits have a mnemotechnical significance: in no way do they tax human memory. Large stepnumbers can be coded in rainbow digits with the same ease as smaller ones can in decimal digits. And they can also be deciphered with the same ease.

The ‘politically correct’ name for converting stepnumbers into decimals is “ranking algorithm for set partitions”.

The proofs in STEPNUMBERS are heuristic. They involve counting non-zero entries in the rows of Sierpinski’s triangle (mod p) for the binomial coefficients, and for the Stirling numbers of the first and second kind. I leave the task of fully exploiting this method to a younger generation of mathematicians along with my strong suggestion that Sierpinski’s triangles have not yielded all their secrets yet.

Substance perishes, but form lives forever!

The binary number system was invented in 1697 by Gottfried Wiihelm Leibniz (1646-1716) who gave expression to his jubilation with his cry eureka: “One has created everything from nothing“, engraved on a medallion of his own design (see Frontispiece).

I invented the stepnumber system 300 years later, in 1997. The reader may forgive my own cry eureka: “Substance perishes, but form lives forever!“. It suggests that the significance of the stepnumber system eclipses that of the binary that epitomizes substance as opposed to form, the latter being the epitome of stepnumbers.

The significance of the binary number system was not really appreciated before the computer revolution. By this metric, the significance of the stepnumber system may not be recognized for a couple of centuries. The binary system, “the mother tongue of computing”, is far too entrenched. It may appear that the computer revolution has made the enthronement of the binary number system all but irrevocable.

Yet we ought to guard ourselves against making hasty predictions about the future. The binary number system owes its adaptability to three facts from physics.

  • The first is that there are two kinds of magnetic charge: North and South. It is this fact that makes erasable magnetic disks and tapes suitable for recording information in binary code for storage.
  • The second is that there are two possible states of a capacitor: uncharged and charged. It is this fact that makes transmitting information in binary code easy.
  • The third is that there are two possible states in regard to an electric circuit: open and closed. It is this fact that makes retrieving information in binary code possible.

However, with the advent of semiconductors, erasable etching of information on a laser disk, and quantum computers — in particular, the possibility of using the orbit structure of electrons in the atom for coding purposes — one can no longer be certain about the permanent hegemony of a black-and-white binary system. The full spectrum of colors is threatening to displace it. With further advances of technology codes using an unspecified number of digits are conceivable.

In this work we challenge the hegemony of the binary system and advocate the introduction of its dual, the stepnumber system utilizing infinitely many digits and variable positional values for them. These two stand out as the only natural number systems — natural in a sense that they do not depend on arbitrary choices such as a base.

The binary number system is the simplest in that it calls for the smallest number of digits. At the same time it is also most uneconomical: it takes the longest string of digits to write a number in binary form.

By contrast, the stepnumber system calls for infinitely many digits. It is also the most economical: it takes the shortest string of digits to write a number n, sufficiently large, in stepnumber form. It is most economical in a second sense as well. The next larger digit is not pressed into service until the full potential of the lower digits has been exhausted. Furthermore, after the new digit puts in an appearance, it is being used most sparingly.

The binary system may indeed become obsolete for most applications involving extremely large numbers which are not yet but may well become the staple of science in the future. Clearly, it is wasteful, inefficient, and uneconomic. We have to find the optimal number system employing more than two digits. It may appear that cultivators of mathematics have been tardy in preparing the stage for the next phase of the computer revolution. We don’t seem to have a clear idea how to go about increasing information efficiency and economy by increasing the base of a number system, or where to stop. Can we admit infinitely many digits without losing the advantage of positional value, which is the mainstay of the economy and efficiency of a number system? Clearly, a new idea is needed before we can make further headway with the problem of improving information efficiency by graduating to a more versatile number system.

The stepnumber system is the dual of the binary number system. It furnishes the missing number system at the far-end of the spectrum: the number system with base n, as n → ∞. The stepnumber system compares to the binary as color TV does to the black-and-white. We may assume that in the quantum computer of the future the fundamental unit of information will not be the bit of the binary system: the binary digits with their rigidly fixed positional value. It will probably be the new bit of the stepnumber system: the rainbow digits

0123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789

with their variable positional value.

The binary and the stepnumber systems are the only natural number systems in the sense that neither does depend on arbitrary choices such as that of the base number n. In fact, there exist natural isomorphisms, one peculiar to each.

  • The binary number system is naturally isomorphic to the graded lattice of finite subsets.
  • The stepnumber system to the graded lattice of finite quotient sets.

These natural isomorphisms reveal that both the binary numbers and the stepnumbers are in fact characteristic functions.

  • Binary numbers are characteristic functions of finite subsets.
  • Stepnumbers are characteristic functions of finite quotient sets.

This fact further reveals that the two number systems have a common genesis. It also indicates that the stepnumber system is a genuine piece of mathematics waiting to be discovered, even though the waiting has taken 300 years after the original discovery of Leibniz. In the opinion of the author quotient sets are still sadly neglected in mathematical education and in the epistemology of mathematics. This is perhaps the real reason for the unusual delay of three centuries between the two discoveries.

To repeat, there is a natural isomorphism between the binary number system and the graded lattice of finite subsets. In more details, consider ℕ = {1, 2, 3,…, n,…}, the set of natural numbers, and its subsets ℕn = {1, 2, 3,…, n}. ℕn form a lattice for every n = 1, 2, 3,… under inclusion. The union of these is a graded lattice with grading furnished by n, the number of digits. A binary number of at most n digits can be interpreted as a characteristic function of ℕn , provided that we add a sufficient number of 0 digits up front to make it a binary number of exactly n digits (which, of course, will not affect its value). This is a one-to-one correspondence between binary numbers and finite subsets. It can be extended to a lattice isomorphism preserving the union ∪ and the intersection ∩ as well as the inclusion ⊆ of subsets. It does not depend on arbitrary choices. In enumerating binary numbers we actually construct all finite subsets. Thus binary numbers can be used to count the number of subsets. The great utility of the binary number system is due mostly to this fact, which is not widely recognized. The binary number system owes its naturality to the existence of this natural isomorphism.

The stepnumbers form another number system that is natural in the sense that there is a natural isomorphism between the stepnumber system and the graded lattice of finite quotient sets. In more details, consider ℕ = {1, 2, 3,…, n}, the set of natural numbers and its subsets ℕn = {1, 2, 3,…, n} of n elements. The quotient sets of ℕn form a lattice under rarefaction, the opposite of refinement. The union of the lattices ℕn for all n is a graded lattice. Grading is furnished by the number n of elements of ℕ, i.e., the number of digits. Every stepnumber of at most n digits can be interpreted as a characteristic function of ℕ, provided that we add a sufficient number of 0 digits up front to make it a stepnumber of exactly n digits (this of course will not affect its value). There is a one-to-one correspondence between the set of stepnumbers and the graded lattice of finite quotient sets. The former is endowed by a lattice structure under this correspondence, and we shall refer to it as the natural isomorphism between the stepnumber system and the graded lattice of finite quotient sets. It is also natural in that it does not depend on arbitrary choices such as, e.g., the basis of the number system. Thus the stepnumber system is dual to its analogue, the binary number system. In enumerating stepnumbers we actually construct all finite quotient sets. Thus stepnumbers can be used to count the number of quotient sets. The great utility of stepnumbers is due mostly to this fact [which is not recognized at all].

Digital information technology is usually thought of as a great improvement over the analog. Yet rumors of the demise of the latter are ‘grossly exaggerated’. Nature still uses form, rather than substance, for encoding purposes when it comes to genetics. If it is true that the substance making up the human body is changed every seven years through metabolism, then our brain should not be thought of as an aggregate of molecules, but an arrangement of aggregates. In fact quotient sets may be the appropriate tool to investigate the structure and operation of the mind. What we are, our memory, our emotions, our psyche, are not encoded through the agency of substance. They are encoded through the agency of form. Substance is incidental and transient, and it can be substituted without changing the information content. More permanent than substance is form. To the extent it is, analog information technology will never be obsolete. Quotient sets along with stepnumbers will likely find a role in encoding and carrying analog messages efficiently, just as subsets along with binary numbers are already carriers of digital messages.

One of the great remaining mysteries in mathematics is the question whether a formula exists whereby consecutive prime numbers can be calculated. The conjecture is still outstanding that such a formula does not exist in the same sense as the set of all sets doesn’t. If this is the case, then the best one can hope for is a rapid development of various algorithms to find ever larger prime numbers. This raises the possibility of decoupling between substance and form! Finding the substance, namely, ever larger prime numbers, may outpace the form in which the new information can be put. Information technology, in particular the binary number system, may be an obstruction. The physical limitations of computer memory could defeat our efforts to forge ahead with the theory, in want of a better facility to handle very large numbers. The quantum computer reinforced with the stepnumber system fitting as a glove opens up new perspectives in computing.

Philosophy has been grappling with the dichotomy of substance and form for thousands of years. It tacitly assumes that they are inseparable as guardians of the depository of knowledge. Decoupling would most certainly create a crisis of the first magnitude. The discovery of stepnumbers opens a new chapter in philosophy in that it extends the tenure of the partnership of substance and form in storing, transmitting, retrieving, or otherwise manipulating and organizing information.

To summarize:

  • Subsets + binary numbers carry digital messages encoded through the agency of substance.
  • Quotient sets + stepnumbers carry analog messages encoded through the agency of form.

The weak duality between the binary number system and stepnumbers

Set theory is not complete without an explicit recognition of a weak duality between the lattice of subsets and the lattice of quotient sets.

The same way as the lattice of subsets is weak dual to the lattice of quotient sets, in the sense that every property of the latter has a dual property in the former (but not the other way round), the binary number system is weak dual to the stepnumber system.

Quotients sets and a new model for how the human mind works

A MESSAGE FROM PROFESSOR ANTAL E. FEKETE TO YOUNG MATHEMATICIANS

Colin Blakemore, Professor of Neuroscience at Oxford University was asked to what scientific question he would like to have the answer during his lifetime most*. His response was: “It would be nice to know how the human brain works.”

Indeed, presently we are nowhere near to answering this question. Everyone assumes that the human brain is some kind of computing machine. It receives data, processes it, and makes decisions. But what are the information-carrying agents, the zeros and ones of the ordinary computer, and what is the algorithmic process they undergo?

Professor Blakemore went on: “We just don’t know what the fundamental computing elements in the brain are. Is it a dendron1; is it the spines2 of dendrites3; or is it a synapse4? We just don’t know.”

In the absence of this knowledge the available mathematical models from computer science are of no use. To find the relevant mathematical model is not a matter of slog — it is a matter of insight. One that only an extraordinary genius may possess. We need another Newton or another Einstein.

It is quite possible that we need a brand new number system that has not yet been discovered. Or, even more daringly, we need to put mathematics on a brand new foundation, discarding set theory and substitute it with something else.

If you are excited about such questions and such a search, STEPNUMBERS is for you. It has been suggested that set theory ought to be supplanted by the quotient-set theory of Nicolas Bourbaki, who introduced it in 1937. However, no concrete steps were taken in this direction.

There is one clue pointing to the possibility that quotient sets have a role to play in the working of the human brain, as distinct from the brain of animals. While animals, like humans, can conceive of a subset, for example, a monkey can distinguish between green and ripe bananas; only humans can conceive of a quotient set, that is, a complete classification with respect to an equivalence relation. For example, a monkey is unable to distinguish between a pile often bananas and a pile of eleven bananas. To do that, monkeys should be able to classify piles according as they have the same or different number of bananas. This they are not able, nor can they be taught to do. The ability to handle quotient sets may be the criterion that separates the working of the human brain from that of the animal brain.

During the past fifteen years I have been advocating a program to go beyond the binary number system admitting two digits only: 0 and 1 (the mainstay of computer science as it is presently constituted). It is uneconomical and becoming obsolete fast, for the simple reason that it uses the memory capacity of computers most wastefully. Expanding an integer in the binary system yields a longer string of digits than expanding it in any other number system. But is there a number system wherein expansion yields the shortest string of digits for integers sufficiently large? The answer, surprisingly, is in the affirmative. The stepnumber system, discovered [by Fekete] in 1997, is such a number system. The next generation of computers, the quantum computers will in all likelihood use the stepnumber system rather than the binary, in order to optimize memory utilization. STEPNUMBERS is a primer on quotient sets and on the stepnumber system.

To be sure, changes in mathematical attitudes would be just one small step towards answering Professor Blakemore’s quandary, but it will not be the first time in history that mathematicians have anticipated the needs of other scientists by decades. Recall that the Maxwell equations were first written down long before electromagnetic waves were even thought of and their existence demonstrated. It has turned out that the spectrum of electromagnetic waves is the solution to the Maxwell equations.

This, then, is the challenge facing young mathematicians today as I see it. They are called upon to anticipate the mathematical needs of other branches of science, including neuroscience. To this I wish you all inspiration and good luck.

Endnotes:

* The Times, February 23, 2013; see the article: Life, the universe and everything else

  1. A dendron is the branching projection of a nerve cell.
  2. A spine is a thorn; a thin, pointed spike on a skeleton crystal.
  3. A dendrite is a tree-like crystalline aggregate or skeleton crystal.
  4. A synapse is an interlacing or enveloping connection of one nerve cell to another.

Mathematical education for the blind, and a new improved Braille system based on adding quotient sets

This is a personal note explaining the nature of STEPNUMBERS, outlining the larger design that has animated its writing. I took early retirement as professor of mathematics and subsequently decided that I wanted to dedicate myself to the cause of mathematics education of the blind. I am sighted and have, as most of my colleagues, had virtually no contact during my teaching career with sightless students. But the abstract nature of my discipline has often made me think about the problem how best to educate talented blind children in mathematics and information technology.

It has always been clear to me that the curriculum and the didactic aims of such a program would have to be radically different from its conventional counterpart. It must not be a mere adaptation of traditional material to the special needs of the blind. It ought to contain material the sightless can absorb and manipulate better than the sighted. I also believe that the problem must be approached not only with sensitivity but also with a great deal of humility. This is a case par excellence where the teacher must learn from the student. The sightless are less prone to succumb to what I call “the gravitation of atavistic visual imagery”, the greatest obstacle in the way of the single-minded pursuit of abstraction that permeates all mathematical enterprise. Some of the greatest cultivators of mathematics were blind (the names of Euler, Lefschetz, and Pontryagin readily come to mind) doing inspired work even in the field of geometry where eyesight had been thought to be a paramount prerequisite. It is a great pity that they did not leave reminiscences to posterity on the question whether or how their handicap may have helped them to sharpen their faculty of abstract thinking. Be that as it may, we must deem it possible that the sightless, given the nature of their handicap, may have more than an equal chance to develop their mathematical abilities to the fullest extent, granted ideal conditions. A lot of talent may have been wasted in giving blind children skills in basket weaving and massaging, rather than mathematics.

In addition, I find it hard to escape the conclusion that the very concept of a quotient set may furnish the missing link in the mathematics education of the blind. Louis Braille (1809-1852) used the non-trivial subsets of the six-cell ⠿ as raw material for codes out of which he fashioned his system of reading for the blind. Nobody today would dispute the proposition that the adoption of the Braille code was one of the great success stories of the 19th century. Perhaps the abstract nature of the concept of subsets, de-emphasizing as it does the visual aspects of the code, has something to do with it. At any rate, with the development of science there was soon need for more codes to accommodate an increasing list of essential symbols. And it was here that a historical mistake was made by the experts. Encouraged by the success of Braille, they became his epigoni. They slavishly copied a successful idea, but without the inspiration animating the original. The experts replaced the six-cell with an eight-cell, thus increasing the inventory of available codes from 26 – 1 = 63, to 28 – 1 = 255. They failed to realize, however, that the eight-cell covers a larger surface area. Therefore the blind reader will have to track codes vertically as well where previously horizontal tracking sufficed, with the result that the reading process would be slowed down considerably. The failure of the eight-cell system gave me the impetus to start advocating the use of quotient sets for the purpose of enlarging the inventory of codes. The original six-cell of Braille has 203 quotient sets in addition to the 63 non-trivial subsets already in use. The combined number 203 + 63 = 266 exceeds 255, the size of the inventory of eight-cell codes. Further augmentation of the system is still possible if we include the quotient sets of the three-, four-, and five-cells. Most importantly, none of the new proposed codes has a larger surface area than the original six-cell of Braille, so that there is no reason to believe that the efficiency of an experienced reader would be dulled on account of the increase in the size of the inventory. Horizontal tracking is all that is needed, as before. No vertical tracking — no handicap.

There is a larger issue here than that of parochial rivalries between the various competing systems to augment the original Braille. Quotient sets furnish the ideal tool for the mathematical education of the blind. They are completely non-visual and, for all we know, a sightless person may have a better chance to grasp their true nature and to manipulate them than a sighted one. Counting quotient sets is a rich source of meaningful exercises that could fill many hours devoted to homework.

It was while working on the problem to include the quotient sets of the six-cell in order to augment Braille, that I stumbled over a novel number system: that of the stepnumbers.

The first edition of STEPNUMBERS was intended as a textbook for pupils who were born blind. Although the project to test this material in a classroom setting was abandoned early on for lack of interest on the part of the educational establishment for the blind, I left the didactic features in the second edition of the book unchanged. This explains the copious in-text worked examples and end-of-chapter exercises which may be of little interest to readers who want to get acquainted with stepnumbers as quickly as possible.

Quotient sets and increased information efficiency in coding, including Chinese telegraphic codes

We have every reason to believe that, sooner or later, information technology will embrace the concept of quotient sets as a vehicle towards improved information efficiency.

Quotient sets are also important for the promise they hold out to increase information efficiency when used in coding.

For example, the entire corpus of 10,000 Chinese telegraphic codes can be rendered as quotient sets of the nine-cell, with more than 11,000 quotient sets left over and available for other purposes.