Leibniz Abstraction, Structure Identity and Univalence
In mathematics, one gets used to thinking of a particular mathematical object - say a group, or a graph, or a partial order, or a field, or a topological space in abstract terms. That is, given the model one "forgets" the specific nature of the carrier set , and one focuses only on properties of the mathematical model/structure, which are invariant under isomorphism. This means that one is, in a sense, thinking of some "entity" which all isomorphic copies "have in common".
So, for example, if our models and are isomorphic graphs, then one imagines that there is some other thingy -- call it -- such that . Obviously, the carrier sets and can be distinct. But this is "abstracted away". If our models are isomorphic partial orders and , then we imagine that there are corresponding "abstract structures" and such that .
More generally, we imagine we have some map,
are ... But whatever they are, they are not models, with a carrier set. Their carrier set has been abstracted away, somehow.
Vladimir Voevodsky's Univalence Axiom, as I understand, is an attempt to make this very intuitive idea mathematically precise. There are many formulations, including in the book on Homotopy Type Theory, of course. Here is a formulation from Ulrik Buchholtz, from a 2013 talk on "Univalent Foundations and the Structure Identity Principle":
Now I'm fairly sure that this overlaps very closely with the following: one can define "thingies" such that Leibniz Abstraction holds, for set-sized mathematical models as follows:
The rough idea is this: let be some mathematical object, with a set-sized carrier set/domain (and special or distinguished relations ). can be a graph, a group, etc.
One can define a purely logical formula , in a language , possibly infinitary, with free (second-order) variables amongst , such that categoricity holds:
defines the isomorphism type (groupoid) of . The formula is called the diagram formula for . It is called this by analogy with the notion of a diagram in model theory. The diagram of a model is a kind of "picture" of all the basic relationships between elements of the model , obtained by introducing a constant to name each . But the diagram formula itself does not contain any constants labelling domain elements, Rather, these have been existentially quantified.
Then we let be the propositional function expressed by the diagram formua . Then Leibniz Abstraction follows. So far as I can tell, this also implements the intuitive idea that Univalence is intended to implement too: namely, the Structure Identity Principle.
So, for example, if our models
More generally, we imagine we have some map,
taking us from graphs, orderings, groups, linear spaces, topological spaces, etc., etc., to abstract graphs, orderings, groups, linear spaces, etc., etc. such that
holds. I call this principle Leibniz Abstraction. But, unfortunately, no one knows that these abstract "thingies"iff .
Vladimir Voevodsky's Univalence Axiom, as I understand, is an attempt to make this very intuitive idea mathematically precise. There are many formulations, including in the book on Homotopy Type Theory, of course. Here is a formulation from Ulrik Buchholtz, from a 2013 talk on "Univalent Foundations and the Structure Identity Principle":
Univalence Axiom (Voevodsky)(I think that the "Structure Identity Principle" amounts to what I call "Leibniz Abstraction" above; certainly, this is what has been discussed a lot by philosophers of mathematics for decades. Particularly structuralist philosophers of mathematics, like Shapiro, Hellman and Resnik.)
For typesand , the identity type is equivalent to the type of (homotopy) equivalences between and .
Now I'm fairly sure that this overlaps very closely with the following: one can define "thingies"
Leibniz AbstractionThese entities are propositional diagrams.
iff .
The rough idea is this: let
One can define a purely logical formula
Thus the formulaiff .
Then we let
Hi Jeff,
ReplyDeletethanks for the mention of my talk! I don't quite see how your construction implements the SIP, though: If A and B are isomorphic structures, then we'd like any statement made about A to hold for B, and we'd like any construction mentioning A to work for B as well. Obviously, we can only allow suitably “structural” statements and constructions. This works when A and B are equal (as per univalence), but how does it help that A and B are mapped to equal objects by your construction?
Cheers,
Ulrik
Ulrik,
and are mathematical objects, they have their carrier sets with them, so can't be literally equal. E.g., let and be isomorphic linear orders, with . They can't be identical, because . On the other hand, if A and B are isomorphic models, then (structural) statements true of A are true of B, and vice versa.
such that the Leibniz abstraction principle,
iff .
is a quasi-syntactic entity: a purely "structural picture" of A. And the carrier set/domain of A has been eliminated entirely. Only the abstract structure remains.
is the Zermelo model of the numbers, and is the von Neumann model. The carrier sets X and Y are distinct; and the relations and are extensionally distinct.
. That is, the Zermelo model and the von Neumann model have the same "abstract structure": their structural picture is identical.
ReplyDeleteOh thanks - I guessed you must be the same Ulrik!
The thing is, if
On the diagram construction, we get a map
holds.
(And I think that's very close to what you mean by Structure Identity Principle ...)
The entity
So, to use the example in your talk, suppose
But, since they're isomorphic, we get:
Cheers,
Jeff
Jeff,
and can be equal; not literally, but via an inhabited identity type. Since identity types let you do almost everything you want with “equal” objects, it works out. Of course, you have to give up proof irrelevance: as you note, the carrier sets will be equal, and in general that can happen in several ways, so you need to remember “how” they're equal. But you can't make an omelette without breaking some eggs, I guess!
is a propositional function of structures (over a fixed signature), and holds of , and equals (so and are isomorphic), how do conclude that holds of ? Do you need some extra conditions on ? Presumably it works when is a formula over the signature?
ReplyDeletewell, the point of HTT is that in fact
I looked at your post on abstract structure (here: http://m-phi.blogspot.com/2013/03/what-is-abstract-structure.html), but I'm still unclear how you perform the transport: If
Cheers,
Ulrik
Ulrik,
depends on the starting model and its signature. (Here is the carrier set/domain, are the special relations on .)
has a sequence of second-order variables, which are "labels" of the carrier set and distinguished relations in .
, which takes us from the distinguished relations to second-order variables, preserving arity: - so, maps the carrier set to a unary second-order variable, say , and maps each special relation to a second-order variable of the same arity. To define , there is also a "domain labelling", , which maps each domain element to a first-order variable in . These free first-order variables are then existentially quantified).
. So, logically equivalent formulas express the same propositional function. And, eventually the "abstract structure" of is the propositional function expressed by the diagram formula . And I write for this propositional function.
ReplyDeleteYes, the construction of the diagram language
The diagram formula
(In the notes on this I have, I call this a "relation-labelling",
Then, we can prove a categoricity result, which lets us transfer between isomorphic models. But the only properties which are transferred are purely "structural".
Does that sound ok? What I'm doing is coming from model theory, rather than category theory though.
The propositional function bit is to remove the dependence on syntactic issues, because strictly speaking one can get syntactically distinct formulas defining the isomorphism type of
(Hope the latex works, as our preview here doesn't run the latex - if not, I may have to edit and redo the comment.)
Cheers,
Jeff
Jeff,
anymore, but about instead? Is there a transparent translation of structural talk about into talk about that preserves all the meaningful statements about ?
is a cateory, does capture up to equivalence of categories (that's what we want), or merely up to isomorphism?
ReplyDeletethanks, that sounds all right. But I'm still a little skeptical as to whether it really provides an implementation of the SIP: Is the proposal to talk not about
I also worry about getting the correct notion of equivalence for higher-categorical notions, for instance “category” itself: If
Cheers,
Ulrik
Ulrik,
into talk about ?
. So, roughly, the translation is one that shows that, for a formula , then " is true in " is equivalent to " 's is implied by the diagram formula ". I.e.,
iff .
.
of . These permutations are then automorphisms of just when the skolemizations are logically equivalent. Intuitively, it's like labelling an unlabelled graph using two distinct labellings; the resulting labelled graphs are (literally) identical because of an automorphism of the graph.)
DeleteYes, we no longer talk about the models, but rather about their abstract structures instead. E.g., instead of talking about the von Neumann implementation, or the Zermelo implementation, we have the abstract structure itself (that both "have in common") instead. This abstract structure is the propositional function (in Frege's sense) expressed by the diagram formula. But because propositional functions are hard to deal with, it's easier to talk about the diagram formula, which expresses the propositional function (and defines the isomorphism type).
Is there a transparent translation of structural talk about
It's easier to deal with the diagram formula
It's a bit easier to see how it works if one skolemizes the diagram formula to get
(It then turns out that pairs of skolemizations of the formula induce permutations of the original carrier set
That said - perhaps the Leibniz Abstraction Principle is different, in some important conceptual sense, from the intent behind the Structure Identity Principle. What I'm doing is more like "quotienting" with respect to isomorphism of relational models. The abstract representative of an equivalence type of models isn't a model though, because the carrier set has been thrown away: on my view, they're propositional diagrams.
Cheers,
Jeff
Ulrik,
is a cateory, does capture up to equivalence of categories (that's what we want), or merely up to isomorphism?
only captures up to isomorphism, not equivalence of categories.
, there may be a way of defining this tighter notion "quasi-syntactically" too and then the result would be some kind of "equivalence structure" of . But to be honest, I'm not sure ...
DeleteIf
Yes,
I suspect that, given
Cheers,
Jeff