Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.


Math Forum
»
Discussions
»
sci.math.*
»
sci.math
Notice: We are no longer accepting new posts, but the forums will continue to be readable.
Topic:
distinguishability  in context, according to definitions
Replies:
43
Last Post:
Feb 22, 2013 10:04 AM



fom
Posts:
1,968
Registered:
12/4/12


distinguishability  in context, according to definitions
Posted:
Feb 10, 2013 2:54 AM


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 signvehicle (i.e., an inscription). In contrast, Piercean semiotics is subject to infinitary regress into nongrammatical signfunctionality.
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 "FiniteState 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 kdistinguishable. States that are not distinguishable by any experiment of length k or less are called kequivalent. It follows that two states are equivalent iff they are kequivalent for every finite value of k.
"The definition of kdistinguishability 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 zsuccessors of the two states are distinguishable by an experiment of length (k1).
These rules provide the basis for a stepbystep procedure for determining which states of a machine are oneequivalent, which are twoequivalent, 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 oneequivalent and in different blocks if they are onedistinguishable."
For the automaton applied when the cut corresponds to an irrational,
P_1=(A,B,C,D,...)
For that applied to the singlyrepresented rational the example state table yields,
P_1=(A,B,E,F,...)(C,D,G,H,...)
For the doublyrepresented 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 zsuccessors lie in a common block of P_1. Note that P_2 must be a refinement of P_1, for if two states are twoequivalent, they must certainly be oneequivalent. 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 singlyrepresented rational the second partition for the example state table yields,
P_2=(A,E,...)(B,F,...)(C,G,...)(D,H,...)
For the doublyrepresented 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 singlyrepresented 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 doublyrepresented 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 singlyrepresented rational, one has
 0  1   A  B0  B0   B  C0  C0   C  D1  D1   D  A1  A1 
For the doublyrepresented 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 doublyrepresented, one or more states are found to be transitioning into themselves.
Relative to the model investigated here, the notion of reduced machine relative to kequivalent 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_0B_0C_0...M...C_1B_1A_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 settheoretic omega and let the selections be indexed by the nonzero 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 wellformed 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.



