Mathematical Foundations

Basic definitions

Definition — Knowledge Structure

A knowledge structure on a finite domain \(Q\) is a pair \((Q, \mathcal{K})\) where \(\mathcal{K} \subseteq 2^Q\) is a family of subsets (called knowledge states) such that:

  1. \(\emptyset \in \mathcal{K}\) (the empty state)

  2. \(Q \in \mathcal{K}\) (the full domain)

The elements of \(Q\) are called items — they represent problems, questions, or competencies that can be mastered.

Special structures

Definition — Knowledge Space

A knowledge structure \((Q, \mathcal{K})\) is a knowledge space if \(\mathcal{K}\) is closed under set union:

\[K_1, K_2 \in \mathcal{K} \implies K_1 \cup K_2 \in \mathcal{K}\]

Definition — Learning Space

A knowledge space \((Q, \mathcal{K})\) is a learning space if it is well-graded: for every non-empty state \(K \in \mathcal{K}\), there exists an item \(q \in K\) such that \(K \setminus \{q\} \in \mathcal{K}\).

A learning space guarantees that every skill combination is reachable from \(\emptyset\) by adding items one at a time — there is always a learning path.

Surmise relations

A surmise relation (or prerequisite relation) is a partial order \(\preceq\) on \(Q\). If \(a \preceq b\), then mastering \(a\) is a prerequisite for mastering \(b\).

The ordinal space generated by a surmise relation is the family of all downsets (downward-closed subsets):

\[\mathcal{K} = \{K \subseteq Q \mid \forall q \in K, \; \text{prereq}(q) \subseteq K\}\]

This is always closed under both union and intersection (a distributive lattice).

Surmise functions

A surmise function \(\sigma: Q \to 2^{2^Q}\) generalises the surmise relation. For each item \(q\), \(\sigma(q)\) is a family of clauses — alternative minimal foundations for mastering \(q\).

Four axioms define a surmise function (Def. 5.1.2):

  1. \(\sigma(q) \neq \emptyset\) — at least one clause per item

  2. \(q \in C\) for all \(C \in \sigma(q)\) — each clause contains its item

  3. If \(q' \in C \in \sigma(q)\), then \(\exists\, C' \in \sigma(q')\) with \(C' \subseteq C\) — refinement

  4. Clauses for the same item are incomparable under \(\subseteq\)

Theorem 5.2.5 (Learning Spaces): There is a one-to-one correspondence between granular knowledge spaces and surmise functions. The clauses of \(\sigma\) are exactly the atoms of \(\mathcal{K}\), and a set \(K\) is a state iff:

\[\forall q \in K, \; \exists\, C \in \sigma(q) : C \subseteq K\]

When each item has exactly one clause, \(\sigma\) reduces to a surmise relation (the ordinal case).

Competence-Based KST

The CB-KST framework separates skills from items:

  • \(S\): a set of skills

  • \(\mu: Q \to 2^S\): for each item, the skills required to solve it

  • A surmise relation on \(S\) (skill prerequisites)

The problem function maps a competence state \(C \subseteq S\) to the set of solvable items:

\[p(C) = \{q \in Q \mid \mu(q) \subseteq C\}\]

The knowledge structure is:

\[\mathcal{K} = \{p(C) \mid C \in \mathcal{C}\}\]

where \(\mathcal{C}\) is the competence structure (downsets of the skill order).

References

  • Doignon, J.-P., & Falmagne, J.-C. (1999). Knowledge Spaces. Springer-Verlag.

  • Falmagne, J.-C., & Doignon, J.-P. (2011). Learning Spaces. Springer-Verlag.