Given a set $S$ with

  • An associative binary "addition" operation $+$ with corresponding neutral element $0$ such that $(S, +)$ is a monoid
  • A non-associative binary "truncated subtraction" operation $-$ such that $(S, -)$ is a magma (truncating at the element that is neutral with respect to $+$, i.e.: $\forall x,y \in S: y - y = 0$)

Is there a name for such a structure?

Examples:

  • (This is the motivating example) I am trying to define an algebra of (Unix) globs, considered not as limited by the syntax but as an abstraction allowing the the ability to combine the results of two globs, or to remove the results of one glob from another, with a glob definable in the syntax acting as a sort of urelement, I suppose. It appears to me that from an algebraic perspective, a glob is an encoding or a specifier of a set of files. The set is hypothetical in the sense that its actual contents are not known until the glob is evaluated. However, it should be possible to define the algebra at play without dealing with the evaluation.
  • (Seemingly analogous example) Sets, where only union and set difference (relative complement) are under consideration.
  • (Seemingly analogous example) The naturals, where only addition and truncated subtraction are under consideration.
  • 1
    In terms of the definition of the glob, there exists an underlying set $U$ that consists of ALL possible finite strings in your alphabet. Your glob defines a subset $G$ thereof. The current state of your file system $S$ is a finite subset of $U$. The evaluation of the glob is $G\cap S$. So I think it is perfectly fine to just think in terms of whatever terminology that comes from sets. – Willie Wong Apr 9 at 18:08
up vote 3 down vote accepted

Is commutative monoid with monus what you're looking for?

  • Looks like it. It seems $\leq$ is the key here, and it is clearly able to be defined for Nats and Sets and as I am conceptualizing the globs as something conceptual analogous to sets, I would say that it could be defined for the globs in the same manner as for sets. – Kazark Apr 9 at 17:55
  • 1
    I think you can define it by saying that $x\le y$ if $x-y=0$. Actually proving that this is a partial order respecting the monoid structure requires various axioms on $-$ that I don't think anyone has written down before, so it makes more sense to define $-$ having already defined $\le$. – John Gowers Apr 9 at 18:34

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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