Prev: Better late than never
Next: Logic Researchers: Collaborate with over 14,300 Researchers at MyNetResearch.com
From: Newberry on 27 Jun 2010 12:39
This is from Wikipedia
http://en.wikipedia.org/wiki/Computable_reals

Although the set of real numbers is uncountable, the set of computable
numbers is countable and thus almost all real numbers are not
computable. The computable numbers can be counted by assigning a Gödel
number to each Turing machine definition. This gives a function from
the naturals to the computable reals. Although the computable numbers
are an ordered field, the set of Gödel numbers corresponding to
computable numbers is not itself computably enumerable, because it is
not possible to effectively determine which Gödel numbers correspond
to Turing machines that produce computable reals. In order to produce
a computable real, a Turing machine must compute a total function, but
the corresponding decision problem is in Turing degree 0′′. 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?

B) Can we postulate the existence of 1-2-1 mapping from naturals to
computable reals? If so this list does not have an antidiagonal.

Some will object that the function from naturals to reals is not
constructive. What the heck does it matter? The theory would be
constructive in the sense that no unconstructible set or element
exists.
From: Rupert on 27 Jun 2010 20:03
On Jun 28, 2:39 am, Newberry <newberr...(a)gmail.com> wrote:
> This is from Wikipediahttp://en.wikipedia.org/wiki/Computable_reals
>
> Although the set of real numbers is uncountable, the set of computable
> numbers is countable and thus almost all real numbers are not
> computable. The computable numbers can be counted by assigning a Gödel
> number to each Turing machine definition. This gives a function from
> the naturals to the computable reals. Although the computable numbers
> are an ordered field, the set of Gödel numbers corresponding to
> computable numbers is not itself computably enumerable, because it is
> not possible to effectively determine which Gödel numbers correspond
> to Turing machines that produce computable reals. In order to produce
> a computable real, a Turing machine must compute a total function, but
> the corresponding decision problem is in Turing degree 0′′. 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?
>

The term "countable reals" doesn't mean anything. Perhaps you meant to
say "computable reals". The theory RCA_0+"every real is computable" is
consistent (and proves that the reals are uncountable). I do not know
whether this can be converted into something recognisable as a system
of set theory.

> B) Can we postulate the existence of 1-2-1 mapping from naturals to
> computable reals? If so this list does not have an antidiagonal.
>

No. If you believe that every real is computable, then the real coding
a surjection from the naturals onto the computable reals does not
exist.

> Some will object that the function from naturals to reals is not
> constructive. What the heck does it matter? The theory would be
> constructive in the sense that no unconstructible set or element
> exists.

I don't understand this.
From: Newberry on 27 Jun 2010 20:31
On Jun 27, 5:03 pm, Rupert <rupertmccal...(a)yahoo.com> wrote:
> On Jun 28, 2:39 am, Newberry <newberr...(a)gmail.com> wrote:
>
>
>
>
>
> > This is from Wikipediahttp://en.wikipedia.org/wiki/Computable_reals
>
> > Although the set of real numbers is uncountable, the set of computable
> > numbers is countable and thus almost all real numbers are not
> > computable. The computable numbers can be counted by assigning a Gödel
> > number to each Turing machine definition. This gives a function from
> > the naturals to the computable reals. Although the computable numbers
> > are an ordered field, the set of Gödel numbers corresponding to
> > computable numbers is not itself computably enumerable, because it is
> > not possible to effectively determine which Gödel numbers correspond
> > to Turing machines that produce computable reals. In order to produce
> > a computable real, a Turing machine must compute a total function, but
> > the corresponding decision problem is in Turing degree 0′′. 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?
>
> The term "countable reals" doesn't mean anything. Perhaps you meant to
> say "computable reals".

I meant "computable."

The theory RCA_0+"every real is computable" is
> consistent (and proves that the reals are uncountable).

I do not know how relevant this fact is for question A.

> I do not know
> whether this can be converted into something recognisable as a system
> of set theory.
>
> > B) Can we postulate the existence of 1-2-1 mapping from naturals to
> > computable reals? If so this list does not have an antidiagonal.
>
> No. If you believe that every real is computable, then the real coding
> a surjection from the naturals onto the computable reals does not
> exist.

It does not exist effectively. How do you know that it does not exist?
If the computable reals are countable then it implies 1 to 1 mapping,
does it not?

>
> > Some will object that the function from naturals to reals is not
> > constructive. What the heck does it matter? The theory would be
> > constructive in the sense that no unconstructible set or element
> > exists.
>
> I don't understand this.- Hide quoted text -
>
> - Show quoted text -

From: Rupert on 27 Jun 2010 23:32
On Jun 28, 10:31 am, Newberry <newberr...(a)gmail.com> wrote:
> On Jun 27, 5:03 pm, Rupert <rupertmccal...(a)yahoo.com> wrote:
>
>
>
>
>
> > On Jun 28, 2:39 am, Newberry <newberr...(a)gmail.com> wrote:
>
> > > This is from Wikipediahttp://en.wikipedia.org/wiki/Computable_reals
>
> > > Although the set of real numbers is uncountable, the set of computable
> > > numbers is countable and thus almost all real numbers are not
> > > computable. The computable numbers can be counted by assigning a Gödel
> > > number to each Turing machine definition. This gives a function from
> > > the naturals to the computable reals. Although the computable numbers
> > > are an ordered field, the set of Gödel numbers corresponding to
> > > computable numbers is not itself computably enumerable, because it is
> > > not possible to effectively determine which Gödel numbers correspond
> > > to Turing machines that produce computable reals. In order to produce
> > > a computable real, a Turing machine must compute a total function, but
> > > the corresponding decision problem is in Turing degree 0′′. 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?
>
> > The term "countable reals" doesn't mean anything. Perhaps you meant to
> > say "computable reals".
>
> I meant "computable."
>
>  The theory RCA_0+"every real is computable" is
>
> > consistent (and proves that the reals are uncountable).
>
> I do not know how relevant this fact is for question A.
>

I have given you an example of a consistent theory which proves that
every real is computable. It is a theory whose language has variables
which range over natural numbers and variables which range over sets
of natural numbers. If you are happy to call it a set theory then I
have given you the answer to your question. But I think that this is
probably not what most people have in mind when they think about a
"set theory".

However, if I consider Zermelo set theory with Delta_0 Separation and
Sigma_1 Induction, I would think it would be consistent with that
theory that every real is computable. So there is an example of a "set
theory" in which every real is computable.

> > I do not know
> > whether this can be converted into something recognisable as a system
> > of set theory.
>
> > > B) Can we postulate the existence of 1-2-1 mapping from naturals to
> > > computable reals? If so this list does not have an antidiagonal.
>
> > No. If you believe that every real is computable, then the real coding
> > a surjection from the naturals onto the computable reals does not
> > exist.
>
> It does not exist effectively. How do you know that it does not exist?

In a set theory which only permits computable reals, it cannot exist,
because the real which encodes the function is not computable.

> If the computable reals are countable then it implies 1 to 1 mapping,
> does it not?
>

The computable reals can be proved to be countable in a set theory
which acknowledges the existence of incomputable reals. However, the
set theory I mentioned just now proves that the computable reals are
uncountable.

>
>
>
>
> > > Some will object that the function from naturals to reals is not
> > > constructive. What the heck does it matter? The theory would be
> > > constructive in the sense that no unconstructible set or element
> > > exists.
>
> > I don't understand this.- Hide quoted text -
>
> > - Show quoted text -- Hide quoted text -
>
> - Show quoted text -- Hide quoted text -
>
> - Show quoted text -

From: Newberry on 27 Jun 2010 23:51
On Jun 27, 8:32 pm, Rupert <rupertmccal...(a)yahoo.com> wrote:
> On Jun 28, 10:31 am, Newberry <newberr...(a)gmail.com> wrote:
>
>
>
>
>
> > On Jun 27, 5:03 pm, Rupert <rupertmccal...(a)yahoo.com> wrote:
>
> > > On Jun 28, 2:39 am, Newberry <newberr...(a)gmail.com> wrote:
>
> > > > This is from Wikipediahttp://en.wikipedia.org/wiki/Computable_reals
>
> > > > Although the set of real numbers is uncountable, the set of computable
> > > > numbers is countable and thus almost all real numbers are not
> > > > computable. The computable numbers can be counted by assigning a Gödel
> > > > number to each Turing machine definition. This gives a function from
> > > > the naturals to the computable reals. Although the computable numbers
> > > > are an ordered field, the set of Gödel numbers corresponding to
> > > > computable numbers is not itself computably enumerable, because it is
> > > > not possible to effectively determine which Gödel numbers correspond
> > > > to Turing machines that produce computable reals. In order to produce
> > > > a computable real, a Turing machine must compute a total function, but
> > > > the corresponding decision problem is in Turing degree 0′′. 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?
>
> > > The term "countable reals" doesn't mean anything. Perhaps you meant to
> > > say "computable reals".
>
> > I meant "computable."
>
> >  The theory RCA_0+"every real is computable" is
>
> > > consistent (and proves that the reals are uncountable).
>
> > I do not know how relevant this fact is for question A.
>
> I have given you an example of a consistent theory which proves that
> every real is computable. It is a theory whose language has variables
> which range over natural numbers and variables which range over sets
> of natural numbers. If you are happy to call it a set theory then I
> have given you the answer to your question. But I think that this is
> probably not what most people have in mind when they think about a
> "set theory".
>
> However, if I consider Zermelo set theory with Delta_0 Separation and
> Sigma_1 Induction, I would think it would be consistent with that
> theory that every real is computable. So there is an example of a "set
> theory" in which every real is computable.
>
> > > I do not know
> > > whether this can be converted into something recognisable as a system
> > > of set theory.
>
> > > > B) Can we postulate the existence of 1-2-1 mapping from naturals to
> > > > computable reals? If so this list does not have an antidiagonal.
>
> > > No. If you believe that every real is computable, then the real coding
> > > a surjection from the naturals onto the computable reals does not
> > > exist.
>
> > It does not exist effectively. How do you know that it does not exist?
>
> 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?

>
> > If the computable reals are countable then it implies 1 to 1 mapping,
> > does it not?
>
> The computable reals can be proved to be countable in a set theory
> which acknowledges the existence of incomputable reals. However, the
> set theory I mentioned just now proves that the computable reals are
> uncountable.
>
>
>
>
>
> > > > Some will object that the function from naturals to reals is not
> > > > constructive. What the heck does it matter? The theory would be
> > > > constructive in the sense that no unconstructible set or element
> > > > exists.
>
> > > I don't understand this.- Hide quoted text -
>
> > > - Show quoted text -- Hide quoted text -
>
> > - Show quoted text -- Hide quoted text -
>
> > - Show quoted text -- Hide quoted text -
>
> - Show quoted text -- Hide quoted text -
>
> - Show quoted text -

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