Precedence Relation

Imagine you are a student who just learned how to solve simple equations for x. Given that you have this knowledge, it is reasonable to assume you are also able to understand the four basic operations, addition, subtraction, division and multiplication. Also, if you are able to solve these problems in written form, you probably know how to write (at least you know how to write numbers and the letter 'x'). Hence, we may surmise that a student who masters the item 'solving for x' will also master items involving 'basic arithmetic operations' only.

In knowledge space theory a relation such as this one, in which one problem precedes another one, is known as a 'precedence relation'. It is usually written as $$a \preccurlyeq b$$ Precedence relations may be represented graphically, as in the following diagram:

From this plot you can gather that items \(a\) and \(b\) are required to master \(c\). \(e\) in turn cannot be mastered unless you learned \(c\) and \(d\) first.

An important property of a precedence relation is transitivity. This means that, for example, if \(a\) precedes \(b\), and \(b\) precedes \(c\), then \(a\) must also precede \(c\).

If precedence holds in both directions for any two items, then these items are in fact equivalent with respect to the precedence relation, and they are called 'equally informative'. Whenever items \(a\) and \(b\) are equally informative, then $$a \preccurlyeq b, \quad and \quad b \preccurlyeq a,$$ and we write $$a \sim b.$$

Technically speaking, the precedence relations form 'quasi orders' on the domain \(Q\), which are the reflexive and transitive binary relations on \(Q\).

Quasi-Ordinal Knowledge Space

In celebrated result by Garrett Birkhoff (1937), it is shown that the quasi orders on \(Q\) are in one-to-one correspondence to particular knowledge structures, which are closed under union and intersection, and are called 'quasi-ordinal knowledge spaces'. This means that each precedence relation defines a unique quasi-ordinal knowledge space, and each quasi-ordinal knowledge space corresponds to a unique precedence relation.

Given a precedence relation \(\preccurlyeq\) defined on the domain \(Q\), the corresponding quasi-ordinal knowledge space \(\mathcal{K}\) is defined by $$K \in \mathcal{K} \quad iff \quad (p \preccurlyeq q,~~ q \in K ~~implies~~ p \in K).$$

Notice that the more constraints a precedence relation puts on the order of the items, the fewer knowledge states will be consistent with these constraints, and the smaller the corresponding quasi-ordinal knowledge space is.

Play and Test Tabs

The one-to-one correspondence between precedence relations and quasi-ordinal knowledge spaces on a domain $$Q = \{a, b, c, d, e\}.$$ is illustrated in the next tab, where you can define your own precedence relation. You may play around with the relation and observe the effect on the corresponding quasi-ordinal knowledge space, which is illustrated on the right. Notice that, whatever the relation looks like, the induced knowledge structure is closed under union and intersection. This means that with any two knowledge states their union as well as their intersection is a knowledge state, too.

Finally, you may take the quiz in the third tab to test your knowledge, whenever you feel ready to do so.