Learnability of machine learning is provably an undecidable?—part 3: closure

Update on 23 January 2019, 17:55 IST:

In this series of posts, which was just a step further from the initial, brain-storming kind of a stage, I had come to the conclusion that based on certain epistemological (and metaphysical) considerations, Ben-David et al.’s conclusion (that learnability can be an undecidable) is logically untenable.

However, now, as explained here [^], I find that this particular conclusion which I drew, was erroneous. I now stand corrected, i.e., I now consider Ben-David et al.’s result to be plausible. Obviously, it merits a further, deeper, study.

However, even as acknowledging the above-mentioned mistake, let me also hasten to clarify that I still stick to my other positions, especially the central theme in this series of posts. The central theme here was that there are certain core features of the set theory which make implications such as Godel’s incompleteness theorems possible. These features (of the set theory) demonstrably carry a glaring epistemological flaw such that applying Godel’s theorem outside of its narrow technical scope in mathematics or computer science is not permissible. In particular, Godel’s incompleteness theorem does not apply to knowledge or its validation in the more general sense of these terms. This theme, I believe, continues to hold as is.

Update over.


Gosh! I gotta get this series out of my hand—and also head! ASAP, really!! … So, I am going to scrap the bits and pieces I had written for it earlier; they would have turned this series into a 4- or 5-part one. Instead, I am going to start entirely afresh, and I am going to approach this topic from an entirely different angle—a somewhat indirect but a faster route, sort of like a short-cut. Let’s get going.


Statements:

Open any article, research paper, book or a post, and what do you find? Basically, all these consist of sentences after sentences. That is, a series of statements, in a way. That’s all. So, let’s get going at the level of statements, from a “logical” (i.e. logic-thoretical) point of view.

Statements are made to propose or to identify (or at least to assert) some (or the other) fact(s) of reality. That’s what their purpose is.


The conceptual-level consciousness as being prone to making errors:

Coming to the consciousness of man, there are broadly two levels of cognition at which it operates: the sensory-perceptual, and the conceptual.

Examples of the sensory-perceptual level consciousness would consist of reaching a mental grasp of such facts of reality as: “This object exists, here and now;” “this object has this property, to this much degree, in reality,” etc. Notice that what we have done here is to take items of perception, and put them into the form of propositions.

Propositions can be true or false. However, at the perceptual level, a consciousness has no choice in regard to the truth-status. If the item is perceived, that’s it! It’s “true” anyway. Rather, perceptions are not subject to a test of truth- or false-hoods; they are at the very base standards of deciding truth- or false-hoods.

A consciousness—better still, an organism—does have some choice, even at the perceptual level. The choice which it has exists in regard to such things as: what aspect of reality to focus on, with what degree of focus, with what end (or purpose), etc. But we are not talking about such things here. What matters to us here is just the truth-status, that’s all. Thus, keeping only the truth-status in mind, we can say that this very idea itself (of a truth-status) is inapplicable at the purely perceptual level. However, it is very much relevant at the conceptual level. The reason is that at the conceptual level, the consciousness is prone to err.

The conceptual level of consciousness may be said to involve two different abilities:

  • First, the ability to conceive of (i.e. create) the mental units that are the concepts.
  • Second, the ability to connect together the various existing concepts to create propositions which express different aspects of the truths pertaining to them.

It is possible for a consciousness to go wrong in either of the two respects. However, mistakes are much more easier to make when it comes to the second respect.

Homework 1: Supply an example of going wrong in the first way, i.e., right at the stage of forming concepts. (Hint: Take a concept that is at least somewhat higher-level so that mistakes are easier in forming it; consider its valid definition; then modify its definition by dropping one of its defining characteristics and substituting a non-essential in it.)

Homework 2: Supply a few examples of going wrong in the second way, i.e., in forming propositions. (Hint: I guess almost any logical fallacy can be taken as a starting point for generating examples here.)


Truth-hood operator for statements:

As seen above, statements (i.e. complete sentences that formally can be treated as propositions) made at the conceptual level can, and do, go wrong.

We therefore define a truth-hood operator which, when it operates on a statement, yields the result as to whether the given statement is true or non-true. (Aside: Without getting into further epistemological complexities, let me note here that I reject the idea of the arbitrary, and thus regard non-true as nothing but a sub-category of the false. Thus, in my view, a proposition is either true or it is false. There is no middle (as Aristotle said), or even an “outside” (like the arbitrary) to its truth-status.)

Here are a few examples of applying the truth-status (or truth-hood) operator to a statement:

  • Truth-hood[ California is not a state in the USA ] = false
  • Truth-hood[ Texas is a state in the USA ] = true
  • Truth-hood[ All reasonable people are leftists ] = false
  • Truth-hood[ All reasonable people are rightists ] = false
  • Truth-hood[ Indians have significantly contributed to mankind’s culture ] = true
  • etc.

For ease in writing and manipulation, we propose to give names to statements. Thus, first declaring

A: California is not a state in the USA

and then applying the Truth-hood operator to “A”, is fully equivalent to applying this operator to the entire sentence appearing after the colon (:) symbol. Thus,

Truth-hood[ A ] <==> Truth-hood[ California is not a state in the USA ] = false


Just a bit of the computer languages theory: terminals and non-terminals:

To take a short-cut through this entire theory, we would like to approach the idea of statements from a little abstract perspective. Accordingly, borrowing some terminology from the area of computer languages, we define and use two types of symbols: terminals and non-terminals. The overall idea is this. We regard any program (i.e. a “write-up”) written in any computer-language as consisting of a sequence of statements. A statement, in turn, consists of certain well-defined arrangement of words or symbols. Now, we observe that symbols (or words) can be  either terminals or non-terminals.

You can think of a non-terminal symbol in different ways: as higher-level or more abstract words, as “potent” symbols. The non-terminal symbols have a “definition”—i.e., an expansion rule. (In CS, it is customary to call an expansion rule a “production” rule.) Here is a simple example of a non-terminal and its expansion:

  • P => S1 S2

where the symbol “=>” is taken to mean things like: “is the same as” or “is fully equivalent to” or “expands to.” What we have here is an example of an abstract statement. We interpret this statement as the following. Wherever you see the symbol “P,” you may substitute it using the train of the two symbols, S1 and S2, written in that order (and without anything else coming in between them).

Now consider the following non-terminals, and their expansion rules:

  • P1 => P2 P S1
  • P2 => S3

The question is: Given the expansion rules for P, P1, and P2, what exactly does P1 mean? what precisely does it stand for?

Answer:

  • P1 => (P2) P S1 => S3 (P) S1 => S3 S1 S2 S1

In the above, we first take the expansion rule for P1. Then, we expand the P2 symbol in it. Finally, we expand the P symbol. When no non-terminal symbol is left to expand, we arrive at our answer that “P1” means the same as “S3 S1 S2 S1.” We could have said the same fact using the colon symbol, because the colon (:) and the “expands to” symbol “=>” mean one and the same thing. Thus, we can say:

  • P1: S3 S1 S2 S1

The left hand-side and the right hand-side are fully equivalent ways of saying the same thing. If you want, you may regard the expression on the right hand-side as a “meaning” of the symbol on the left hand-side.

It is at this point that we are able to understand the terms: terminals and non-terminals.

The symbols which do not have any further expansion for them are called, for obvious reasons, the terminal symbols. In contrast, non-terminal symbols are those which can be expanded in terms of an ordered sequence of non-terminals and/or terminals.

We can now connect our present discussion (which is in terms of computer languages) to our prior discussion of statements (which is in terms of symbolic logic), and arrive at the following correspondence:

The name of every named statement is a non-terminal; and the statement body itself is an expansion rule.

This correspondence works also in the reverse direction.

You can always think of a non-terminal (from a computer language) as the name of a named proposition or statement, and you can think of an expansion rule as the body of the statement.

Easy enough, right? … I think that we are now all set to consider the next topic, which is: liar’s paradox.


Liar’s paradox:

The liar paradox is a topic from the theory of logic [^]. It has been resolved by many people in different ways. We would like to treat it from the viewpoint of the elementary computer languages theory (as covered above).

The simplest example of the liar paradox is , using the terminology of the computer languages theory, the following named statement or expansion rule:

  • A: A is false.

Notice, it wouldn’t be a paradox if the same non-terminal symbol, viz. “A” were not to appear on both sides of the expansion rule.

To understand why the above expansion rule (or “definition”) involves a paradox, let’s get into the game.

Our task will be to evaluate the truth-status of the named statement that is “A”. This is the “A” which comes on the left hand-side, i.e., before the colon.

In symbolic logic, a statement is nothing but its expansion; the two are exactly and fully identical, i.e., they are one and the same. Accordingly, to evaluate the truth-status of “A” (the one which comes before the colon), we consider its expansion (which comes after the colon), and get the following:

  • Truth-hood[ A ] = Truth-hood[ A is false ] = false           (equation 1)

Alright. From this point onward, I will drop explicitly writing down the Truth-hood operator. It is still there; it’s just that to simplify typing out the ensuing discussion, I am not going to note it explicitly every time.

Anyway, coming back to the game, what we have got thus far is the truth-hood status of the given statement in this form:

  • A: “A is false”

Now, realizing that the “A” appearing on the right hand-side itself also is a non-terminal, we can substitute for its expansion within the aforementioned expansion. We thus get to the following:

  • A: “(A is false) is false”

We can apply the Truth-hood operator to this expansion, and thereby get the following: The statement which appears within the parentheses, viz., the “A is false” part, itself is false. Accordingly, the Truth-hood operator must now evaluate thus:

  • Truth-hood[ A ] = Truth-hood[ A is false] = Truth-hood[ (A is false) is false ] = Truth-hood[ A is true ] = true            (equation 2)

Fun, isn’t it? Initially, via equation 1, we got the result that A is false. Now, via equation 2, we get the result that A is true. That is the paradox.

But the fun doesn’t stop there. It can continue. In fact, it can continue indefinitely. Let’s see how.

If only we were not to halt the expansions, i.e., if only we continue a bit further with the game, we could have just as well made one more expansion, and got to the following:

  • A: ((A is false) is false) is false.

The Truth-hood status of the immediately preceding expansion now is: false. Convince yourself that it is so. Hint: Always expand the inner-most parentheses first.

Homework 3: Convince yourself that what we get here is an indefinitely long alternating sequence of the Truth-hood statuses that: A is false, A is true, A is false, A is true

What can we say by way of a conclusion?

Conclusion: The truth-status of “A” is not uniquely decidable.

The emphasis is on the word “uniquely.”

We have used all the seemingly simple rules of logic, and yet have stumbled on to the result that, apparently, logic does not allow us to decide something uniquely or meaningfully.


Liar’s paradox and the set theory:

The importance of the liar paradox to our present concerns is this:

Godel himself believed, correctly, that the liar paradox was a semantic analogue to his Incompleteness Theorem [^].

Go read the Wiki article (or anything else on the topic) to understand why. For our purposes here, I will simply point out what the connection of the liar paradox is to the set theory, and then (more or less) call it a day. The key observation I want to make is the following:

You can think of every named statement as an instance of an ordered set.

What the above key observation does is to tie the symbolic logic of proposition with the set theory. We thus have three equivalent ways of describing the same idea: symbolic logic (name of a statement and its body), computer languages theory (non-terminals and their expansions to terminals), and set theory (the label of an ordered set and its enumeration).

As an aside, the set in question may have further properties, or further mathematical or logical structures and attributes embedded in itself. But at its minimal, we can say that the name of a named statement can be seen as a non-terminal, and the “body” of the statement (or the expansion rule) can be seen as an ordered set of some symbols—an arbitrarily specified sequence of some (zero or more) terminals and (zero or more) non-terminals.

Two clarifications:

  • Yes, in case there is no sequence in a production at all, it can be called the empty set.
  • When you have the same non-terminal on both sides of an expansion rule, it is said to form a recursion relation.

An aside: It might be fun to convince yourself that the liar paradox cannot be posed or discussed in terms of Venn’s diagram. The property of the “sheet” on which Venn’ diagram is drawn is, by some simple intuitive notions we all bring to bear on Venn’s diagram, cannot have a “recursion” relation.

Yes, the set theory itself was always “powerful” enough to allow for recursions. People like Godel merely made this feature explicit, and took full “advantage” of it.


Recursion, the continuum, and epistemological (and metaphysical) validity:

In our discussion above, I had merely asserted, without giving even a hint of a proof, that the three ways (viz., the symbolic logic of statements or  propositions, the computer languages theory, and the set theory) were all equivalent ways of expressing the same basic idea (i.e. the one which we are concerned about, here).

I will now once again make a few more observations, but without explaining them in detail or supplying even an indication of their proofs. The factoids I must point out are the following:

  • You can start with the natural numbers, and by using simple operations such as addition and its inverse, and multiplication and its inverse, you can reach the real number system. The generalization goes as: Natural to Whole to Integers to Rationals to Reals. Another name for the real number system is: the continuum.
  • You can use the computer languages theory to generate a machine representation for the natural numbers. You can also mechanize the addition etc. operations. Thus, you can “in principle” (i.e. with infinite time and infinite memory) represent the continuum in the CS terms.
  • Generating a machine representation for natural numbers requires the use of recursion.

Finally, a few words about epistemological (and metaphysical) validity.

  • The concepts of numbers (whether natural or real) have a logical precedence, i.e., they come first. The entire arithmetic and the calculus must come before does the computer-representation of some of their concepts.
  • A machine-representation (or, equivalently, a set-theoretic representation) is merely a representation. That is to say, it captures only some aspects or attributes of the actual concepts from maths (whether arithmetic or the continuum hypothesis). This issue is exactly like what we saw in the first and second posts in this series: a set is a concrete collection, unlike a concept which involves a consciously cast unit perspective.
  • If you try to translate the idea of recursion into the usual cognitive terms, you get absurdities such as: You can be your child, literally speaking. Not in the sense that using scientific advances in biology, you can create a clone of yourself and regard that clone to be both yourself and your child. No, not that way. Actually, such a clone is always your twin, not child, but still, the idea here is even worse. The idea here is you can literally father your own self.
  • Aristotle got it right. Look up the distinction between completed processes and the uncompleted ones. Metaphysically, only those objects or attributes can exist which correspond to completed mathematical processes. (Yes, as an extension, you can throw in the finite limiting values, too, provided they otherwise do mean something.)
  • Recursion by very definition involves not just absence of completion but the essence of the very inability to do so.

Closure on the “learnability issue”:

Homework 4: Go through the last two posts in this series as well as this one, and figure out that the only reason that the set theory allows a “recursive” relation is because a set is, by the design of the set theory, a concrete object whose definition does not have to involve an epistemologically valid process—a unit perspective as in a properly formed concept—and so, its name does not have to stand for an abstract mentally held unit. Call this happenstance “The Glaring Epistemological Flaw of the Set Theory” (or TGEFST for short).

Homework 5: Convince yourself that any lemma or theorem that makes use of Godel’s Incompleteness Theorem is necessarily based on TGEFST, and for the same reason, its truth-status is: it is not true. (In other words, any lemma or theorem based on Godel’s theorem is an invalid or untenable idea, i.e., essentially, a falsehood.)

Homework 6: Realize that the learnability issue, as discussed in Prof. Lev Reyzin’s news article (discussed in the first part of this series [^]), must be one that makes use of Godel’s Incompleteness Theorem. Then convince yourself that for precisely the same reason, it too must be untenable.

[Yes, Betteridge’s law [^] holds.]


Other remarks:

Remark 1:

As “asymptotical” pointed out at the relevant Reddit thread [^], the authors themselves say, in another paper posted at arXiv [^] that

While this case may not arise in practical ML applications, it does serve to show that the fundamental definitions of PAC learnability (in this case, their generalization to the EMX setting) is vulnerable in the sense of not being robust to changing the underlying set theoretical model.

What I now remark here is stronger. I am saying that it can be shown, on rigorously theoretical (epistemological) grounds, that the “learnability as undecidable” thesis by itself is, logically speaking, entirely and in principle untenable.

Remark 2:

Another point. My preceding conclusion does not mean that the work reported in the paper itself is, in all its aspects, completely worthless. For instance, it might perhaps come in handy while characterizing some tricky issues related to learnability. I certainly do admit of this possibility. (To give a vague analogy, this issue is something like running into a mathematically somewhat novel way into a known type of mathematical singularity, or so.) Of course, I am not competent enough to judge how valuable the work of the paper(s) might turn out to be, in the narrow technical contexts like that.

However, what I can, and will say is this: the result does not—and cannot—bring the very learnability of ANNs itself into doubt.


Phew! First, Panpsychiasm, and immediately then, Learnability and Godel. … I’ve had to deal with two untenable claims back to back here on this blog!

… My head aches….

… Code! I have to write some code! Or write some neat notes on ML in LaTeX. Only then will, I guess, my head stop aching so much…

Honestly, I just downloaded TensorFlow yesterday, and configured an environment for it in Anaconda. I am excited, and look forward to trying out some tutorials on it…

BTW, I also honestly hope that I don’t run into anything untenable, at least for a few weeks or so…

…BTW, I also feel like taking a break… May be I should go visit IIT Bombay or some place in konkan. … But there are money constraints… Anyway, bye, really, for now…


A song I like:

(Marathi) “hirvyaa hirvyaa rangaachi jhaaDee ghanadaaTa”
Music: Sooraj (the pen-name of “Shankar” from the Shankar-Jaikishan pair)
Lyrics: Ramesh Anavakar
Singers: Jaywant Kulkarni, Sharada


[Any editing would be minimal; guess I will not even note it down separately.] Did an extensive revision by 2019.01.21 23:13 IST. Now I will leave this post in the shape in which it is. Bye for now.

Learnability of machine learning is provably an undecidable?—part 2

Update on 23 January 2019, 17:55 IST:

In this series of posts, which was just a step further from the initial, brain-storming kind of a stage, I had come to the conclusion that based on certain epistemological (and metaphysical) considerations, Ben-David et al.’s conclusion (that learnability can be an undecidable) is logically untenable.

However, now, as explained here [^], I find that this particular conclusion which I drew, was erroneous. I now stand corrected, i.e., I now consider Ben-David et al.’s result to be plausible. Obviously, it merits a further, deeper, study.

However, even as acknowledging the above-mentioned mistake, let me also hasten to clarify that I still stick to my other positions, especially the central theme in this series of posts. The central theme here was that there are certain core features of the set theory which make implications such as Godel’s incompleteness theorems possible. These features (of the set theory) demonstrably carry a glaring epistemological flaw such that applying Godel’s theorem outside of its narrow technical scope in mathematics or computer science is not permissible. In particular, Godel’s incompleteness theorem does not apply to knowledge or its validation in the more general sense of these terms. This theme, I believe, continues to hold as is.

Update over.


In this post, we look into the differences of the idea of sets from that of concepts. The discussion here is exploratory, and hence, not very well isolated. There are overlaps of points between sections. Indeed, there are going to be overlaps of points from post to post too! The idea behind this series of posts is not to present a long thought out and matured point of view; it is much in the nature of jotting down salient points and trying to bring some initial structure to them. Thus the writing in this series is just a step further from the stage of brain-storming, really speaking.

There is no direct discussion in this post regarding the learnability issue at all. However, the points we note here are crucial to understanding Godel’s incompleteness theorem, and in that sense, the contents of this post are crucially important in framing the learnability issue right.

Anyway, let’s get going over the differences of sets and concepts.


A concept as an abstract unit of mental integration:

Concepts are mental abstractions. It is true that concepts, once formed, can themselves be regarded as mental units, and qua units, they can further be integrated together into even higher-level concepts, or possibly sub-divided into narrower concepts. However, regardless of the level of abstraction at which a given concept exists, the concretes being subsumed under it are necessarily required to be less abstract than the single mental unit that is the concept itself.

Using the terms of computer science, the “graph” of a concept and its associated concrete units is not only acyclic and directional (from the concretes to the higher-level mental abstraction that is the concept), its connections too can be drawn if and only if the concretes satisfy the rules of conceptual commensurability.

A concept is necessarily a mental abstraction, and as a unit of mental integration, it always exists at a higher level of abstraction as compared to the units it subsumes.


A set as a mathematical object that is just a concrete collection:

Sets, on the other hand, necessarily are just concrete objects in themselves, even if they do represent collections of other concrete objects. Sets take birth as concrete objects—i.e., as objects that don’t have to represent any act of mental isolation and integration—and they remain that way till the end of their life.

For the same reason, set theory carries absolutely no rules whereby constraints can be placed on combining sets. No meaning is supposed to be assigned to the very act of placing braces around the rule which defines admissibility of objects as members into a set (or that of enumeration of their member objects).

The act of creating the collection that is a set is formally allowed to proceed even in the absence of any preceding act of mental differentiations and integrations.

This distinction between these two ideas, the idea of a concept, and that of a set, is important to grasp.


An instance of a mental abstraction vs. a membership into a concrete collection:

In the last post in this series, I had used the terminology in a particular way: I had said that there is a concept “table,” and that there is a set of “tables.” The plural form for the idea of the set was not a typo; it was a deliberate device to highlight this same significant point, viz., the essential concreteness of any set.

The mathematical theory of sets didn’t have to be designed this way, but given the way it anyway has actually been designed, one of the inevitable implications of its conception—its very design—has been this difference which exists between the ideas of concepts and sets. Since this difference is extremely important, it may be worth our while to look at it from yet another viewpoint.

When we look at a table and, having already had reached the concept of “table” we affirm that the given concrete table in front of us is indeed a table, this seemingly simple and almost instantaneously completed act of recognition itself implicitly involves a complex mental process. The process includes invoking a previously generated mental integration—an integration which was, sometime in the past, performed in reference to those attributes which actually exist in reality and which make a concrete object a table. The process begins with the availability of this context as a pre-requisite, and now involves an application of the concept. It involves actively bringing forth the pre-existing mental integration, actively “see” that yet another concrete instance of a table does indeed in reality carry the attributes which make an object a table, and thereby concluding that it is a table.

In other words, if you put the concept table symbolically as:

table = { this table X, that table Y, now yet another table Z, … etc. }

then it is understood that what the symbol on the left hand side stands for is a mental integration, and that each of the concrete entities X, Y, Z, etc. appearing in the list on the right hand-side is, by itself, an instance corresponding to that unit of mental integration.

But if you interpret the same “equation” as one standing for the set “tables”, then strictly speaking, according to the actual formalism of the set theory itself (i.e., without bringing into the context any additional perspective which we by habit do, but sticking strictly only to the formalism), each of the X, Y, Z etc. objects remains just a concrete member of a merely concrete collection or aggregate that is the set. The mental integration which regards X, Y, Z as equally similar instances of the idea of “table” is missing altogether.

Thus, no idea of similarity (or of differences) among the members at all gets involved, because there is no mental abstraction: “table” in the first place. There are only concrete tables, and there is a well-specified but concrete object, a collective, which is only formally defined to be stand for this concrete collection (of those specified tables).

Grasp this difference, and the incompleteness paradox brought forth by Godel begins to dissolve away.


The idea of an infinite set cuts out the preceding theoretical context:

Since the aforementioned point is complex but important, there is no risk in repeating (though there could be boredom!):

There is no place-holder in the set theory which would be equivalent to saying: “being able to regard concretes as the units of an abstract, singular, mental perspective—a perspective reached in recognition of certain facts of reality.”

The way set theory progresses in this regard is indeed extreme. Here is one way to look at it.

The idea of an infinite set is altogether inconceivable before you first have grasped the concept of infinity. On the other hand, grasping the concept of infinity can be accomplished without any involvement of the set theory anyway—formally or informally. However, since every set you actually observe in the concrete reality can only be finite, and since sets themselves are concrete objects, there is no way to conceive of the very idea of an infinite sets, unless you already know what infinity means (at least in some working, implicit, sense). Thus, to generate the concrete members contained in the given infinite set, you of course need the conceptual knowledge of infinite sequences and series.

However, even if the set theory must use this theoretical apparatus of analysis, the actual mathematical object it ends up having still captures only the “concrete-collection” aspect of it—none other. In other words, the set theory drops from its very considerations some of the crucially important aspects of knowledge with which infinite sets can at all be conceived of. For instance, it drops the idea that the infinite set-generating rule is in itself an abstraction. The set theory asks you to supply and use that rule. The theory itself is merely content in being supplied some well-defined entities as the members of a set.

It is at places like this that the infamous incompleteness creeps into the theory—I mean, the theory of sets, not the theory that is the analysis as was historically formulated and practiced.


The name of a set vs. the word that stands for a concept:

The name given to a set (the symbol or label appearing on the left hand-side of the equation) is just an arbitrary and concrete a label; it is not a theoretical place-holder for the corresponding mental concept—not so long as you remain strictly within the formalism, and therefore, the scope of application of, the set theory.

When they introduce you to the set theory in your high-school, they take care to choose each of the examples only such a way that there always is an easy-to-invoke and well-defined concept; this per-existing concept can then be put into a 1:1 correspondence with the definition of that particular set.

But if you therefore begin thinking that there is a well-defined concept for each possible instance of a set, then such a characterization is only a figment of your own imagination. An idea like this is certainly not to be found in the actual formalism of the set theory.

Show me the place in the axioms, or their combinations, or theorems, or even just lemmas or definitions in the set theory where they say that the label for a set, or the rule for formation of a set, must always stand for a conceptually coherent mental integration. Such an idea is simply absent from the mathematical theory.

The designers of the set theory, to put it directly, simply didn’t have the wits to include such ideas in their theory.


Implications for the allowed operations:

The reason why the set theory allows for any arbitrary operands (including those which don’t make any sense in the real world) is, thus, not an accident. It is a direct consequence of the fact that sets are, by design, concrete aggregates, not mental integrations based on certain rules of cognition (which in turn must make a reference to the actual characteristics and attributes possessed by the actually existing objects).

Since sets are mere aggregations, not integrations, as a consequence, we no longer remain concerned with the fact that there have to be two or more common characteristics to the concrete objects being put together, or with the problem of having to pick up the most fundamental one among them.

When it comes to sets, there are no such constraints on the further manipulations. Thus arises the possibility of being apply any operator any which way you feel like on any given set.


Godel’s incompleteness theorem as merely a consequence:

Given such a nature of the set theory—its glaring epistemological flaws—something like Kurt Godel’s incompleteness theorem had to arrive in the scene, sooner or later. The theorem succeeds only because the set theory (on which it is based) does give it what it needs—viz., a loss of a connection between a word (a set label) and how it is meant to be used (the contexts in which it can be further used, and how).


In the next part, we will reiterate some of these points by looking at the issue of (i) systems of axioms based on the set theory on the one hand, and (ii) the actual conceptual body of knowledge that is arithmetic, on the other hand. We will recast the discussion so far in terms of the “is a” vs. the “has a” types of relationships. The “is a” relationship may be described as the “is an instance of a mental integration or concept of” relationship. The “has a” relationship may be described as “is (somehow) defined (in whatever way) to carry the given concrete” type of a relationship. If you are curious, here is the preview: concepts allow for both types of relationships to exist; however, for defining a concept, the “is an instance or unit of” relationship is crucially important. In contrast, the set theory requires and has the formal place for only the “has a” type of relationships. A necessary outcome is that each set itself must remain only a concrete collection.

 

On whether A is not non-A

This post has its origin in a neat comment I received on my last post [^]; see the exchange starting here: [^].


The question is whether I accept that A is not non-A.

My answer is: No, I do not accept that, logically speaking, A is not non-A—not unless the context to accept this statement is understood clearly and unambiguously (and the best way to do that is to spell it out explicitly).

Another way to say the same thing is that I can accept that “A is not non-A,” but only after applying proper qualifications; I won’t accept it in an unqualified way.

Let me explain by considering various cases arising, using a simple example.


The Venn diagram:

Let’s begin by drawing a Venn diagram.

Draw a rectangle and call it the set R. Draw a circle completely contained in it, and call it the set A. You can’t put a round peg to fill a rectangular hole, so, the remaining area of the rectangle is not zero. Call the remaining area B. See the diagram below.

The Venn Diagram

Case 1: All sets are non-empty:

Assume that neither A nor B is empty. Using symbolic terms, we can say that:
A \neq \emptyset,
B \neq \emptyset, and
R \equiv A \cup B
where the symbol \emptyset denotes an empty set, and \equiv means “is defined as.”

We take R as the universal set—of this context. For example, R may represent, say the set of all the computers you own, with A denoting your laptops and B denoting your desktops.

I take the term “proper set” to mean a set that has at least one element or member in it, i.e., a set which is not empty.

Now, focus on A. Since the set A is a proper set, then it is meaningful to apply the negation- or complement-operator to it. [May be, I have given away my complete answer right here…] Denote the resulting set, the non-A, as A^{\complement }. Then, in symbolic terms:
A^{\complement } \equiv R \setminus A.
where the symbol \setminus denotes taking the complement of the second operand, in the context of the first operand (i.e., “subtracting” A from R). In our example,
A^{\complement } = B,
and so:
A^{\complement } \neq \emptyset.
Thus, here, A^{\complement } also is a proper (i.e. non-empty) set.

To conclude this part, the words “non-A”, when translated into symbolic terms, means A^{\complement }, and this set here is exactly the same as B.

To find the meaning of the phrase “not non-A,” I presume that it means applying the negation i.e. the complement operator to the set A^{\complement }.

It is possible to apply the complement operator because A ^{\complement } \neq \emptyset. Let us define the result of this operation as A^{\complement \complement}; note the two ^{\complement}s appearing in its name. The operation, in symbols becomes:
A^{\complement \complement} \equiv R \setminus A^{\complement} = R \setminus B = A.
Note that we could apply the complement operator to A and later on to A^{\complement} only because each was non-empty.

As the simple algebra of the above simple-minded example shows,
A = A^{\complement\complement},
which means, we have to accept, in this example, that A is not non-A.

Remarks on the Case 1:

However, note that we can accept the proposition only under the given assumptions.

In  particular, in arriving at it, we have applied the complement-operator twice. (i) First, we applied it to the “innermost” operand i.e. A, which gave us A^{\complement}. (ii) Then, we took this result, and applied the complement-operator to it once again, yielding A^{\complement\complement}. Thus, the operand for the second complement-operator was A^{\complement}.

Now, here is the rule:

Rule 1: We cannot meaningfully apply the complement-operator unless the operand set is proper (i.e. non-empty).

People probably make mistakes in deciding whether A is not non-A, because, probably, they informally (and properly) do take the “innermost” operand, viz. A, to be non-empty. But then, further down the line, they do not check whether the second operand, viz. A^{\complement} turns out to be empty or not.

Case 2: When the set A^{\complement} is empty:

The set A^{\complement} will be empty if B = \emptyset, which will happen if and only if A = R. Recall, R is defined to be the union of A and B.

So, every time there are two mutually exclusive and collectively exhaustive sets, if any one of them is made empty, you cannot doubly apply the negation or the complement operator to the other (nonempty) set.

Such a situation always occurs whenever the remaining set coincides with the universal set of a given context.

In attempting a double negation, if your first (or innermost) operand itself is a universal set, then you cannot apply the negation operator for the second time, because by Rule 1, the result of the first operator comes out as an empty set.


The nature of an empty set:

But why this rule that you can’t negate (or take the complement of) an empty set?

An empty set contains no element (or member). Since it is the elements which together impart identity to a set, an empty set has no identity of its own.

As an aside, some people think that all the usages of the phrase “empty set” refers to the one and the only set (in the entire universe, for all possible logical propositions involving sets). For instance, the empty set obtained by taking an intersection of dogs and cats, they say, is exactly the same empty set as the one obtained by taking an intersection of cars and bikes.

I reject this position. It seems to me to be Platonic in nature, and there is no reason to give Plato even an inch of the wedge-space in this Aristotlean universe of logic and reality.

As a clarification, notice, we are talking of the basic and universal logic here, not the implementation details of a programming language. A programming language may choose to point all the occurrences of the NULL string to the same memory location. This is merely an implementation choice to save on the limited computer memory. But it still makes no sense to say that all empty C-strings exist at the same memory location—but that’s what you end up having if you call an empty set the empty set. Which brings us to the next issue.

If an empty set has no identity of its own, if it has no elements, and hence no referents, then how come it can at all be defined? After all, a definition requires identity.

The answer is: Structurally speaking, an empty set acquires its meaning—its identity—“externally;” it has no “internally” generated identity.

The only identity applicable to an empty set is an abstract one which gets imparted to it externally; the purpose of this identity is to bring a logical closure (or logical completeness) to the primitive operations defined on sets.

For instance, intersection is an operator. To formally bring closure to the intersection operation, we have to acknowledge that it may operate over any combination of any operand sets, regardless of their natures. This range includes having to define the intersection operator for two sets that have no element in common. We abstractly define the result of such a case as an empty set. In this case, the meaning of the empty set refers not to a result set of a specific internal identity, but only to the operation and the disjoint nature the operands which together generated it, i.e., via a logical relation whose meaning is external to the contents of the empty set.

Inasmuch as an empty set necessarily includes a reference to an operation, it is a concept of method. Inasmuch as many combinations of various operations and operands can together give rise to numerous particular instances of an empty set, there cannot be a unique instance of it which is applicable in all contexts. In other words, an empty set is not a singleton; it is wrong to call it the empty set.

Since an empty set has no identity of its own, the notion cannot be applied in an existence-related (or ontic or metaphysical) sense. The only sense it has is in the methodological (or epistemic) sense.


Extending the meaning of operations on an empty set:

In a derivative sense, we may redefine (i.e. extend) our terms.

First, we observe that since an empty set lacks an identity of its own, the result of any operator applied to it cannot have any (internal) identity of its own. Then, equating these two lacks of existence-related identities (which is where the extension of the meaning occurs), we may say, even if only in a derivative or secondary sense, that

Rule 2: The result of an operator applied to an empty set again is another empty set.

Thus, if we now allow the complement-operator to operate also on an empty set (which, earlier, we did not allow), then the result would have to be another empty set.

Again, the meaning of this second empty set depends on the entirety of its generating context.

Case 3: When the non-empty set is the universal set:

For our particular example, assuming B = \emptyset and hence A = R, if we allow complement operator to be applied (in the extended sense) to A^{\complement}, then

A^{\complement\complement} \equiv R \setminus A^{\complement} = R \setminus (R \setminus A) = R \setminus B = R \setminus (\emptyset) = R = A.

Carefully note, in the above sequence, the place where the extended theory kicks in is at the expression: R \setminus (\emptyset).

We can apply the \setminus operator here only in an extended sense, not primary.

We could here perform this operation only because the left hand-side operand for the complement operator, viz., the set R here was a universal set. Any time you have a universal set on the left hand-side of a complement operator, there is no more any scope left for ambiguity. This state is irrespective of whether the operand on the right hand-side is a proper set or an empty set.

So, in this extended sense, feel free to say that A is not non-A, provided A is the universal set for a given context.


To recap:

The idea of an empty set acquires meaning only externally, i.e., only in reference to some other non-empty set(s). An empty set is thus only an abstract place-holder for the result of an operation applied to proper set(s), the operation being such that it yields no elements. It is a place-holder because it refers to the result of an operation; it is abstract, because this result has no element, hence no internally generated identity, hence no concrete meaning except in an abstract relation to that specific operation (including those specific operands). There is no “the” empty set; each empty set, despite being abstract, refers to a combination of an instance of proper set(s) and an instance of an operation giving rise to it.


Exercises:

E1: Draw a rectangle and put three non-overlapping circles completely contained in it. The circles respectively represent the three sets A, B, C, and the remaining portion of the rectangle represents the fourth set D. Assuming this Venn diagram, determine the meaning of the following expressions:

(i) R \setminus (B \cup C) (ii) R \setminus (B \cap C) (iii) R \setminus (A \cup B \cup C) (iv) R \setminus (A \cap B \cap C).

(v)–(viii) Repeat (i)–(iv) by substituting D in place of R.

(ix)–(xvi) Repeat (i)–(viii) if A and B partly overlap.

E2: Identify the nature of set theoretical relations implied by that simple rule of algebra which states that two negatives make a positive.


A bit philosophical, and a form better than “A is not non-A”:

When Aristotle said that “A is A,” and when Ayn Rand taught its proper meaning: “Existence is identity,” they referred to the concepts of “existence” and “identity.” Thus, they referred to the universals. Here, the word “universals” is to be taken in the sense of a conceptual abstraction.

If concepts—any concepts, not necessarily only the philosophical axioms—are to be represented in terms of the set theory, how can we proceed doing that?

(BTW, I reject the position that the set theory, even the so-called axiomatic set theory, is more fundamental than the philosophic abstractions.)

Before we address this issue of representation, understand that there are two ways in which we can specify a set: (i) by enumeration, i.e. by listing out all its (relatively concrete) members, and (ii) by rule, i.e. by specifying a definition (which may denote an infinity of concretes of a certain kind, within a certain range of measurements).

The virtue of the set theory is that it can be applied equally well to both finite sets and infinite sets.

The finite sets can always be completely specified via enumeration, at least in principle. On the other hand, infinite sets can never be completely specified via enumeration. (An infinite set is one that has an infinity of members or elements.)

A concept (any concept, whether of maths, or art, or engineering, or philosophy…) by definition stands for an infinity of concretes. Now, in the set theory, an infinity of concretes can be specified only using a rule.

Therefore, the only set-theoretic means capable of representing concepts in that theory is to specify their meaning via “rule” i.e. definition of the concept.

Now, consider for a moment a philosophical axiom such as the concept of “existence.” Since the only possible set-theoretic representation of a concept is as an infinite set, and since philosophical axiomatic concepts have no antecedents, no priors, the set-theoretic representation of the axiom of “existence” would necessarily be as a universal set.

We saw that the complement of a universal set is an empty set. This is a set-theoretic conclusion. Its broader-based, philosophic analog is: there are no contraries to axiomatic concepts.

For the reasons explained above, you may thus conclude, in the derivative sense, that:

“existence is not void”,

where “void” is taken as exactly synonymous to “non-existence”.

The proposition quoted in the last sentence is true.

However, as the set theory makes it clear and easy to understand, it does not mean that you can take this formulation for a definition of the concept of existence. The term “void” here has no independent existence; it can be defined only by a negation of existence itself.

You cannot locate the meaning of existence in reference to void, even if it is true that “existence is not void”.

Even if you use the terms in an extended sense and thereby do apply the “not” qualfier (in the set-theoretic representation, it would be an operator) to the void (to the empty set), for the above-mentioned reasons, you still cannot then read the term “is” to mean “is defined as,” or “is completely synonymous with.” Not just our philosophical knowledge but even its narrower set-theoretical representation is powerful enough that it doesn’t allow us doing so.

That’s why a better way to connect “existence” with “void” is to instead say:

“Existence is not just the absence of the void.”

The same principle applies to any concept, not just to the most fundamental philosophic axioms, so long as you are careful to delineate and delimit the context—and as we saw, the most crucial element here is the universal set. You can take a complement of an empty set only when the left hand-side operator is a universal set.

Let us consider a few concepts, and compare putting them in the two forms:

  • from “A is not non-A”
  • to “A is not the [just] absence [or negation] of non-A,” or, “A is much more than just a negation of the non-A”.

Consider the concept: focus. Following the first form, a statement we can formulate is:

“focus is not evasion.”

However, it does make much more sense to say that

“focus is not just an absence of evasion,” or that “focus is not limited to an anti-evasion process.”

Both these statements follow the second form. The first form, even if it is logically true, is not as illuminating as is the second.

Exercises:

Here are a few sentences formulated in the first form—i.e. in the form “A is not non-A” or something similar. Reformulate them into the second form—i.e. in the form such as: “A is not just an absence or negation of non-A” or “A is much better than or much more than just a complement or negation of non-A”. (Note: SPPU means the Savitribai Phule Pune University):

  • Engineers are not mathematicians
  • C++ programmers are not kids
  • IISc Bangalore is not SPPU
  • IIT Madras is not SPPU
  • IIT Kanpur is not SPPU
  • IIT Bombay is not SPPU
  • The University of Mumbai is not SPPU
  • The Shivaji University is not SPPU

[Lest someone from SPPU choose for his examples the statements “Mechanical Engg. is not Metallurgy” and “Metallurgy is not Mechanical Engg.,” we would suggest him another exercise, one which would be better suited to the universal set of all his intellectual means. The exercise involves operations mostly on the finite sets alone. We would ask him to verify (and not to find out in the first place) whether the finite set (specified with an indicative enumeration) consisting of {CFD, Fluid Mechanics, Heat Transfer, Thermodynamics, Strength of Materials, FEM, Stress Analysis, NDT, Failure Analysis,…} represents an intersection of Mechanical Engg and Metallurgy or not.]

 


A Song I Like:

[I had run this song way back in 2011, but now want to run it again.]

(Hindi) “are nahin nahin nahin nahin, nahin nahin, koee tumasaa hanseen…”
Singers: Kishore Kumar, Asha Bhosale
Music: Rajesh Roshan
Lyrics: Anand Bakshi

[But I won’t disappoint you. Here is another song I like and one I haven’t run so far.]

(Hindi) “baaghon mein bahaar hain…”
Music: S. D. Burman [but it sounds so much like R.D., too!]
Singers: Mohamad Rafi, Lata Mangeshkar
Lyrics: Anand Bakshi

[Exercise, again!: For each song, whenever a no’s-containing line comes up, count the number of no’s in it. Then figure out whether the rule that double negatives cancel out applies or not. Why or why not?]


 

[Mostly done. Done editing now (right on 2016.10.22). Drop me a line if something isn’t clear—logic is a difficult topic to write on.]

[E&OE]