Set Theory in KIF 3.0

Regarding Russell Paradox, KIF 3.0 set up a special set theory that is based on von Neumann-Bernays-Gödel (NBG). The 7th chapter of the reference manual, which is titled “Sets” starts with the description as follows.

“In many applications, it is helpful to talk about sets of objects as objects in their own right, e.g. to specify their cardinality, to talk about subset relationships, and so forth.
The formalization of sets of simple objects is a simple matter; but, when we begin to talk about sets of sets, the job becomes difficult due to the threat of paradoxes (like Russell’s hypothesized set of all sets that do not contain themselves).”

So, it is obvious that the KIF Group were worried about the paradox in set theories in making the KIF specification. Then, what is NBG theory? And how is it different from Zermelo-Fraenkel (ZF) set theory? As I mentioned in the previous blog page, ZF set theory does not fit to discuss the foundation of ontology, because it does not include any individuals except the empty set. NBG allows us to make sets that include individuals. The axioms in NBG is divided into two parts; one is for sets, in which a set is expressed using variables without capital letters, and another is for classes, in which a class is expressed using variables with capital letters.

Here, I would like to give you a discussion on wording of ‘class’ in set theories. Some people do not discriminate between set and class, but ZF uses the least terminology ‘class’. Russell Paradox shows that we cannot define a set without any paradox in case of the unrestricted comprehension principle as an attribute of a set. In ZF class is called as a thing such that is obtained as ultimate results in operations of cumulative procedures (a class is not a set in ZF). As shown in earlier blog pages, we cannot define a set using abstract sets. We cannot construct a set using any abstract sets. When mathematicians name ‘the set-theoretic universe V’ (see the previous page), the total universe V that is obtained as a result by infinite cumulative procedures is a class in ZF, and it is just used as a representative of the universe of discourse or the totallity of sets.

More complicated, in NBG, the class in ZF is called ‘a proper class’ and the set and the proper class are called class. Willard van Orman Quine noted the following on proper class.

“Basically ‘set’ is simply a synonym of ‘class’ that happens to have more currency than ‘class’ in mathematical contexts. But this excess terminology is often used also to mark a technical distinction. As will emerge, there are advantages (and disadvantages) in holding with von Neumann and perhaps Cantor that not all classes are capable of being members of classes. In theories that hold this, the excess vocabulary has come in handy for marking the distinction; classes capable of being members are called sets. The other have lamely been called ‘proper classes’, on the analogy of ‘Boston proper’ or ‘proper part’; I prefer to call them ultimate classes, in allusion to their not being members in turn of further classes.” (Set Theory and its Logic, Introduction, Quine (1963))

So, I would like to say that the universe of discourse in RDF, RI, is not a set and it is just a device for the discussion of RDF semantics.

KIF, which is based on NBG, took notice of ‘proper class’ as follows.

“An important word of warning for mathematicians. In KIF, certain words are used nontraditionally. Specifically, the standard notion of class is here called a set; the standard notion of set is replaced by the notion of bounded set; and the standard notion of proper class is replaced by unbounded set.”

KIF discriminates between bounded set and unbounded set. A bounded set can be a member of a set, but an unbounded set cannot be a member of set. A bounded set is finite. A finite set is bounded, but an infinite set is unbounded. KIF contains one more notation, that is, individuals.

“In KIF, a fundamental distinction is drawn between individuals and sets. A set is a collection of objects. An individual is any object that is not a set.
A distinction is also drawn between objects that are bounded and those that are unbounded. This distinction is orthogonal to the distinction between individuals and sets. There are bounded individuals and unbounded individuals. There are bounded sets and unbounded sets.
The fundamental relationship among these various types of entities is that of membership. Sets can have members, but individuals cannot. Bounded objects can be members of sets, but unbounded objects cannot. (It is this condition that allows us to avoid the traditional paradoxes of set theory.)” (KIF 3.0, §7.1 Basic Concepts)

I am personally interested in ‘unbounded individuals’. However, there is no explanation about ‘unbounded individuals’ in KIF theory. Does an unbounded individual really exist? If so, what is it? It should perhaps be infinity or uncountable thing. How should we treat uncountable things in ontology construction? Anyway, we can avoid Russell Paradox by the principle of restricted set abstraction, in which a set is restricted to bounded sets.

Russell Paradox is described in KIF as follows.

“The paradoxes appear only when we try to define set primitives that are too powerful. We have defined the sentence (member ) to be true in exactly those cases when the object denoted by  is a member of the set denoted by , and we might consider defining the term (setofall ) to mean simply the set of all objects denoted by  for any assignment of the free variables of  that satisfies . Unfortunately, these two definitions quickly lead to paradoxes.
Let  be the result of substituting term  for all free occurrences of  in sentence . Provided that  is a term not containing any free variables captured in , then the following schema follows from our informal definition. This schema is called the principle of unrestricted set abstraction.

(<=> (member  (setofall  )) )”

Note this form is equivalent to Cantor’s unrestricted comprehension principle and it causes Russell Paradox. Instead of this principle, KIF adopts the following principle.

“In the von-Neuman-Gödel-Bernays version of set theory, these paradoxes are avoided by replacing the principle of unrestricted set abstraction with the principle of restricted set abstraction given above.
(<=> (member  (setofall  )) (and (bounded ) ))

That’s it! Please compare this formula with the separation (aussonderung) principle in ZF (see my blog page titled ‘What is Russell paradox?’). A bounded object is used instead of ‘( x ∈ B )’.

However, in order to understand the framework for meta-modeling of ontology and the higher order structure in CLOS, Phython, and RDF, Russell’s ramified type theory is much suitable to explain how these languages can avoid Russell Paradox.

Advertisements

About seijikoide

Please check my page as researcher of computer scientist.
This entry was posted in RDF and tagged , , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s