Enumerability
2 views
Skip to first unread message
Mike
Feb 2, 2009, 11:35:14 PM2/2/09
to Computability and Logic
Copied from email for the archives.
-----
I was thinking about something I said at our meeting - something like
"A set is uncountable if there is an infinity of infinities."
referring to an infinite number of numbers which are all inexpressible
by a terminating decimal.
I realized today that this is also a somewhat misleading and probably
incorrect way to describe unenumerability - for the list "1/9, 2/9,
3/9, 4/9..." displays this property when expressed in base-10 decimal,
yet, is clearly not uncountable.
I've been thinking hard about this issue and it's somewhat clear that
trying to associate the concept of unenumerability with the concept of
(finite) unexpressability in base-10 (or any base, or any scheme of
representing numbers, for that matter) are two *entirely* different
concepts and trying to explain one in terms of the other is an
exercise in futility.
I can sympathize with using the correlation as an intuitive tool - I
find myself doing it often. But to put too much faith in the intuition
is hazardous, I think.
I believe the only way to define, as it were, uncountable sets are the
ways they do in the book, that is, an uncountable set is such that
*any* enumeration will fail to exhaust the entirety of the set.
A more interesting idea I've been thinking about is *why* exactly this
is possible for countable sets, yet impossible for uncountable ones.
What is so fundamental about the action of listing the elements of a
set that certain types of sets resist it so stubbornly? Is there some
other action that is possible with the set of real numbers but is not
possible with the power set of reals?
-----
OK, let me try this again, since I also have been thinking about it
since our meeting.
How about the following statement?
If EACH element of a set S can be FULLY specified with a
finite amount of
information, then the set is enumerable.
It still connects set enumerability (B) with finite expressibility
(A) of its elements (using Nick's terminology).
By amount of information I mean the number of bits (if binary notation
is used) or the number of decimal digits, or the number of symbols of
any (enumerable) alphabet used in the specification of the elements.
This new formulation of the "rule" is just A => B, whereas at our
meeting, I was trying to argue for ~A => ~B.
The latter is clearly not true since the infinite set {pi+1, pi+2, pi
+3, ...}, as Nick pointed out, satisfies ~A, but does satisfy B.
On the other hand, there is obviously a more fundamental problem here,
which is how to define "finite expressibility".
One could make the argument that 1/9 IS a finite expression that FULLY
specifies the infinite decimal expansion 0.11111..., since there is a
mechanical procedure to generate (arbitrarily long prefixes of) the
decimal expansion using only the input 1 and 9 (namely long division).
Unfortunately, the same could be said of pi.
But is this true of all transcendental numbers? What do we mean by
finite expressibility?
-----
> > If EACH element of a set S can be FULLY
> > specified with a finite amount of
> > information, then the set is enumerable.
>
>
> Hmm - I think you might get into trouble with the set of all
> functions from R to R on that one. The set is uncountable,
> apparently it's bigger than the set of reals (~B), yet all its
> members are specifiable with a finite amount of information (A) -
> is that right? It's almost closing time on friday so it's hard
> for me to think straight...
>
> If this is right i think this is a better argument than my last
> for uncountability having to do with "listability" rather than
> "specifiabilty", which makes perfect sense, if you consider that
> "our", in a general sense, ways of representing numbers (or
> functions, or anything) is arbitrary, in a sense, and one way of
> specifying numerals may be more finite than another... I think.
-----
Well, all functions can be simply defined by the list of all
(argument,value) pairs, which is obviously an infinite description,
whether the numbers involved are in N or R (although it is "more
infinite" over R than over N 8^)
Of course, some functions can be defined by a finite expression. For
example:
the function: (1,2), (2,4), (3,6), (4,8), ... can also be fully
specified by "for all n, f(n) = 2n", which is finite, even if one
includes as part of the expression the algorithm for doing
multiplication. But then, the sub-expression, "for all n" also hides a
lot of inductive reasoning on the natural numbers, which should be
explicitly included in the expression of the function. Which goes
back to my earlier point: what to we mean by finitely expressing/
specifying an element of the set? Where do we bottom out? There are
obviously some sub-expressions that will have to remain undefined.
So, to go back to your question, how would you specify each and every
function from R -> R (or even N->N) using finite information?
-----
Ahh yes, i seem to have forgetten that there are more functions than
turing machines... still, the definition of "finite expressibility" is
elusive - perhaps that reason alone is good enough to distinguish
between expressibility and uncountability... but maybe not. It's an
interesting question nonetheless.
-----
I was thinking about something I said at our meeting - something like
"A set is uncountable if there is an infinity of infinities."
referring to an infinite number of numbers which are all inexpressible
by a terminating decimal.
I realized today that this is also a somewhat misleading and probably
incorrect way to describe unenumerability - for the list "1/9, 2/9,
3/9, 4/9..." displays this property when expressed in base-10 decimal,
yet, is clearly not uncountable.
I've been thinking hard about this issue and it's somewhat clear that
trying to associate the concept of unenumerability with the concept of
(finite) unexpressability in base-10 (or any base, or any scheme of
representing numbers, for that matter) are two *entirely* different
concepts and trying to explain one in terms of the other is an
exercise in futility.
I can sympathize with using the correlation as an intuitive tool - I
find myself doing it often. But to put too much faith in the intuition
is hazardous, I think.
I believe the only way to define, as it were, uncountable sets are the
ways they do in the book, that is, an uncountable set is such that
*any* enumeration will fail to exhaust the entirety of the set.
A more interesting idea I've been thinking about is *why* exactly this
is possible for countable sets, yet impossible for uncountable ones.
What is so fundamental about the action of listing the elements of a
set that certain types of sets resist it so stubbornly? Is there some
other action that is possible with the set of real numbers but is not
possible with the power set of reals?
-----
OK, let me try this again, since I also have been thinking about it
since our meeting.
How about the following statement?
If EACH element of a set S can be FULLY specified with a
finite amount of
information, then the set is enumerable.
It still connects set enumerability (B) with finite expressibility
(A) of its elements (using Nick's terminology).
By amount of information I mean the number of bits (if binary notation
is used) or the number of decimal digits, or the number of symbols of
any (enumerable) alphabet used in the specification of the elements.
This new formulation of the "rule" is just A => B, whereas at our
meeting, I was trying to argue for ~A => ~B.
The latter is clearly not true since the infinite set {pi+1, pi+2, pi
+3, ...}, as Nick pointed out, satisfies ~A, but does satisfy B.
On the other hand, there is obviously a more fundamental problem here,
which is how to define "finite expressibility".
One could make the argument that 1/9 IS a finite expression that FULLY
specifies the infinite decimal expansion 0.11111..., since there is a
mechanical procedure to generate (arbitrarily long prefixes of) the
decimal expansion using only the input 1 and 9 (namely long division).
Unfortunately, the same could be said of pi.
But is this true of all transcendental numbers? What do we mean by
finite expressibility?
-----
> > If EACH element of a set S can be FULLY
> > specified with a finite amount of
> > information, then the set is enumerable.
>
>
> Hmm - I think you might get into trouble with the set of all
> functions from R to R on that one. The set is uncountable,
> apparently it's bigger than the set of reals (~B), yet all its
> members are specifiable with a finite amount of information (A) -
> is that right? It's almost closing time on friday so it's hard
> for me to think straight...
>
> If this is right i think this is a better argument than my last
> for uncountability having to do with "listability" rather than
> "specifiabilty", which makes perfect sense, if you consider that
> "our", in a general sense, ways of representing numbers (or
> functions, or anything) is arbitrary, in a sense, and one way of
> specifying numerals may be more finite than another... I think.
-----
Well, all functions can be simply defined by the list of all
(argument,value) pairs, which is obviously an infinite description,
whether the numbers involved are in N or R (although it is "more
infinite" over R than over N 8^)
Of course, some functions can be defined by a finite expression. For
example:
the function: (1,2), (2,4), (3,6), (4,8), ... can also be fully
specified by "for all n, f(n) = 2n", which is finite, even if one
includes as part of the expression the algorithm for doing
multiplication. But then, the sub-expression, "for all n" also hides a
lot of inductive reasoning on the natural numbers, which should be
explicitly included in the expression of the function. Which goes
back to my earlier point: what to we mean by finitely expressing/
specifying an element of the set? Where do we bottom out? There are
obviously some sub-expressions that will have to remain undefined.
So, to go back to your question, how would you specify each and every
function from R -> R (or even N->N) using finite information?
-----
Ahh yes, i seem to have forgetten that there are more functions than
turing machines... still, the definition of "finite expressibility" is
elusive - perhaps that reason alone is good enough to distinguish
between expressibility and uncountability... but maybe not. It's an
interesting question nonetheless.
Mike
Feb 3, 2009, 12:27:14 AM2/3/09
to Computability and Logic
I like the distinction between enumerability and finite
expressability. It seems clear that these are two separate concepts,
and I believe enumerability comes down to what Nick said: "an
>"A more interesting idea I've been thinking about is *why* exactly this
>is possible for countable sets, yet impossible for uncountable ones.
>What is so fundamental about the action of listing the elements of a
>set that certain types of sets resist it so stubbornly? Is there some
>other action that is possible with the set of real numbers but is not
>possible with the power set of reals?"
I'm not sure if I understood the question posed, doesn't the set of
all natural numbers, described in the text, { 1, 3, 5, 7, ... , 2, 4,
6, 8 } intuitively explains the concept? Which also differentiates
enumerability vs. finite expressability. Although each element can be
finitely expressed, the list as a whole is unenumerable. I believe
this counters the statement:
> If EACH element of a set S can be FULLY
> specified with a finite amount of
> information, then the set is enumerable.
Where are you trying to go with finite expressability? At first I
thought this was for the elements of the range, is it generalizable to
the elements of the domain as well? When are you no longer expressing
a number? For example, you mentioned that 1/9 is a finite expression
of the decimal number 0.11111..., since you could build a machine to
perform long division. But isn't the description of the rational
number a/b, namely 1/9, a perfectly valid expression (without any need
of justification to decimal representation)? However, transcendental
numbers (based on the quick definitions I looked up), are irrational
numbers which have no function to compute them. Would this mean
transcendental numbers are uncomputable? I may need clarification
here...
expressability. It seems clear that these are two separate concepts,
and I believe enumerability comes down to what Nick said: "an
uncountable set is such that
*any* enumeration will fail to exhaust the entirety of the set. ".
>"A more interesting idea I've been thinking about is *why* exactly this
>is possible for countable sets, yet impossible for uncountable ones.
>What is so fundamental about the action of listing the elements of a
>set that certain types of sets resist it so stubbornly? Is there some
>other action that is possible with the set of real numbers but is not
>possible with the power set of reals?"
all natural numbers, described in the text, { 1, 3, 5, 7, ... , 2, 4,
6, 8 } intuitively explains the concept? Which also differentiates
enumerability vs. finite expressability. Although each element can be
finitely expressed, the list as a whole is unenumerable. I believe
this counters the statement:
> If EACH element of a set S can be FULLY
> specified with a finite amount of
> information, then the set is enumerable.
thought this was for the elements of the range, is it generalizable to
the elements of the domain as well? When are you no longer expressing
a number? For example, you mentioned that 1/9 is a finite expression
of the decimal number 0.11111..., since you could build a machine to
perform long division. But isn't the description of the rational
number a/b, namely 1/9, a perfectly valid expression (without any need
of justification to decimal representation)? However, transcendental
numbers (based on the quick definitions I looked up), are irrational
numbers which have no function to compute them. Would this mean
transcendental numbers are uncomputable? I may need clarification
here...
Message has been deleted
David
Feb 3, 2009, 4:49:07 PM2/3/09
to Computability and Logic
> I'm not sure if I understood the question posed, doesn't the set of
> all natural numbers, described in the text, { 1, 3, 5, 7, ... , 2, 4,
> 6, 8 } intuitively explains the concept? Which also differentiates
> enumerability vs. finite expressability. Although each element can be
> finitely expressed, the list as a whole is unenumerable. I believe
> this counters the statement:
Since I was the one who brought the idea of "finite expressibility"
> all natural numbers, described in the text, { 1, 3, 5, 7, ... , 2, 4,
> 6, 8 } intuitively explains the concept? Which also differentiates
> enumerability vs. finite expressability. Although each element can be
> finitely expressed, the list as a whole is unenumerable. I believe
> this counters the statement:
into the discussion as a rule of thumb for figuring out (without a
proof) that a set is enumerable, I'd like to suggest that we drop it.
It just seems to me that it confuses our group discussions rather than
help. Just my 2 cents...
>
> > If EACH element of a set S can be FULLY
> > specified with a finite amount of
> > information, then the set is enumerable.
>
> Where are you trying to go with finite expressability? At first I
> thought this was for the elements of the range, is it generalizable to
> the elements of the domain as well? When are you no longer expressing
> a number? For example, you mentioned that 1/9 is a finite expression
> of the decimal number 0.11111..., since you could build a machine to
> perform long division. But isn't the description of the rational
> number a/b, namely 1/9, a perfectly valid expression (without any need
> of justification to decimal representation)? However, transcendental
> numbers (based on the quick definitions I looked up), are irrational
> numbers which have no function to compute them. Would this mean
> transcendental numbers are uncomputable? I may need clarification
> here...
algebraic, they have an infinite fractional expansion
and are thus not computable in a finite amount of time. On the other
hand, there are functions to compute the full expansion of PI, but it
will get you only so far in a given amount of time. Does that make
sense?
Mike
Feb 3, 2009, 5:20:35 PM2/3/09
to Computability and Logic
> Since I was the one who brought the idea of "finite expressibility"
> into the discussion as a rule of thumb for figuring out (without a
> proof) that a set is enumerable, I'd like to suggest that we drop it.
> It just seems to me that it confuses our group discussions rather than
> help. Just my 2 cents...
>
elements of the list have no need to be finitely computable, correct?
This satisfies Nick's argument of the list {pi, pi+1, pi+2, ...}.
Basically, as long as every element as some finite natural number as
its index in the set?
> Since transcendental numbers such as PI are not rational and not
> algebraic, they have an infinite fractional expansion
> and are thus not computable in a finite amount of time. On the other
> hand, there are functions to compute the full expansion of PI, but it
> will get you only so far in a given amount of time. Does that make
> sense?
night!
David
Feb 3, 2009, 5:28:29 PM2/3/09
to Computability and Logic
> it seems that individual
> elements of the list have no need to be finitely computable, correct?
> This satisfies Nick's argument of the list {pi, pi+1, pi+2, ...}.
> Basically, as long as every element as some finite natural number as
> its index in the set?
I agree. In fact, that was the point where my INITIAL intuitive
> elements of the list have no need to be finitely computable, correct?
> This satisfies Nick's argument of the list {pi, pi+1, pi+2, ...}.
> Basically, as long as every element as some finite natural number as
> its index in the set?
approach/rule of thumb for determining whether a set was non-
enumerable broke down, and the reason why I reversed my "rule" in our
earlier email discussion in order to determine when a set IS
enumerable. Oh well, enough with these "finite expressibility"
arguments...
Message has been deleted
David
Feb 3, 2009, 7:51:42 PM2/3/09
to Computability and Logic
> I'm confused here - in what sense are we using "computable"?
Turing-computable would appear to be an obvious choice for us, CS
types. But I would be fine with defining it as abacus-computable, or
recursively computable etc., or even effectively computable, since I
am not in the mood to argue against Turing/Church's thesis.
> Im not
> sure time has anything to do with it -- it would take an infinite
> amount of time to "compute" all the decimals of 1/9... yet it is not
> transcendental. In the same sense, like Dr. Furcy mentioned, there are
> infinite series that sum to pi... aren't these "computable" in a
> similar sense as 1/9? I think transcendental and computable are two
> different ideas...
Certainly. But without the two notions being identical or even
directly related, why couldn't I ask the question:
Is the function f(n) = PI + n computable?
Turing-computable would appear to be an obvious choice for us, CS
types. But I would be fine with defining it as abacus-computable, or
recursively computable etc., or even effectively computable, since I
am not in the mood to argue against Turing/Church's thesis.
> Im not
> sure time has anything to do with it -- it would take an infinite
> amount of time to "compute" all the decimals of 1/9... yet it is not
> transcendental. In the same sense, like Dr. Furcy mentioned, there are
> infinite series that sum to pi... aren't these "computable" in a
> similar sense as 1/9? I think transcendental and computable are two
> different ideas...
Certainly. But without the two notions being identical or even
directly related, why couldn't I ask the question:
Is the function f(n) = PI + n computable?
Reply all
Reply to author
Forward
0 new messages