This chapter looks at some of the mathematics of sets and predicates and simple reasoning processes. These find their way into the Sematic Web, but not always in such clean ways.
Whenever we perform a classification of any kind, we are using set theory. This has an expression in mathematics, and until you you get into the weirder aspects of set theory, commonsense ideas and mathematics coincide.
If a group of objects share some common characteristic, then we can call that collection a set. For example, all Australian citizens form a set. All UK citizens form another. All pink, fluffy dogs form yet another. Sets can be related in many ways.
To the best of our knowledge, there aren't any Martian citizens. They form an empty set, that is a set with no members at all. The mathematical notation for the empty set is Ø.
On the other hand, the set of everything is the Universal set \mathbb{U}. Most of time, what amounts to "everything" is pretty straightforward and isn't going to cause any problems - at least to us. However Russell's paradox showed that the Universal set led to a contradiction within the then-accepted set theories and caused an upheaval in Mathematics at the time, so in extreme cases it can cause issues.
The Wikipedia article Russell's paradox includes the following as an example of a variation of Russell's paradox, the Grelling-Nelson paradox:
Suppose that every public library has to compile a catalogue of all its books. Since the catalogue is itself one of the library's books, some librarians include it in the catalogue for completeness; while others leave it out as it being one of the library's books is self-evident.
Now imagine that all these catalogues are sent to the national library. Some of them include themselves in their listings, others do not. The national librarian compiles two master catalogues – one of all the catalogues that list themselves, and one of all those that don't.
The question is: should these catalogues list themselves? The 'Catalogue of all catalogues that list themselves' is no problem. If the librarian doesn't include it in its own listing, it is still a true catalog of those catalogues that do include themselves. If he does include it, it remains a true catalogue of those that list themselves.
However, just as the librarian cannot go wrong with the first master catalogue, he is doomed to fail with the second. When it comes to the 'Catalogue of all catalogues that don't list themselves', the librarian cannot include it in its own listing, because then it would include itself. But in that case, it should belong to the other catalogue, that of catalogues that do include themselves. However, if the librarian leaves it out, the catalogue is incomplete. Either way, it can never be a true catalogue of catalogues that do not list themselves.
So you can see that either the concept of the Universal set is problematic, or the things that you can say about such sets are problematic. This is probably the simplest of the areas in which apparently simple ideas bump up against complex mathematical problems. We shall ignore such issues in the sequel :-)
The Web, the Semantic Web and many other systems are composed of two parts:
Predicates define the relationship between two or more objects, such as "John loves Jane". We only consider binary relationships in the Semantic Web, where a predicate takes a single subject and a single object. Predicates can also be formed between predicates, such as "Love is stronger than hating", but we shall just stick to simple cases for now.
Two predicates may be equivalent. That means they have the same meaning and apply to the same pairs of subject/object. Only their 'label' is different, and on the Web that means that their URIs are different.
A predicate P is reflexive if for all
objects A
A P A
Equality is reflexive: every object is equal
to itself. On the other hand bigger
is not: no object is bigger than itself.
A predicate P is symmetric if for all
objects A and B,
if
A P B
then
B P A
For example "is married to" is reflexive while "is in love with" is sadly not: "John loves Jill" does not mean that "Jill loves John".
A predicate is transitive if it for all objects
A, B and C
if
A P B and B P C
then
A P C
Equivalence is transitive: if A is equivalent to B and B is equivalent to C, then A is equivalent to C. "bigger than" is also transitive: if A is bigger than B and B is bigger than C, then A is bigger than C. On the other hand, "knows" is not: if I know you and you know him then maybe/maybe not I know him.
This chapter has looked in brief at a number of mathematical concepts. These are the simple forms: some of them translate into the Semantic Web, but the syntax becomes more complex, and even whether or not the simple maths is applicable to a real-life domain is sometimes not so clear.
Copyright © Jan Newmarch, jan@newmarch.name
If you like this book, please contribute using Flattr
or donate using PayPal