Kitchen Style Tutorials: Set Theory #4

Unions and Intersections of Sets

Can we really do anything?

When we introduced Axiom of Specification we allowed ourselves to create new sets from the ones we can already find out there in the Universe. When we introduced Axiom of Pairing, we agreed we can combine those (sub)sets as elements into other sets (of the higher hierarchy). But what about combining elements of (sub)sets into new sets, effectively “melting” their boundaries? Or, by Descartes’ analogy, creating chimeras from the parts of existing animals? That is quite a debatable question whether chimeras exist in the Universe, therefore, we, again, have to make a voluntary decision that they do exist in the Axiom of Unions (or we can call it Axiom of Chimeras) that says that for every collection of sets C there exists a set that contains all the elements which belong at least to one set of the collection.

We depict the resulting, “chimera” set as ∪ = {x: x ∈ X for some X in C}, or we can use shorter notations like:

∪ C, or ∪ {X: X ∈ C}, or ∪X ∈ C X, or ∪ {X: X ∈ {A, B, … D}} = A ∪ B ∪ … D

From the definition above, there follow immediately such equations as:

∪ ∅ = ∅ and ∪ {A} = A

Intuitively, easily understandable properties of the set unions, which may still require simple proofs, are:

A ∪ ∅ = A *

A ∪ B = B ∪ A (commutativity)

A ∪ (B ∪ C) = (A ∪ B) ∪ C (associability)

A ∪ A = A

A ⊂ B iff A ∪ B = B (or A ⊂ B ⇔ A ∪ B = B ) **

Those simple proofs, following from the definition of the ∪ set: A ∪ B = {x: either x ∈ A or x ∈ B}, would be like those two for the first and last property (the rest we left to the reader):

* We have to prove that the left and right sides of the equation A ∪ ∅ = A are indeed equal. Let’s take an arbitrary x belonging to the set ∪ on the left side. That “belonging” means that x either belongs to A or doesn’t exist. An arbitrary x belonging to the set on the right side belongs to the set A. Therefore (or ∴) if any arbitrary x on the left side is present also on the right side, all x that belong to the left side belongs to the right side. QED (quod erat demonstrandum – which was demonstrated) or notation ■.

** By definition of A ⊂ B, if x ∈ A, also x ∈ B. Then, an arbitrary x belonging to the left side of A ∪ B, belongs either to A (and also to B due to the early A ⊂ B proposal) or to B. An arbitrary x belonging to the right side, belongs to B. i.e. both sides equal, therefore A ⊂ B ⇒ A ∪ B = B. Conversely, if both sides of expression A ∪ B = B are equal, that means that every x belonging to A also belongs to B, which means that A ⊂ B, i.e. A ⊂ B ⇐ A ∪ B = B. Now, we proved A ⊂ B ⇔ A ∪ B = B in both directions ■. Why we do that in both directions? The very Set Theory will tell us later, and for now, we can just throw a word isomorphism, and left the reader guessing what that is 🙂

If we substitute word “some” by “all” in the union definition, we’ll get another type of the “chimera” set – intersection ∩ = {x: x ∈ X for all X in C}, which could be denoted as: ∩ C, or ∩ {X: X ∈ C}, or ∩X ∈ C X, or ∩ {X: X ∈ {A, B, … D}} = A ∩ B ∩ … D, with similar (or one can say some of them are “anti-similar”) qualities:

A ∩ ∅ = ∅

A ∩ B = B ∩ A (commutativity)

A ∩ (B ∩ C) = (A ∩ B) ∩ C (associability)

A ∩ A = A

A ⊂ B iff A ∪ B = A (or A ⊂ B ⇔ A ∩ B = A )

If A ∩ B = ∅, such sets are called disjoint. There are also couple useful qualities involving both, union and intersection sets, which are called distributive laws:

A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) ***

A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)

*** The first one we can prove similarly to the above proofs: if an arbitrary x belongs to the left side, that means it belongs both to A and B ∪ C, which means it belongs either to B or to C. Then, if x belongs to A and B it belongs to the right side, or, in the other only case, if it belongs to A and C, it still belongs to the right side. Conversely, if x on the right side belongs to A ∩ B or A ∩ C, it always belongs to A and either to B or C, which is exactly the left side ■.

The other, not present proofs are, again, left for the reader to practice by the proof templates above. Do we have any quirkiness with the definitions we came up, so usual for the deep diving into Set Theory, which only AI or ETI can comprehend? Let’s see in the other chapter…

Examples in Natural Language and Artificial Intelligence Domains

Fascinating, we can just grub arbitrary fragments from any texts, paste them together, and get nothing less than a text. You, and me, and everybody sometimes (or maybe more often than sometimes, but we won’t tell it anyone, he-he) as students used to cut and pasted pretty much random fragments from pompous books of wise authors to quickly bake an essay for a hated mandatory class, and usually were getting away with that, even occasionally getting high grades for such a Kunststück – a peculiar kraft.

But just pause, and think about it… You take a representation of Thought – something unique, complex, carefully crafted, carelessly butcher it, mix it up with other remains of which used to be Thoughts, and voilà – here it is – a brand new shining Thought. Isn’t that remarkable, surprising, …and scary?

In the utilitarian sense, for ChatBots, and generally for the Natural Language Generation (and here we step into AI domain in its true meaning – the meaning of agency) applications, that means we do not need to make up Texts, – it would be enough to combine them from fragments of the existing corpora. Yes, it’s all that it is – the innate concept of Creativity we have such an admiration to, is no more than Unions of Subsets in the set-theoretic terms applied to the agency-full AI.

As for our previous example: “Dog bites man” and “Man bites dog” sentences, the relation-full set representation would be (we even don’t do lemmatization here), for the first sentense: A = {{dog}, {man}, {bites}, {dog}, {bites, dog), {bites, dog, man}}, for the second one: B = {{dog}, {man}, {bites}, {man}, {bites, man), {bites, dog, man}}, and for the Union: A ∪ B = {{dog}, {dog}, {man}, {man}, {bites}, {bites, dog}, {bites, man}, {bites, dog, man}}. The Union doesn’t have dog-man order – counts for them are the same – 3. Or, if we wite the same set in a more structured way:

A ∪ B = {{dog}, {bites}, {man},    
         {dog,   bites},
                {bites,   man},
         {dog,   bites,   man}}

we will see that order (and relations it represents) is bidirectional. I.e. our Union, which represents text Generation and Generalization of the original texts, tries to say that either active-passive relation is possible, while what is more importants is the biting action. Which observation is quite philosophical, and impressive for the simple set-theoretic representation and operations.

Yet another bizarre, as well as, again, scary thing about the intersection of texts is that they do exist. Again, stop and think – how in the world, all these unique an personal things as Thoughts (and their duals – Texts), can have common parts, even if they are empty sets? Nevertheless, they do, and we can exploit that fact for practical purposes – finding commonalities between texts (otherwise that would be hopeless). And, again, that is all we need for another human innate opaque concept of high reverence – Search – in application to AI.

Again, for our “Dog bites man”/”Man bites dog” example, the Intersection would be: A ∩ B = {{dog}, {man}, {bites}, {bites, dog, man}}. The Intersection, as well as the Union, don’t have an order – all word counts are the same – 2, but now the relation it represents is not directional at all:

A ∩ B = {{dog}, {bites}, {man},  
         {dog,   bites,   man}}

Which means the text we just generated, is indeed a generic Search request text – we are interested in any texts mentioning dogs, men, and their biting relation regardless of its direction.

PS: There is actually some sloppiness, related to “uniqlessness”, lurking in the examples, which we’ll talk later, and so far left for readers to figure out…

 

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.

Advertisements
This entry was posted in Mathematical Ruminations 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 )

Google+ photo

You are commenting using your Google+ 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 )

Connecting to %s