Axiom of Regularity and AFA theorem decidability

Written by  on April 5, 2011

Below are some thoughts I had in relation to an e-mail discussion where the following question arose: What is a representation? The arching context of this discussion was a seminar exploring the psychological theory that feelings are a form of self-perception. I.e. if self-perception theory is true, this would explain the abundance of clinical evidence showing that feelings follow behaviors rather than preceding them.

In any case, the group has a large contingent of technical types and the discussion of representation eventually raised the question of the difference between processes and things, verbs and nouns, [en|de]coders and an encoding, or code and data. The underlying itch seems to be the concept of self-modifying processes or, in computer science terms, code as data and data as code. It seemed to me the holistic thinkers see an aspect to living things, organisms, that is not present in machines. (This inarticulate distinction isn’t new, of course. Great minds have been trying to tease them apart for millenia. And my puny mind won’t add anything to what they’ve already done. But this blog has gotten a bit stale; so I must post something.)

The group seemed to have stalled at the ontological status of a representation. Such a thing seems to have an autonomy all on its own. For example, if you scratch an image of your grandmother into a piece of granite, then humanity goes extinct, do those scratches on the granite still represent your grandmother? Or are they then just meaningless scratches on a rock? To what extent is the decoding process required for an encoded artifact to still be meaningful?

Anyway, this obviously raises all sorts of questions for anyone who likes to think deeply or completely. But the (shallow and incomplete) question it raises to me is fairly common to all the philosophical problems I think about: circular reference. In logic, an impredicative definition is one that defines an object using a quantification over all the other objects like the object being defined. In other words, it’s a self-referencing definition. It’s im-predicative simply because it’s not predicative. In the foundations of math, it boils down to von Neumann’s Axiom of Regularity, which states that sets cannot have elements that, when cracked open, contain elements present anywhere in the cumulative hierarchy of sets above them. In other words, the set hierarchy cannot contain loops.

It seems to me that an organism, and in particular those of us who are capable of using symbols to communicate with one another, is impredicatively defined in terms of its environment. The symbols used are in constant redefinition as the organism and its environment evolve. Hence, any representation, e.g. of the environment by the organism or of the organism by the environment, will be self-referential and inseparable from its context.

So, this leads me to ask why we ascribe ontological status to representations? Why do we think the image of a grandmother scratched into a rock will persist as a representation? I think the answer lies in how we count, which is (probably) based on the fact that we have fingers, digits. We count ordinally: 1, 2, 3 …. And because we do so, our intuitive concept of numbers and sets of things is constructive. Abstractly, math is about grammar, sentences, consistency, and completeness. But concretely, math is about how we relate large bunches of things to small bunches of things, 100 cows to 10 bails of hay, 10 fingers to a billion stars, etc.

When considering these relationships, abstract or concrete, various problems arise like how to represent nothing, the result of taking away 6 cows from a total of 6 cows to give you no cows. How does one represent no cows? Infinity and density are other such problems. What lies after the largest number to which you can count? What lies between two very close numbers? Etc.

In the course of handling some of these issues, von Neumann formulated a constraint (regularity) to avoid unconstructable, cyclic set hierarchies. Later, Turing came up with the “halting problem”: given a step-by-step procedure, decide whether the procedure halts or continues forever. These sorts of problem obviously depend critically on construction. Whether you can tell if a procedure will halt depends on whether and how it can be constructed.

It is this sense of constructability and automatic deduction (no consciousness required), that I think leads to ascribing more ontological status to representations/encodings than is objectively warranted. Another interesting twist arises because so many people use the computer as a metaphor for organisms, the hardware is likened to the body and the software is likened to the mind. But again, this metaphor raises the hackles of those who think organisms are categorically different from machines.

We can seamlessly use the term “representation” to mean a thought in the mind of an organism and an encoding in the software of a machine. But the character of the term changes between the two usages. Saying “the computer uses a representation of your grandmother” is very different to an ordinary layperson than saying “you have a representation of your grandmother in your mind”.

Perhaps this goes back to the axiom of regularity in that the most common modern computer architecture is the von Neumann architecture, where the CPU (process) is categorically distinct from the memory (objects) upon which it operates. These modern computers function by counting, constructing one state from previous states. That separation between the CPU and the memory disallows cyclic sets. At any given time, the objects in the memory can be enumerated, which would not be true without the axiom of regularity. No register can be a member of itself.

Of course, we can simulate circularity by first enumerating some of the set, then moving the CPU pointer back to a register it already finished reading and letting it read again from that same register. But this is not a circular or impredicative definition because at any particular time, the memory is completely, acyclically, enumerable. I take this to imply that a von Neumann architecture is incapable of realizing a non-well-founded set.

Of course, I’m not really a mathematician and I’m certainly not a meta-mathematician. So, my intuition and/or reasoning could be completely off. One discussant pointed out that an alternative set of axioms, called AFA (Anti-Foundation Axiom, which refers to the ZFC without the axiom of regularity plus the anti-foundation axiom) is just as consistent as ZFC (Zermelo-Fraenkel plus the Axiom of Choice). And others[1] point out that AFA and ZFC are shown to be “mutually interpretable”. So, perhaps this means that a sentence in AFA, involving a cyclic set (not possible in ZFC), can be “constructed” by first transforming the sentence into some equivalent in ZFC, constructing that in the normal way, then transforming it back. This would mean that a von Neumann architecture machine, although based in the intuitive counting-based construction with which we’re familiar, would still be able to compute AFA sentences … kinda like transforming a problem from the time domain into the frequency domain, solving it there, and transforming it back. I don’t know. But it sure seems suspicious to me.

In any case, perhaps my suspicion is evidence that I’ve bought into the false dichotomy von Neumann so insidiously implanted in our modern, digitally myopic minds? Perhaps representations (or symbols, in general) really do become entirely meaningless when violently torn from their context?

[1] http://research.microsoft.com/pubs/70350/tr-2006-138.pdf