Journal of Formalized Mathematics
Volume 15, 2003
University of Bialystok
Copyright (c) 2003 Association of Mizar Users

The abstract of the Mizar article:

Intuitionistic Propositional Calculus in the Extended Framework with Modal Operator. Part I

by
Takao Inoue

Received April 3, 2003

MML identifier: INTPRO_1
[ Mizar article, MML identifier index ]


environ

 vocabulary FINSEQ_1, RELAT_1, FUNCT_1, ZF_LANG, BOOLE, INTPRO_1, QC_LANG2;
 notation TARSKI, XBOOLE_0, SUBSET_1, NUMBERS, RELAT_1, FUNCT_1, NAT_1,
      FINSEQ_1;
 constructors NAT_1, CQC_LANG, MEMBERED;
 clusters RELSET_1, MEMBERED, NUMBERS, ORDINAL2;
 requirements NUMERALS, BOOLE, SUBSET;


begin :: Intuitionistic propositional calculus IPC in the extended
      :: language with modal operator

definition let E be set;
  attr E is with_FALSUM means
:: INTPRO_1:def 1
      <*0*>in E;
end;

definition let E be set;
  attr E is with_int_implication means
:: INTPRO_1:def 2
  for p, q being FinSequence st
         p in E & q in E holds <*1*>^p^q in E;
end;

definition let E be set;
  attr E is with_int_conjunction means
:: INTPRO_1:def 3
     for p, q being FinSequence st
     p in E & q in E holds <*2*>^p^q in E;
end;

definition let E be set;
  attr E is with_int_disjunction means
:: INTPRO_1:def 4
     for p, q being FinSequence st
         p in E & q in E holds <*3*>^p^q in E;
end;

definition let E be set;
  attr E is with_int_propositional_variables means
:: INTPRO_1:def 5
     for n being Nat holds <* 5+2*n *> in E;
end;

definition let E be set;
  attr E is with_modal_operator means
:: INTPRO_1:def 6
  for p being FinSequence st
         p in E holds <*6*>^p in E;
end;

:: We reserve <*4*> for verum for a possible formulation.
:: So do we <* 5+2*n+1 *> for every n >= 1 for introduction of a number of
:: other logical connectives (e.g. for polymodal logics,
:: hybrid logics, recent computer-oriented logics and so on).

definition let E be set;
  attr E is MC-closed means
:: INTPRO_1:def 7
   E c= NAT* &
   E is with_FALSUM with_int_implication
        with_int_conjunction with_int_disjunction
        with_int_propositional_variables
        with_modal_operator;
end;

definition
  cluster MC-closed ->
     with_FALSUM with_int_implication
     with_int_conjunction with_int_disjunction
     with_int_propositional_variables
     with_modal_operator non empty set;
  cluster
      with_FALSUM with_int_implication
      with_int_conjunction with_int_disjunction
      with_int_propositional_variables
      with_modal_operator -> MC-closed Subset of NAT*;
end;

definition
  func MC-wff -> set means
:: INTPRO_1:def 8
   it is MC-closed &
   for E being set st E is MC-closed holds it c= E;
end;

definition
  cluster MC-wff -> MC-closed;
end;

definition
  cluster MC-closed non empty set;
end;

definition
  cluster -> Relation-like Function-like Element of MC-wff;
end;

definition
  cluster -> FinSequence-like Element of MC-wff;
end;

definition
  mode MC-formula is Element of MC-wff;
end;

definition
  func FALSUM -> MC-formula equals
:: INTPRO_1:def 9
    <*0*>;

  let p, q be Element of MC-wff;
  func p => q -> MC-formula equals
:: INTPRO_1:def 10
    <*1*>^p^q;

  func p '&' q -> MC-formula equals
:: INTPRO_1:def 11
    <*2*>^p^q;

  func p 'or' q -> MC-formula equals
:: INTPRO_1:def 12
    <*3*>^p^q;
end;

definition
let p be Element of MC-wff;
  func Nes p -> MC-formula equals
:: INTPRO_1:def 13
    <*6*>^p;
end;

 reserve T, X, Y for Subset of MC-wff;
 reserve p, q, r, s for Element of MC-wff;

definition let T be Subset of MC-wff;
  attr T is IPC_theory means
:: INTPRO_1:def 14
    for p, q, r being Element of MC-wff holds
    p => (q => p) in T &
    (p => (q => r)) => ((p => q) => (p => r)) in T &
    (p '&' q) => p in T &
    (p '&' q) => q in T &
    p => (q => (p '&' q)) in T &
    p => (p 'or' q) in T &
    q => (p 'or' q) in T &
    (p => r) => ((q => r) => ((p 'or' q) => r)) in T &
    FALSUM => p in T &
    (p in T & p => q in T implies q in T);
end;

definition let X;
  func CnIPC X -> Subset of MC-wff means
:: INTPRO_1:def 15
  r in it iff for T st T is IPC_theory & X c= T holds r in T;
end;

definition
  func IPC-Taut -> Subset of MC-wff equals
:: INTPRO_1:def 16
    CnIPC({}(MC-wff));
end;

definition
  let p be Element of MC-wff;
  func neg p -> MC-formula equals
:: INTPRO_1:def 17
        (p => FALSUM);
end;

definition
  func IVERUM -> MC-formula equals
:: INTPRO_1:def 18
  (FALSUM => FALSUM);
end;

theorem :: INTPRO_1:1
  p => (q => p) in CnIPC (X);

theorem :: INTPRO_1:2
  (p => (q => r)) => ((p => q) => (p => r)) in CnIPC (X);

theorem :: INTPRO_1:3
  p '&' q => p in CnIPC(X);

theorem :: INTPRO_1:4
  p '&' q => q in CnIPC(X);

theorem :: INTPRO_1:5
  p => (q => (p '&' q)) in CnIPC (X);

theorem :: INTPRO_1:6
  p => (p 'or' q) in CnIPC (X);

theorem :: INTPRO_1:7
  q => (p 'or' q) in CnIPC (X);

theorem :: INTPRO_1:8
  (p => r) => ((q => r) => ((p 'or' q) => r)) in CnIPC (X);

theorem :: INTPRO_1:9
  FALSUM => p in CnIPC (X);

theorem :: INTPRO_1:10
  p in CnIPC(X) & p => q in CnIPC(X) implies q in CnIPC(X);

theorem :: INTPRO_1:11
T is IPC_theory & X c= T implies CnIPC(X) c= T;

theorem :: INTPRO_1:12
  X c= CnIPC(X);

theorem :: INTPRO_1:13
  X c= Y implies CnIPC(X) c= CnIPC(Y);

theorem :: INTPRO_1:14 :: Th14:
    CnIPC(CnIPC(X)) = CnIPC(X);

definition let X be Subset of MC-wff;
  cluster CnIPC(X) -> IPC_theory;
end;

theorem :: INTPRO_1:15
  T is IPC_theory iff CnIPC(T) = T;

theorem :: INTPRO_1:16 :: Th16:
    T is IPC_theory implies IPC-Taut c= T;

definition
  cluster IPC-Taut -> IPC_theory;
end;

begin  :: Formulas provable in IPC : implication

theorem :: INTPRO_1:17   :: Identity law
  p => p in IPC-Taut;

theorem :: INTPRO_1:18
  q in IPC-Taut implies p => q in IPC-Taut;

theorem :: INTPRO_1:19 :: Th19:
    IVERUM in IPC-Taut;

theorem :: INTPRO_1:20 :: Th20:
    (p => q) => (p => p) in IPC-Taut;

theorem :: INTPRO_1:21 :: Th21:
    (q => p) => (p => p) in IPC-Taut;

theorem :: INTPRO_1:22
  (q => r) => ((p => q) => (p => r)) in IPC-Taut;

theorem :: INTPRO_1:23
  p => (q => r) in IPC-Taut implies q => (p => r) in IPC-Taut;

theorem :: INTPRO_1:24  :: Hypothetical syllogism
  (p => q) => ((q => r) => (p => r)) in IPC-Taut;

theorem :: INTPRO_1:25
  p => q in IPC-Taut implies (q => r) => (p => r) in IPC-Taut;

theorem :: INTPRO_1:26
  p => q in IPC-Taut & q => r in IPC-Taut implies p => r in IPC-Taut;

theorem :: INTPRO_1:27
 (p => (q => r)) => ((s => q) => (p => (s => r))) in IPC-Taut;

theorem :: INTPRO_1:28 :: Th28:
    ((p => q) => r) => (q => r) in IPC-Taut;

theorem :: INTPRO_1:29  :: Contraposition
  (p => (q => r)) => (q => (p => r)) in IPC-Taut;

theorem :: INTPRO_1:30   :: A Hilbert axiom
  (p => (p => q)) => (p => q) in IPC-Taut;

theorem :: INTPRO_1:31 :: Th31: :: Modus ponendo ponens
    q => ((q => p) => p) in IPC-Taut;

theorem :: INTPRO_1:32
  s => (q => p) in IPC-Taut & q in IPC-Taut implies s => p in IPC-Taut;

begin :: Formulas provable in IPC : conjunction

theorem :: INTPRO_1:33
  p => (p '&' p) in IPC-Taut;

theorem :: INTPRO_1:34
  (p '&' q) in IPC-Taut iff p in IPC-Taut & q in IPC-Taut;

theorem :: INTPRO_1:35 :: Th35:
    (p '&' q) in IPC-Taut iff (q '&' p) in IPC-Taut;

theorem :: INTPRO_1:36
  (( p '&' q ) => r ) => ( p => ( q => r )) in IPC-Taut;

theorem :: INTPRO_1:37
  ( p => ( q => r )) => (( p '&' q ) => r ) in IPC-Taut;

theorem :: INTPRO_1:38
  ( r => p ) => (( r => q ) => ( r => ( p '&' q ))) in IPC-Taut;

theorem :: INTPRO_1:39
  ( (p => q) '&' p ) => q in IPC-Taut;

theorem :: INTPRO_1:40 :: Th40:
    (( (p => q) '&' p ) '&' s ) => q in IPC-Taut;

theorem :: INTPRO_1:41 :: Th41:
    (q => s) => (( p '&' q ) => s) in IPC-Taut;

theorem :: INTPRO_1:42
  (q => s) => (( q '&' p ) => s) in IPC-Taut;

theorem :: INTPRO_1:43
  ( (p '&' s) => q ) => ((p '&' s) => (q '&' s)) in IPC-Taut;

theorem :: INTPRO_1:44
  ( p => q ) => ((p '&' s) => (q '&' s)) in IPC-Taut;

theorem :: INTPRO_1:45
  (( p => q ) '&' ( p '&' s )) => ( q '&' s ) in IPC-Taut;

theorem :: INTPRO_1:46
  ( p '&' q ) => ( q '&' p ) in IPC-Taut;

theorem :: INTPRO_1:47
  ( p => q ) '&' ( p '&' s ) => ( s '&' q ) in IPC-Taut;

theorem :: INTPRO_1:48
  ( p => q ) => (( p '&' s ) => ( s '&' q )) in IPC-Taut;

theorem :: INTPRO_1:49
  ( p => q ) => (( s '&' p ) => ( s '&' q )) in IPC-Taut;

theorem :: INTPRO_1:50 :: Th50:
    ( p '&' (s '&' q) ) => ( p '&' (q '&' s) ) in IPC-Taut;

theorem :: INTPRO_1:51 :: Th51:
    ( ( p => q ) '&' (p => s) ) => ( p => (q '&' s) ) in IPC-Taut;

theorem :: INTPRO_1:52 :: Th52:
    (p '&' q) '&' s => p '&' (q '&' s) in IPC-Taut;

theorem :: INTPRO_1:53 :: Th53:
    p '&' (q '&' s) => (p '&' q) '&' s in IPC-Taut;

begin :: Formulas provable in IPC: disjunction

theorem :: INTPRO_1:54
  (p 'or' p) => p in IPC-Taut;

theorem :: INTPRO_1:55 :: Th55:
    p in IPC-Taut or q in IPC-Taut implies (p 'or' q) in IPC-Taut;

theorem :: INTPRO_1:56
  (p 'or' q) => (q 'or' p) in IPC-Taut;

theorem :: INTPRO_1:57 :: Th57:
    (p 'or' q) in IPC-Taut iff (q 'or' p) in IPC-Taut;

theorem :: INTPRO_1:58
  (p => q) => (p => (q 'or' s)) in IPC-Taut;

theorem :: INTPRO_1:59
  (p => q) => (p => (s 'or' q)) in IPC-Taut;

theorem :: INTPRO_1:60
  ( p => q ) => ((p 'or' s) => (q 'or' s)) in IPC-Taut;


theorem :: INTPRO_1:61
  p => q in IPC-Taut implies (p 'or' s) => (q 'or' s) in IPC-Taut;

theorem :: INTPRO_1:62
  ( p => q ) => (( s 'or' p ) => ( s 'or' q )) in IPC-Taut;

theorem :: INTPRO_1:63
  p => q in IPC-Taut implies ( s 'or' p ) => ( s 'or' q ) in IPC-Taut;

theorem :: INTPRO_1:64
  ( p 'or' (q 'or' s) ) => ( q 'or' (p 'or' s) ) in IPC-Taut;

theorem :: INTPRO_1:65 :: Th65:
    ( p 'or' (q 'or' s) ) => ( (p 'or' q) 'or' s ) in IPC-Taut;

theorem :: INTPRO_1:66 :: Th66:
    ( (p 'or' q) 'or' s ) => ( p 'or' (q 'or' s) ) in IPC-Taut;

begin :: Classical propositional calculus CPC

reserve T, X, Y for Subset of MC-wff;
reserve p, q, r for Element of MC-wff;

definition let T be Subset of MC-wff;
  attr T is CPC_theory means
:: INTPRO_1:def 19
    for p, q, r being Element of MC-wff holds
    p => (q => p) in T &
    (p => (q => r)) => ((p => q) => (p => r)) in T &
    (p '&' q) => p in T &
    (p '&' q) => q in T &
    p => (q => (p '&' q)) in T &
    p => (p 'or' q) in T &
    q => (p 'or' q) in T &
    (p => r) => ((q => r) => ((p 'or' q) => r)) in T &
    FALSUM => p in T &
    p 'or' (p => FALSUM) in T &
    (p in T & p => q in T implies q in T);
end;

theorem :: INTPRO_1:67
T is CPC_theory implies T is IPC_theory;

definition let X;
  func CnCPC X -> Subset of MC-wff means
:: INTPRO_1:def 20
  r in it iff for T st T is CPC_theory & X c= T holds r in T;
end;

definition
  func CPC-Taut -> Subset of MC-wff equals
:: INTPRO_1:def 21
    CnCPC({}(MC-wff));
end;

theorem :: INTPRO_1:68
CnIPC (X) c= CnCPC (X);

theorem :: INTPRO_1:69
  p => (q => p) in CnCPC (X) &
 (p => (q => r)) => ((p => q) => (p => r)) in CnCPC (X) &
  p '&' q => p in CnCPC (X) &
  p '&' q => q in CnCPC (X) &
  p => (q => (p '&' q)) in CnCPC (X) &
  p => (p 'or' q) in CnCPC (X) &
  q => (p 'or' q) in CnCPC (X) &
  (p => r) => ((q => r) => ((p 'or' q) => r)) in CnCPC (X) &
  FALSUM => p in CnCPC (X) &
  p 'or' (p => FALSUM) in CnCPC (X);

theorem :: INTPRO_1:70
p in CnCPC(X) & p => q in CnCPC(X) implies q in CnCPC(X);


theorem :: INTPRO_1:71
T is CPC_theory & X c= T implies CnCPC(X) c= T;

theorem :: INTPRO_1:72
  X c= CnCPC(X);

theorem :: INTPRO_1:73
  X c= Y implies CnCPC(X) c= CnCPC(Y);

theorem :: INTPRO_1:74 :: Th6C:
    CnCPC(CnCPC(X)) = CnCPC(X);

definition let X be Subset of MC-wff;
  cluster CnCPC(X) -> CPC_theory;
end;

theorem :: INTPRO_1:75
  T is CPC_theory iff CnCPC(T) = T;

theorem :: INTPRO_1:76 :: Th8C:
    T is CPC_theory implies CPC-Taut c= T;

definition
  cluster CPC-Taut -> CPC_theory;
end;

theorem :: INTPRO_1:77 :: CPCincIPC:
  IPC-Taut c= CPC-Taut;

begin :: Modal calculus S4

reserve T, X, Y for Subset of MC-wff;
reserve p, q, r for Element of MC-wff;

definition let T be Subset of MC-wff;
  attr T is S4_theory means
:: INTPRO_1:def 22
    for p, q, r being Element of MC-wff holds
    p => (q => p) in T &
    (p => (q => r)) => ((p => q) => (p => r)) in T &
    (p '&' q) => p in T &
    (p '&' q) => q in T &
    p => (q => (p '&' q)) in T &
    p => (p 'or' q) in T &
    q => (p 'or' q) in T &
    (p => r) => ((q => r) => ((p 'or' q) => r)) in T &
    FALSUM => p in T &
    p 'or' (p => FALSUM) in T &
    (Nes (p => q)) => ((Nes p) => (Nes q)) in T &
    (Nes p) => p in T &
    (Nes p) => Nes (Nes p) in T &
    (p in T & p => q in T implies q in T) &
    (p in T implies Nes p in T);
end;

theorem :: INTPRO_1:78
T is S4_theory implies T is CPC_theory;

theorem :: INTPRO_1:79 :: S4TincIPCT:
  T is S4_theory implies T is IPC_theory;

definition let X;
  func CnS4 X -> Subset of MC-wff means
:: INTPRO_1:def 23
  r in it iff for T st T is S4_theory & X c= T holds r in T;
end;

definition
  func S4-Taut -> Subset of MC-wff equals
:: INTPRO_1:def 24
    CnS4({}(MC-wff));
end;

theorem :: INTPRO_1:80
CnCPC (X) c= CnS4 (X);

theorem :: INTPRO_1:81
CnIPC (X) c= CnS4 (X);

theorem :: INTPRO_1:82
  p => (q => p) in CnS4 (X) &
 (p => (q => r)) => ((p => q) => (p => r)) in CnS4 (X) &
  p '&' q => p in CnS4 (X) &
  p '&' q => q in CnS4 (X) &
  p => (q => (p '&' q)) in CnS4 (X) &
  p => (p 'or' q) in CnS4 (X) &
  q => (p 'or' q) in CnS4 (X) &
  (p => r) => ((q => r) => ((p 'or' q) => r)) in CnS4 (X) &
  FALSUM => p in CnS4 (X) &
  p 'or' (p => FALSUM) in CnS4 (X);

theorem :: INTPRO_1:83
p in CnS4 (X) & p => q in CnS4 (X) implies q in CnS4 (X);

theorem :: INTPRO_1:84
(Nes (p => q)) => ((Nes p) => (Nes q)) in CnS4 (X);

theorem :: INTPRO_1:85
(Nes p) => p in CnS4 (X);

theorem :: INTPRO_1:86
(Nes p) => Nes (Nes p) in CnS4 (X);

theorem :: INTPRO_1:87
p in CnS4 (X) implies Nes p in CnS4 (X);

theorem :: INTPRO_1:88
T is S4_theory & X c= T implies CnS4(X) c= T;

theorem :: INTPRO_1:89
  X c= CnS4(X);

theorem :: INTPRO_1:90
  X c= Y implies CnS4(X) c= CnS4(Y);

theorem :: INTPRO_1:91 :: Th10M:
    CnS4(CnS4(X)) = CnS4(X);

definition let X be Subset of MC-wff;
  cluster CnS4(X) -> S4_theory;
end;

theorem :: INTPRO_1:92
  T is S4_theory iff CnS4(T) = T;

theorem :: INTPRO_1:93 :: Th12M:
    T is S4_theory implies S4-Taut c= T;

definition
  cluster S4-Taut -> S4_theory;
end;

theorem :: INTPRO_1:94 :: S4incCPC:
  CPC-Taut c= S4-Taut;

theorem :: INTPRO_1:95 :: S4incIPC:
  IPC-Taut c= S4-Taut;

Back to top