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 *n*_{1} and *n*_{2} just in case the relation *E* holds between *n*_{1} and *n*_{2} (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 *n*_{1}, *n*_{2} in *N**, there is an edge in *E* between *n*_{1} and *n*_{2} if and only if:

*n*_{1}, *n*_{2} are in *N* and there is an edge in *E* between *n*_{1} and *n*_{2}.

*n*_{1} = r and there is no edge between *n*_{2} 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 *n*_{1} and *n*_{2} if and only if *n*_{1} shaves *n*_{2}. 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 *n*_{1} and *n*_{2} if and only if *n*_{2} is a member of *n*_{1}. 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 *n*_{1} and *n*_{2} if and only if *n*_{1} is a painting that depicts *n*_{2}. 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 *n*_{1} and *n*_{2} if and only if *n*_{1} hyperlinks to *n*_{2}. 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 *n*_{1} and *n*_{2} if and only if *n*_{1} loves *n*_{2}. 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 *n*_{1} and *n*_{2} if and only if members of species *n*_{1} eat members of *n*_{2}. 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. *

The post Graphs and paradoxes appeared first on OUPblog.

*This post first appeared on OUPblog | Oxford University Press’s Academic Ins, please read the originial post: here*