Relations
Alone as Islands in the Ocean…
So far we were talking about Sets as collections of isolated objects – like Islands in the Ocean, maybe aggregating into Archipelagos, but still unconnected and unrelated to each other. That is a quite boring picture and actually unrealistic one. There are birds flying from Island to Island, there are ocean currents bringing coconuts, branches, seeds from trees growing on one Island, to shores of others, not even mentioning ocean animals cruising waters around Archipelagos, or traveling half a Globe from one to another. And deep on the Ocean floor level, we can see these Islands are really is just one thing – Earth Crust having ridges and spouts here and there.
It’s a whole Space of Interconnected and Interrelated entities, whatever way we look at it. We already mentioned that Mathematics is based on the Real World and the ways we, humans, percept it. Relations between objects is what we see everywhere (even if there are “really” no ones) – it is a nature of the human mind. Hence, how is it useful, or even, possible to have such mathematical abstractions as Sets, which have only one type of relation (belonging) that exists only between Somethings (Set elements) and Nothings (Sets themselves, as we defined them in Axiom of Extension)? Let’s not even rush to answer this question yet, but instead, let’s fix this obvious shortcoming of Set Theory, and define what Relations are.
The surprising answer to the question “What Relation is?” would be “Don’t know, don’t care (that don’t know)”. As previously, when we were talking about Sets themselves, we are rather concerned with the ways we can represent those innate concepts as Sets, and now, Relations. If Relation is a “thing” between two objects x and y that could be held either as True or False, then we can represent it as an Ordered Pair:
r = (x, y)
(as we remember, Ordered Pair means (x, y) ≠ (y, x))
Then relations between elements x belonging to set X, and elements y belonging to set Y, could be represented also as a Set of Ordered Pairs R, and particular relation (x, y) belonging to R could be depicted as:
x R y
and we can say that set R is a relation from set X to set Y.
In our Tropical Islands analogy, we may define set X as all coconuts that have grown on one island, set Y – on another, and an innate relation we want to represent, say, is a look-alikeness relation. Everyone feels what does that mean that one object looks like another, (though particular judgments may vary from person to person) so a set of pair-wise observations that a coconut from island X looks like another from island Y would be relation R from X to Y. One coconut from island X may look like many coconuts on island Y, and one coconut on island Y may look like many coconuts on island X, hence Relation is a many-to-many “thing” in general case, and is good to represent such equations as x² + y² = a, which are not functions (ok, we haven’t defined what all these things are, yet, but your innate mathematical understanding is enough to make it clear).
All coconuts from island X that present in the set of relations R could be named as domain, while all coconuts from island Y found in the set R – range:
dom R = {x: for all y in (x R y)}
ran R = {y: for all x in (x R y)}
We usually agree that particular object (or coconut) looks exactly like itself, and that holds true for each and every coconut (at least at a particular moment). Such a relation x R x that holds true for all (depicted as ∀) x ∈ X ∨ Y is called reflexive. Also, if one coconut looks like another, that implies that another looks like the former: x R y ⇒ y R x (∀(x, y) ∈ R). Such relations possessing that quality are called symmetric. If we have three coconuts, that usually means that if coconut a looks like b, and b looks like c, then a also looks like c (∀(a, b) ∈ R ∧ ∀(b, c) ∈ R). Such a relation is called transitive.
From our innate experience, we know that not all relations are such. If set X is coconut palms and set Y is coconuts, and relation between them is the relation of “growth”, then such a relation is not reflexive (coconut or palm does not grow on itself), not symmetric (if a coconut grew on a palm, does not mean that the palm grew on that coconut), and not transitive (even if a second generation coconut grew on a palm that came out of the first generation coconut, it still did not grow on the original first generation palm).
We can envision Relations even in a more tangible way, as coconuts floating from one island X, to another – Y, where places of the palm growth would be elements of these islands-sets. Although some particular coconuts may float off and then back to the same palm, or float from island X to Y and back to the same palm growth place, or float to place c, while others hop to b and then to c, those conditions won’t be satisfied for each and other coconut, so such a relation will be neither reflexive, nor symmetric, nor transitive. If we prefer to look at a more respectable, mathematic-like examples with real numbers, then the circle equation above is symmetric but isn’t reflexive or transitive. “Greater” or “less” relations are transitive but aren’t reflexive or symmetric. And |x – y| < 1 is reflexive and symmetric but isn’t transitive.
Relations “from X to X” (also called “in X”) that are reflexive, symmetric and transitive do have a special place and are called equivalence relations. For all y for which x R y holds true, these relations create so-called equivalence classes in respect to x (depicted as x/R, or π(x)), which are either disjoint or equal *. Collection or set C of these equivalence classes, depicted as C = X/R, could be called a partition, or quotient, or factor set. On the other hand, we can say that partition C induces equivalence relation R in set X, or R = X/C **.
* In a more formal way, we want to prove that if a, b ∈ X and a/R ∩ b/R ≠ ∅, then a/R = b/R. Let’s pick an arbitrary c that belongs to the intersection of two equivalence classes: c ∈ a/R ∩ b/R. Belonging of c to a/R would mean a R c, as well as, belonging of c to b/R means b R c. Let’s pick an arbitrary x that belongs just to a/R, which would mean a R x. From symmetry: a R c ⇒ c R a, and from transitivity: c R a, a R x ⇒ c R x. Also from transitivity of b R c and c R x ⇒ b R x, which means that arbitrary x belonging to a/R always belongs to b/R, or a/R ⊂ b/R. Applying the same logic to arbitrary x belonging to b/R, we’ll get b/R ⊂ a/R, or a/R = b/R. Also, by definition, because every x belongs to some equivalence class, then ∪ x/R = X. I.e., indeed whole set X is partitioned on a collection of disjoint equivalence classes.
** Here we want to show, which is quite obvious, that when we partition set X into set of subsets C, and each of these subsets would have elements x, y, z, and if we can come up with a relation R (which we indeed always can – for example, relation of belonging to the same subset) that would guaranty reflexivity, symmetry and transitivity between them, then such a subset would be an equivalence class, and all of them would be a quotient set.
The latter fact is quite dramatic – it means that we don’t deal with pure sets, we always work with spaces. When we curve out subsets from the Universe, in accordance to the Axiom of Specification, we willingly or unwillingly partition it, and that partitioning is guided by our perception, and implicitly or explicitly that perception imposes or induces relations (at least the equivalence ones) between elements of the newly created sets. There maybe exist whole, clean, unpartitioned (by our perception) sets out there in the Universe, but we don’t have access to them. I guess, we, humans, are not upset about that, because we always look for relations between things 🙂
Natural Language Processing examples
An obvious example of a relation between words in a whole sentence is their order. We can represent the order either in a form of immediate ordered pairs, or longer ordered tuples. It could be argued that majority of syntax (and corresponding semantic) structures could be represented naturally via binary relations, and those structures that do not naturally map to them (like enumerations or compound words) could be still technically represented as recursive pairwise structures without much of the structural information loss. If we don’t agree with that, we still may use three-, four-, etc- wise relations.
Let us start building on the “Dog Bites Man” (usually) example from previous chapters, and extend it to a sentence S1 = “Agitated Brown Dog Bites Tall Man In Large Park”. Such a concept level statement looks a bit awkward (daring hasty generalization or unfounded assumption is weird) but let’s stick to simpler grammatical forms to avoid dealing with stop-words and stemming. Should we break up the sentence into a set of ordered pairs, or treat it as a whole long ordered tuple? Or break it up into smaller, but still tuples longer than pairs? The answer(s) may be not so obvious if looking for it from the inside of an analytic language such as English.
It doesn’t matter what formal instruments a particular language uses, the ultimate goal is to express partitioning of a sentence, for example, into Theme (what we speak of) and Rheme (what we speak about it), or, on a finer level, into Subject, Verbal Group, Direct and Indirect Objects, Adverbial Clauses, etc. Purely Synthetic/Flective languages use Case System to bind nouns, adjectives, and participles into Subject, Object, Adverbial Clauses and delineate them from each other. For example, the Accusative Case would mark Direct Object, Dative – Indirect, and so on. Order of all these words – nouns, adjectives, participles is irrelevant, and they may be intermixed with each other arbitrary, but knowing their cases (via inflection, for example), we can easily find out to which partition of the sentence they belong.
As we mentioned before, any partitioning or subsetting of a set implies the existence of an Equivalence Relation between members of a subset. The Case partitioning, being more fundamental (at least for Indo-European languages), implies that we have to look for a similar equivalence relation in Analytic languages. Strong Greater or Less relations, being applied to the whole sentence set, are obviously not good for that, because they are neither reflexive nor symmetric. What we can do for analytical language is to create an ordered subset of delineating words (in our case S2 = (Bites, In, .), then S3 = S1 – S2), and use the relation R = “in between of the same delineating word ordered pairs (listed in set Q = {(∅, Bites), (Bites, In), (In, .)})”, to partition the sentence: S3/R = {{Agitated, Brown, Dog}, {Tall, Man}, {Large, Park}} (which could be implemented as an intersection of the Less relation relative to delineating words).
Does the order-based relation partitioning have its useful place in NLP? Of course, it does. We mentioned before that not only relations define partitioning, but the opposite is also true – the very partition of a set implies there exist a relation defining that partition. For example, our sentence starts with “Monday Morning Agitated Brown Dog…”. There is no helper word here to delineate Adverbial from Subject, still, we can partition that fragment, for example using colocation dictionaries, and recreate the elusive relation.
Yet another thing we could be interested in is to find relations between members of the quotient set S3/R = {{Agitated, Brown, Dog}, {Tall, Man}, {Large, Park}}. What can help us in that is a mapping to its dual set Q = {(∅, Bites), (Bites, In), (In, .)} we used to partition the original set S3. And about that stuff of functions and mappings, we’ll talk in the next chapter…
References:
Halmos, Paul R., 1960: Naive Set Theory. Princeton, N.J.: D. Van Nostrand Company, Inc., repr. 2017, Mineola, New York: Dover Publications, Inc.
Mendelson, Bart, 1975: Introduction to Topology. Boston: Allyn and Bacon, first edition 1962, second edition 1968, repr. 1990, New York: Dover Publications, Inc.
Pinter, Charles C., 1971: A Book of Set Theory. Reading, Massachusetts: Addison-Wesley Publishing Company, repr. 2014, Mineola, New York: Dover Publications, Inc.
Data Science Research Blog 