## Supervenience in mathematics

I'm not quite sure if this is the right place to ask, and if this is the right way to ask, but I dare.

In philosophy (of mind, e.g.) the concept of supervenience is used:

"Supervenience [is] used to describe relationships between sets of properties in a manner which does not imply a strong reductive relationship."

That means an object might possess higher properties that depend on some base properties, but cannot be reduced to (defined by) them.

My question is: Can this situation occur in mathematics?

As I see it, for every mathematical object - be it a set with a structure or a vertex in an abstract graph or an object in a category - all its (relevant) properties are determined by its inner structure or its relations/morphisms to other objects. To me it seems unconceivable that a mathematical object can have any extra properties, let alone in a supervenient manner, that is, two isomorphic objects would have to share them.

But maybe I'm wrong. Can anyone point me to an example?

-
Disregarding the quote in your post, which provides more of an example for how philosophers' language could profit from some clarity or at least some well-defined terminology, the notion of "supervenience" as defined in Wikipedia has plenty of applications in mathematics. For example, Tannaka duality is about in how far an algebraic group is determined by its category of representations. – darij grinberg Jan 6 2011 at 12:14
What about the answers to mathoverflow.net/questions/10993/… ? Isn't it supervenience if you can prove an equivalence abstractly (and so definable in terms of low-level properties) but not calculate anything? – Daniel Moskovich Jan 6 2011 at 12:59
I don't see the point of having this discussion until someone provides a clearer and more precise definition of supervenience. – Qiaochu Yuan Jan 6 2011 at 14:00
@Joel: all the more reason for this discussion not to take place on MO, then! – Qiaochu Yuan Jan 6 2011 at 15:19
Well, I'm sorry you feel that way. I view philosophical questions about the foundations of mathematics, particularly those involving a technical concept, as on-topic for MO. My objection to your remark above is that there are dozens of competing precise proposals for the meaning of supervenience. Perhaps the situation is like the use of the terms "explicit" or "canonical", often used on MO in vague ways, even though these terms have a variety of competing precise formulations. But these terms, like "supervenience", have a mathematical nature that can be usefully discussed by mathematicians. – Joel David Hamkins Jan 6 2011 at 15:49
show 11 more comments

I want to try another answer, not because I think you will necessarily accept it, but because if you don't then I think your reasons for not doing so will clarify the question.

One definition of supervenience is that A supervenes on B if you can't have a change to A without a change to B. For instance, some people hold that the mind supervenes on the physical properties of the brain because you could not have two distinct mental states arising from brains that were physically identical. (Others dispute this, but that does not matter here.)

Now consider the halting property. That clearly supervenes on the specification of the given Turing machine (encoded as a sequence of 0s and 1s, say), since if one Turing machine halts and another doesn't, then they can't have identical specifications. But it's not clear that there's any sense in which the property of halting or otherwise is reducible to the specification of the Turing machine.

-
To support your final point, consider that one may write down a specific Turing machine program for which the question of whether that program halts or not depends on the set-theoretic universe in which this question is asked. Thus, the question of halting or not depends not just on the program itself, but on the nature of the set-theoretic universe. The program is simply the program that searches for a contradiction in ZFC. (Or some other strong theory, such as ZFC+large cardinals, if one prefers.) – Joel David Hamkins Jan 8 2011 at 18:25
@Timothy: I have to accept this answer, because it hits the bull's eye. That's exactly the direction in which I proceeded thinking. I'll come up with a related question, soon. Thank you for having tried to understand! (Also to Joel and Todd!) – Hans Stricker Jan 8 2011 at 21:51
@Timothy: Please have a look at this question: mathoverflow.net/questions/51506/… – Hans Stricker Jan 9 2011 at 0:23
@Joel: Whether such a program halts or not does not depend on the set-theoretic universe in which this question is asked in the nontrivial sense you seem to be implying; "T is true of the ambient set-theoretic universe" and "T has no contradictions (according to the ambient set-theoretic universe)" are hardly the same thing. – Sridhar Ramesh Jun 23 2011 at 21:18

I think that an interesting phenomenon analogous to the relation of informal mathematics to its set theoretical foundations described by Joel David Hamkins is the relation between those meta-arithmetical notions, theorems, and proofs that we formulate by the help of Gödel numbering. Actually, it is a perplexing fact that we can establish the truth of arithmetical theorems without having the faintest idea of their arithmetical content. For example, we know that the Gödel sentence of a consistent theory is true. The statement carrying this metamathematical content is actually a sentence of the language of arithmetic. But, obviously, its arithmetical content is incomprehensible by any human being.

-

To my way of thinking, the most natural example of supervenience in mathematics---and the most similar to how this term is used in the philosophy of mind, where one uses it to describe the relation of the higher order properties, such as features of the mind, to the lower order properties, such as molecular structures in the brain---is provided by the sense in which set theory is viewed as forming a foundation for mathematics.

On that view of the foundations of mathematics (and there are many other views), the set-theoretic universe is seen to provide an ontological foundation for mathematics, in the sense that every mathematical object is regarded fundamentally as a set. One builds the natural numbers from sets as ordinals and then the integers and the rationals and the reals in any of the usual set-theoretic constructions; a group is a set with a binary operation (a set) having certain properties; a topological space is a set together with a set of subsets having a certain nature; and so on. On this view, every mathematical object is regarded as a set and the context of set theory is taken to provide a common forum in which to treat mathematical objects and constructions from what would otherwise be diverse forums. The existence of such a common forum allows us sensibly to apply knowledge from one area of mathematics to arguments in a distantly related area, and this is important.

So the view is that the basic features of the reals or of any mathematical object ultimately reduce to set theory in the sense that that object is fundamentally a set. But meanwhile, although this reduction of mathematics to set theory is important foundationally (and there are resulting a number of intriguing or even startling conclusions about ZFC-independence and paradox in non-set-theoretic contexts), the main view is also that the set-theoretic reduction is largely irrelevant for ordinary mathematics. We don't want to undertake most arguments in number theory or algebraic geometry or whatever with constant reference to the complete set-theoretic reduction of the subject, for example, by speaking of the "elements" of $\pi$. Thus, mathematics can be seen to reduce to set theory, but for most higher level mathematics, this reduction is either very complicated or not seen as illuminating of the interesting mathematical phenomenon at hand.

This relation seems very similar to the relation between our current understanding of mental properties and molecular structures in the brain. In principle, we believe that there is a reduction, but that reduction is either very complicated or not particularly illuminating of the mental phenomenon. We seem to fulfill the following analogy:

       Higher-order                             Higher-order
mental features                        mathematical objects
and properties                            and relations
-----------------                       ------------------
molecular structure                         sets and the
of the brain                           membership relation


So this situation seems to accord accurately with your description of supervenience.

Addendum. Let me also mention another sense of supervenience, related to the point made by Gowers, in his second paragraph. The truth of a universal statement $\forall n\ \varphi(n)$ in arithmetic, say, reduces to the instances $\varphi(0), \varphi(1),\varphi(2)$, and so on. But by the Compactness theorem, one cannot prove the universal statement merely from those assertions in first order logic. Thus, the truth of $\forall n\ \varphi(n)$ would seem to supervene on those instances in the sense of the question. We don't prove a universal statement by proving each instance separately.

-
 Please see my answer to your comment on my question. – Hans Stricker Jan 6 2011 at 13:35 @Joel: Please have a look at this question: mathoverflow.net/questions/51506/… – Hans Stricker Jan 9 2011 at 0:24

To me it seems unconceivable that a mathematical object can have any extra properties, let alone in a supervenient manner, that is, two isomorphic objects would have to share them.

I first of all agreed that mathematics should be like that, but the potential counterexample that sprang to mind is set theory, specifically membership-based set theory with urelements.

By "membership-based set theory", I mean the traditional sort of set theory like ZF which is based on a membership relation $\in$; I do not mean a structural or categorical set theory like Lawvere's Elementary Theory of the Category of Sets. This comes to mind because two sets that are "isomorphic", which in the first instance might mean there is a bijection between them, may have very different set-theoretic properties; for example they may have different ranks.

Upon further reflection, I felt this notion of isomorphism as bijection could be a loaded way to interpret "relation to other objects" and that one should look further to the structure of membership trees. Are two sets with the same inner structure (i.e., that have isomorphic membership trees) distinguishable as sets? In ordinary ZF, I believe one can prove by recursion that two sets with isomorphic membership trees are in fact equal. But this is not the case in a set theory with urelements. If we permit ordinary objects to be urelements of sets, then I can't think of any mathematical properties based on $\in$ alone which might distinguish two sets with three urelements each (thinking of say a box with three cats and another with three dogs), although we'd certainly want to distinguish them. My admittedly cursory reading leads me to believe that set theorists who work with New Foundations take this possibility seriously; I was glancing in particular at this Wikipedia article. I'd be happy to hear from set theorists who derive a different conclusion.

-
 @Todd: Please have a look at this question: mathoverflow.net/questions/51506/… – Hans Stricker Jan 9 2011 at 0:24

It seems to me that even if the exact philosophical notion doesn't quite apply to mathematics, there are other notions, similar but a bit more precise, that do. For example, mathematical structures can have high-level properties that are definable in terms of low-level properties but are not easily computable. In that case, it may be that the reduction, even though it exists, is not useful. This seems to me to be fairly like a physical example such as the difficulty of defining what a liquid is in microscopic terms.

What I'm getting at (but also slightly struggling with) is that reductionism has its defects in mathematics just as it does in philosophy. To give an example, to prove the prime number theorem one doesn't break it up into lots of small statements, prove those, and put them together again. That would be quite impossible, given that the largest known prime is very finite. Rather, one somehow looks at all the primes at once. It's tempting to say that the true meaning of the prime number theorem is not that all those numbers out there are prime, but rather a more global statement about density that supervenes on the properties of the numbers themselves.

-
I guess supervenience means more than "not easily computable", but "not computable at all". – Hans Stricker Jan 6 2011 at 12:07
That's why I wrote "similar" rather than "analogous". I haven't quite given up hope of thinking of an example of true mathematical supervenience but I don't have one at the moment. – gowers Jan 7 2011 at 9:16
I see something like the Prime Number Theorem - quite simply - as a property of an object, e.g. of $\mathbb{N}$ (with its structure). Since the theorem is statable and provable, the property is definable and decidable und thus not supervenient (in the narrower sense of "irreducible"). – Hans Stricker Jan 7 2011 at 9:30
Perhaps Goodstein's theorem (which asserts that every Goodstein sequence eventually hits zero) is an example of the phenomenon, in the following sense. The universal claim would seem to be supervenient on the individual instances, because the universal claim amounts to the sum total of all those instances, but although PA proves all the individual instances, it does not prove the universal claim. – Joel David Hamkins Jan 8 2011 at 18:21