A directed graph is a pair <N, E> where N is any collection or set of objects (the nodes of the graph) and E is a relation on N (the edges). Intuitively speaking, we can think of a directed graph in terms of a dot-and-arrow diagram, where the nodes are represented as dots, and the edges are represented as arrows. For example, in the following figure we have a graph that consists of three nodes–A, B, and C, and four edges: one from A to A, one from A to B, one from B to C, and one from C to B.
Note that with directed graphs we distinguish between those cases where a node has an arrow from itself to itself and those cases where it does not, and we also take into account the direction of the edge–that is, the edge from B to C is distinct from the edge from C to B (we do, however, represent cases where we have arrows going in both directions with a single line with two “arrowheads”).
In the diagram above, the nodes might represent Alice, Betty, and Carla, and the relation E might be “loves.” Thus, the diagram represents Alice loving both herself and Betty (and no one else), Betty loving Carla (and no one else), and Carla loving Betty (and no one else).
Assume we have a collection of objects N (our nodes) and a relation E such that for any two objects in N, the relation E might or might not hold of them, and in particular, E might or might not hold between an object in N and itself. Now, consider the graph where the collection of nodes is N and the collection of edges (which we will also call E) contains an edge between two nodes n1 and n2 just in case the relation E holds between n1 and n2 (in that order). Now, given any such structure, we can arrive at our puzzle by considering the following question:
Given such a situation, modelled by a directed graph <N, E>, can we construct a new directed graph <N*, E*> where N* = N È {r} (where r is not already in N) and, for any n1, n2 in N*, there is an edge in E between n1 and n2 if and only if:
n1, n2 are in N and there is an edge in E between n1 and n2.
n1 = r and there is no edge between n2 and itself.
In other words, given any directed graph, can we add a single additional node to the graph, and some additional edges to the graph, such that there is an edge between the new node r and any node n in N* if and only if there is no edge from n to itself?
The answer, of course, is no. If we were successful, then we would have a directed graph <N*, E*> where:
For any n in N*, there is an edge in E*from r to n if and only if there is no edge in E* from n to n.
Substituting r for n gives us a contradiction, however:
There is an edge in E* from r to r if and only if there is no edge in E* from r to r.
This pattern is a general one underlying a number of paradoxes – some familiar, some less so. For example:
The Barber Paradox:
N = the collection of men and there is an edge between two nodes n1 and n2 if and only if n1 shaves n2. The new node r is the barber who shaves all and only those who do not shave themselves.
The Russell Paradox:
N = the collection of sets and there is an edge between two nodes n1 and n2 if and only if n2 is a member of n1. The new node r is the set of all sets that are not members of themselves.
The Impossible Painting Paradox:
N = the collection of painting and there is an edge between two nodes n1 and n2 if and only if n1 is a painting that depicts n2. The new node r is the painting that depicts all and only those paintings that do not depict themselves.
The Hyperlink Paradox:
N = the collection of websites and there is an edge between two nodes n1 and n2 if and only if n1 hyperlinks to n2. The new node r is the website that links to all and only those websites that do not link to themselves.
The Lover of Self-loathers Paradox:
N = the collection of people and there is an edge between two nodes n1 and n2 if and only if n1 loves n2. The new node r is the lover of self-loathers – a person who loves all and only those people who do not love themselves.
The Anti-Cannibalism Predator Paradox:
N = the collection of species, there is an edge between two nodes n1 and n2 if and only if members of species n1 eat members of n2. The new node r is the anti-cannibal predator species, members of which eat all and only members of those species that don’t eat members of their own species.
The Hyperlink Paradox is, as far as I can tell, due to Øystein Linnebo, and the Lover of Self-Loathers Paradox and the Anti-Cannibalism Predator Paradox are new. Now that you’ve seen the pattern, you can have fun constructing your own paradoxical notions!
Featured image: Partial view of the Mandelbrot set by Wolfgang Beyer. CC-BY-SA 3.0 via Wikimedia Commons.
Hello,
This approach is very much related to work done by Bill Lawvere in a paper entitled “Diagonal arguments and cartesian closed categories”. Yanofsky would build on this work in a paper entitled “A universal approach to self referential paradoxes” — in particular, he makes Lawvere’s work more accessible by reformulating it in set theory and showing that his work applies to many more cases.
In essence, very many if not all the “paradoxes” and certain related theorems (incompleteness, undefinability of truth, Cantor’s diagonalization argument, etc. ) we know seem to boil down to some simple algebra in a Cartesian closed (or even just cartesian) category. I highly recommend both papers, especially to philosophers who, in general, do not seem to be familiar with them.
Best,
Jared