Does Wolfram say all functional graphs have countably many vertices?

Question

Does Wolfram here say all functional graphs have countably many vertices?

Let a functional graph $G$ map the orbit of the following function $f:\Bbb Z_p\to\Bbb Z_p$

$x\mapsto p^{-1}\cdot(x-(x\pmod p))$ through the $p-$adic integers.

(Here $x\pmod p$ is the function that maps to the natural number $n$ representative of some element of $\Bbb Z/p\Bbb Z$ which is $0\leq n<p$) So you can think of $f$ as simply deleting the most significant digit of any $p-$adic number.

Then this functional graph comprises uncountably many connected subgraphs. The ones with eventually periodic orbits of period $m$ can be represented by the base $p$ Lyndon words of length $m$. Then there are uncountably many left over, which one needs the axiom of choice to pick representatives of.

I'm confused by where Wolfram says;

and can therefore be specified by a function mapping $\{1,...,n\}$ onto itself

which appears to imply a functional graph must be countable. How does this sentence apply to my example? As I'm pretty sure I'm misunderstanding it.

Answer 1

The functional graphs in the MathWorld article wouldn't just be countable; they'd be finite. This is not surprising to see in that article:

• Many, perhaps most discussions of graph theory only consider finite graphs; many results about finite graphs do not extend to infinite graphs, or take considerably more work to do so. If I read anything about graph theory, I would not assume it applies to infinite graphs unless this is specifically mentioned.
• In particular, if 50% of the article is devoted to implementation details in Mathematica, which cannot possibly hope to deal with infinite graphs, I think it's safe to say that it only considers the finite case.

Nevertheless, there's nothing wrong with talking about an infinite functional graph; it can be specified by a function mapping the vertex set $V$ to itself, but there's nothing inherently wrong with $V$ being infinite. Some definitions for finite graphs break down for infinite graphs before you even try to prove anything about them, but this isn't one of them.

Your example is a perfectly good uncountably infinite functional graph, though there are two warnings that should always be given in this situation:

1. Be careful about applying any particular theorems about functional graphs you encounter, before you check if those theorems make sense in the infinite (and the uncountable) settings.
2. If you're discussing it with graph theorists, you should be upfront about the vertex set being uncountably infinite if you want to avoid any confusion.