Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/5/84; site anasazi.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!bellcore!decvax!ittatc!dcdwest!sdcsvax!sdcrdcf!hplabs!hao!noao!terak!mot!anasazi!steve
From: steve@anasazi.UUCP (Steve Villee)
Newsgroups: net.puzzle
Subject: Re: truth machine clarification**2
Message-ID: <659@anasazi.UUCP>
Date: Wed, 19-Mar-86 15:47:22 EST
Article-I.D.: anasazi.659
Posted: Wed Mar 19 15:47:22 1986
Date-Received: Sun, 23-Mar-86 00:48:01 EST
References: <423@watdragon.UUCP> <2664@pucc-h> <394@link.UUCP>
Organization: Anasazi, Phoenix Az.
Lines: 45

> Or perhaps he's right, if he just means that any particular sentence
> is of finite length.  But as long as that length is unbounded, you
> still haven't guaranteed a countable language.  Here's another grammar:
> 
> S --> aS
> S --> bS
> S --> a
> S --> b
> 
> The language is any nonempty string of a and b.  Any particular sentence
> is finite, but the language is ripe for a diagonal argument showing that
> it's uncountable.    Readers for whom the construction is obvious,
> please skip to end.
>      Give me a putative mapping from the natural numbers
> to the sentences of this language, and I construct a sentence which differs
> from your sentence #1 in place #1, differs from your #2 in place #2, etc,
> yet which accords with the grammar.  This is easy to do: if your sentence
> #n has length n or greater, I pick the other character at position #n; if
> your sentence #n is shorter than n characters, I freely pick a or b.  My
> sentence is a nonempty string of a and b, so it's in the language.  Is it
> on your list?  You have it as #1307?  No, it differs in position #1307.
> -- 
> 
>             -- Mitch Marks @ UChicago 
>                ...ihnp4!gargoyle!sphinx!mmar

I think this argument is faulty, and that the set of sentences in the above
language is in fact countable.  One obvious bijection from the natural numbers
to this set is as follows.  For each natural number n, represent n+1 in base 2.
The first (i.e. most significant) digit will be a 1.  Discard this digit.
For the remaining digits, substitute a for 0 and b for 1.  You now have the
sentence to be associated with the number n.  This is assuming 0 is not a
natural number; many mathematicians include 0, in which case you need to
represent n+2 in base 2 instead of n+1.

Mitch attempts to construct a sentence which is not associated with any
natural number under my mapping.  However, if I am reading correctly, his
sentence is not of finite length.  Of course, if the language includes
infinitely long strings of a and b, then the set is not countable.

--- Steve Villee (ihnp4!terak!anasazi!steve)
    International Anasazi, Inc.
    7500 North Dreamy Draw Drive, Suite 120
    Phoenix, Arizona 85020
    (602) 870-3330