Kitchen Style Tutorials: Set Theory #3

Sets of Sets

You know you are Center of the Universe, don’t you?

When we introduced Axiom of Specification, consequences from that were quite drastic. We said that we may only create new sets from sets already existing out there, in the Universe, and we explicitly prohibited the existence of the Set of All Sets. But what about other Sets of Sets Which Are Not All Sets? Losing such a potentially convenient concept of a set being a member of another set, which we promised initially, would significantly impoverish Set Theory. We can not produce sets of sets from the Whole Universe due to the Axiom of Specification. We do can argue that there exist “things” in the Universe we may create sets from, but what about sets of sets? Do they really exist in the Universe (except itself we had prohibited to view as a set)? The Smaller Than Universe Sets of Sets is an abstract debatable concept hardly perceptible directly, which acceptance rely on the will of a particular person, therefore, to avoid potential arguments, we have to come up with another Axiom that would build up sets of sets from the opposite, bottom-to-top side.

It’s called Axiom of Pairing, and it declares that for any two sets there is a set those sets belong to. Or, unofficially we can call it Axiom of the “Universe Thickness” – basically what it says is that, though we can’t have the Whole Universe Set, the Universe is so Vast and so Dense that for any Subsets, we are able to come up with, it will contain a Set those Subsets belong to. Is that easily comprehensible by a human (at least the regular one)? Hardly. So, again, let’s wait for AI or ETI comprehend that and explain it to us.

Meanwhile, while we wait on AI and ETI, we may discuss few things understandable by humans. Because of the Axiom, if a and b are sets, we do can write {x ∈ A: T(x)} (before we weren’t aware of the existence of set A), where generating function T(x) holds true for x=a or x=b, or maybe some other x. As a particular case we can build subset P = {x ∈ A: x=a or x=b} (or {x ∈ A: x=a ∨ x=b}) and call set P={a,b}={b,a} a pair (the unordered one, which concept we, again, do not define yet). Or, we can build subset S = {x ∈ A: (x=a or x=b) and a=b} as a special case of pair P, and call S={a,a}={a} a singleton. Those definitions explain such Set properties as “orderlessness” and “uniquelessness” we already briefly mentioned. Also, we can see a relation between the very relations of “belonging” ∈ and “inclusion” ⊂: if we define B = {x ∈ A: x=a} that means B ⊂ A, or B = {a} ⊂ A when a ∈ A.

Ordering Sets

However, what if we want to order unordered Sets? Should we define a new concept of Order? Not necessarily. For example, we have set A = {a, b, c, d}, which, by the Axiom of Extension, is exactly the same as {d, c, b, a}, or other permutations. What if we want to deal with the only one ordered permutation, which we denote by the rounded brackets, for example, A’ = (c, a, d, b)? Now, when we have defined the Axiom of Pairing and allowed Sets of Sets to exist, we can associate with our set A a set C of subsets of A, still unordered, but composed by going from one side of the ordered collection of elements of set A, and including, step by step, elements occurring before the current position in the ordered collection such as: C = { {d, c, a}, {c}, {c, a, b, d}, {a, c} }. The number of occurrences of the members of set A would define their position in the ordered list A’.

The remarkable thing about this representation of Order is that all sets in it remain unordered. Not that we may want to replace our innate human understanding of what Order is by this formalization of combining Set Theory concepts, but demonstration of the possibility of mapping basis ontological concepts easily and implicitly understandably by humans into basis concepts of the other space we as humans obviously having problem to grasp (look at those Paradoxes and Axims of the Set Theory) is astonishing. Apparently, computationally and algorithmically (AI, are you there?) it would be easier to work with sets rather than with the innate, but, because of that, difficult to formalize concepts. That makes us guess that maybe we won’t be hugely successful in formalizing human ontologies (because of the blind spot of their innate nature), but instead, we may be quite successful in formalizing non-human perception ontologies (and vice versa), for the mutual human, AI, and ETI benefits.

The alien nature of some Axiomatic Set Theory concepts may be seen in some mathematicians calling them pathological and hoping to get rid of them, while some, who embraced those concepts, still trying to use them where they are needed and quickly forget afterward. Axiomatic Set Theory, using the above mentioned Order representation, does equate set A’ with collection C: A’ = (c, a, d, b) = { {d, c, a}, {c}, {c, a, b, d}, {a, c} }, and mainly uses it for the concept of ordered pairs: OP = (a, b) = { {a}, {a, b} }, in order to show that, unlike unordered pairs in Axiom of Extension, the ordered pairs (a, b) and (x, y) are equal only iff a = x and b = y. After achieving the goal, this Order representation gets abandoned and replaced by the ≤ relation. The reason for that that consequences of that Order interpretation lead to the uncomfortable “pathological” consequence: {a, b} ∈ (a, b).

Examples in Natural Language Domain

Still, that approach may be not so unwanted, but rather, in opposite, be welcomed, for example in Natural Language Processing, and not only for the Order relation, which is, actually, local feature of the Analytical languages that flatten a more general Tree/Hierarchical Structure of the Flective/Synthetical languages, which Hierarchical Structure could be also represented by the similar approach. And, not necessarily in the way Set Theory does, but maybe in the Topological approach style, where we add a list of sets as a form of the relation representation over the original untouched Set.

If we were to express the Order relation in a pure Set Theory way, for example, for sentence “Dog bites man”, the implicitly ordered set could be: {{dog}, {bites, dog}, {bites, dog, man}}, while sentence “Man bites dog” would look like: {{man}, {bites, man}, {bites, dog, man}}. Isn’t it remarcable?

The Axiom of Pairing is even more astonishing in its application to NLP. We may take two arbitrary linguistic entities: words, clauses, sentences, texts, – and find or define a higher hierarchical entity they would belong to. It may not be a part of today’s Normative Grammar, but it could have been, or will be, or we may make it be so :). One more thing we see here is that we may have not only Flat syntaxes but, as we mentioned before, Hierarchical ones, too, which allows existence not only Analytical languages. Also, we may say that we may convert any type of syntax tree into a binary one.

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