I've been wondering what the cardinality of all binary trees would be?
Let me define binary trees to be clear. I am using an inductive definition :
The set $B(\mathbb{N})$ of binary trees over the natural numbers is defined as follows :
- $\epsilon$ is the empty tree and $\epsilon \in B$
- if $l \in B$ and $r \in B$ and $v \in \mathbb{N}$ then $(l, v, b) \in B$
I have a feeling it is uncountable.
To prove that it is uncountable I would have to somehow conjure up Cantor's diagonalization argument.
At first, I tried listing all traversals of one kind, say preorder traversals. I found out very quickly that this would not work. For any one traversal, there exists more than one binary tree.
I'm not even sure that the set is uncountable, I just have a very strong feeling.
Is there any standard technique on how to talk about the cardinality of inductively defined sets that I could use?
Best Answer
You can use your definition to show there are only countably many such binary trees for every given size $n$ using induction. Let $B_n$ be the set of binary trees on $n$ vertices. The case $n=0$ is clear, there is only one empty tree.
If $n>0$ then for any given $v\in \mathbb{N}$ there are most $$ \left| \bigcup_{i=0}^{n-1} B_i \times B_{n-1-i}\right| $$ binary trees of the form $(l,r,v)$ with $n$ vertices as you describe. This is countably many, and so ranging over all $v$ we get that $|B_n|$ is countable.
Then the total number is $|B_1\cup B_2 \cup\ldots |$, a countable union of countable sets, which is countable