Abstract

De Clercq [-@declercq_r:2012] proposes a strategy for denying purported graph-theoretic counterexamples to the Principle of the Identity of Indiscernibles (PII), by assuming that any vertex is contained by multiple graphs. Duguid [-@duguid_c:2016] objects that De Clercq fails to show that the relevant vertices are discernible. Duguid is right, but De Clercq’s strategy can be rescued. This note clarifies what assumptions about graph ontology are needed by De Clercq, and shows that, given those assumptions, any two vertices are weakly discernible, and so are not counterexamples to the version of PII that requires only weak discernibility.

The Principle of the Identity of Indiscernibles (hereafter PII) states that there are no solo numero differences. In other words, between any two things that differ numerically (i.e., differ in identity), there is a non-numerical difference (a difference that is not merely a difference in identity). Various purported counterexamples to PII have been proposed, among them Black’s (1952) two intrinsically identical spheres located two miles apart in empty space. Saunders (2003) and Ladyman (2005) point out that Black’s spheres and similar examples do not violate the version of PII whereby only weak discernibility is necessary for non-identity. A relation \(R\) weakly discerns objects \(a\) and \(b\) if and only if \(Rab\& Rba\& \lnot Raa\&\lnot Rbb\) (Caulton and Butterfield 2012, 50). Black’s spheres are weakly discerned by the relation being two miles from. Leitgeb and Ladyman (2008) propose cases drawn from graph theory in which, they claim, two distinct objects are not even weakly discernible. Leitgeb and Ladyman claim that—whereas the two vertices in the graph consisting of two vertices and an edge connecting them are weakly discernible—the two vertices in the graph consisting of two vertices and no edges are not in any way discernible. De Clercq (2012) argues that Leitgeb and Ladyman’s counterexample rests on a controversial view about the ontology of graphs, namely one that rejects assumption (i) below; and that on another plausible view about the ontology of graphs, which De Clercq favours, the case that Leitgeb and Ladyman propose is not a counterexample to PII, because the two vertices are discernible in virtue of the relations in which they stand in other graphs that contain them. Duguid (2016) objects that the two vertices are not discernible in virtue of such relations, so that, even granting De Clercq’s favoured view about the ontology of graphs, Leitgeb and Ladyman’s case is a counterexample to PII, even the version of PII that requires only weak discernibility.

In this note, I clarify what assumptions about the ontology of graphs are needed by De Clercq, and show that De Clercq’s strategy can be rescued from Duguid’s rejoinder insofar as it can be shown that, granted De Clercq’s assumptions about the ontology of graphs, any two vertices are weakly discernible. I give an example of a relation that weakly discerns vertices: x has greater degree in some graph than y. If De Clercq is correct about the ontology of graphs, therefore, the purported graph-theoretic counterexamples that have been proposed do not falsify the version of PII that requires only weak discernibility and thus do not, in this respect, improve on Black’s spheres.

1 De Clercq’s Strategy

Graphs are arrangements of vertices and edges connecting vertices such that edges do not have a direction and any two vertices in a graph are either connected by one edge or not connected by any edge.¹ The degree of a vertex in a graph is the number of edges that connect it with other vertices in the graph. A vertex is isolated in a graph if and only if it has degree 0 in the graph. Two graphs are isomorphic if and only if (regardless of the identities of their vertices) they have the same structure of vertices and edges; that is, two graphs are isomorphic if and only if there is a bijection from the set of the vertices of the first graph to the set of the vertices of the second graph such that any two vertices are connected by an edge in the first graph if and only if their images under the bijection are connected by an edge in the second graph.

More formally, graphs are commonly defined set-theoretically, so that a graph \(G\) is an ordered pair \((V,E)\) where \(V\) is a set of vertices and \(E\) is a (possibly empty) set of subsets of \(V\) that have two members, and any distinct vertices \(v\) and w in \(V\) are said to be connected in \((V,E)\) by an edge if and only if {\(v,w\)} is a member of \(E\).² Let us call the identification of graphs with ordered pairs of vertex and edge sets Identity. Leitgeb and Ladyman do not accept Identity, while De Clercq does. Other graph-theoretic terms can also be defined set-theoretically.

De Clercq defends PII against Leitgeb and Ladyman’s purported counterexample by arguing that, in a graph \(G\)₀ that consists of two vertices \(a\) and \(b\) and no edges, \(a\) and \(b\) are discernible in virtue of the relations in which they stand in other graphs: “vertices in labeled graphs are always distinguishable, not just because they bear different labels, but also because they feature in (structurally!) different ways in different graphs” (2012, 670). The distinctness of \(a\) and \(b\), for example, is, according to De Clercq, not a solo numero difference, because there is a graph \(G\)₂, consisting of three vertices \(a\), \(b\) and \(c\) (where \(a\) and \(b\) are respectively identical to the vertices \(a\) and \(b\) in \(G\)₀) and an edge connecting \(a\) and \(c\), in which \(a\) and \(b\) stand in different relations.

Two assumptions are necessary and sufficient for De Clercq’s strategy: (i) that there are no unlabelled graphs such that their vertices are objects, and (ii) that if \(G\)₀ exists, then \(G\)₂ exists. Regarding (i): De Clercq and Leitgeb and Ladyman disagree about what unlabelled graphs are. According to Leitgeb and Ladyman, unlabelled graphs are graphs such that the vertices of an unlabelled graph are distinguished only by their relations within that unlabelled graph, and any isomorphic unlabelled graphs are identical. On this view, there are objects that are the vertices of unlabelled graphs, and vertices of distinct unlabelled graphs do not stand in relations of identity. De Clercq (2012, 666), in contrast, claims that “unlabelled graphs are not graphs but isomorphism classes of graphs” (that is, the equivalence classes into which the set of all graphs is partitioned by the isomorphism relation).³ On this view, talk of the vertices of unlabelled graphs is not ontologically committing, and there are no unlabelled graphs such that their vertices are objects. Regarding (ii): Since, as specified above, \(G\)₂ is a graph some of whose vertices are respectively identical to some vertices of \(G\)₀, (ii) presupposes (iii) that some vertices in distinct graphs are identical.⁴ De Clercq (2012, 665–669) defends (i) and (iii) by appealing to the practice of graph theorists.⁵

Assuming uncontroversially that there exist graphs of three or more vertices and thus that there exists at least one vertex other than \(a\) and \(b\), (ii) follows from the following claim:

Plenitude. For every subset \(V\) of the set \(W\) of all vertices, for every (possibly empty) set \(E\) of sets consisting of two members of \(V\), there exists a graph consisting of the vertices in \(V\) and edges connecting every pair of members \(u\), \(v\) of \(V\) such that {\(u,v\)} is in \(E\).⁶

In turn, Plenitude follows from Identity, since any set exists if its members exist, and any ordered pair exists if its members exist. So, De Clercq can accept Identity and infer (ii) from Identity, but only if he also accepts Plenitude. Might one accept (ii) without accepting Plenitude? As noted above, (ii) implies (iii) that some vertices in distinct graphs are identical, or, in other words, that some vertices are contained by multiple graphs. De Clercq (2012, 666–667) argues that, while (iii) follows from Identity, it is also plausible in light of mathematical practice, independently of the truth of Identity. Nonetheless, as long as some vertices are contained by multiple graphs, it would be arbitrary to suppose that some finite graphs that can be formed out of vertices from \(W\) and edges connecting them exist but others do not. De Clercq’s assumption of (ii), therefore, commits him to Plenitude.

It is Plenitude that leaves De Clercq’s defence of PII vulnerable, even granting (i), to Duguid’s reply: for any graph where \(a\) and \(b\) bear different relations, another graph exists in which \(a\) and \(b\) are permuted, so that (for instance) corresponding to \(G\)₂ there exists an isomorphic graph \(G\)₁ which consists of three vertices \(a\), \(b\) and \(c\), and an edge connecting \(b\) and \(c\). Now, \(b\) has the property being isolated in a graph consisting of three vertices and an edge connecting two of them, in virtue of \(G\)₂, but \(a\) has the same property, in virtue of \(G\)₁. To discern \(a\) and \(b\), De Clercq would have to appeal to properties that distinguish between isomorphic graphs (for example, the property being isolated in \(G\)₂).⁷ But since distinct isomorphic graphs differ only in the identity of their vertices, in order to distinguish between isomorphic graphs, a property “must utilize object names” (Duguid 2016, 472). Let us say that a property or relation is forbidden for PII if and only if allowing being discerned by it to count as discernibility would make PII metaphysically uninteresting. For example, a version of PII that allows that \(a\) and \(b\) are discernible on the ground that they are discerned by the property is identical to \(a\) is metaphysically uninteresting, as is a version of PII that allows that \(a\) and \(b\) are discernible on the ground that they are weakly discerned by the relation is distinct from. ((Rodriguez-Pereyra 2006) and (Muller 2015) discuss what would make PII trivial and as such metaphysically uninteresting.) Following Muller (2015), Duguid considers properties in which object names occur to be forbidden for PII. De Clercq, Duguid concludes, fails to save PII.

2 Weakly Discerning Vertices

Ladyman, Linnebo and Pettigrew (2012) show in their Theorem 6.4 that two objects are weakly discernible in a language \(L\) if and only if they are in any way discernible in the language that includes a constant for every element of the domain of \(L\) (i.e., the language that includes names for all of its objects). It follows, as Duguid accepts, that, if there are object-name-containing properties that discern two vertices \(a\) and \(b\), there is a non-object-name-containing relation that weakly discerns \(a\) and \(b\). Nonetheless, Duguid writes (2016, 473): “such a relation has not yet been provided. And neither can I see what it might be.”

Here is one:

\(\Phi (x, y) : \equal \exists g\) ((\(g\) is a graph) \(\&\) (\(g\) contains \(x\) and \(y\)) \(\&\) (\(x\) has greater degree in \(g\) than \(y\)))

Given De Clercq’s assumptions, this relation, x has greater degree in some graph than y, holds between any two vertices \(a\) and \(b\) in both directions, but not between either vertex and itself. Hence, contra Duguid, any two vertices are weakly discernible, and Leitgeb and Ladyman’s case is not a counterexample to the version of PII that requires only weak discernibility.

Whether De Clercq’s strategy for saving PII from purported graph-theoretic counterexamples is ultimately successful depends on the plausibility of its assumptions about graph ontology: Plenitude, and that there are no unlabelled graphs such that their vertices are objects. Granted these assumptions, however, any two vertices are indeed weakly discernible.

In directed graphs, edges have a direction. In multigraphs, vertices may be connected by more than one edge. Directed graphs and multigraphs are not considered in this note.↩︎
Note: this definition is not committed to identifying edges with sets of two vertices.↩︎
Note: De Clercq’s identification of unlabelled graphs with isomorphism classes is not necessary for his argument. One could instead claim, for example, that unlabelled graphs are mereological atoms that correspond one-to-one with isomorphism classes. But perhaps it is the best motivated of claims that imply (i).↩︎
Note: Identity is not necessary for De Clercq’s strategy because (i) and (ii) are sufficient for it and do not imply Identity. Identity is also not sufficient for De Clercq’s strategy because, although Identity implies that there are no graphs that are Leitgeb and Ladyman’s unlabelled graphs, Identity does not imply that Leitgeb and Ladyman’s unlabelled graphs do not exist, and as long as such entities exist, there are counterexamples to PII.↩︎
In defending the rejection of (i), Leitgeb and Ladyman (2008, 390) also appeal to the practice of graph theorists.↩︎
Note: Plenitude, thus formulated, does not presuppose Identity, as it would if “a graph consisting […] is in \(E\)” were replaced with “a graph (\(V\), \(E\)).”↩︎
Duguid (2016, 472) says that De Clercq must appeal to a property that is “specific enough to single out a single graph.” This is not correct, since the property is isolated in a graph consisting of a, b and some third vertex and an edge connecting a and the third vertex, which does not single out a single graph, would also do.↩︎

References

Black, Max. 1952. “The Identity of Indiscernibles.” Mind 61(242): 152–164. Reprinted in Black (1954, 80–92), doi:10.1093/mind/LXI.242.153.

—. 1954. Problems of Analysis: Philosophical Essays. Ithaca, New York: Cornell University Press.

Caulton, Adam and Butterfield, Jeremy. 2012. “On Kinds of Indiscernibility in Logic and Metaphysics.” The British Journal for the Philosophy of Science 63(1): 27–84, doi:10.1093/bjps/axr007.

de Clercq, Rafael. 2012. “On some Putative Graph-Theoretic Counterexamples to the Principle of the Identity of Indiscernibles.” Synthese 187(2): 661–672, doi:10.1007/s11229-010-9867-3.

Duguid, Callum. 2016. “Graph Theory and the Identity of Indiscernibles.” Dialectica 70(3): 463–474, doi:10.1111/1746-8361.12151.

Ladyman, James. 2005. “Mathematical Structuralism and the Identity of Indiscernibles.” Analysis 65(3): 218–221, doi:10.1111/j.1467-8284.2005.00552.x.

Ladyman, James, Linnebo, Øystein and Pettigrew, Richard. 2012. “Identity and Discernibility in Philosophy and Logic.” The Review of Symbolic Logic 5(1): 162–186, doi:10.1017/S1755020311000281.

Leitgeb, Hannes and Ladyman, James. 2008. “Criteria of Identity and Structuralist Ontology.” Philosophia Mathematica 16(3): 388–396, doi:10.1093/philmat/nkm039.

Muller, F. A. 2015. “The Rise of Relationals.” Mind 124(493): 201–237, doi:10.1093/mind/fzu175.

Rodriguez-Pereyra, Gonzalo. 2006. “How Not to Trivialiize the Identity of Indiscernibles.” in Universals, Concepts and Qualities: New Essays on the Meaning of Predicates, edited by Peter Frederick Strawson and Arindam Chakrabarti, pp. 205–224. Aldershot, Hampshire: Ashgate Publishing Limited.

Saunders, Simon W. 2003. “Physics and Leibniz’s Principles.” in Symmetries in Physics: Philosophical Reflections, edited by Katherine Brading and Elena Castellani, pp. 289–307. Cambridge: Cambridge University Press, doi:10.1017/CBO9780511535369.017.