Date: Feb 10, 2013 2:54 AM Author: fom Subject: distinguishability - in context, according to definitions

This post is motivated by recent discussions

involving a term with which I had been

personally unfamiliar. It is an exercise

in "basic" logic.

Consider the "math trick,"

9.999...

-0.999...

---------

9.000...

in relation to

10x

-x

----

9x

By pattern matching, one infers

0.999...=1

x=1

Since x=1 is surmised from the algebraic

syntax.

Now, in what follows, the particular

problem will be considering the nature

of eventually constant sequences taken

to be ontologically "the same." So, in

addition to the above, the identity,

1=1.000...

is considered to be a presupposition

available to the analysis. So, what

is actually being considered is the

syntax,

0.999...=1.000...

and, at the appropriate time, the

analysis will turn to binary sequences

for ease of presentation. Thus, this analysis

is not necessarily applicable to the

example with which it has been introduced.

It will be, however, applicable to the

context from which the term "distinguishability"

has been found to have a sourced definition.

In the tradition of logic that has become

popular, the logical problem being investigated

may be stated as being an assertion of ontological

identity using an informative identity statement. That

problem is particularly difficult, in general, as

the classic Fregean identity puzzle

"Hesperus is Phosphorus"

has shown. But, by analogy with polynomials

of degree greater than 4, there is no reason

to think that some classes of problems of

this nature are not amenable to analysis.

To be formally explicit, the analysis presented

here is based on Sausserian semiotics wherein a

syntactic signal antecedent to its consequent

use as a sign never regresses beyond an

observable sign-vehicle (i.e., an inscription).

In contrast, Piercean semiotics is subject

to infinitary regress into non-grammatical

sign-functionality.

So, that we clarify the nature of the received

paradigm in this matter, we address the issue

of uniform semantic interpretation of inscriptions

by invoking Carnap's notion of syntactic equality.

Hence, what is expressed by

0.999...=1.000...

is the identity of two equivalence classes

[0.999...]=[1.000...]

relative to which some quotient model must

be formed to accommodate the fact that an

ontological assertion is being made using

an informative identity.

Because the received paradigm does not

address informative identity directly, it

is possible that there are interpretations

in which

[0.999...]=[1.000...]

is false.

With these preliminaries out of the way,

it is time to consider how the presupposition

1=1.000...

is indicated as the canonical representation

given that, alternatively,

1=0.999...

is also a candidate for the canonical

representation.

Consider the construction of the real

numbers in relation to Dedekind cuts. To

accept this construction is to accept the

fact that in a hierarchy of definition, there

is information about the defined system that

is epistemically prior by virtue of the

construction.

What is taken to be known essentially is that

for any given Dedekind cut, it is in the class

of rational cuts or it is in the class of irrational

cuts.

However, there is still more information associated

with the construction that informs with respect to

the analysis at hand. Because one has a choice as

to which direction of the linear order in the underlying

rationals will be used for the cuts, there is a

decision that may be applied to the representations

of rationals in relation to decimal expansions.

Since, for any finite initial segement of the

expression 0.999... it is held that

0.999 < 1.000...

the system of Dedekind cuts will be given its

fundamental partition according to whether or

not its greatest lower bound is an element. This

choice is compatible with the usual notion that

an eventually constant sequence of trailing zeros

is the same as a long division that terminates.

It is at this point that the context of the

analysis will be changed to binary strings. The

principal concern will be the relationship of

eventually constant strings to one another in

constrast to strings that never become eventually

constant.

The next step is to represent the orientation of

cuts with respect to a preferred canonical

representation.

Now, what motivates the choice of theoretical

context for this analysis is the information

content in the assertion,

0.999...=1.000...

The model that best seems to reflect a selection

of preference here is that of automata -- in

particular, the selection of preference is

characterized in terms of lossless and lossy

machines.

Since it is almost trivial, we begin by recalling

that there is prior knowledge that distinguishes

the cuts into two classes and look to those cuts

that are defined as irrational real numbers. Let

the automaton that is applied to identifying

concatenations of alphabet letters for the irrational

cuts simply copy its input to its output,

| 0 | 1 |

--|----|----|

A | B0 | B1 |

--|----|----|

B | C0 | C1 |

--|----|----|

C | D0 | D1 |

--|----|----|

D | E0 | E1 |

--|----|----|

and so on

Thus, each state S_k copies its input symbol to

its output symbol and transitions to its grammatical

successor S_(k+1)

The simplicity of the irrational automaton arises

from the fact that it is applied to the identifying

sequence for a given Dedekind cut when that cut is

not a rational cut. It is defined negatively, and,

the simplicity of its content reflects that fact.

For the rational numbers, the situation is different

because the hierarchy of logical definition affords

prior knowledge. The automaton for each rational

cut simply outputs the identifying concatenation of

alphabet letters as a known sequence, regardless

of input symbols. Those rational numbers that do not enjoy

two distinct representations by virtue of eventually

constant sequences are lossless. That is,

| 0 | 1 |

--|-------|-------|

A | B a_1 | B a_1 |

--|-------|-------|

B | C a_2 | C a_2 |

--|-------|-------|

C | D a_3 | D a_3 |

--|-------|-------|

D | E a_4 | E a_4 |

--|-------|-------|

and so on

They do repeat, however. Take for example,

the string obtained for the fraction 1/5,

00110011...

| 0 | 1 |

--|----|----|

A | B0 | B0 |

--|----|----|

B | C0 | C0 |

--|----|----|

C | D1 | D1 |

--|----|----|

D | E1 | E1 |

--|----|----|

E | F0 | F0 |

--|----|----|

F | G0 | G0 |

--|----|----|

G | H1 | H1 |

--|----|----|

H | I1 | I1 |

--|----|----|

and so on.

The states may be seen to correspond

with the labelling,

ABCDEFGH

00110011...

Although each state transitions to its

grammatical successor as with the machine

applied to irrational numbers, the output

symbols reflect the state of prior knowledge

and are not simply copies of the input

symbols.

In constrast, those rational cuts with a

plural multiplicity of identifying concatenations

of alphabet letters have a different pattern

of state transitions from the prior cases.

Consider,

| 0 | 1 |

--|--------|--------|

A | B ab_1 | B ab_1 |

--|--------|--------|

B | C ab_2 | C ab_2 |

--|--------|--------|

C | D ab_3 | D ab_3 |

--|--------|--------|

D | E ab_4 | E ab_4 |

--|--------|--------|

E | F a_5 | G b_5 |

--|--------|--------|

F | H a_6 | H a_6 |

--|--------|--------|

G | I b_6 | I b_6 |

--|--------|--------|

H | J a_7 | J a_7 |

--|--------|--------|

I | K b_7 | K b_7 |

--|--------|--------|

J | L a_8 | L a_8 |

--|--------|--------|

K | M b_8 | M b_8 |

--|--------|--------|

L | N a_9 | N a_9 |

--|--------|--------|

M | O b_9 | O b_9 |

--|--------|--------|

and so on

As the state table makes clear, it can

no longer be said that states transition

to their grammatical successor as a general

rule.

Consider a particular example. Suppose one

has the sequences,

11010000...

11001111...

Prior to any preference, the state table for

the automaton is given as

| 0 | 1 |

--|----|----|

A | B1 | B1 |

--|----|----|

B | C1 | C1 |

--|----|----|

C | D0 | E0 |

--|----|----|

D | F1 | F1 |

--|----|----|

E | G0 | G0 |

--|----|----|

F | H0 | H0 |

--|----|----|

G | I1 | I1 |

--|----|----|

H | J0 | J0 |

--|----|----|

I | K1 | K1 |

--|----|----|

J | L0 | L0 |

--|----|----|

K | M1 | M1 |

--|----|----|

L | N0 | N0 |

--|----|----|

and so on

The states may be seen to correspond

with the labelling,

ABCDFHJL

11010000...

ABCEGIKM

11001111...

But, the choice to establish a canonical

representation -- the choice which informed

the directionality to be used for the

cuts -- has a different automaton,

| 0 | 1 |

--|----|----|

A | B1 | B1 |

--|----|----|

B | C1 | C1 |

--|----|----|

C | D0 | E0 |

--|----|----|

D | F1 | F1 |

--|----|----|

E | G1 | G1 |

--|----|----|

F | H0 | H0 |

--|----|----|

G | I0 | I0 |

--|----|----|

H | J0 | J0 |

--|----|----|

I | K0 | K0 |

--|----|----|

J | L0 | L0 |

--|----|----|

K | M0 | M0 |

--|----|----|

L | N0 | N0 |

--|----|----|

and so on

It is this representation that is lossy.

Now, the following quoted material is the

definition for distinguishability that shall

be considered here. It is taken from "Finite-State

Models for Logical Machines" by Frederick C. Hennie.

Although it is not the best, it is all that is on

my bookshelves. To see what I mean in this regard,

consider the subsequent description for the associated

partitions carefully. By my reading, the uqualified

description for the construction of partitions would

not partition the states in the manner suggested by

the subsequent qualifying remarks describing a

sequence of refinements. Perhaps I am wrong.

Sometimes mathematics is so easy that it is hard.

I included the qualifying remarks concerning the

description of partitions specifically because I

am having a hard time seeing the claim directly

from the unqualified statement.

With the qualifying remarks, the description of

the partitions appears to correspond with the

definition.

Distinguishability is defined as follows

"The most convenient way of finding equivalences

that exist among the states of a machine is to

concentrate on the states that are not equivalent.

Thus, we say that two states are *distinguishable*

iff there exists a finite input sequence that

yields one output sequence when the machine is

started in one state and a different output sequence

when the machine is started in the other state.

If this input sequence contains k symbols, the

states are said to be distinguishable by an experiment

of length k, or simply k-distinguishable. States

that are not distinguishable by any experiment of

length k or less are called k-equivalent. It

follows that two states are equivalent iff they

are k-equivalent for every finite value of k.

"The definition of k-distinguishability becomes

more useful when recast in the form of two

rules:

(1) Two states are distinguishable by an experiment

of length one iff there is some input symbol that

produces different output symbols according to

which of the two states the machine is in.

(2) Two states are distinguishable by an experiment

of length k (with k>1) iff there is some input symbol,

say z, such that the z-successors of the two states

are distinguishable by an experiment of length (k-1).

These rules provide the basis for a step-by-step

procedure for determining which states of a machine

are one-equivalent, which are two-equivalent, and

so on.

"The first step is the formation of a partition P_1

in which two states are placed in the same block iff

they produce identical output symbols for each possible

input symbol. This clearly puts two states in the

same block of P_1 if they are one-equivalent and in

different blocks if they are one-distinguishable."

For the automaton applied when the cut corresponds

to an irrational,

P_1=(A,B,C,D,...)

For that applied to the singly-represented rational

the example state table yields,

P_1=(A,B,E,F,...)(C,D,G,H,...)

For the doubly-represented rational example, this

is the partition before a canonical representative

is indicated through the Dedekind cut,

P_1=(A,B,D,G,I,K,...)(C,E,F,H,J,L,...)

and this is the partition after,

P_1=(A,B,D,E)(C,F,G,H,I,J,K,L,...)

Continuing the quoted exposition concerning the

definition of distinguishability,

"The next step is the formation of a partition

P_2 in which two states are placed in the same

block iff, for each input symbol z, their z-successors

lie in a common block of P_1. Note that P_2

must be a refinement of P_1, for if two states

are two-equivalent, they must certainly be

one-equivalent. Partition P_2 is most

easily formed by splitting the various blocks

of P_1 in such a way that the defining

conditions for P_2 are met."

For the automaton applied when the cut corresponds

to an irrational, the second partition is given as

P_2=(A,B,C,D,...)

Observe that there has been no change.

For that applied for the singly-represented rational

the second partition for the example state table

yields,

P_2=(A,E,...)(B,F,...)(C,G,...)(D,H,...)

For the doubly-represented rational example, this

is the second partition before a canonical representative

is indicated through the Dedekind cut,

P_2=(A,G,I,K,...)(B,D)(C)(E)(F,H,J,L,...)

and this is the second partition after,

P_2=(A)(B,D,E)(C)(F,G,H,I,J,K,L,...)

Continuing the quoted exposition concerning the

definition of distinguishability,

"Partitions P_3, P_4, ..., P_k,... can be formed

in a similar manner.[...]

"[...], we see that the partitioning process

may be terminated as soon as some partition

P_(m+1) is found to be identical to its

predecessor P_m."

Thus, the automaton applied when the cut corresponds

to an irrational has already terminated its

sequence of partitions given

P_1=(A,B,C,D,...)

P_2=(A,B,C,D,...)

For that applied for the singly-represented rational

the partition sequence for the example state table

yields,

P_1=(A,B,E,F,...)(C,D,G,H,...)

P_2=(A,E,...)(B,F,...)(C,G,...)(D,H,...)

P_3=(A,E,...)(B,F,...)(C,G,...)(D,H,...)

For the doubly-represented rational example before

orientation by the Dedekind cut,

P_1=(A,B,D,G,I,K,...)(C,E,F,H,J,L,...)

P_2=(A,G,I,K,...)(B,D)(C)(E)(F,H,J,L,...)

P_3=(A)(B)(C)(D)(E)(F,H,J,L,...)(G,I,K,...)

P_4=(A)(B)(C)(D)(E)(F,H,J,L,...)(G,I,K,...)

and after,

P_1=(A,B,D,E)(C,F,G,H,I,J,K,L,...)

P_2=(A)(B,D,E)(C)(F,G,H,I,J,K,L,...)

P_3=(A)(B)(C)(D,E)(F,G,H,I,J,K,L,...)

P_4=(A)(B)(C)(D,E)(F,G,H,I,J,K,L,...)

So, up to this point, it is clear that the various

relationships in the definition of real numbers

via Dedekind cuts and the presuppositions of

a trivial algebraic substitution do have discernible

representation relative to modeling with automatons.

With regard to the relationship of finitism and

the apparent simplicity of a symbol such as

1.000...

it is instructive to look at the reduced machines for

these examples. For the automaton applied when the

cut is an irrational, one has

| 0 | 1 |

--|----|----|

A | A0 | A1 |

--|----|----|

For that applied when the cut corresponds with a

singly-represented rational, one has

| 0 | 1 |

--|----|----|

A | B0 | B0 |

--|----|----|

B | C0 | C0 |

--|----|----|

C | D1 | D1 |

--|----|----|

D | A1 | A1 |

For the doubly-represented rational example before

orientation by the Dedekind cut,

| 0 | 1 |

--|----|----|

A | B1 | B1 |

--|----|----|

B | C1 | C1 |

--|----|----|

C | D0 | E0 |

--|----|----|

D | F1 | F1 |

--|----|----|

E | G0 | G0 |

--|----|----|

F | F0 | F0 |

--|----|----|

G | G1 | G1 |

--|----|----|

and after,

| 0 | 1 |

--|----|----|

A | B1 | B1 |

--|----|----|

B | C1 | C1 |

--|----|----|

C | D0 | E0 |

--|----|----|

D | F1 | F1 |

--|----|----|

F | F0 | F0 |

--|----|----|

In all cases, the finiteness of the reduced representation

relies on circularity. In the cases where the cuts are

either irrational or doubly-represented, one or more states

are found to be transitioning into themselves.

Relative to the model investigated here, the notion

of reduced machine relative to k-equivalent states

permits all of the possible machine configurations

derived from consideration of Dedekind cuts to have

finite representation -- provided one does not object

to the use of circularity in the state tables.

The problem with simply writing out sequences

and naively "knowing" the intended meaning of

"distinguishability" is that the automaton for

the irrational cuts is applied to the identifying

concatenation of alphabet for all sequences

without regard for the hierarchy of logical

definition.

This analysis, as far as it goes, is not yet

adequate.

The definition of distinguishability is characterized

in terms of "experiments." It seems prudent to

consider this aspect of the definition further and

with respect to the infinitary nature of the original

problem.

For each state, there are two possible outcomes in

the sense of traversing a decision tree. Suppose

states are redefined as choices and the components

of each state are taken to be selections. Then

an experiment is a sequence of selections taken

the purpose of destroying an assertion of equivalence.

In other words, just a subtle change of language

characterizes this model in relation to the historical

epistemic condition associated with the assertion

of "sameness" in relation to definitions.

However, the primary purpose for this further analysis

is to construct a topology.

One thing that will be required for this construction

is an enumeration of fractions which is the familiar

diagonalized listing on Z^+xZ^+.

Each fraction, representing a rational number,

corresponds to one of the automata discussed in

the preceding remarks. As before, there is no

immediate concern for uniqueness constraints since

that destroys information.

Given any fraction, take the reduced state table, say M,

for the lossless representation and organize the selections

for the unreduced state table relative to their grammatical

order according to

A_0---B_0---C_0---...M...---C_1---B_1---A_1

Let this ordering be given the interval topology.

Observe that M is the endpoint of no interval.

Now, let the enumeration of fractions be given the

discrete topology, and, as a first specification

for the topology being constructed, let an enumeration

of sequences like that above be given the product

topology.

For the next step, it is easiest to use numerical

coordinates. So, let the machine symbol M be

taken as set-theoretic omega and let the selections

be indexed by the non-zero integers according to

(1)---(2)---(3)---...omega...---(-3)---(-2)---(-1)

Extend the construction with the letters of the

input alphabet, namely '0' and '1'. Remembering

that the interval topology on the representation

above has, for example, (2)<omega and omega<(-2),

and, remembering that the omega in the representation

above has an natural number index according to the

enumeration of fractions, augment the topology

described so far with basis elements,

B_n_0={0}u{(i,j)|i<omega /\ j>=n}

B_n_1={1}u{(i,j)|i>omega /\ j>=n}

This is the minimal Hausdorff topology.

Before continuing with the present example, take a moment

to consider a countable language with a unary negation

symbol.The well-formed formulae may be partitioned

according to whether or not the first symbol from

among the logical constants is the symbol for negation.

They can be partitioned into an enumerable sequence

of lines according to the formulae that can be formed

relative to each step of a stepwise introduction of variable

terms. The negation symbol, itself can be taken as

"omega." Then, the formulae can be arranged in this manner

relative to extension with the Fregean constants,

"the True" and "the False." Language, at least that

fragment that can be formalized, is topological.

Returning to the present analysis, consider the

quotient topology induced by a map of this minimal

Hausdorff topology into the set of reduced lossless

machines applied to the identifying sequences of

alphabet letters for rational Dedekind cuts. Such

a topology exists because the map from the minimal

Hausdorff topology is surjective onto the set of

lossless machines provided that the map takes each

"line" of selections to the reduced machine for which

its choices form the states of the unreduced machine.

Because the topology on the enumeration of fractions

is discrete, the inverse image of each machine

corresponds to a representation of the equivalence

class of fractions for some particular rational

Dedekind cut.

Based on the inverse images, there is a partition

of the minimal Hausdorff topology by which a quotient

space on the topology may be formed.

Something for another time.

In any case, the definition of "distinguishability" is

obtained by a stepwise condition involving "experiments

of length K". But -- and here is the important aspect

of this analysis -- equivalence is an infinitary concept.

You do not get to write

0.999...=1.000...

with neither circularity nor a completed infinity.

It is one or the other.