Function minimum associated to a congruence on integral n-tuple space

摘要

Let R be an arbitrary congruence on Nn, the problem of computing unique representations for equivalent objects (=i/i.e problem of canonical simplification) consists in finding an effective procedure S that maps N71 in Nn and has the following specifications: for all elements s,t in Nn S(t) R t and s R t => S(s) = S(t). Suppose N" well ordered for a determined order, we define ft : Nn/R —> Nn as xQx]) = minimumfai], we shall prove that the set of elements of Nn which are not in the image of μ is an ideal of Nn, we shall also prove that if {oi,..., ar} is the system of generators for the ideal mentioned, then μ can be perfectly determined knowing li{[ai]),...,fj,([aT]); furthermore we will prove that {(oi,m([°i])).(°n KM))} is a system of generators for the congruence R. As a consequence we shall obtain a new proof of that "every congruence on Nn is finitely generated," a fact proved for example in [3], [4] and [6]. The system of generators {(ax, ([04.])),..., (or, μ([aT]))} for the congruence R will be called a "good system of generators" for R because it allows us to answer to the problem of canonical simplification. Finally, we shall give an algorithm to compute {(01, μ([