2
$\begingroup$

For any equivalence $\sim$ on some collection of objects $C$ consider the problem of trying to determine if two arbitrary objects $x$ and $y$ in $C$ are equivalent i.e. if $x\sim y$ now by definition an invarient is just a function $\phi$ satisfying $x\sim y\implies f(x)=f(y)$ while the function $\phi$ is a complete invariant iff we have that $x\sim y\iff \phi(x)=\phi(y)$. Now my question is suppose we have some invarient $\phi$ that satisfies $x\sim y\iff \phi(x)=\phi(y)$ but only for a sub-collection $C'$ of $C$.

Would it be correct terminology to say $\phi$ is a "complete invarient over $C'$"? In the sense it becomes a complete invarient were one to only consider the class of objects $C'$ rather then all objects in $C$.

If not then is there already some terminology in use for reffering to this concept?

The usefulness of defining such a generalization of a complete invarient over a subcollection of objects would be that solving a classification problem could then be reduced to finding simple invarients that are complete over sub collections whose union forms the original collection.

Here would be an example, consider the graph isomorphism problem and for an arbitrary graph $G$ the graph invarient $f$ that maps $G$ to the cardinality of its vertex set i.e. we have $f(G)=|V(G)|$. Now the invariant $f$ is "complete over all path graphs" since for any two path graphs $G$ and $H$ we have $f(G)=f(H)\iff G\cong H$ similarly $f$ is "complete over all cycle graphs" as for two cycle graphs $G$ and $H$ we get $f(G)=f(H)\iff G\cong H$ further $f$ is "complete over all wheel graphs" as again for any two wheel graphs $G$ and $H$ we have $f(G)=f(H)\iff G\cong H$. However the function $f$ would not be a complete invarient over all trees because we may have for two trees $T,T'$ that $f(T)=f(T')$ and yet $T\not\cong T'$ thus $f$ is not in general a complete graph invarient, however it is "complete for path graphs" and also "complete for cycle graphs" and "complete for wheel graphs" using the terminology I made up.

So just to re-iterate does this weaker notion of a complete invarient in a classification problem have a name? Would it be proper convention to say an invarient is "complete over < sub-collection >" like I just did when working on some arbitrary classification problem?

$\endgroup$

1 Answer 1

2
$\begingroup$

It seems totally fine. Maybe instead of "complete over $C'$" use "complete for $C'$" or "complete invariant of path graphs".

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.