Sets Early and Probability

SETS  EARLY  and  PROBABILITY   ABSTRACT   Sets  are  fundamental  concepts  that  underlie  much  of  computing.  This  paper  shows   how   sets   can   be   introduced   early   and   then   lead   quickly   and   smoothly   to   logic   and   especially  probability.  This  is  done  with  a  series  of  example  systems   g rowing   i n   s ize   and  complexity.  It  uses  the  Python  language  along  with  some  graphical  set  diagrams   to   provide   a   balanced   approach   for   various   learning   styles   of   students.   The   paper   also  provides  a  new  simple  measure  of  the  probabilistic  dependence  between  sets.   INTRODUCTION   Sets   are   fundamental   to   computing,   as   well   as   philosophy,   mathematics,   engineering,   education   and   life.   In   fact   it   has   been   argued   [2]   that   all   mathematics   can   be   based   on   sets.   Here   we   deal   mainly   with   finite   sets,   which   can   serve   to   complement   a   combinatorial   approach   to   probability.   Various   diagrammatic   set   maps   are   used   as   tools   to   model,   analyze,   compare,   systematize   and   optimize   systems  of  sets  and  to  provide  insights.     Python   3   is   used   for   practical   programming   since   it   has   a   simple   elegant   notation   for   sets,   with   an   interpretive   mode   for   a   constructivist   pedagogical   approach,   Early   refers   not   only   to   the   time   in   the   curriculum,   before   logic   and   probability,   but   also   possibly  at  preu university  levels.   1. SETS  AND  ELEMENTS:  Equal  Status Sets   consist   of   elements,   but   often   the   emphasis   is   only   on   the   sets.   Elements   of   sets can  be  specified  as  records  or  structures  having  binary  attributes  (in  a  set  or  not  in it).   This   balance   is   shown   in   the   given   set   of   ten   decimal   digits   and   the   sample element   digit   “7”   having   (or   not)   four   binary   attributes   (Even,   Lucky,   Rounded, Sticky).  All  of  the  other  9  similar  digits  have  a  binary  value  for  each  attribute. Programming   of   sets   is   finally   possible   and   easy   thanks   to   the   language   Python,   and   especially   the   latest   version,   Python3.   A   sample   program   follows.   It   involves   two   sets  r,  s  of  the  ten  decimal  digits;              r  is  a  set  of  digits  having  rounded  parts,    {0,  2,  3,  5,  6,  8,  9}            s  is  a  set  of  digits  having  straight,  stick-­‐like  parts.  {1,  2,  4,  5,  7}   This   complete   program   includes   comments   which   follow   the   pound   (or   sharp,   #)   sign   to   the   end   of   a   line.   The   output   of   this   program   at   the   right   can   be   done   interactively  also  (with  outputs  shown  after  each  print  command).   Diagrammatic   representation   of   sets   can   be   given   to   balance   left   and   right   brain   preferences   of   students.   Venn   diagrams   are   drawn   as   circular   areas   below   for   the   above   round/sticky   sets.   Karnaugh   maps   [3,   5]   are   rectangular   versions   of   Venn   diagrams  as  shown  below.     Karnaugh   maps   are   preferable   set   diagrams,   because   the   Venn   diagrams   are   incomplete  after  3  sets.  For  four  sets  the  circular  Venn  Diagrams  show  only  14  of  the   16   possible   main   subsets   (minSets);   the   blackened   areas   show   which   are   not   possible  on  the  circular  Venn  diagram.  Karnaugh  set  maps  are  not  only  complete  but   are   easier   to   draw,   compare   and   analyze,   and   they   also   can   provide   more   insight.   The   previous   digital   sets   are   shown   extended   by   two   attributes   (Lucky,   Even).   Length   or   size   of   a   set   s,   len(s),   is   especially   of   interest   in   computing   probabilities.   Gonditional   probabilities   are   insightful   and   easy   to   compute.   For   example  the  probability  of  set  s  given  set  t  is  defined  by  the  simple  Python  function:   def conditionalProb (s, t) : return len(s,t) / len(t) 2. SYSTEMS  OF  2  SETS:  Communication  Channel Communication   channels   or   relays   involve   binary   signals   sent   s,   and   received   r.   The four   probabilities   within   the   given   set   table   and   set   diagram   indicate   the   joint probability   of   each   s,r   pair.     For   example,   a   zero   is   sent   and   a   one   received   with probability  0.1,  also  a  one  is  sent  and  received  as  a  zero  with  probability  0.2,  thus resulting   in   a   probability   of   error   of   0.3.   Summing   joint   probabilities   horizontally and  vertically  (at  the  margins  of  the  table)  indicate  a  marginal  probability  of  sending (.6)  and  receiving  (.5)  of  the  digit  1.  Ratios  of  these  joint  and  marginal  values  yield many  conditional  probabilities  (both  forward  and  reverse). Forward probability is the probability of receiving a value r given a sent value s: i.e. probability that (r = 1) given (s = 0) is (.1 / .4) = .25 Reverse probability is the probability of a sent value s given a received value r. All these forward and reverse probabilities are summarized on the following sagittal diagrams. Measure  of  Dependence It   is   often   useful   to   have   one   number   to   measure   the   relationship   (dependence,   uncertainty)   between   sets;   for   example   between   sent   and   received   signals,   stimulus   and   response,   smoking   and   sickness,   etc.   Two   common   measures   are   chi-­‐square     (from  statistics),  and  entropy  (from  information  theory).   The    chi-­‐square  method  begins  with  the  set  of  actual  joint  probabilities,  and  creates   a  second  set  of  independent  probabilities  by  multiplying  the  marginal  probabilities.   The  differences  between  each  pair  of  actual/independent  values   yields  a  third  set  t.   All   the   values   are   identical   in   magnitude,   but   differ   in   sign.   This   surprizing   result   happens  for  sets  (binary  values)  with  probabilities.     The   chi-­‐square   method   continues   by   squaring   the   differences,   but   here   we   depart   and   use   absolute   values.     These   values   are   then   weighted   as   in   the   information   theoretic   method   with   their   joint   probability   of   occurrence.   The   resulting   average     simplifies  to  a  nice  and  elegant  measure  D  of  dependence:   D = p(r & s) - P(r) * P(s) that  in  this  communication  example  is:   D = .4 - .6 * .5 = 0.10 If  the  sets  were  independent,  the  dependence  measure  would  be  D  =  0;  if  the  joint   probability   was   .2   (with   the   same   sending/receiving   probabilities   and   the   other   joint   values   adjusted)   then   the   dependence   measure   would     be   -­‐0.10.   Such   a   negative  value  indicates  an  inverse  relationship  between  input  and  output  (a  poor   channel).   This   D   measure   only   applies   to   sets   (which   are   binary),   and   can   be   extended   to   many  sets,  whereas  the  other  two  measures  can  apply  also  to  non-­‐binary  systems,   but   are   usually   limited   to   fewer   variables.   There   is   a   trade-­‐off   between   number   of   values  and  number  of  variables.   3. SYSTEMS  OF  3  SETS:  Influenza  Study Systems  involving  3  sets  are  illustrated  by  a  study  of  the  spread  of  flu  in  a  dormitory [1].  Some   students   wore   surgical   masks   and   some   washed   hands   often   as   shown   by percentages   in   the   given   set   diagram.   The   original   design   study   did   not   include those  who  washed  only  and  so  the  data  here  are  fictional  with  convenient  numerical values. This  example  leads  to  many  probabilities,  some  of  which  are  listed  here.  They  may   be   determined   in   two   ways   (preferably   both)   either   by   writing   a   program   or   by   selecting  areas  of  the  set  diagrams.  Many  more  probabilities  are  possible.   Counting  Probabilities   The  number  of  subsets  and  especially  probabilities  is  surprising.  For  3  sets  there  are   8  minSets  and  thus  256  possible  subsets,  which  can  be  generated  by  a  program.  All   possible  conditional  probabilities  between  any  two  subsets  (256*256;  over  65,000)   can  also  be  generated,  and  during  the  generation  some  special  ones  can  be  selected   and   studied   to   reveal   interesting   relationships   between   the   sets.   This   process   can   provide  a  different  way  of  viewing  complex  data.  .  For  4  finite  sets  there  are  over  4   billion  conditional  probabilities;  some  may  be  surprising.!   4. SYSTEMS  OF  4  SETS:  Personality  Types Personalities  have  been  classified  [4,  6]  into  four  types  or  preferences.: These  four  sets  (E,S,T,J)  and  corresponding  complements  (I,N,F,P)  create  16   subsets   of   personality   types   as   shown   in   the   given   figure.   Each   of   the   16   types   is   designated   by   four   letters   such   as   INFP,   ENTP.   Probabilities   of   these   personality   types   can   be   shown   in   set   diagrams   where   different   groups   of   people   would   have   different  distributions.   Immutable   sets,   called   frozen   sets,   are   also   available   in   Python;   they   may   include   subsets  as  elements.  Operations  that  change  contents  (pop,  update,  etc)  do  not  apply   to  these  special  sets.     SUMMARY   Sets  can  be  introduced  early  into  a  curriculum  either  in  a  first  programming  class,  or   in  a  discrete  structures  class.    Recent  languages  such  as  Python  3  make  this  possible   and   convenient.   The   set   concepts   are   closely   related   to   those   of   logic   but   seem   simpler   and   so   can   be   introduced   before   logic   and   especially   before   probability.   Karnaugh   maps   provide   intuitive   and   standard   forms   for   comparing,   structuring   and  studying  sets.  Sets  can  also  be  viewed  as  examples  of  an  object-­‐oriented  system.     Sets,   when   applied   to   probabilistic   systems   involve   unusual   counting,   comparing   and  measuring  methods  with  fewer  values  but  more  variables  than  other  measures   (chi-­‐square  and  entropy)  that  can  involve  more  values  but  usually  fewer  variables.     Sets  provide  elegant  as  well  as  practical  insights,  and  a  natural  introduction  to  logic,   probability  and  systems.   REFERENCES   [1] Aiello,   Allison   E.,   et   al,   Mask   use,   hand   hygiene,   and   seasonal   influenza-­‐like illness  among  young  adults:  a  randomized  intervention  trial.  Journal  of  Infectious Disease,  Feb  15,  2010. [2] [3] [4] Bourbaki,  Nicolas,  Theory  of  Sets,  Reading  MA:  Addison-­‐Wesley,  1968. Karnaugh,   Maurice,     The   Map   Method   for   Synthesis   of   Combinational   Logic Circuits.   Transactions   of   the   American   Institute   of   Electrical   Engineers   part   1 (72(9),  593-­‐599,  November,  1953. Keirsey,   David,   Bates,   Marilyn,   Please   Understand   Me:   Character   and Temperament  Types,  Del  Mar  CA:  Prometheus  Nemesis  Book  Company,  1984. [5] Motil,  John,  Digital  Systems  Fundamentals,  New  York,  NY:  McGraw  Hill,  1972. [6] Myers-­‐Briggs,  Isabel,  Meyers,  Peter  B.,  Gifts  Differing:  Understanding  Personality Type,  Mountain  View,  CA:  Davies-­‐Black  Publishing,  (1980,  1995).