Thursday, December 29, 2016

p-Adic logic and hierarchy of partition algebras

As found in the article Boolean algebra, Stone spaces, and TGD, one can generalize Boolean logic to a logic in finite field G(p) with p elements. p-Logics have very nice features. For a given set the p-Boolean algebra can be represented as maps having values in finite field G(p). The subsets with a given value 0≤ k<p define subsets of a partition and one indeed obtains p subsets some of which are empty unless the map is surjection.

The basic challenges are following: generalize logical negation and generalize Boolean operations AND and OR. I have considered several options but the one based on category theoretical thinking seems to be the most promising one. One can imbed p1-Boolean algebras to p-Boolean algebra by considering functions which have values in G(p1)⊂ G(p). One can also project G(p) valued functions to G(p1) by mod p1 operation. The operations should respect the logical negation and p-Boolean operations
if possible.

  1. The basic question is how to define logical negation. Since 2-Boolean algebra is imbeddable to any p-Boolean algebra, it is natural to require that also in p-Boolean case the operation permute 0 and 1. These elements are also preferred elements algebraically since they are neutral elements for sum and product. This condition could be satisfied by simply defining negation as an operation leaving other elements of G(p) un-affected. An alternative definition would be as shift k→ k-1. This is an attractive option since it corresponds to a cyclic symmetry.For G(p) also higher powers of this operation would define analogs of negation in accordance with p-valuedness.

    I have considered also the possibility that for p>2 the analog of logical negation could be defined as an additive inverse k→ p-k in G(p) and k=p-1 would be mapped to k=1 as one might expect. The non-allowed value k=0 is mapped to k=p=0. k=0 would be its own negation. This would suggest that k=0 corresponds to an ill-defined truth value for p>2. For p=2 k=0 must however correspond to false. This option is not however consistent with category theory inspired thinking.

  2. For G(p)-valued functions f, one can define the p-analogs of both XOR (excluded or [(A OR B) but not (A AND B)] and AND using local sum and product for the everywhere-non-vanishing G(p)-valued functions. One can also define the analog of OR in terms of f1+f2-f1f2 for arbitrary G(p)-valued functions. Note that minus sign is essential as one can see by considering p=3 case (1+1-1× 1=1 and 1+1+1× 1=0). For p=2 this would give ordinary OR and it would be obviously non-vanishing unless both functions are identically zero. For p>2 A OR B defined in this manner f1 +f2- f1f2 for functions having no zeros can however have zeros. The mod p1 projection from G(p)→ G(p1) indeed commutes with these operations.

    Could 3-logic with 0 interpreted as ill-defined logical value serve as a representation of Boolean logic? This is not the case: 1× 2=2 would correspond to 1× 0=0 but 2× 2=1 does not correspond to 0× 0=0.

  3. It would be nice to have well-defined inverse of Boolean function giving additional algebra structure for the partitions. For non-vanishing values of f(x) one would have (1/f)(x)=1/f(x). How to define (1/f)(x) for f(x)=0? One can consider three options.

    1. Option I: If 0 is interpreted as ill-defined value of p-Boolean function, there is a temptation to argue that the value of 1/f is also ill defined: (1/f)(x)=0 for f(x)=0. That function values would be replaced with their inverses only at points, where they are no-vanishing would conform with how ill-defined Boolean values are treated in computation. This leads to a well-defined algebra structure but the inverse defined in this manner is only local inverse. One has f (f-1) (x))=1 only for f(x)>0. One has algebra but not a field.

    2. Option II: One could consider the extension of G(p) by the inverse of 0, call it ∞, satisfying 0× ∞=1 ("false" AND ∞ = "true"!). Arithmetic intuition would suggest k× ∞ = ∞ for k>0 and k+∞ = ∞ for all k.

      On the other hand, the interpretation of + as XOR would suggest that k+∞ corresponds to [(k OR ∞) but not (k AND ∞)=∞] suggesting k+∞= k so that 0 and ∞ would be in completely symmetrical position with respect to product and sum (k+∞=k and k+0=k; k× ∞=∞ and k× 0=0). It would be nice to have a logical interpretation for the inverse and for the element ∞. Especially so in 2-Boolean case. A plausible looking interpretation of ∞ would be as "ill-defined" implying that k OR ∞ and k AND ∞ is also "ill-defined". ["false" AND "ill-defined"]="true" sounds however strange.

      For a set with N elements this would give a genuine field with (p+1)N elements. For the more convincing arithmetic option the outcome is completely analogous to the addition of point ∞ to real or complex numbers.

    3. Option III: One could also consider functions, which are non-vanishing at all points of the set are allowed. This function space is not however closed under summation.

  4. For these three options one would have K(N)=pN, K(N)=(p+1)N and K(N)=(p-1)N different maps of this kind having additive and multiplicative inverses. This hierarchy of statements about statements continues ad infinitum with K(n)=K(K(n-1)). For Option II this gives K(n)= (p+1)K(n-1) so that one does not obtain finite field G(p,N) with pN elements but function field.

  5. One can also consider maps for which values are in the range 0<k<p. This set of maps would be however closed with respect to OR and would not obtain hierarchy of finite fields. In this case the interpretation of 0 would be is un-determined and for p=2 this option would be trivial. For p=3 one would have effectively two well-defined logic values but the algebra would not be equivalent with ordinary Boolean algebra.

The outcome for Option II would be a very nice algebraic structure having also geometric interpretation possibly interesting from the point of view of logic. p-Boolean algebra provides p-partitions with generalizations of XOR, OR, AND, negation, and finite field structure at each level of the hierarchy: kind of calculus for p-partitions.

The lowest level of the algebraic structure generalizes as such also to p-adic-valued functions in discrete or even continuous set. The negation fails to have an obvious generalization and the second level of the hierarchy would require defining functions in the infinite-D space of p-adic-valued functions.

See the article Boolean algebra, Stone spaces, and TGD.

For a summary of earlier postings see Latest progress in TGD.

Articles and other material related to TGD.

No comments: