# How can the set of all graphs be the same size as its power set?

Supose a set $G$ containing all graphs, either finite or infinite. If I take a set $S\in P(G)$ and draw all the graphs in $S$ on a paper I can always just combine them and create one posibly disconnected graph which is an element of $G$. So the combination of some graphs is itself a graph, meaning that $G=P(G)$.

How can this be posible or where is the error?

• Every set can be made into a graph (e.g. with no edges). So your set of all graphs can be compared to the set of all sets which does not exists in usual set theories. Your derivation is based on false assumptions. – M. Winter Sep 27 '17 at 10:47
• @M.Winter The answers explain why this doesn't work, but I really like your succinct refutation. Short, to the point, and tragic! I remember first reading about how "the set of all sets" does not exist in ZFC over and over, trying to figure out how my intuitive grasp of math failed me. – Cort Ammon Sep 27 '17 at 18:36

There are (at least) two issues:

1. When you combine the graphs, graphs usually only have finitely many vertices and edges, while $S\in\mathcal{P}(G)$ may have infinitely many subgraphs. So, does $G$ contain infinite graphs? (see @HenningMakholm's comments below why $G$ can't contain infinite graphs.)

2. Suppose that graph $A\in G$ is a disjoint union of two graphs $B$ and $C$. Then using your construction, there are two ways to get $A$, $\{A\}\in\mathcal{P}(G)$ and $\{B,C\}\in\mathcal{P}(G)$. Therefore, your map is not injective. Hence, the argument does not show that $G=\mathcal{P}(G)$, only that there is a surjective map onto $G$.

• And there is no set of all infinite graphs -- not even a set containing a representative of each isomorphism class of infinite graphs. – hmakholm left over Monica Sep 27 '17 at 10:09
• @Garmekain: There is no such set. Just like there is no set of all sets. – hmakholm left over Monica Sep 27 '17 at 10:10
• The collection of all possible graphs would be really really big. It has similar problems as "the set of all sets" – Michael Burr Sep 27 '17 at 10:11
• But math.stackexchange.com/q/2446740/375741 says that there are the same number of graphs and labelled graphs, so it has a cardinality,right? – Garmekain Sep 27 '17 at 10:14
• @Garmekain The graphs in the labelling question are finite, but yes $G$ has a cardinality if it consists of the set of (finite) graphs. – Michael Burr Sep 27 '17 at 10:16

You're not mistaken. You just proved that there is no "set of all graphs". In fact, there is no set of all singletons either. And so definitely there will be no set of all graphs.

In some set theories which admit a universal set (e.g. Quine's New Foundations), this is still not a problem, because the function mapping a set on its power set is not itself a set, so there is no contradiction to Cantor's theorem. (The reason this is happening is that the existence of a universal set means that not every formula can be used to define a subset.)

(Also, one minor mistake you have here, is that you didn't actually prove that $G=\mathcal P(G)$, but rather that there is a surjection from $G$ onto its power set. Note that a graph is not just a set, it's an ordered pair of set [of vertices] and a set of edges. So it isn't usually the case that a set of ordered pairs is itself an ordered pair.)