3.4  KLs and logic

In building the theory of sets from the intuitive concepts of membership and collection, we arrive to paradoxes coming from the use of self-membership (or self-reference). One of them is the famous Russell paradox. The Russell set is defined to be the set of all sets that are not members of themselves. X is a member of X exactly when X is not a member of X (Kauffman, 1994). Using the language of mathematical logic, this means that =1, where denotes Øp, and 1 stands for "True".

A similar paradox based on a self-reference is the sentence: "This statement is false", that implies the logical equation = (Epimenides paradox).

Whitehead and Russell (1927) posed the problem in terms of self-membership (or self-reference), and solved those paradoxes by prohibiting mixing different levels of discourse.

In Gödel-Bernays set theory these paradoxes are solved by making a distinction between set and class, i.e., by introducing a hierarchy of levels. A class is a set if it is a member of another class. In this system the Russell class is R={X|X Ï X and X is a set}, so R is a class, but not a set. That concept accepts self-membership, or self-reference. Namely, a self-reference can be used as a tool for a construction of interesting ascending chains of membership.

Let us denote the empty set by a line segment ^-. A finite expression E in line segments is well-formed if:

1. E is empty set, or
2. E= G, where F and G are well-formed.

A finite ordered multi-set S is an expression in the form S=, where T is any well-formed expression. It follows that T=A₁A₂...A_n, where n Î N, and each A_i (i=1,2,¼,n) is a finite ordered multi-set. The terms A_i are the members of S. This way, we obtain different multi-sets, e.g., S= , where the members of S are - , - ,  , respectively. The term S can be encoded by a sequence 0 0 1 0 1 0 0 1 0 1 1 1, where 0 stands for left, and 1 for right ends of line segments. Somewhat more complex encoding is shown in the following figure.

Two finite ordered multi-sets are equal iff they have the same members in the same order, i.e., iff their 0-1 encodings are identical. An isomorphic visual interpretation of S can be obtained by taking rectangles instead of line segments. Ordered finite multi-sets are isomorphic to the class of rooted planar tries, by graphical dualities illustrated in the next figure. A depth of a level to which a member belongs, directly visible from S, can be obtained by counting nodes from the root of tree.