backsets

Backsets is a term used in multiple disciplines and does not have a single universal definition. In order theory and lattice theory, a backset of an element a in a partially ordered set (P, ≤) is commonly taken as the set of elements that precede a: {x ∈ P | x ≤ a}. In many texts this is called a down-set or initial segment, but some authors retain the term backset to stress its backward orientation toward smaller elements.

In graph theory and computer science, backset may refer to the backward reachable set of a node: the collection of all vertices that can reach a given target via directed paths. This concept is central to backward reachability analyses and model checking.

In dynamical systems and related areas, the backset of a subset A under a function f can be defined as the preimage f^{-1}(A) or as f^{-n}(A), the set of points that map into A after n iterations.

Because terminology is not standardized, it is important to confirm a field's definition when encountering the term backset. The common thread is a backward or preimage notion associated with a reference element, set, or state.

Examples: In a linear order {1,2,3,4} with ≤, the backset of 3 is {1,2,3}. In a directed graph with edges toward greater numbers, the backset of 4 comprises nodes that can reach 4.

See also: down-set, initial segment, backward reachable set, preimage.