A relation is characterized after three specifications (or equivalently an ordered triple) of Domain, Co-domain and Graph. All those specifications can be defined by 'intension' by using predicate symbols definable after formulas satisfied for objects having that relation or predicate; or they can be defined by extension as classes of sets. One of the best extensional implementations is to represent relations as classes of ordered pairs. The full extensional display of a relation would specify three classes, the first is the domain, the second is the co-domain and the third is the graph which is a class of ordered pairs having their first projections belonging to the domain and their second projections belonging to the co-domain. To be noticed is that there is nothing in the extensional coding of relations that pertains to those classes being sets, i.e. elements of other classes, but there is a requirement that ordered pairs must be sets when used to implement graphs of relations, however they not need to be sets when they serve to represent the relation itself as a triplet of three classes mentioned above. The requirements for a definition of a type of ordered pair are that it must hold of sets only (at graph implementations), and it must satisfy the basic property of ordered pairs, and it must be the case that for any classes A,B and any relation R from A to B there must exist a class of all ordered pairs of that type with projections related by R. In addition it must be the case that for any class of ordered pairs we must be able to recover a domain and a co-domain of the relation coded by that class.
Coding relations:
A) By intension: the easiest way to present a relation is as a predicate symbol definable after a formula with free variables, so for example the relation between any object and its singleton would be denoted by a relation symbol R with the following defining formula:
For all x,y (x R y <-> y={x})
However that is the graph of that relation, if we take a relation to be the triplet of domain, co-domain and graph we then use a string of three predicate symbols to characterize a relation, so for example the above relation would be a string of three Predicate symbols V,V,R where R is defined as above and V is the predicate defined as:
For all x (V(x) <-> x=x).
However the graph R of this relation can also be coded using a predicate defined after ONE free variable, i.e. a unary predicate, for example suppose that we have a certain function F that fulfills the basic property of ordered pairs, then we can define R after the formula defining ordered pairs between projections having that relation between them, so we'll use R* to denote the unary predicate code of R, the definition is:
For all x( R*(x) <-> Exist a,b (x=F(a,b) ^ a R b))
In this way we can show that R* is a unary code of R by the following coding of the graph of the relation (domain and co-domain need not be coded since they are unary already, so they remain fixed)
For all x,y ( Exist z in R* (x is 1st of z & y is 2nd of z) <-> x R y)
This would be called the code checking formula.
So the full coding string would be D,cD,R*, where D is the domain, cD is the co-domain, of R. So for the above relation it would be V,V,R*.
The above way is called coding of relations by intension. We note that in Zermelo for any two place set function F that fulfills the basic property, there is an intentional code of the Cartesian product between any two sets; that would easily be the formula
For all x (C(x) <-> Exist a in A, b in B (x=F(a,b)))
And from this coupled with specification we can define any relation between any two sets by intention. So at intentional level every two element list set function (a set function just fulfilling the basic property of ordered pairs) is qualified to be used to define relations.
B) By extension:
Here we code a relation by an object in the universe of discourse of the implementing theory; in this way those coding objects can be considered as embodiments of that relation since they translate them into the object world. One of the easiest and most general ways of doing that is coding relations by classes of ordered pairs. For such coding to be implemented in the most general way we need a theory that defines classes and not just sets, one such theory would be Zermelo + proper classes which can be formulated as NBG with the size limitation axiom replaced by the subsets axiom stating that a subclass of a set is a set, we'll denote this theory as Z*, while Z shall be reserved to denote Zermelo's set theory. This formulation is just a conservative extension of Z. Now one can prove in this theory that for any function that hold of sets and that fulfills the basic property of ordered pairs, i.e. a two-element list set function, then we can have class Cartesian products based on them between any two classes. Thus that function would be justified to be used in implementing relations. So this theory does copy its intentional coding over the realm of classes, BUT not over the realm of sets, since some sets in it might not have set Cartesian products in terms of any two-element set list. That's why Z cannot use any type of two-element set lists to implement relations.
The abstract aspect of a relation: relations are abstract in the sense that they transcend all particular representations of them. Any object or a predicate symbol coding a relation would possess some particulars that are in excess of representing that relation and such that in principle it is understood that those can to be dispensed with when coding relations, i.e. we can code the very same relation using another code that do not share those particulars with it, however it is clear that in order to grasp the 'content' of a relation we only need one code to discern that, but one or few codes would not help in depicting the abstract nature of a relation. In order to fully grasp the abstract nature of a relation we need to capture all possible codes of that relation and in this way it can be shown that since those are different representations but all are equivalent in coding the same relation then the relation is shown to transcend the particulars of those codes, what remains is shared between all of those distinct codes and is the relation they code. However it might not be possible to display all codes of a relation, but at least if every "principal" code of a relation is displayed then we can say that the relation is abstract over principal coding of it. However another useful concept is that of a relation "transcending" a particular realm of representation of it, this means that a truthful understanding of its abstract nature involves presenting a code of it that doesn't belong to that realm. For example "humanity" transcends "being American", for although we can code humanity after each American but still a truthful understanding of the abstract nature of humanity requires presenting a code for humanity that is non American.
A theory that do not manage to present all possible codes of a relation at least with respect to the ordered pair based approach to relations (which is regarded here as a principal coding of a relation) would be a theory that cannot show the abstract nature of the relation those codes are coding, although it can fully grasp the content of that relation using any one of these codes. A natural simile would be the abstract nature of a story like for example Oliver Twist, this can be displayed in form of animated movie, or a full cinematic movie, or a television series, or a play at a theater, or by puppets, etc..., each would display the full particulars of the story but each would also use particulars that the original story has nothing to do with, like the particulars of Cartoon industry, the actors, film industry particulars etc.. all of those particulars are technical tools used to achieve the display of the story. Now each of those ways mentioned above can be considered here as codes of the story, they are actually not just codes, they are embodiments of the story, since each one captures the full detail of the content of the story. It is perfectly understood that one display is enough to grasp all of the content of the story, but showing one embodiment of the story will not rule out the story being identified with it, so in order to show the abstract nature of Oliver Twist story over say the realm of film and theatrical industry of the twentieth century, then one needs to have all of those displays at hand, and by then of course the abstract nature of the story will be grasped as what is shared between all of those after all particulars not related to the story are shed away by not being common to all of those displays. A similar condition occurs here with the implementation of relations using object class extensions, those portray the content of the relation in an exact manner, and so they are not just dummy codes of the relation, they are perfect illustrations of the relation to the degree of being personifications or embodiments of the relation, notice that the formula defining the relation is part of their defining formula, and thus the relation is conceptually a part of them, when we have all of those classes at hand then all particulars of coding not related to the relation itself will be shed away and what remain is the relation itself.
What set\class theory is ought to capture:
Relations are best illustrated in terms of classes, and therefore it is thought that class\set theories must capture essential truths of relations especially of relations between sets. That set theory is employed for capturing the content of any relation between two sets is something that we know for sure, Z is one a famous example. However is the abstract nature of a relation as depicted above to be considered among essential aspects of a relation that set theory must pick up? Well clearly it is that relations are abstract is a very naïve and basic feature of relations, so we'd expect set\class theory to capture it at least in part if not in full.
An argument of Mathias:
Adrian Mathias argued that the abstractness of the ordered pair data type coupled with assuring existence of Cartesian products using any objects satisfying the basic property of ordered pairs implies axiom of replacement. What is meant by abstractness of ordered pairs is that we can use any function fulfilling the basic property of ordered pairs in implementing relations. To present this formally, we'd say that if we add the following scheme to Z then Replacement is proven:
Axiom of Abstract Cartesian products: If P is a two place function symbol definable after a formula in which symbol C doesn't occur free, then
[For all a,b,c,d (P(a,b)=P(c,d) -> a=c ^ b=d)
->
For all A,B Exist C (for all y. y in C <-> Exist a in A, b in B (y=P(a,b)))]
Is an axiom.
An argument of Holmes:
Randall Holmes presented a critique to this argument in his on-line pdf document titled "On ordered pairs". His argument in nutshell is that it is not enough for a function to fulfill the basic property in order for it to be considered as an "ordered pair" function, he names any function that merely fulfills that property as a "two element" list function to discriminate it from "ordered pair" function. He requires for a function to be an ordered pair function eligible to be used in representing relations to also fulfill the condition that for any sets A,B there must exist a Cartesian product of them using that function, so this property must be added to the Antecedent of the above axiom scheme of Mathias, and of course this addition would render the scheme into a tautology thus blocking the whole argument. So according to that the conceptual backing that Mathias gave to his schema would vanish, and thus it turns to be BOGUS argument on the conceptual level and thus the alleged conceptual justification for that argument would be viewed as a Fundamental mistake. However Holmes does acknowledge that the schema is deeply interesting as a reformulation of Replacement but he also holds that it was not properly motivated.
In Response to Holmes:
If we present Mathias's argument in Z* then Holmes tautology block would vanish. So the above Mathias schema is to be re-stated as:
Axiom of Abstract Cartesian products: If P is a two place function symbol definable after a formula in which symbol C doesn't occur free, then:
[For all a,b,c,d (P(a,b)=P(c,d) -> a=c ^ b=d ^ P(a,b) is a set) ^
For all A,B Exist C for all y (y in C <-> Exist a in A, b in B (y=P(a,b)))
->
For all sets A,B Exist a set C for all y (y in C <-> Exist a in A, b in B (y=P(a,b)))]
is an axiom.
We can even add existence ranges and domains to the antecedent. Now this escapes the tautological block of Holmes, because it is not a logical necessity to have every definable Cartesian product class being a set. Now in Z* the above schema with all requirements on the antecedent would burn down to:
Axiom of Abstract Cartesian products: If P is a partial two place function symbol definable after a formula in which symbol C doesn't occur free, then:
[For all a,b,c,d (P(a,b)=P(c,d) -> a=c ^ b=d) ^
For all a,b,c (c=F(a,b) -> a,b,c are sets) ^
For all sets a,b Exist c (c=F(a,b))
- >
For all sets A,B Exist a set C for all y (y in C <-> Exist a in A, b in B (y=P(a,b)))]
is an axiom.
So this re-presentation of Mathias argument in terms of classes actually clarifies the intension behind this argument. Clearly any two-element list set function (i.e. sets obeying the basic property with set projections) is eligible to define Relation classes (i.e. class codes of relations) since they fulfill ALL requirements needed in coding a relation. So to properly rephrase what Mathias should have said we'd say that "the abstractness of the ordered pair date type coupled with the assumption that each Cartesian product class between two sets is a set! Then this would prove replacement!
However when the argument is presented like that using double species of extension that of 'sets' and of 'classes', then one must seek to justify the set-hood of any Cartesian product class straddling between two sets. However I find two kinds of natural motivations for that assumption, a technical one and a conceptual one.
Technical and conceptual motivations for Mathias's argument:
A) Technical motivation: The mere existence of Cartesian products between any two sets doesn't infer that those products must be sets, for although existence of those is True at classes level, it is not always true to have sets fulfilling true statements of classes, a bitter lesson we came to know about from Russell's paradox. So we need to seek some justification when we say that classes fulfilling some property phi are always sets! From work with set theory like Z, it appears safe to assume the set-hood of a class that is embraced by sets, for example subclasses of sets are assured to exist by the powerful class comprehension scheme (whether predicative or not) but since the membership of those is completely restricted to be a membership of sets, so those classes are strangulated at the membership level which is the most basic of relations in set/class theory and thus cannot be a proper class. We say that those subclasses were embraced by sets at membership level. Similarly the motivation for replacement comes from the domain of a definable function being a set, and the stated result is that the range of that function would be a set. Now range would be stipulated to be a set, because it is embraced by the set-hood of the domain of the function class and by the restrictions involved when being a function. However I see here that the set embracing of a Cartesian product class between two sets is even clearer than that of replacement!!! Actually I consider it as a natural extension of subsets axioms through extending it to involve relations, not only that one can even state Mathias scheme as saying that: "Any Cartesian product relation class between sets, having set implementations of it, is a set". Here such a class is embraced by the set concept from three sides, the domain, the co-domain and the set copies of the Cartesian product relation between the domain and co-domain, so here this, technically speaking, supply us with more set embracing input and thus supply us with more confidence in the safety of assuming those classes to be sets! actually much more than that of Replacement itself where we just have one set and two classes and what is asserted immediately is the set-hood of one class (the range of the function) while the other one (the function) is left as a class, although we know it is provable to also be a set in the resulting theory, but this is not an immediate result from the statement of the axiom of schema of replacement itself, so we have just one set and two classes hanging one stipulated to be a set while the other is left hanging as a class. While here the situation show much more evidence of "embracing by sets" technical feature, and thus the Cartesian product schema of Mathias is actually safer than replacement and inspires more confidence in its truth than do replacement, and thus it does constitute a motivation for Replacement!
B) Conceptual motivation: The conceptual motivation of Mathias's schema is a little bit tricky and somewhat hard, but what would be demonstrated here is that it is the more plausible alternative.
To say that Mathias's argument is false is to say that there exists two sets A,B such that the Cartesian product relation from A to B is embodied by a proper class. This leads to saying that this relation would have a nature that is in excess of the nature of its domain and co-domain which are sets. We naively hold a relation between two classes to have the same nature as its domain and co-domain and never exceed them; this is a simple naïve glimpse of intuition that is mostly likely to be true. To further expound on how outrageous that would be, I'll give the natural simile of Oliver Twist story. Now it would be understandable to say that Oliver Twist novel transcends American cartoon industry, yes because a truthful understanding of the abstract notion of that novel requires supplying a representation (an embodiment) of it that is not a cartoon, like a movie for example, it is also perfectly understandable to say that Oliver twist novel transcends the whole American film industry, that's clear, but it won't be understandable to say that this novel transcends the whole human act, i.e. to say that there must be an embodiment of this story that is not produced by humans, like in saying that there MUST be some alien creature industry producing some theme that exactly captures Oliver Twist story? The problem is in the "MUST" condition, this would mean that there is something inherent in the story that links it to the alien theme production while at the same time maintaining that the origin of the story which is Charles Dickens is just a human being and its meant audience are human beings and the whole of what is present in it is just about human issues, so all in all it is a human issue, so how come we arrive at a conclusion about its nature 'essentially' encountering something that goes beyond humans? Extremely awkward! What I want to say here is that saying that for some relation between two sets it is true that we have a non set embodiment of it is as awkward as the above statement about Oliver Twist novel being exemplified by some non human act. It is a very odd assumption and highly undesirable!
In nutshell Mathias's argument can be decomposed into two parts, the abstract part and the set part, the first refers to the liberal use of any set two element list data type in implementing relations, the second is about the set-hood of any class Cartesian product of sets. The first part only thrives in a milieu of classes; otherwise it would be subject to Holmes tautology block. However without the second part it only manages to constitute a conservative extension of Z. With the second part, replacement would be proven, and the second part has a trivial justification both on conceptual grounds as well as on the technical side.
Reformulation of ZF.
Axioms: Extensionality, Foundation, Pairing, Union, Power, Infinity,
Axiom of Abstract Relation: If P is a two place function symbol definable after a formula in which symbol C doesn't occur free, and if R is a relation symbol definable after a formula in which symbols a,b occur free but the symbol C doesn't occur free, then:
[For all a,b,c,d (P(a,b)=P(c,d) -> a=c ^ b=d)
->
For all A,B Exist C for all y (y in C <-> Exist a in A, b in B (y=P(a,b) ^ a R b))]
is an axiom.
A Last word!
"Sets capture the abstractness of relations between sets" is ZF.
Zuhair Al-Johar
October 9, 2015