Registered: Dec 2005
To what extent are binary sequences a "universal representation system"?
Hi, I was wondering if anyone could point me in the right direction for the answer to a question I've had recently.
In a previous post I asked about the possibility of a CA's output being equivalent to some kind of set, or in general some other kind of mathematical structure. The reply answered the question by basically equating "sets, data, patterns", etc., with sequences--that is, arrays of binary digits.
I felt like this makes a lot of intuitive sense (take a long enough string of binary digits and you can probably provide enough information to differentiate any two different sets, patterns, etc.). But now I'm wondering to what extent it really is true that sequences can capture "all forms of mathematical structure, organization, etc.". I suppose words like objects, structures, patterns, data, etc. are "fuzzy" epistemic words without well-defined meanings, but in an informal and intuitive sense the meaning is clear.
I guess my question is really about the foundations of mathematics. Set theory seems to be the backbone of modern math, with other structures, like groups, rings, vector fields, etc. defined in terms of sets with binary operations satisfying certain properties etc. I noticed that in NKS there is large use of sequences (in the form of rows of black and white squares) in discussing the foundations of mathematics. I'm basically just trying to further understand what's going on here.
Here is an example in group theory which I hope will clarify what I'm after. Consider the group G = (G, *), with * the binary operation. Now suppose I want to represent G using a binary sequence. How would I do it?
Here's the idea I was playing with: The meat of the group seems to be contained in the definition of the binary operation. Suppose |G| = 3 and we call the elements of the group a1, a2, a3. Then suppose the binary map * is defined by the 3^2 = 9 relations:
a1 * a1 = a1
a1 * a2 = a2
a1 * a3 = a3
a2 * a1 = a2
a2 * a2 = a3
a2 * a3 = a1
a3 * a1 = a3
a3 * a2 = a1
a3 * a3 = a2
That is, a1 is the identity, and a2 is the inverse of a3. Now, to form a sequence that represents the group, I thought maybe we could let
a1 -> 00
a2 -> 01
a3 -> 10
And now, write each of the nine relations as a sequence, so that for instance, a1 * a2 = a2 becomes (a1)(a2)(a2) = 000101. Is this the correct way to represent a function using sequences? If not, what would be more correct?
Supposing the above is reasonable, then perhaps we could join these 9 sequences to form:
000000 000101 001010 010001 010110 011000 100010 100100 101001
(where the spaces mean nothing and are only for visual clarity)
Now here's the question: Is this a valid sequence representation of group? By which all I really mean is, does this "make sense"? When is such a process of continually appending sequences to make one giant sequence sensible and appropriate?
Consider B, the set of sequences that the set of all groups maps onto. Assuming that the translation is injective, we should be able to determine the original group given sequences in B, right?
That is, it seems that we should have an inverse function on the subset B of the codomain. Is this the criterion for our representation to "make sense"? If not, what is the criterion?
Also, I'm very curious to know: To get from the huge string of bits above back to the original group, our translating function has to know some things, like the fact that there are always N^2 relations for a group of order N, and that each relation has 3 components (two inputs and an output).
What's the nature of the knowledge that the translating function has to have? By which I mean, does the fact that the translating function has to do a lot of work mean that we haven't totally captured the entire structure of the group in our current sequence scheme? Is there a way to modify our scheme to capture the entire structure? What is the best way to know that one has captured the entire structure?
A similar curiosity arose from the way NKS classifies elementary CAs. Since there are exactly 255 CAs, one can distinguish them simply using the numbers 0-255. So it almost makes you want to say that the number 130 is a "complete representation" of CA rule 130. But really, this number says nothing about the structural nature of the algorithm performed by the CA, only of its place in the small set of elementary CAs. When we speak of "representation", do we always face this issue? Is representation in general always in some way dependant on the "scope" of different possibilities that we care about, or is there some more universal means of representation?
Thanks for any help and insight on this issue. Also, any suggestions on good papers/books that use binary sequences heavily in the discussion of axiomatic systems, fundamental math, the nature of representation, etc. besides NKS would be very helpful.
Last edited by Stedman on 01-09-2006 at 09:59 AM
Report this post to a moderator | IP: Logged