Tuesday, April 10, 2012

                                                          Mimic Operations

The author writes informal proofs in the following.  The author uses Reverse Polish Notation also.

Suppose we have an infinite set S, and a operation "*". A mimic operation *' of * consists of an operation on S such that for all but a finite number of points a1, ..., an *=a1, ..., an *'. So, for a unary operation F on the natural numbers N, a mimic operation F' satisfies xF=xF' except for a finite set of natural numbers {a1,...,an}. For a binary operation G on N, a mimic of B, B' satisfies xyB=xyB' except for a finite number of pairs of natural numbers {(a, b)1,...,(a, b)n} and so on.

Theorem 1: For any n-ary operation O on an infinite set, there exists an infinity of mimic operations, O'.

Proof: An n-ary operation O can get defined by a set of n 1 + tuples. E. G. the binary operation of addition can get defined by the triples (2, 4, 6), (1, 1, 2) such that for (x, y, z), xy+=z. Now consider the set of such tuples T for O. Vary the n 1 + part of the tuples in T for some finite number of tuples. This forms a set of tuples T' which describes an n-ary operation distinct from O in but a finite number of points, and thus forms a mimic operation O'. Note that since there exist an infinity of tuples belonging to T, there exists an infinity of ways to form T' given T. Thus, given an n-ary operation O, there exists an infinity of mimic operations O'.

Define a k-mimic operation Mk of an operation M as an operation which differs from M by but k points, where both operations operate over an infinite set. In other words, for an operation Mn of arity n with mimic Mkn, a1...anMn=a1...anMkn, except for k tuples {(b1, ..., bn), ..., (l1, ..., ln)} where this equality fails.

Theorem 2: For any n-ary operation O on an infinite set, there exists an infinity of k mimic operations.

Proof: Since given the set of tuples T for an operation O there exist an infinity of ways to form T' (see the proof of Theorem 1). From T' we have an infinity of k-mimic operations O' of O.

Theorem 3: If a binary operation O satisfies commutativity, then if xxO=xxO1,  O1 does not satisfy commutativity.

Proof: If O1 is a 1-mimic of O, then xyO=xyO1 for all but one pair (a, b). Suppose that for all x and y, if xyO=yxO, and xyO1=yxO1.  Suppose that (a, b) consists of the point where O and O1 differ, by say letting abO=c, and letting abO1=d, where d does not equal c.  It follows then that abO1=d=baO1 by supposition of commutation for O1. But, this implies that the pair (b, a) consists of a second point where O and O1 differ, which contradicts the supposition of O1 as a 1-mimic of O.  Consequently, the theorem follows and if O1 satisfies commutation it at least consists of a 2-mimic.

Conjecture: If On and Ok are mimics of operation O, then On and Ok are mimics of each other.

The author thinks theorem 3 generalizes to o-mimics, where "o" indicates any positive odd number. The author also thinks that converse of the theorem holds in that if a 1-mimic does satisfy commutation, the operation which it mimics will not satisfy commutation also.  Do there exist any relationships (or lack thereof) between an associative operation and its mimics?  Between an idempotent operation and its mimics?