Kind of Godel numbering
in [Math]
|
Prev: chapt4 Dirac's new-radioactivities and Dirac's multiplicative-creation #212 Atom Totality theory
Next: Mathematically-Rigorous Path Integration??
From: Ilmari Karonen on 23 Dec 2009 17:39 On 2009-12-23, JohnF <john(a)please.see.sig.for.email.com> wrote: > Ilmari Karonen <usenet2(a)vyznev.invalid> wrote: >> >> Assuming you have some way of numbering the objects themselves without >> duplicates, you could always use some kind of zig-zag numbering for >> the containers. For example, let the label for the k-th container in >> the n-th object be p( (n+k)(n+k-1)/2 - n ), where p(i) denotes the >> i-th prime. [snip] > By the way, the standard "zig-zag" enumeration > of ordered pairs I'm familiar with looks like [snip] > so that the ordered pair (k,n) --> (k+n)(k+n+1)/2 + n. > Yours starts with (1,1)-->0 rather than (0,0)-->0? I actually meant to start with (1,1) -> 1, but forgot to add 1 after subtracting n. :) In any case, they're all trivially related. Anyway, I'm glad to have been of assistance. -- Ilmari Karonen To reply by e-mail, please replace ".invalid" with ".net" in address.
From: cbrown on 23 Dec 2009 18:57 On Dec 23, 11:35 am, JohnF <j...(a)please.see.sig.for.email.com> wrote: > cbr...(a)cbrownsystems.com <cbr...(a)cbrownsystems.com> wrote: > > JohnF <j...(a)please.see.sig.for.email.com> wrote: > >> Ilmari Karonen <usen...(a)vyznev.invalid> wrote: > >> > JohnF <j...(a)please.see.sig.for.email.com> wrote: > >> >> I have objects, each of which is an unordered collection > >> >> of "containers", with each container in an object labelled by > >> >> an integer, e.g., object B = { (b1,B1), (b2,B2), (b3,B3),... } > >> >> with Bi a container labelled by integer bi in object B. > >> >> The bi's are arbitrary integer labels except that bi must > >> >> uniquely identify the object Bi it labels. > >> >> Trouble arises because I want to define multiplication > >> >> of these objects in the following way. Given B above and a similar > >> >> C, define BC = { (bi*cj,(BiCj)) | (bi,Bi)\in B & (cj,Cj)\in C } > >> >> where bi*cj is just integer multiplication, and (BiCj) just means > >> >> a single container with the combined contents of Bi and Cj in it. > >> >> The problem is that each bi*cj label for container (BiCj) > >> >> must identify both original component containers Bi and Cj. > >> >> That is, while ordering BiCj versus CjBi is unimportant, > >> >> the bi*cj label must nevertheless identify both i and j as well as > >> >> which (i or j) belongs to b and which (j or i) to c. > >> >> Any way to define labels that satisfy these requirements? > <snip> > > You could select distinct primes p_b, p_c, p_d, etc. associated with > > each collection B, C, D, etc. (resp.). Then set b_i = (p_b)^i, c_j = > > (p_c)^j to get distinct products b_i * c_j. > > E.g., let B = { (2,B1), (4,B2), (8,B3), ...) and C = ( (3,C1), (9,C2), > > (27,C3),...). > > Cheers - Chas > > Thanks, Chas. I now see that you and Ilmari are right -- there's no way > to accomplish what I really want, i.e., to label containers in each > object independently of any other objects. That would require allowing > duplicate labels. But since integer (or any scalar) multiplication > is commutative, the bicj versus bjci problem can't be solved unless > the b-labels and c-labels are somehow unique. > Your very Godel-like solution obviously works, and also seems the > most elegant way to do it given that it won't be getting done my way. > Thanks a lot (both you and Ilmari, and also kunzmilan), No problemo! Your statement "...the bicj versus bjci problem can't be solved unless the b-labels and c-labels are somehow unique" gave me another thought: use a hash function to encode elements such as B_i to a (probabilistically unique) large integer b_i (e.g., SHA hashes might map your objects to 40 digit hexadecimal numbers). Off the top of my head, I'd guess that for an appropriately chosen hash function H and arbitrary objects X, Y and Z, while it is obvious that H(X) will divide both H(X)*H(Y) and H(X)*H(Z), the probability that H(X) divides H(Y)*H(Z) can be made pretty darn unlikely. (Caveat: please consult a number theorist before attempting!). Using this strategy, you wouldn't need to know in advance exactly how many elements belong to B or C in order to acheive your goals; instead, you'd just need to know an upper bound on the number of possible such elements in order to verify that collisions are "sufficiently unlikely". For a basic link to hash functions try (but of course!): http://en.wikipedia.org/wiki/Hash_function Cheers - Chas
From: john forkosh on 28 Dec 2009 19:13
"cbr...(a)cbrownsystems.com" <cbr...(a)cbrownsystems.com> wrote: > JohnF <j...(a)please.see.sig.for.email.com> wrote: > > cbr...(a)cbrownsystems.com <cbr...(a)cbrownsystems.com> wrote: > > > JohnF <j...(a)please.see.sig.for.email.com> wrote: > > >> Ilmari Karonen <usen...(a)vyznev.invalid> wrote: > > >> > JohnF <j...(a)please.see.sig.for.email.com> wrote: > > >> >> I have objects, each of which is an unordered collection > > >> >> of "containers", with each container in an object labelled by > > >> >> an integer, e.g., object B = { (b1,B1), (b2,B2), (b3,B3),... } > > >> >> with Bi a container labelled by integer bi in object B. > > >> >> The bi's are arbitrary integer labels except that bi must > > >> >> uniquely identify the object Bi it labels. > > >> >> Trouble arises because I want to define multiplication > > >> >> of these objects in the following way. Given B and a similar > > >> >> C, define BC = { (bi*cj,(BiCj)) | (bi,Bi)\in B & (cj,Cj)\in C } > > >> >> where bi*cj is integer multiplication, and (BiCj) just means > > >> >> a single container with the contents of Bi and Cj in it. > > >> >> The problem is that each bi*cj label for container (BiCj) > > >> >> must identify both original component containers Bi and Cj. > > >> >> That is, while ordering BiCj versus CjBi is unimportant, > > >> >> the bi*cj label must nevertheless identify i and j as well as > > >> >> which (i or j) belongs to b and which (j or i) to c. > > >> >> Any way to define labels that satisfy these requirements? > <snip> > > > You could select distinct primes p_b, p_c, p_d, etc. associated with > > > each collection B, C, D, etc. (resp.). Then set b_i = (p_b)^i, c_j = > > > (p_c)^j to get distinct products b_i * c_j. > > > E.g., let B={ (2,B1), (4,B2), (8,B3), ...) and C=( (3,C1), (9,C2), > > > (27,C3),...). > > > Cheers - Chas > > > Thanks, Chas. I see that you and Ilmari are right -- there's no way > > to accomplish what I really want, i.e., to label containers in each > > object independently of other objects. That would require allowing > > duplicate labels. But since integer (or any scalar) multiplication > > is commutative, the bicj versus bjci problem can't be solved unless > > the b-labels and c-labels are somehow unique. > > Your veryGodel-like solution obviously works, and also seems the > > most elegant way to do it given that it won't be getting done my way. > > Thanks a lot (both you and Ilmari, and also kunzmilan), > > No problemo! > Your statement "...the bicj versus bjci problem can't be solved unless > the b-labels and c-labels are somehow unique" gave me another thought: > use a hash function to encode elements such as B_i to a > (probabilistically unique) large integer b_i (e.g., SHA hashes might > map your objects to 40 digit hexadecimal numbers). > Off the top of my head, I'd guess that for an appropriately chosen > hash function H and arbitrary objects X, Y and Z, while it is obvious > that H(X) will divide both H(X)*H(Y) and H(X)*H(Z), the probability > that H(X) divides H(Y)*H(Z) can be made pretty darn unlikely. > (Caveat: please consult a number theorist before attempting!). > Using this strategy, you wouldn't need to know in advance exactly how > many elements belong to B or C in order to acheive your goals; > instead, you'd just need to know an upper bound on the number of > possible such elements in order to verify that collisions are > "sufficiently unlikely". > For a basic link to hash functions try (but of course!): > http://en.wikipedia.org/wiki/Hash_function > Cheers - Chas Thanks again, Chas. Actually, though, it's not a computational problem. I want to prove some algebraic properties about these objects, but first need to establish that they concretely exist. So I was looking for a (set-theoretic-like) representation, but only for existence purposes. Complexity, or any other kind of "algorithmic efficacy" of that representation wasn't really an issue. Apparently, as you and Ilmari pointed out, the most general class of such objects I had in mind doesn't exist. So at this point I'm just trying to see what does exist and if I can accomplish anything useful with it. Thanks, -- John Forkosh ( email to: j(a)f.com where j=john and f=forkosh ) |