Re: Another set with cardinality |Z|

stephen_at_nomail.com
Date: 09/28/04 

Date: 28 Sep 2004 16:08:47 GMT

In comp.theory Eray Ozkural exa <erayo@bilkent.edu.tr> wrote:
: stephen@nomail.com wrote in message news:<cjahpf$cld$1@msunews.cl.msu.edu>...
:> In comp.theory Eray Ozkural exa <erayo@bilkent.edu.tr> wrote:
:> : "Tim Peters" <tim.one@comcast.net> wrote in message news:<R5adnTP0EPYGCMXcRVn-uw@comcast.com>...
:> :> It's unclear what you mean by "infinite path" (I realize you don't think
:> :> it's unclear <wink>). Perhaps part of what you intend is that by "path" you
:> :> mean "simple path" (a path that never visits a vertex twice). It's also
:> :> unclear what you mean by "pick".
:>
:> : I indeed meant simple path. It's been a while since I took the graph
:> : theory course, so some imprecision may have found its way into my
:> : terms.
:>
:> : By "pick", I mean the ordinary graph theoretic usage of "choose", such
:> : as in "choose any vertex u of G", or "choose a minimal A-B path".
:>
:> If you pick any two vertices u and v, then the depth of u, d(u), will
:> be finite and the depth of v, d(v), will be finite. The length
:> of the path between u and v will be either d(u)+d(v) or |d(u)-d(v)|,
:> both of which are finite. It seems pretty intuitive to me that
:> there are no infinite paths in your tree.

: That's very interesting indeed, but a path does not have to be named
: like that to exist, in my opinion.

In order for a path to exist it must connect to vertices that exist.
Every vertex has a finite depth.

: I can show inductively that I can always find a path of length one
: more than you can (stating your choice as a base case), e.g. the
: agreed upon definition of countable infinity, hence there is at least
: one simple path that has infinite cardinality. You can view the path
: as a set of pairs (u,i) where u is a vertex and i is its a position in
: the sequence, starting from 1. All i's are finite, but the cardinality
: of the set is |N|. Does that make sense?

No. It makes as mush sense as claiming that there is an infinite
integer because you can always find an integer larger than any
integer I name. There are no infinite integers.

Stephen

Relevant Pages

  • Re: Another set with cardinality |Z|
    ... In comp.theory Eray Ozkural exa wrote: ... since this is a nonhalting algorithm (or since I can ... : infinite binary expansion. ... simply are counter to most people's intuitions. ...
    (comp.theory)
  • Re: Another set with cardinality |Z|
    ... In comp.theory Eray Ozkural exa wrote: ... since this is a nonhalting algorithm (or since I can ... : infinite binary expansion. ... simply are counter to most people's intuitions. ...
    (sci.math)
  • Re: Another set with cardinality |Z|
    ... :> In comp.theory Eray Ozkural exa wrote: ... one simple path that has infinite cardinality. ... It makes as mush sense as claiming that there is an infinite ...
    (comp.theory)
  • Re: Raatikainens critique of Chaitin
    ... Eray Ozkural exa wrote: ... >>There is an infinite number of twin primes, ... It is useful (makes proofs easier/shorter) ...
    (sci.math)
  • Re: Raatikainens critique of Chaitin
    ... Eray Ozkural exa wrote: ... >>There is an infinite number of twin primes, ... It is useful (makes proofs easier/shorter) ...
    (comp.theory)