Let \((f_i)_{i \in \iota }\) be a family of values in the extended natural numbers \(\mathbb {N}_\infty = \mathbb {N}\cup \{ \infty \} \), indexed by an arbitrary type \(\iota \), and let \(n \in \mathbb {N}\). Then \(\inf _{i} f_i \le n\) if and only if there exists an index \(i\) with \(f_i \le n\), where \(n\) is regarded as an element of \(\mathbb {N}_\infty \) via the canonical inclusion.

Let \(f : X \to Y \to \alpha \) be a two-argument function and let \(n\) be a natural number. Then the deterministic communication complexity \(D(f)\) satisfies \(D(f) \le n\) if and only if there exists a deterministic communication protocol \(p\) over inputs \(X\) and \(Y\) that computes \(f\) and whose communication complexity is at most \(n\).

Let \(X\), \(Y\), and \(\alpha \) be types, let \(f : X \to Y \to \alpha \) be a two-argument function, and let \(n\) be a natural number. Then the deterministic communication complexity satisfies \(D(f) \le n\) if and only if there exists a finite-message protocol \(p\) over inputs \(X\), \(Y\) and outputs \(\alpha \) whose execution computes \(f\), in the sense that \(p\) run on inputs \(x\) and \(y\) returns \(f(x)(y)\) for all \(x\) and \(y\), and whose communication complexity is at most \(n\).

Let \(f : X \to Y \to \alpha \) be a two-argument function, let \(D(f) \in \mathbb {N}_\infty \) denote its deterministic communication complexity, and let \(n\) be a natural number. Then \(n \le D(f)\) if and only if every deterministic protocol \(p\) that computes \(f\) has communication complexity at least \(n\).