Modelling Informational Entropy

By ‘informational entropy’, we understand an inherent boundary to knowability, due e.g. to perceptual, theoretical, evidential or linguistic limits. In this paper, we discuss a logical framework in which this boundary is incorporated into the semantic and deductive machinery, and outline how this framework can be used to model various situations in which informational entropy arises.

1. 1.

   A formal context [17], or polarity, is a structure such that A and X are sets, and \(I\subseteq A\times X\) is a binary relation. Every such induces maps \((\cdot )^\uparrow : \mathcal {P}(A)\rightarrow \mathcal {P}(X)\) and \((\cdot )^\downarrow : \mathcal {P}(X)\rightarrow \mathcal {P}(A)\), respectively defined by the assignments \(B^\uparrow : = I^{(1)}[B]\) and \(Y^\downarrow : = I^{(0)}[Y]\). A formal concept of is a pair \(c = (B, Y)\) such that \(B\subseteq A\), \(Y\subseteq X\), and \(B^{\uparrow } = Y\) and \(Y^{\downarrow } = B\). Given a formal concept \(c = (B,Y)\) we will often write \([\![{c}]\!]\) for B and \((\![{c}]\!)\) for Y and, consequently, \(c = ([\![{c}]\!], (\![{c}]\!))\). The set of the formal concepts of can be partially ordered as follows: for any ,

   $$\begin{aligned} c\le d\quad \text{ iff } \quad B_1\subseteq B_2 \quad \text{ iff } \quad Y_2\subseteq Y_1. \end{aligned}$$

   With this order, is a complete lattice, the concept lattice of . Any complete lattice is isomorphic to the concept lattice of some polarity .

2. 2.

   Applying the notation (2) to a graph-based \(\mathcal {L}\)-frame , we will sometimes abbreviate \(E^{[0]}[Y]\) and \(E^{[1]}[B]\) as \(Y^{[0]}\) and \(B^{[1]}\), respectively, for each \(Y, B\subseteq Z\). If \(Y= \{y\}\) and \(B = \{b\}\), we write \(y^{[0]}\) and \(b^{[1]}\) for \(\{y\}^{[0]}\) and \(\{b\}^{[1]}\), and write \(Y^{[01]}\) and \(B^{[10]}\) for \((Y^{[0]})^{[1]}\) and \((B^{[1]})^{[0]}\), respectively. Notice that, by Lemma 3, \(Y^{[0]} = I_{E^c}^{(0)}[Y] = Y^{\downarrow }\) and \(B^{[1]} = I_{E^c}^{(1)}[B] = B^{\uparrow }\), where the maps \((\cdot )^\downarrow \) and \((\cdot )^\uparrow \) are those associated with the polarity .

3. 3.

   In well-known settings (e.g. [15, 22]), indiscernibility is modelled as an equivalence relation. However, transitivity will fail, for example, when zEy iff \(d(z, y)<\alpha \) for some distance function d. It has been argued in the psychological literature (cf. [21, 25]) that symmetry will fail in situations where indiscernibility is understood as similarity, defined e.g. as z is similar to y iff z has all the features y has.

4. 4.

   Notice that since the E-relation in this example is only ‘one step’, it is automatically transitive and therefore a pre-order. Hence, unsurprisingly, the associated concept lattice is distributive.

Authors and Affiliations

1. University of the Witwatersrand, Johannesburg, South Africa

   Willem Conradie

2. University of Johannesburg, Johannesburg, South Africa

   Andrew Craig, Alessandra Palmigiano & Nachoem M. Wijnberg

3. Delft University of Technology, Delft, The Netherlands

   Alessandra Palmigiano

4. University of Amsterdam, Amsterdam, The Netherlands

   Nachoem M. Wijnberg

Corresponding author

Correspondence to Andrew Craig .

Editors and Affiliations

1. Department of Philosophy and Religious Studies, Utrecht University, Utrecht, The Netherlands

   Rosalie Iemhoff

2. Utrecht Institute of Linguistics OTS, Utrecht University, Utrecht, The Netherlands

   Michael Moortgat

3. Centro de Informática, Universidade Federal de Pernambuco (UFPE), Recife, Brazil

   Ruy de Queiroz

A Equivalent Compatibility Conditions in Formal Contexts

Lemma 9

1. 1.

   The following are equivalent for every formal context and every relation \(R\subseteq A\times X\):

   1. (i)

      \(R^{(0)}[x]\) is Galois-stable for every \(x\in X\);

   2. (ii)

      \(R^{(0)} [Y]\) is Galois-stable for every \(Y\subseteq X\);

   3. (iii)

      \(R^{(1)}[B]=R^{(1)}[B^{\uparrow \downarrow }]\) for every \(B\subseteq A\).

2. 2.

   The following are equivalent for every formal context and every relation \(R\subseteq A\times X\):

   1. (i)

      \(R^{(1)}[a]\) is Galois-stable for every \(a\in A\);

   2. (ii)

      \(R^{(1)} [B]\) is Galois-stable, for every \(B\subseteq A\);

   3. (iii)

      \(R^{(0)}[Y]=R^{(0)}[Y^{\downarrow \uparrow }]\) for every \(Y\subseteq X\).

Proof

We only prove item 1, the proof of item 2 being similar. For \((i)\Rightarrow (ii)\), see [7, Lemma 4]. The converse direction is immediate.

\((i)\Rightarrow (iii)\). Since \((\cdot )^{\uparrow \downarrow }\) is a closure operator, \(B\subseteq B^{\uparrow \downarrow }\). Hence, Lemma 1.1 implies that \(R_{\Box }^{(1)}[B^{\uparrow \downarrow }]\subseteq R_{\Box }^{(1)}[B]\). For the converse inclusion, let \(x\in R_{\Box }^{(1)}[B]\). By Lemma 1.2, this is equivalent to \(B\subseteq R_{\Box }^{(0)}[x]\). Since \(R_{\Box }^{(0)}[x]\) is Galois-stable by assumption, this implies that \(B^{\uparrow \downarrow }\subseteq R_{\Box }^{(0)}[x]\), i.e., again by Lemma 1.2, \(x\in R_{\Box }^{(1)}[B^{\uparrow \downarrow }]\). This shows that \(R_{\Box }^{(1)}[B]\subseteq R_{\Box }^{(1)}[B^{\uparrow \downarrow }]\), as required.

\((iii)\Rightarrow (i)\). Let \(x\in X\). It is enough to show that \((R_{\Box }^{(0)}[x])^{\uparrow \downarrow }\subseteq R_{\Box }^{(0)}[x]\). By Lemma 1.2, \(R_\Box ^{(0)}[x]\subseteq R_\Box ^{(0)}[x]\) is equivalent to \(x\in R_\Box ^{(1)}[R_\Box ^{(0)}[x]]\). By assumption, \(R_{\Box }^{(1)}[R_\Box ^{(0)}[x]]=R_\Box ^{(1)}[(R_\Box ^{(0)}[x])^{\uparrow \downarrow }]\), hence \(x\in R_\Box ^{(1)}[(R_\Box ^{(0)}[x])^{\uparrow \downarrow }]\). Again by Lemma 1.2, this is equivalent to \((R_{\Box }^{(0)}[x])^{\uparrow \downarrow }\subseteq R_{\Box }^{(0)}[x]\), as required.

B Composing Relations on Graph-Based Structures

The present section collects properties of the E-compositions (cf. Definition 5).

Lemma 10

For any graph , relations \(R, S\subseteq Z \times Z\) and \(a, x\in Z\),

Proof

We only prove the identities in the left column.

Lemma 11

If \(R, T\subseteq Z\times Z\) and R is E-compatible, then so are \(R \circ _{E} T\) and \(R \bullet _{E} T\).

Proof

Let \(a\in Z\). By Lemma 10, \((R;T)^{[0]} [a] = R^{[0]}[I^{[0]}[T^{[0]} [a]]]\), hence the following chain of identities holds:

the second identity in the chain above following from the E-compatibility of R and Lemma 4.1. The remaining conditions for the E-compatibility of \(R \circ _{E} T\) and \(R \bullet _{E} T\) are shown similarly.

The following lemma is the counterpart of [5, Lemma 6] in graph-based semantics.

Lemma 12

If \(R,T\subseteq Z\times Z\) are E-compatible, then for any \(B,Y\subseteq Z\),

Proof

We only prove the first identity, the remaining ones being proved similarly.

Lemma 13

If \(R, T, U\subseteq Z\times Z\) are E-compatible, then \((R\circ _E T)\circ _E U = R\circ _E (T\circ _E U)\) and \((R\bullet _E T)\bullet _E U = R\bullet _E (T\bullet _E U)\).

Proof

For every \(x\in Z\), repeatedly applying Lemma 12 we get:

which shows that \(x (R\circ _E (T\circ _E U))^c a\) iff \(x ((R\circ _E T)\circ _E U)^ca\) for any \(x, a\in Z\), and hence \(x (R\circ _E (T\circ _E U)) a\) iff \(x ((R\circ _E T)\circ _E U)a\) for any \(x, a\in Z\), as required. The remaining statements are proven similarly.

C Proof of Proposition 4

2.

3.

4.

5.

6.

Reprints and permissions

© 2019 Springer-Verlag GmbH Germany, part of Springer Nature

Policies and ethics