Kitchen Style Tutorials: Set Theory #5

What exactly box are you thinking outside of?

If you haven’t noticed (likely you have, just have forgiven it) we weren’t rigorous in our definition of the union of sets: ∪ = {x: x ∈ X for some X in C}, or intersection of sets ∩ = {x: x ∈ X for all X in C}, which does not explicitly acknowledge Axiom of Specification in the form ∪ = {x ∈ S: x ∈ X for some X in C} or ∩ = {x ∈ S: x ∈ X for all X in C}. Of course, we can imply that sets X in collection C were defined rigorously according to Axiom of Specification as X = {x ∈ S: some condition}, and get away with that a bit sloppy union or intersection definition.

If we don’t imply these Axiom of Specification things, we again prone to things incomprehensible by the usual human mind. For example, what if collection C is an empty set ∅? What is ∪ = {x: x ∈ X for some X in ∅}, or ∩ = {x: x ∈ X for all X in ∅}? What are these things that belong to other things which belong to Nothing? That is unclear, and we may want to try to answer that question from the other side – which things do not comply with our definition, and the rest will be our answer. So, there should be some x that does not belong to one (intersection) or all (union) X belonging to empty set. But nothing belongs to ∅, therefore there are not such x’s. Therefore any and every x of the Universe, or even more than Universe belong to the union or intersection of the empty set members. Ok, AI or ETI, can you explain this thing to humans? No? Then we are back to our human intelligence safe Axiom of Specification, which says that all members of the sets, we are talking about, are members of some superset S, therefore ∪ ∅ = ∩ ∅ = S. So we are fine and sane again.

Complements

So far, in the Unions and Intersections section, we were talking about creating our “chimera” sets by joining (one or another (inner or outer) way) original “genuine” sets we carved out of the Universe. What about other ways of creating “chimera” sets? For example by separating (in some ways) parts of the original “genuine” sets?

Yes, we can define the difference set (or operation over sets, though we haven’t defined yet what it is, and we’ll just rely on the innate understanding of that word so far), known also as relative complement, which we can denote as A – B = {x ∈ A: x ∉ B}. In this notation B is not necessarily a subset of A (B ⊂ A) and could be B ⊄ A. We can mention here some easily provable facts (in a sense of Latin root of the word – to make, compose, construct), and let the reader prove them:

A ⊂ B iff A – B = ∅

A – (A – B) = A ∩ B

A ∩ (B – C) = (A ∩ B) – (A ∩ C)

We can also define the symmetric difference, or Boolean sum: A + B = (A – B) ∪ (B – A), which could be easily seen (and left for the reader to prove), is commutative A + B = B + A, as well as A + ∅ = A, and A + A = ∅. The symmetric difference is also associative A + (B + C) = (A + B) + C, which is a bit less transparent. The left part of the equation boils down to A + (B + C) = (A – ((B – C) ∪ (C – B))) ∪ (((B – C) ∪ (C – B)) – A), where ((B – C) ∪ (C – B)) means that an arbitrary x belongs either to B or C, and not to both, while A – ((B – C) ∪ (C – B)) means that x belongs either to A or to all three A, B, and C; also ((B – C) ∪ (C – B)) – A means x belongs to either to B or C, and the same time not in A. Careful right side unwinding (which is left to the reader) will lead to the same result ■. Actually, often in Set Theory graphic proofs via Venn diagrams (which the reader has already heard of or seen in every place mentioning Set Theory (therefore we don’t mention them here)) could be faster and easier to understand 🙂

We can also assume that set A (and any other set in this paragraph) belong to a superset S: A ⊂ S, and call this complement absolute, and denote it as A’, or C(A), and come up (literally make it up :)) with some easily provable facts:

(A’)’ = A

∅’ = S and S’ = ∅

A ∩ A’ = ∅ and A ∪ A’ = S

A ⊂ B iff B’ ⊂ A’

and most useful facts in everyday life are called DeMorgan laws:

(A ∪ B)’ = A’ ∩ B’ * (or in the collection, of family form: ∪’ {X: X ∈ C} = ∩ {X’: X ∈ C})

(A ∩ B)’ = A’ ∪ B’  (or in the collection, of family form: ∩’ {X: X ∈ C} = ∪ {X’: X ∈ C})

* Let’s prove the first law for two sets. The left side means that arbitrary x belongs to S and does not belong to either A or B, which means x does not belong to A and does not belong to B, which we see on the right side, therefore we can say at least (A ∪ B)’ ⊂ A’ ∩ B’. But what about right side? Does something from there doesn’t belong to the left side? The right side means that x belongs to S and does not belong to A and does not belong to B, or in other words – doesn’t belong to either one, i.e., at least (A ∪ B)’ ⊃ A’ ∩ B’. Does the left side contain anything that is not on the right side? Previously we already have proven it does not, therefore (A ∪ B)’ = A’ ∩ B’ ■. Why are we doing these things – going from left to right, then from right to left? We have already mentioned that Set Theory will actually tell us why, and that is related to isomorphism (which we didn’t define yet), and here, in particular, we want to make sure that Null Space (Null T) is ∅, and T is onto. What all that is will discuss later, so stay tuned 🙂

Examples in Natural Language and Artificial Intelligence Domains

The Union or Intersection over Empty Set idiosyncrasy seems as an unimportant peculiarity, but if we look at Unions as ways of creating new texts, the Empty Set as a starting point means the beginning of a conversation. Since such a Union is everything in the Universe then anything is good enough for starting a dialog. That’s quite an interesting point for the real, agency-full AI development.

Complements so far look like the most important set-theoretic feature for the agency-full AI. It’s really amazing – you want to create a new subset out of the other ones, and “accidentally” you create another, “delta” set you don’t intend, but it is a text with its own meaning. Of course, we can ignore and throw away that unintended text, but also we can learn from it. From word2vec models we’ve learned there is a delta vector between words “King” and “Queen”, and not only between the words, but texts associated with them, and even more, the similar delta vector is seen between texts associated with other gender-related actors: female and male Presidents, PMs, pilots, etc…

When subtracting set “King” from set “Queen” (which of course have the common Intersection Set with such elements as {“power”, “will”, “respect”, …}) we’ll get a Relative Complement {“beauty”, “charm”, “intrigue”, …}, while doing the opposite subtraction we’ll get another part of the Boolean Sum set: {“hunting”, “fight”, “sword”, …}, which would represent just learned concepts of Femininity and Masculinity.

For our “Dog bites man”/”Man bites dog” example, one Relative complement would be: A – B = {{dog}, {bites, dog}}, while B – A = {{man}, {bites, man}}. That means that Relative complements (or Boolean sum) allow us learn about difference in relations in these two sentences.

It is Complements which are really new, i.e. unexpected and unintended sets, which we really want (and fear) from the agency-full AI.

 

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