Re: Another set with cardinality |Z|

From: Tim Peters (tim.one_at_comcast.net)
Date: 09/28/04

  • Next message: Robert Low: "Re: Another set with cardinality |Z|" 
    Date: Mon, 27 Sep 2004 23:54:02 -0400

    [Tim Peters]
    >> The set of paths in your tree has cardinality c. The set of vertices
    >> has cardinality aleph_0. "Intuition" derived from experience with
    >> *finite* trees is that there's a bijection between the set of vertices
    >> and the set of paths (identify each vertex with the path from the root
    >> to that vertex). Intuition derived from finite trees simply doesn't
    >> extend to infinite trees. You may be taking a wrong lesson from your
    >> example <wink>.

    [Eray Ozkural]
    > You mean an infinite tree is no more a tree.

    If by "a tree", you mean a finite tree, then yes, an infinite tree is not a
    tree. But it would be more fruitful to pick a non-private definition of
    infinite trees, and see what follows from that.

    > That's worse than merely being counter intuitive.

    I don't think so. If you want to insist that combinatoric properties you
    like are preserved when going beyond the finite, you're going to be baffled
    deeply and often. I suggest the *only* thing that's bothering you here is
    in fact your intuition, and that your intuition is misleading you here. The
    number of edges in a finite tree is one less than the number of vertices,
    and you lose that in an infinite tree too. Etc. Doesn't mean an infinite
    tree isn't "a tree", it means that if you want to play with the transfinite,
    you have to stop using experience with finite structures as your guide.

    > I should require a reference for this "fact".

    Sorry, I know of no reference for "an infinite tree is no more a tree" other
    than your declaration above <wink>. Seriously, you're assuming something
    about trees you haven't made explicit, in your attempt to stay astonished.
    These basic facts about infinite graphs are covered in any intro to the
    subject, so pick one. Which references have you already consulted, or are
    you just flying blind (going entirely on intuition)?

    For example, König's Lemma, and that a connected locally-countable infinite
    graph (which your tree is) is countable, are both proved in the first two
    pages of the brief section on infinite graphs in Robin Wilson's
    _Introduction to Graph Theory_.

    On the other hand, you shouldn't need that. As has been pointed out more
    than once here, the set of vertices in your tree is a countable union of
    finite sets, so the set of vertices is countable by a fundamental result in
    the theory of cardinals (and, indeed, Wilson's proof of the countability of
    a connected locally-countable infinite graph amounts to no more than that).

  • Next message: Robert Low: "Re: Another set with cardinality |Z|"

    Relevant Pages

    • Re:Mueckenheims Confusion
      ... >> This does not tell us anything about the infinite tree. ... The cross sections ... binary tree, but the cardinality of the set of paths, which is easily ...
      (sci.math)
    • Re: Another set with cardinality |Z|
      ... >> The set of paths in your tree has cardinality c. ... > You mean an infinite tree is no more a tree. ... number of edges in a finite tree is one less than the number of vertices, ... These basic facts about infinite graphs are covered in any intro to the ...
      (sci.math)
    • Re: Cantor Confusion
      ... infinite union of finite trees is the infinite tree. ... It is easy to see that these unions result in the infinite tree, i.e., ... already clear when considering the countablility of nodes and edges, ...
      (sci.math)
    • Re: Cantor Confusion
      ... no contradiction. ... In an infinite binary tree there are twice as many ... At the level n the ratio of eges over paths is expressed by ... in the infinite tree? ...
      (sci.math)
    • Re: Cantor Confusion
      ... no contradiction. ... In an infinite binary tree there are twice as many ... At the level n the ratio of eges over paths is expressed by ... in the infinite tree? ...
      (sci.math)