Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
On the diagonal argument (4)
17 views
Skip to first unread message
LudovicoVan
May 23, 2012, 9:54:15 PM5/23/12
to
[Opposite approach from (3), where one could say that all strings can be
numbers, with at least one exception at a time...]
Consider the usual inductive set N, i.e. the set with zero and closed under
the successor operation.
Define an infinite binary string as a sequence of (binary) digits as output
by a function from {"0","1"} to N. For instance "0011011001...", where the
ellipsis are informal for any trailing of digits.
Following an usual convention, periodic trailing in strings will be written
as the period taken once and enclosed in brackets. This notational
short-cut will make some strings finitely printable, still denoting a
(trailing) sequence of digits over indexes in N. For example: given
"1001010..." as an infinite binary string with a trailing supposed to be
periodic with period "10", the string will be written below as "100(10)".
Define (inductively) a sequence 's' of infinite binary strings such that the
strings are systematically indexed in right-to left lexicographical order:
For n in N, n > 0:
s(0) := "(0)"
s(2n) := "0" ~ s(n)
s(2n+1) := "1" ~ s(n)
Writing out the result of enumerating over sequence 's', we get (quotes
omitted):
0: (0)
1: 1(0)
2: 01(0)
3: 11(0)
4: 001(0)
5: 101(0)
6: 011(0)
7: 111(0)
...
Define a *sensible* limit-case for sequence 's' (in the sense of
infinite-case induction):
To see what a sensible limit can be, we can use a "geometric" argument.
Quite simply, if we consider the properties of a lexicographical order, the
"last" few entries of 's' must look as follows:
w-7: 000(1)
w-6: 100(1)
w-5: 010(1)
w-4: 110(1)
w-3: 00(1)
w-2: 10(1)
w-1: 0(1)
w: (1)
So, the limit of sequence 's' *must* be the string "(1)".
Define the limit-case for 's':
lim_{n->w} s(n) := "(1)"
Extend the definition of 's':
For n in N, n > 0:
s(0) := "(0)"
s(2n) := "0" ~ s(n)
s(2n+1) := "1" ~ s(n)
s(w) := "(1)"
(Incidentally, to that we could easily add the following and enumerate in
reverse from 'w':)
s(w-2n) := "1" ~ s(w-n)
s(w-2n-1) := "0" ~ s(w-n)
Consider now the anti-diagonal string 't{s}' of 's' ('t' dependent on 's'),
as usually defined per Cantor's diagonal argument. Using square brackets to
index the single digits of a string sequence, the definition would be:
For x in N, x >= 0:
t{s}[x] := "1" if s(x)[x] = "0", "0" otherwise
It is then easy to show (by deriving from the definitions of 's' and 't'),
that the anti-diagonal of our specific 's' is the string "(1)", i.e. 's(w)',
the limit entry of 's':
t{s} = s(w)
In conclusion, Cantor's diagonal argument seems to stands, but in a very
specific way: our systematic, lexicographically ordered sequence of infinite
binary strings is not complete, yet only in the sense that there is a string
that is not in the sequence as it is its limit. -- I'd think the binary
case (of a *systematic* enumeration of infinite strings) is the "simplest"
(because of the shortest alphabet), meaning the one with only one
anti-diagonal that corresponds exactly to the limit entry of the sequence:
as a lower bound, it should be the reference point for the definition of a
complete set of all possible numbers (the real numbers?)?
-LV
numbers, with at least one exception at a time...]
Consider the usual inductive set N, i.e. the set with zero and closed under
the successor operation.
Define an infinite binary string as a sequence of (binary) digits as output
by a function from {"0","1"} to N. For instance "0011011001...", where the
ellipsis are informal for any trailing of digits.
Following an usual convention, periodic trailing in strings will be written
as the period taken once and enclosed in brackets. This notational
short-cut will make some strings finitely printable, still denoting a
(trailing) sequence of digits over indexes in N. For example: given
"1001010..." as an infinite binary string with a trailing supposed to be
periodic with period "10", the string will be written below as "100(10)".
Define (inductively) a sequence 's' of infinite binary strings such that the
strings are systematically indexed in right-to left lexicographical order:
For n in N, n > 0:
s(0) := "(0)"
s(2n) := "0" ~ s(n)
s(2n+1) := "1" ~ s(n)
Writing out the result of enumerating over sequence 's', we get (quotes
omitted):
0: (0)
1: 1(0)
2: 01(0)
3: 11(0)
4: 001(0)
5: 101(0)
6: 011(0)
7: 111(0)
...
Define a *sensible* limit-case for sequence 's' (in the sense of
infinite-case induction):
To see what a sensible limit can be, we can use a "geometric" argument.
Quite simply, if we consider the properties of a lexicographical order, the
"last" few entries of 's' must look as follows:
w-7: 000(1)
w-6: 100(1)
w-5: 010(1)
w-4: 110(1)
w-3: 00(1)
w-2: 10(1)
w-1: 0(1)
w: (1)
So, the limit of sequence 's' *must* be the string "(1)".
Define the limit-case for 's':
lim_{n->w} s(n) := "(1)"
Extend the definition of 's':
For n in N, n > 0:
s(0) := "(0)"
s(2n) := "0" ~ s(n)
s(2n+1) := "1" ~ s(n)
s(w) := "(1)"
(Incidentally, to that we could easily add the following and enumerate in
reverse from 'w':)
s(w-2n) := "1" ~ s(w-n)
s(w-2n-1) := "0" ~ s(w-n)
Consider now the anti-diagonal string 't{s}' of 's' ('t' dependent on 's'),
as usually defined per Cantor's diagonal argument. Using square brackets to
index the single digits of a string sequence, the definition would be:
For x in N, x >= 0:
t{s}[x] := "1" if s(x)[x] = "0", "0" otherwise
It is then easy to show (by deriving from the definitions of 's' and 't'),
that the anti-diagonal of our specific 's' is the string "(1)", i.e. 's(w)',
the limit entry of 's':
t{s} = s(w)
In conclusion, Cantor's diagonal argument seems to stands, but in a very
specific way: our systematic, lexicographically ordered sequence of infinite
binary strings is not complete, yet only in the sense that there is a string
that is not in the sequence as it is its limit. -- I'd think the binary
case (of a *systematic* enumeration of infinite strings) is the "simplest"
(because of the shortest alphabet), meaning the one with only one
anti-diagonal that corresponds exactly to the limit entry of the sequence:
as a lower bound, it should be the reference point for the definition of a
complete set of all possible numbers (the real numbers?)?
-LV
Virgil
May 23, 2012, 11:55:27 PM5/23/12
to
In article <jpk4cc$r6i$1...@speranza.aioe.org>,
{"0","1"} but not from {"0","1"} to N.
To me, any limit of the sequence you give abode as
0: (0), 1: 1(0), 2: 01(0), 3: 11(0), 4: 001(0), 5: 101(0), 6: 011(0),...
must contain infinitely many non-zero characters in it.
> So, the limit of sequence 's' *must* be the string "(1)".
Wrong!
--
"LudovicoVan" <ju...@diegidio.name> wrote:
> [Opposite approach from (3), where one could say that all strings can be
> numbers, with at least one exception at a time...]
>
> Consider the usual inductive set N, i.e. the set with zero and closed under
> the successor operation.
>
> Define an infinite binary string as a sequence of (binary) digits as output
> by a function from {"0","1"} to N. For instance "0011011001...", where the
> ellipsis are informal for any trailing of digits.
I can visualize a infinite binary string as a function from N to
> [Opposite approach from (3), where one could say that all strings can be
> numbers, with at least one exception at a time...]
>
> Consider the usual inductive set N, i.e. the set with zero and closed under
> the successor operation.
>
> Define an infinite binary string as a sequence of (binary) digits as output
> by a function from {"0","1"} to N. For instance "0011011001...", where the
> ellipsis are informal for any trailing of digits.
{"0","1"} but not from {"0","1"} to N.
>
> Following an usual convention, periodic trailing in strings will be written
> as the period taken once and enclosed in brackets. This notational
> short-cut will make some strings finitely printable, still denoting a
> (trailing) sequence of digits over indexes in N. For example: given
> "1001010..." as an infinite binary string with a trailing supposed to be
> periodic with period "10", the string will be written below as "100(10)".
>
> Define (inductively) a sequence 's' of infinite binary strings such that the
> strings are systematically indexed in right-to left lexicographical order:
>
> For n in N, n > 0:
>
> s(0) := "(0)"
> s(2n) := "0" ~ s(n)
> s(2n+1) := "1" ~ s(n)
>
> Writing out the result of enumerating over sequence 's', we get (quotes
> omitted):
>
> 0: (0)
> 1: 1(0)
> 2: 01(0)
> 3: 11(0)
> 4: 001(0)
> 5: 101(0)
> 6: 011(0)
> 7: 111(0)
> ... of he sequnce
> Following an usual convention, periodic trailing in strings will be written
> as the period taken once and enclosed in brackets. This notational
> short-cut will make some strings finitely printable, still denoting a
> (trailing) sequence of digits over indexes in N. For example: given
> "1001010..." as an infinite binary string with a trailing supposed to be
> periodic with period "10", the string will be written below as "100(10)".
>
> Define (inductively) a sequence 's' of infinite binary strings such that the
> strings are systematically indexed in right-to left lexicographical order:
>
> For n in N, n > 0:
>
> s(0) := "(0)"
> s(2n) := "0" ~ s(n)
> s(2n+1) := "1" ~ s(n)
>
> Writing out the result of enumerating over sequence 's', we get (quotes
> omitted):
>
> 0: (0)
> 1: 1(0)
> 2: 01(0)
> 3: 11(0)
> 4: 001(0)
> 5: 101(0)
> 6: 011(0)
> 7: 111(0)
>
> Define a *sensible* limit-case for sequence 's' (in the sense of
> infinite-case induction):
>
> To see what a sensible limit can be, we can use a "geometric" argument.
> Quite simply, if we consider the properties of a lexicographical order, the
> "last" few entries of 's' must look as follows:
>
> w-7: 000(1)
> w-6: 100(1)
> w-5: 010(1)
> w-4: 110(1)
> w-3: 00(1)
> w-2: 10(1)
> w-1: 0(1)
> w: (1)
Not to me.
> Define a *sensible* limit-case for sequence 's' (in the sense of
> infinite-case induction):
>
> To see what a sensible limit can be, we can use a "geometric" argument.
> Quite simply, if we consider the properties of a lexicographical order, the
> "last" few entries of 's' must look as follows:
>
> w-7: 000(1)
> w-6: 100(1)
> w-5: 010(1)
> w-4: 110(1)
> w-3: 00(1)
> w-2: 10(1)
> w-1: 0(1)
> w: (1)
To me, any limit of the sequence you give abode as
0: (0), 1: 1(0), 2: 01(0), 3: 11(0), 4: 001(0), 5: 101(0), 6: 011(0),...
must contain infinitely many non-zero characters in it.
> So, the limit of sequence 's' *must* be the string "(1)".
--
Shmuel Metz
May 24, 2012, 6:39:37 AM5/24/12
to
In <jpk4cc$r6i$1...@speranza.aioe.org>, on 05/24/2012
> s(2n) := "0" ~ s(n)
You haven't defined what you mean by "~".
>Quite simply, if we consider the properties of a lexicographical
>order, the "last" few entries of 's' must look as follows:
Totally meaningless. There are no last few entries.
>So, the limit of sequence 's' *must* be the string "(1)".
No. You could equally well have defined it to be something else.
>(Incidentally, to that we could easily add the following and
>enumerate in reverse from 'w':)
No, because Omega is a limit ordinal.
>In conclusion, Cantor's diagonal argument seems to stands, but in
>a very specific way: our systematic, lexicographically ordered
>sequence
Your extended s is not a sequence.
>I'd think
You lack the ability.
--
Shmuel (Seymour J.) Metz, SysProg and JOAT <http://patriot.net/~shmuel>
Unsolicited bulk E-mail subject to legal action. I reserve the
right to publicly post or ridicule any abusive E-mail. Reply to
domain Patriot dot net user shmuel+news to contact me. Do not
reply to spam...@library.lspace.org
at 02:54 AM, "LudovicoVan" <ju...@diegidio.name> said:
>Define an infinite binary string as a sequence of (binary) digits as
>output by a function from {"0","1"} to N.
ROTF,LMAO!
>Define an infinite binary string as a sequence of (binary) digits as
>output by a function from {"0","1"} to N.
> s(2n) := "0" ~ s(n)
>Quite simply, if we consider the properties of a lexicographical
>order, the "last" few entries of 's' must look as follows:
>So, the limit of sequence 's' *must* be the string "(1)".
>(Incidentally, to that we could easily add the following and
>enumerate in reverse from 'w':)
>In conclusion, Cantor's diagonal argument seems to stands, but in
>a very specific way: our systematic, lexicographically ordered
>sequence
>I'd think
You lack the ability.
--
Shmuel (Seymour J.) Metz, SysProg and JOAT <http://patriot.net/~shmuel>
Unsolicited bulk E-mail subject to legal action. I reserve the
right to publicly post or ridicule any abusive E-mail. Reply to
domain Patriot dot net user shmuel+news to contact me. Do not
reply to spam...@library.lspace.org
LudovicoVan
May 24, 2012, 1:13:29 PM5/24/12
to
"Virgil" wrote in message
news:virgil-AE5585....@bignews.usenetmonster.com...
<snip>
> I can visualize a infinite binary string as a function from N to
> {"0","1"} but not from {"0","1"} to N.
Of course!
> > w: (1)
>
> Not to me.
>
> To me, any limit of the sequence you give abode as
> 0: (0), 1: 1(0), 2: 01(0), 3: 11(0), 4: 001(0), 5: 101(0), 6: 011(0),...
> must contain infinitely many non-zero characters in it.
That limit does: in fact, it contains *only* non-zero characters.
> > So, the limit of sequence 's' *must* be the string "(1)".
>
> Wrong!
Wrong *what*??
-LV
news:virgil-AE5585....@bignews.usenetmonster.com...
<snip>
> I can visualize a infinite binary string as a function from N to
> {"0","1"} but not from {"0","1"} to N.
> > w: (1)
>
> Not to me.
>
> To me, any limit of the sequence you give abode as
> 0: (0), 1: 1(0), 2: 01(0), 3: 11(0), 4: 001(0), 5: 101(0), 6: 011(0),...
> must contain infinitely many non-zero characters in it.
> > So, the limit of sequence 's' *must* be the string "(1)".
>
> Wrong!
-LV
Virgil
May 24, 2012, 6:07:40 PM5/24/12
to
In article <jplq7l$1kh$1...@speranza.aioe.org>,
If most of the terms in your sequence contain "0"s why must your alleged
limit be without any?
--
limit be without any?
--
LudovicoVan
May 24, 2012, 7:07:22 PM5/24/12
to
"Virgil" <vir...@ligriv.com> wrote in message
news:virgil-1E6CBF....@bignews.usenetmonster.com...
strange, in fact it is quite "natural". I have already provided support to
that choice in the original post: informally (but easily formalizable), it
is a basic property of lexicographical orderings that, given any such sorted
list, the first entry shall be composed of occurrences of the first digit of
the alphabet only, and the last entry of occurrences of the last digit only,
for any suitable definition of "last" list entry. Furthermore, speaking of
evidence, let's try and look at the very diagonal argument: we know that the
anti-diagonal of a list cannot be on that list, and we know that our
anti-diagonal is indeed the string "(1)". What more doubts would you have?
-LV
news:virgil-1E6CBF....@bignews.usenetmonster.com...
> In article <jplq7l$1kh$1...@speranza.aioe.org>,
> "LudovicoVan" <ju...@diegidio.name> wrote:
>> "Virgil" wrote in message
>> news:virgil-AE5585....@bignews.usenetmonster.com...
>> > In article <jpk4cc$r6i$1...@speranza.aioe.org>,
>> > "LudovicoVan" <ju...@diegidio.name> wrote:
<snip>
> "LudovicoVan" <ju...@diegidio.name> wrote:
>> "Virgil" wrote in message
>> news:virgil-AE5585....@bignews.usenetmonster.com...
>> > In article <jpk4cc$r6i$1...@speranza.aioe.org>,
>> > "LudovicoVan" <ju...@diegidio.name> wrote:
<snip>
>> > > w: (1)
>> >
>> > Not to me.
>> >
>> > To me, any limit of the sequence you give abode as
>> > 0: (0), 1: 1(0), 2: 01(0), 3: 11(0), 4: 001(0), 5: 101(0), 6:
>> > 011(0),...
>> > must contain infinitely many non-zero characters in it.
>>
>> That limit does: in fact, it contains *only* non-zero characters.
>>
>> > > So, the limit of sequence 's' *must* be the string "(1)".
>> >
>> > Wrong!
>>
>> Wrong *what*?
>
> If most of the terms in your sequence contain "0"s why must your alleged
> limit be without any?
Reverse direction, same slope! It is a limit entry, so there is nothing
>> >
>> > Not to me.
>> >
>> > To me, any limit of the sequence you give abode as
>> > 0: (0), 1: 1(0), 2: 01(0), 3: 11(0), 4: 001(0), 5: 101(0), 6:
>> > 011(0),...
>> > must contain infinitely many non-zero characters in it.
>>
>> That limit does: in fact, it contains *only* non-zero characters.
>>
>> > > So, the limit of sequence 's' *must* be the string "(1)".
>> >
>> > Wrong!
>>
>> Wrong *what*?
>
> If most of the terms in your sequence contain "0"s why must your alleged
> limit be without any?
strange, in fact it is quite "natural". I have already provided support to
that choice in the original post: informally (but easily formalizable), it
is a basic property of lexicographical orderings that, given any such sorted
list, the first entry shall be composed of occurrences of the first digit of
the alphabet only, and the last entry of occurrences of the last digit only,
for any suitable definition of "last" list entry. Furthermore, speaking of
evidence, let's try and look at the very diagonal argument: we know that the
anti-diagonal of a list cannot be on that list, and we know that our
anti-diagonal is indeed the string "(1)". What more doubts would you have?
-LV
Virgil
May 25, 2012, 12:17:03 AM5/25/12
to
In article <jpmevf$kid$1...@speranza.aioe.org>,
But what makes you claim that a "limit" of sequences of ever increasing
lenght even has a last element?
In your series, it would appear that every term has a finite number of
non-zeros, so why would this not apply to your liit?
Furthermore, speaking of
> evidence, let's try and look at the very diagonal argument: we know that the
> anti-diagonal of a list cannot be on that list, and we know that our
> anti-diagonal is indeed the string "(1)". What more doubts would you have?
>
> -LV
>
--
lenght even has a last element?
In your series, it would appear that every term has a finite number of
non-zeros, so why would this not apply to your liit?
Furthermore, speaking of
> evidence, let's try and look at the very diagonal argument: we know that the
> anti-diagonal of a list cannot be on that list, and we know that our
> anti-diagonal is indeed the string "(1)". What more doubts would you have?
>
> -LV
>
0 new messages