Re: Another set with cardinality |Z|

• Previous message: Eray Ozkural exa: "Re: Zenkin's paper on Cantor"
• Next in thread: Eray Ozkural exa: "Re: Another set with cardinality |Z|"
• Reply: Eray Ozkural exa: "Re: Another set with cardinality |Z|"
• Maybe reply: jesus harold christ: "Re: Another set with cardinality |Z|"
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

Date: Fri, 1 Oct 2004 00:25:07 -0400

[Eray Ozkural]
...
> In this (undirected) tree every vertex except the root vertex is
> incident with exactly three edges. Or if we view it as a directed tree,
> exactly one incoming edge, and two outgoing edges. Am I right?

Sure.

> So, this tree has (by definition)
> |V| = |E| = Aleph-0
> |paths| = c

Those are all true, but none really by definition. That the set of vertices
is countable requires proof (which has been given: it's a countable union
of finite sets). Similarly for the other two.

> While I appreciate this, I cannot prove that there is no bijection
> between the power of a level set I defined (namely all the levels
> excluding the root, cardinality Aleph-0) and the vertex set by an
> induction on the depth of the tree. How to accomplish that? It seemed
> so easy!

Sorry, I don't remember your "level sets" from before, and can't tell what
they are from that description. Is it something like "in a finite
'complete' binary tree with n levels below the root, there are 2^n paths and
2^n+1 vertices, 'therefore' if there are aleph_0 levels below the root there
must be 2^aleph_0 paths and 2^aleph_0+1 == 2^aleph_0 vertices"?

If so, then all I can say is that's the kind of result you get by making
stuff up instead of studying the basics and *then* proving things <wink>.
The same kind of "intuitive" symbol-pushing could just as well conclude that
1 = 0 by subtracting 2^aleph_0 from both sides of 2^aleph_0+1 = 2^aleph_0.

> ...
> Now, another question. How can I prove this fact that there are more
> paths than vertices in this infinite tree? Can I prove it without
> invoking Cantor's theorems?

Very easily, but you won't like it <wink>. Suppose there were a bijection
between the set of vertices and the set of paths. Since the set of vertices
is countable, that bijection can be listed:

vertex path
------ ----
v1 left, left, right, left, right, right, left, right, ...
v2 left, left, left, left, left, left, right, left, left, ...
...
v_i p_i_1, p_i_2, p_i_3, ...
...

Now construct a path p with p_i = left if p_i_i = right, or p_i = right if
p_i_i = left, for all i >= 1. That path, by construction, is not in the
listing. Therefore the claimed bijection isn't one.

Diagonal methods are used so often not because they're the only methods, but
because they're so often the simplest methods; indeed they're often
darned-near obvious methods. Note that the proof above doesn't have
anything to do with the vertices in your tree beyond that they're countable.
It really shows that there's no bijection between the set of paths and any
countable set.

BTW, an infinite path in the tree is a mapping from the naturals to the set
{left, right}. By the definition of cardinal exponentiation, there are

    |{left, right}|^|N|

which is

    2^aleph_0

such mappings. You can also view a path as the characteristic function for
a subset of naturals, via saying, e.g., that p_i = left means i is in the
subset, and p_i = right means i is not in the subset. So the set of paths
is also equinumerous with the powerset of the naturals.

The number of vertices is just 1 + 2 + 4 + ... = aleph_0.

Bottom line: there are more paths than vertices because it's provably so.
The proofs don't care whether intuition approves.

BTW2, William Zwicker found another elementary way of showing that the
powerset of N is bigger than N, but it's not as simple as Cantor's diagonal
proof (I doubt anything could be simpler than that!). Suppose there is a
bijection B: N -> P(N). So B(i) is the subset of naturals identified with
i.

A "Zwicker path" starts by picking a (any) integer i. Then it's extended by
this rule: look at the last integer j on the path so far. If B(j) is the
empty set, the path ends. If B(j) is not the empty set, add any element of
B(j) to the path, and continue.

Call an integer i "normal" if all Zwicker paths starting with i are finite.

For example, if B(0) = {} and B(1) = {0) and B(2) = {1, 2}, then

   - 0 is normal. The only Zwicker path starting with 0 is [0].

   - 1 is normal. The only Zwicker path starting with 1 is [1, 0].

   - 2 is not normal. While there is a finite Zwicker path starting
     with 2, there's also an infinite Zwicker path starting with 2:
     [2, 2, 2, ...].

Now let Z be the set of normal integers. Is Z in the range of B? Nope!
It's a very clever construction, and seems to have nothing in common with
Cantor's.

The "yadda yadda" part: Assume Z is in the range of B. Then Z = B(i) for
some i. Is i normal? If Z is the empty set, yes, because then [i] is the
only Zwicker path starting with i. If Z is not empty, then a Zwicker path
starting with i has as its second element j an element of B(i) = Z, and j is
normal by the definition of Z. So all Zwicker paths starting with j are
finite, so all Zwicker paths starting with [i, j, ...] are also finite. So
i is normal whether Z is empty or not. But if i is normal, then i is an
element of B(i), so that [i, i, i, ...] is an infinite Zwicker path starting
with i: i is *not* normal.

So Z is not in the range of B, so the claimed bijection doesn't exist.

BTW3, if you have ontological misgivings about infinities, of course
studying infinite trees isn't going to relieve them.

> IOW, how do I show that this is one of the things that gets abused.

What is it about the proof(s) above that rankles you?

> One's intuition does not readily accept that the paths extend beyond
> the set of vertices, by _more_ steps than there are vertices.

A single path contains a countable number of vertices -- no path is "longer"
than the set of vertices. It's the set of all paths that's larger than the
set of vertices.

But get uncomfortable at a more fundamental level: an infinite set can be
bijectively mapped to a proper subset of itself. Doesn't that abuse your
intuition to the screaming point? "One's intuition does not readily accept
that a set is bigger than itself" either, right? That's the kind of
statement my real-world-of-eggs-and-metronomes intuition makes about that
*fundamental* property of infinite sets. If you want a mathematics that
doesn't abuse your intuition, make your stand there, where it starts. All
the rest is elaboration. If you swallow the first infinite bite, all the
rest (including "trees" where a vertex can have ancestors but no parent)
follows. I think delightfully so, but you're welcome to find it appallingly
so.

• Previous message: Eray Ozkural exa: "Re: Zenkin's paper on Cantor"
• Next in thread: Eray Ozkural exa: "Re: Another set with cardinality |Z|"
• Reply: Eray Ozkural exa: "Re: Another set with cardinality |Z|"
• Maybe reply: jesus harold christ: "Re: Another set with cardinality |Z|"
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]