Thinking about higher order relations

Higher Order Relations

The arity of a relation is the size of the tuples it defines. Another way of thinking of it is that an arity n relation is one that takes (n-1) arguments and pairs them with another element (this is the same style of thinking as for lambda calculus currying, if that helps). Of course, relations are not necessarily functions, so it might pair them with zero, one, or many elements (thus, thinking of the first (n-1) entries in the tuples as arguments can be misleading).

• unary - atoms (0 arguments)
• binary - relation forming order pairs (1 argument)
• ternary - relation forming ordered triple (2 arguments)
• n-ary - relation forming n-tuples (n-1 arguments)

A higher order relation usually refers to one which is ternary or greater. For example, in the following Alloy fragment (from File System Lesson II), contents and parent are ternary relations.

  sig FileSystem {
    root: Dir,
    objects: set FSObject,
    contents: Dir lone-> FSObject,
    parent: FSObject ->lone Dir
  }

Given a filesystem (FileSystem), you can ask for its contents field, which gets you a relation from directories (Dir) to file system objects (FSObject). That is, given a file system and a Directory, you get some set of file system objects. For now, don't worry about the "lone".