fom
Posts:
1,039
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 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.
|
|
