Mercurial > dylan

     1 #+TITLE: Categorification of Plausible Reasoning

     2 #+AUTHOR: Dylan Holmes

     3 #+MATHJAX: align:"left" mathml:t path:"../MathJax/MathJax.js"

     4 * COMMENT #+OPTIONS: LaTeX:dvipng

     5 

     6 * Deductive and inductive posets

     7 

     8 ** Definition

     9 If you have a collection \(P\) of logical propositions, you can order them by

    10 implication: \(a\) precedes \(b\) if and only if \(a\) implies

    11 \(b\). This makes \(P\) into a poset. Since the ordering arose from

    12 deductive implication, we'll call this a /deductive poset/.

    13 

    14 If you have a deductive poset \(P\),  you can create a related poset \(P^*\)

    15 as follows: the underlying set is the same, and for any two

    16 propositions \(a\) and \(b\) in \(P\), \(a\) precedes

    17 \(ab\) in \(P^*\). We'll call this an /inductive poset/.

    18 

    19 ** A canonical map from  deductive posets to inductive posets

    20 Each poset corresponds with a poset-category, that is a category with

    21 at most one arrow between any two objects. Considered as categories,

    22 inductive and deuctive posets are related as follows: there is a map

    23 \(\mathscr{F}\) which sends each arrow \(a\rightarrow b\) in \(P\) to

    24 the arrow \(a\rightarrow ab\) in \(P^*\). In fact, since \(a\) implies

    25 \(b\) if and only if \(a = ab\), \(\mathscr{F}\) sends each arrow  in \(P\) to

    26 an identity arrow  in \(P^*\) (specifically, it sends the arrow

    27 \(a\rightarrow b\) to the identity arrow \(a\rightarrow a\)).

    28 

    29 

    30 ** Assigning plausibilities to inductive posets

    31 

    32 Inductive posets encode the relative (/qualitative/) plausibilities of its

    33 propositions: there exists an arrow \(x\rightarrow y\) only if \(x\)

    34 is at least as plausible as \(y\).

    35 

    36 *** Consistent reasoning as a commutative diagram

    37 Inductive categories enable the following neat trick: we can interpret

    38 the objects of \(P^*\) as states of given information and interpret

    39 each arrow \(a\rightarrow ab\) in \(P^*\) as an inductive inference: the arrow

    40 \(a\rightarrow ab\) represents an inferential leap from the state of

    41 knowledge where only \(a\) is given to the state of knowledge where

    42 both \(a\) and \(b\) are given\mdash{} in this way, it represents

    43 the process of inferring \(b\) when  given \(a\), and we label the

    44 arrow with \((b|a)\).

    45 

    46 This trick has several important features that suggest its usefulness,

    47 namely

    48  - Composition of arrows corresponds to compound inference.

    49  - In the special case of deductive inference, the inferential arrow is an

    50    identity; the source and destination states of knowledge are the same.

    51  - One aspect of the consistency requirement of Jaynes[fn:1] takes the form of a

    52    commutative square: \(x\rightarrow ax \rightarrow abx\) =

    53    \(x\rightarrow bx \rightarrow abx\) is the categorified version of

    54    \((AB|X)=(A|X)\cdot(B|AX)=(B|X)\cdot(A|BX)\).

    55  - We can make plausibility assignments by enriching the inductive

    56    category \(P^*\) over some monoidal category, e.g. the set of real numbers

    57    (considered as a category) with its usual multiplication. /When we do/,

    58    the identity arrows of \(P^*\) \mdash{}corresponding to

    59    deductive inferences\mdash{} are assigned a value of certainty automatically.

    60 

    61 [fn:1] /(IIIa) If a conclusion can be reasoned out in more than one

    62 way, then every possible way must lead to the same result./

    63 

    64 

    65 *** Reciprocal probabilities

    66 The natural numbers have a comparatively concrete origin: they are the

    67 result of decategorifying the category of finite sets[fn:2], or the

    68 coequalizer of the arrows from a one-object category to a two-object

    69 category with a single nonidentity arrow. Extensions of the set of

    70 natural numbers\mdash{} such as

    71 the set of integers or rational numbers or real numbers\mdash{} strike

    72 me as being somewhat more abstract.

    73 

    74 Jaynes points out that our existing choice of scale for probabilities

    75 (i.e., the scale from 0 for impossibility to 1 for

    76 certainty) has a degree of freedom: any monotonic function of

    77 probability encodes the same information that probability does.

    78 

    79 With this in mind, it seems useful to use not /probability/ but

    80 /reciprocal probability/ instead. This scale, which we might

    81 tentatively call freeness, is a scale ranging 1 (certainty) to

    82 positive infinity (impossibility).

    83 

    84 In this way, the ``probability''

    85 associated with choosing one out of \(n\) indistinguishable choices

    86 becomes identified with \(n\).

    87 

    88 The entropy 

    89 

    90 [fn:2] As Baez says.

    91 

    92 

    93 

    94 ** self-questions

    95 

    96 What circumstances would make \(\mathscr{F}\) an injection?

    97 

    98 What if \(P=\{\top,\bot\}\)?

    99 

   100 

   101 

   102 ** COMMENT 

   103 Inductive and deductive posets are related as follows: there is a monotone

   104 inclusion map \(\mathscr{i}:P^*\hookrightarrow P\) which\mdash{} since \(a\)

   105 implies \(b\) is equivalent to \(a=ab\)\mdash{} sends comparable

   106 propositions in \(P\) to the same proposition in \(P^*\). Conversely,

   107 only comparable propositions in \(P\) are sent to the same proposition

   108 in \(P^*\).

   109 

   110 

   111 

   112 ** Inductive posets and plausibility

   113 

   114 * Inverse Probability
author	Robert McIntyre <rlm@mit.edu>
date	Fri, 28 Oct 2011 00:06:37 -0700
parents	b4de894a1e2e
children