9
$\begingroup$

Even though there are uncountably many subsets of $\mathbb{N}$ there are only countably many isomorphism classes of countably infinite - or countable, for short - models of the empty theory (with no axioms) over one unary relation.

How many isomorphism classes of countable models of the empty theory over one binary relation (a.k.a. graph theory) are there? I.e.: How many countable unlabeled graphs are there?

A handwaving argument might be: Since the number of unlabeled graphs with $n$ nodes grows (faster than) exponentially (as opposed to growing linearly in the case of a unary relation), there must be uncountably many countable unlabeled graphs. (Analogously to the case of subsets: the number of subsets of finite sets grows exponentially, thus (?) there are uncountably many subsets of a countably infinite set.)

How is this argument to be made rigorous?

  • 0
    @Hans: _no._ I already gave you a counterexample. The growth rate means nothing; what matters is what kind of axioms the theory is allowed to impose, and if you were to think along those lines I think you get an interesting model-theoretic question.2011-03-16

8 Answers 8

0

Let $\mathcal{G}$ denote the set of all countable infinite (simple unlabeelled) graphs.

$|\mathcal{G}|\supseteq|\mathbb{R}|$

To see this, we construct an injective function $f:2^\mathbb{N}\rightarrow\mathcal{G}$ (I take $\mathbb{N}=\{1,2,\ldots\}$), because $|2^\mathbb{N}|=|\mathbb{R}|$. Let $P_n$ denote the path graph on $n$ vertices. Note that $P_1$ is the trivial edgeless graph. For two graphs $G_1,G_2$, denote their sum by $G_1\oplus G_2$ (graphically, we just draw both graphs next to another, without connecting them). This operation is commutative and associative and we can without problem generalize it to any set $S$ of graphs to get $\bigoplus_{G\in S}G$. Furthermore for two Graphs $G_1,G_2$ let $G_1\vee G_2$ denote the join of $G_1$ and $G_2$. Then for any graph $G$, $G\vee P_1$ is the graph obtained by adding a new vertex and edges connecting the new vertex with all vertices of $G$.

Now define $f$ by $f(A)=\left(\left(\bigoplus_{n\in A}P_n\right)\vee P_1\right)\oplus \bigoplus_{n\in\mathbb{N}\setminus A} P_n$

Visually, we draw each number in the plane (by their path graph) and then glue all numbers/graphs together which are in the subset $A$.

$|\mathcal{G}|\subseteq|\mathbb{R}|$

We can describe a directed multigraph with a tuple $(V,E,S,T)$ where $V$ is the set of vertices, $E$ is the set of edges and $S,T$ are functions from $E$ to $V$, describing the source and target vertex of every edge. The set of all countable directed multigraphs can then be described by $\mathcal{G}'=\{(\mathbb{N},\mathbb{N},S,T):S,T\in \mathbb{N}^\mathbb{N}\}=\{\mathbb{N}\}\times\{\mathbb{N}\}\times\mathbb{N}^\mathbb{N}\times\mathbb{N}^\mathbb{N}$

Note that this set contains a lot of graphs that are isomorphic to one another. There is also a natural inclusion map from $\mathcal{G}$ into $\mathcal{G}'$, which can be obtained by assigning the natural numbers to the vertices and edge each and a direction to every edge, so $|\mathcal{G}|\subseteq|\mathcal{G}'|$. Furthermore it is known that $|\mathbb{N}^\mathbb{N}|=|\mathbb{R}|$, so $|\mathcal{G}'|=|\{1\}\times\{1\}\times\mathbb{R}\times\mathbb{R}|=|\mathbb{R}^2|=|\mathbb{R}|$.

6

Here is one explicit way of producing continuum-many pairwise nonisomorphic (simple, undirected, loopless) graphs.

Start with a $3$-cycle among vertices labelled $-2,-1,0$. To the vertex $-1$ attach a tail (= path) of length $1$ and to the vertex $-2$ attach a tail of length $2$. Now, for each positive integer $n$, attach a tail of length $n$ to the vertex $0$, and label the terminal vertex in this tail $n$. (So we have some vertices that we have not labelled, but certainly only countably many of them.)

Now focus on the vertices marked $1,2,3,\ldots$: color the odd numbered ones red and the even numbered ones green. Consider the set of all possible bipartite graphs on this vertex set -- i.e., in which all edges connect red to green. There are clearly continuum-many: for instance even the independent choices of including / not including the edges $1--2$, $1--4$, $1--6$, and so forth gives a set of continuum cardinality. I claim that all of these graphs are pairwise nonisomorphic. Indeed, the only three cycle in any of them is formed by the vertices $-2,-1,0$, and it follows easily from this that any isomorphism between any two of these graphs carries $0$ to $0$, $-1$ to $-1$ and $-2$ to $-2$. From this it follows that for all $n \in \mathbb{Z}^+$, an isomorphism takes the vertex labelled $n$ to the vertex labelled $n$ and thus every vertex is fixed.

(By the way, I don't find the argument you suggest to be at all valid. I strongly suspect there are first order theories such that the number of nonisomorphic models of finite size $n$ grows at least exponentially with $n$ but for which there are only countably many isomorphism classes of countable models.)

Added: I want to make sure that the paths from $0$ to $n$ stay pairwise nonisomorphic when edges are added, so it's best to modify the construction slightly. For instance, call the penultimate vertex in the path $p_n$ and attach one more length one tail at $p_n$, so that now $p_n$ has degree $3$.

  • 0
    @Jason: +1 for this example "the other way around".2011-03-17
3

One way is to construct an injection from $2^{\mathbb{N}}$ (or from some other uncountable set) to the set of countable graphs. There are many, many ways to do this.

Here's one way: I will construct a countable graph corresponding to a function $f: \mathbb{N} \rightarrow \{0,1\}$. The graph has vertices $y$ and $x_{n,i}$ for $n \in \mathbb{N}$ and $1 \leq i \leq n+1$. For each fixed $n$, we connect $x_{n,i}$ for all $i$ (in a chain as Alex suggests, or a loop, or a complete graph-- any will work). Then we add an edge from $y$ to $x_{n,1}$ if $f(n)=1$.

This is indeed an injection; we can recover $f$.

Edit: At first I had a multigraph construction, with multiple edges to each vertex, which is not what the question wanted. I have modified the construction to make a simple graph.

  • 1
    You could just more vertices in between $y$ and $x_n$ to break up each edge, which I don't think would interfere with the isomorphism classes.2011-03-16
3

Here is a bijection between $[0,1) \subset \mathbb{R}$, which is uncountable, and a pairwise non-isomorphic collection of countably infinite graphs:

For $x \in [0,1)$, let $0.x_1 x_2 x_3 ....$ be its unique decimal expansion (so $0\le x_i<10$ for each $i$, and no expansion ends in infinitely many 9's). Construct the graph $G_x$ as follows: start with the 3-cycle on $\{a,b,c\}$; attach the infinite chain $(a,1,2,3,...)$ to node $a$; and attach a chain of length $x_i$ to each node $i \ge 1$.

A minimal modification of this (use chain length $x_1 x_2 ... x_i$ in place of $x_i$) gives a bijection that preserves the order relation: $G_x$ is a subgraph of $G_y$ if and only if $x \le y$.

2

I assume you mean by countable graph one that is countably infinite. I will also assume that your relation can be an arbitrary binary relation and not just symmetric since you seem to be interested in that case.

In this case there are uncountably many. For, a special case of a binary relation is a total order. We do not need to add anything to the theory to have a total order; it's just a special case and ordering will be preserved by isomorphism. There are uncountably many nonisomorphic orders on a totally ordered set.

Indeed let $N$ be the natural numbers. Let $S$ be a subset of $N$. Replace each $s\in S$ by a copy of $\mathbb{Q}\cap [0,1]$ where $\mathbb{Q}$ are the rationals. It's easy to show that if $S\not = T$ then you will get nonisomorphic orders this way. But there are uncountably many subsets of $N$.

So there are uncountably many orders on a countable set.

  • 0
    Oh, it's short for the theory.2011-03-16
2

Another very simple way to show that they are uncountable is with well-orderings: By definition the well-orderings of a countable set are $\aleph_1$.

EDIT: Here's another simple way to show that they are $2^{\aleph_0}$ many. Take all but one (let's call it $p$) of the countable nodes and order them with the standard order of the natural numbers. This essentially assigns to every of these nodes a natural number. Now use the edgeless node $p$ that we kept to describe characteristic functions: For every subset $X$ of the natural numbers add an edge from the node that denotes $n$ to $p$ if and only if $n\in X$. It's trivial to see that all these graphs are not isomorphic: If two of them were then two different sets of natural numbers would coincide.

2

You might be interested in a related, but quite different, question. Suppose we choose the edges of a countable graph randomly, according to some probability $p$. How many different graphs do we expect to get, if we repeat the experiment several times?

You might think that every time we'll get a different graph, but in fact, with probability $1$ the graph generated will be isomorphic to the so-called Rado graph. This is the same graph immaterial of the probability $p$, and you even get the same graphs if the probabilities decay not too fast (under some arbitrary $\omega$-ordering of the edges).

The charming proof is an illustration of the back-and-forth argument - check it out.

1

In Wilfrid Hodges "Model Theory", p. 355, I found as an exercise:

(c) if L is the signature with one binary relation symbol, there are continuum many non-isomorphic ultrahomogeneous $\omega$-categorical structures of signature L.

which seems a little bit stronger: ultrahomogeneous and $\omega$-categorical!