Prev: Better late than never
Next: Logic Researchers: Collaborate with over 14,300 Researchers at MyNetResearch.com
From: George Greene on 28 Jun 2010 00:45
On Jun 27, 12:39 pm, Newberry <newberr...(a)gmail.com> wrote:
> Thus Cantor's diagonal argument cannot be used to produce uncountably many
> computable reals; at best, the reals formed from this method will be
> uncomputable.
>
> Now there are two questions:
>
> A) Can we formlate a set theory such that only countable reals exist?

You mis-spoke here. You either meant to say
"such that only" countablY MANY "reals exist", or
"such that only" coMPUTABLE "reals exist.
The answer is "No" in both cases, but the reasons (obviously) will be
different.
As for the "countably many" case, you may formulate any theory you
like,
but BY DEFINITION a "real" is a member of the powerset of the smallest
infinite set, so obviously, you are not going to get "only countably
many reals"
existing without doing enough violence to the theory that it arguably
no longer
counts as a set theory. One way to banish uncountable higher infinity
is
again obviously, simply to drop the axiom of infinity, but if you do
that,
then even N itself becomes "uncountable", and its very existence
cannot even
be proven. Only finite things would be provably available to be
counted or to count with.
Infinite sets might still exist in some models but it would no longer
be provable
that any infinite set might exist.


> B) Can we postulate the existence of 1-2-1 mapping from naturals to
> computable reals?

Yes.

> If so this list does not have an antidiagonal.

Not exactly. It would be necessary in this case for the mapping,
despite existing,
to ITSELF NOT be computable. ZFC doesn't inherently care about what's
computable
and what isn't; you have to add some definitions to it to create a
computability predicate,
not just for reals but for sets in general. You would need at least
two levels of computability,
one for individual subsets of N and another for predicates about sets
that were encodable
as susbets of N.


> Some will object that the function from naturals to reals is not
> constructive. What the heck does it matter?

The problem would not be that it's not *constructive*:
it would be that it's not COMPUTABLE.
From: Newberry on 28 Jun 2010 11:52
On Jun 27, 9:45 pm, George Greene <gree...(a)email.unc.edu> wrote:
> On Jun 27, 12:39 pm, Newberry <newberr...(a)gmail.com> wrote:
>
> > Thus  Cantor's diagonal argument cannot be used to produce uncountably many
> > computable reals; at best, the reals formed from this method will be
> > uncomputable.
>
> > Now there are two questions:
>
> > A) Can we formlate a set theory such that only countable reals exist?
>
> You mis-spoke here.  You either meant to say
> "such that only" countablY MANY "reals exist", or
> "such that only" coMPUTABLE "reals exist.

OK, such that only computable reals exist and only countably many
relas exist.

> The answer is "No" in both cases, but the reasons (obviously) will be
> different.
> As for the "countably many" case, you may formulate any theory you
> like,
> but BY DEFINITION a "real" is a member of the powerset of the smallest
> infinite set, so  obviously, you are not going to get "only countably
> many reals"
> existing without doing enough violence to the theory that it arguably
> no longer
> counts as a set theory.  One way to banish uncountable higher infinity
> is
> again obviously, simply to drop the axiom of infinity, but if you do
> that,
> then even N itself becomes "uncountable", and its very existence
> cannot even
> be proven.

How about dropping the axiom of separation?

>   Only finite things would be provably available to be
> counted or to count with.
> Infinite sets might still exist in some models but it would no longer
> be provable
> that  any infinite set might exist.
>
> > B) Can we postulate the existence of 1-2-1 mapping from naturals to
> > computable reals?
>
> Yes.
>
> > If so this list does not have an antidiagonal.
>
> Not exactly.  It would be necessary in this case for the mapping,
> despite existing,
> to ITSELF NOT be computable.  ZFC doesn't inherently care about what's
> computable
> and what isn't; you have to add some definitions to it to create a
> computability predicate,
> not just for reals but for sets in general.  You would need at least
> two levels of computability,
> one for individual subsets of N and another for predicates about sets
> that were encodable
> as susbets of N.
>
> > Some will object that the function from naturals to reals is not
> > constructive. What the heck does it matter?
>
> The problem would not be that it's not *constructive*:
> it would be  that it's not COMPUTABLE.

From: Jesse F. Hughes on 2 Jul 2010 09:06
Newberry <newberryxy(a)gmail.com> writes:

> On Jun 27, 8:32 pm, Rupert <rupertmccal...(a)yahoo.com> wrote:
>> In a set theory which only permits computable reals, it cannot exist,
>> because the real which encodes the function is not computable.
>
> Why does the function have to be encoded?

It seems to me that your real question is something like this:

Is there a (sensible?) set theory in which the "natural" set R of reals
is such that:

(1) Every real number is computable.

(2) Not every function N -> R is computable.

In such a theory, R would presumably be countable (internally as well as
externally), so what happens with Cantor's theorem?

My own guess is that there is no reasonable set theory in which R
satisfies the above, because R would not satisfy the important
properties of real numbers (closure under Cauchy sequences, for
instance). If R in our theory isn't closed under limits of Cauchy
sequences, then it isn't really much like the reals.

--
"Not all features that are found on the Security tab are designed to
help make your documents and files more secure." --Microsoft on Office
security features (after it was pointed out by a third party that a
certain password setting is easily bypassed.)

From: Alan Smaill on 2 Jul 2010 12:13
"Jesse F. Hughes" <jesse(a)phiwumbda.org> writes:

> Newberry <newberryxy(a)gmail.com> writes:
>
>> On Jun 27, 8:32�pm, Rupert <rupertmccal...(a)yahoo.com> wrote:
>>> In a set theory which only permits computable reals, it cannot exist,
>>> because the real which encodes the function is not computable.
>>
>> Why does the function have to be encoded?
>
> It seems to me that your real question is something like this:
>
> Is there a (sensible?) set theory in which the "natural" set R of reals
> is such that:
>
> (1) Every real number is computable.
>
> (2) Not every function N -> R is computable.
>
> In such a theory, R would presumably be countable (internally as well as
> externally), so what happens with Cantor's theorem?

It says that that any surjective function N -> R is not computable.

> My own guess is that there is no reasonable set theory in which R
> satisfies the above, because R would not satisfy the important
> properties of real numbers (closure under Cauchy sequences, for
> instance). If R in our theory isn't closed under limits of Cauchy
> sequences, then it isn't really much like the reals.

What if R is closed under something like effective Cauchy sequences
(where the sequence as a function N -> R is required to be computable);
wouldn't that be pretty much like the reals?


--
Alan Smaill
From: Daryl McCullough on 2 Jul 2010 12:43
Jesse F. Hughes says...
>
>Newberry <newberryxy(a)gmail.com> writes:
>
>> On Jun 27, 8:32=A0pm, Rupert <rupertmccal...(a)yahoo.com> wrote:
>>> In a set theory which only permits computable reals, it cannot exist,
>>> because the real which encodes the function is not computable.
>>
>> Why does the function have to be encoded?
>
>It seems to me that your real question is something like this:
>
>Is there a (sensible?) set theory in which the "natural" set R of reals
>is such that:
>
>(1) Every real number is computable.
>
>(2) Not every function N -> R is computable.

There is an interesting intuitionistic set theory that is very similar to ZF,
except for a few subtle differences (that are only meaningful given
intuitionistic logic): Noncomputable functions are definable, but they aren't
*functions*. For a set of ordered pairs f to be a *function*, it must be the
case that:

forall x in domain(f), exists y in range(f), <x,y> in f
and forall z in range(f), <x,z> in f -> z=y.

If you try to define a noncomputable function as a set of ordered pairs, you can
define it, but then you can't prove that it actually *is* a function. In
particular, if you try to define the halting function f(x) = 0 if x is the code
for a Turing machine that halts on input 0, and f(x) = 1, otherwise, then you
can define this as a set of ordered pairs, but without using the law of excluded
middle, you can't prove that that set defines a function.

I think it's the case that with the usual definition of real number, there are
no noncomputable reals in this theory.

--
Daryl McCullough
Ithaca, NY

First  |  Prev  |  Next  |  Last
Pages: 1 2 3
Prev: Better late than never
Next: Logic Researchers: Collaborate with over 14,300 Researchers at MyNetResearch.com