TPTP Problem File: COM133+1.p

View Solutions - Solve Problem

%------------------------------------------------------------------------------
% File     : COM133+1 : TPTP v9.0.0. Released v6.4.0.
% Domain   : Computing Theory
% Problem  : T-subst-abs step in progress/preservation proof
% Version  : Augmented > Especial.
% English  : This problem is a step within the proof of progress and 
%            preservation for the standard type system for the simply-typed 
%            lambda calculus.

% Refs     : [Pie02] Pierce (2002), Programming Languages
%          : [Gre15] Grewe (2015), Email to Geoff Sutcliffe
%          : [GE+15] Grewe et al. (2015), Type Systems for the Masses: Deri
% Source   : [Gre15]
% Names    : SubstLemma-T-subst-abs [Gre15]

% Status   : Theorem
% Rating   : 0.33 v9.0.0, 0.36 v8.1.0, 0.28 v7.5.0, 0.31 v7.4.0, 0.37 v7.3.0, 0.38 v7.1.0, 0.43 v7.0.0, 0.50 v6.4.0
% Syntax   : Number of formulae    :   62 (   6 unt;   0 def)
%            Number of atoms       :  314 ( 231 equ)
%            Maximal formula atoms :   33 (   5 avg)
%            Number of connectives :  293 (  41   ~;  17   |; 133   &)
%                                         (   0 <=>; 102  =>;   0  <=;   0 <~>)
%            Maximal formula depth :   23 (   9 avg)
%            Maximal term depth    :    5 (   1 avg)
%            Number of predicates  :    7 (   5 usr;   1 prp; 0-3 aty)
%            Number of functors    :   17 (  17 usr;   4 con; 0-3 aty)
%            Number of variables   :  356 ( 288   !;  68   ?)
% SPC      : FOF_THM_RFO_SEQ

% Comments : Generated by Veritas: https://github.com/stg-tud/type-pragmatics
%          : This is an expanded version of the original, with most axioms
%            combined into COM001+0.ax.
%------------------------------------------------------------------------------
include('Axioms/COM001+0.ax').
%------------------------------------------------------------------------------
fof('T-Weak',axiom,
    ! [Vx,VS,VC,Ve,VT] :
      ( ( vlookup(Vx,VC) = vnoType
        & vtcheck(VC,Ve,VT) )
     => vtcheck(vbind(Vx,VS,VC),Ve,VT) ) ).

fof('T-Strong',axiom,
    ! [Vx,VS,VC,Ve,VT] :
      ( ( ~ visFreeVar(Vx,Ve)
        & vtcheck(vbind(Vx,VS,VC),Ve,VT) )
     => vtcheck(VC,Ve,VT) ) ).

fof('T-Weak-FreeVar',axiom,
    ! [Vx,VS,VC,Ve,VT] :
      ( ( ~ visFreeVar(Vx,Ve)
        & vtcheck(VC,Ve,VT) )
     => vtcheck(vbind(Vx,VS,VC),Ve,VT) ) ).

fof('T-subst-IH-abs',axiom,
    ! [VT,VC,Vx,Ve,VT2] :
      ( ( vtcheck(VC,Ve,VT)
        & vtcheck(vbind(Vx,VT,VC),veabs,VT2) )
     => vtcheck(VC,vsubst(Vx,Ve,veabs),VT2) ) ).

fof('T-subst-abs-1',axiom,
    ! [VT,VC,Vx,Ve,Vy,VS,Ve1,VT2] :
      ( ( Vx = Vy
        & vtcheck(VC,Ve,VT)
        & vtcheck(vbind(Vx,VT,VC),vabs(Vy,VS,Ve1),VT2) )
     => vtcheck(VC,vsubst(Vx,Ve,vabs(Vy,VS,Ve1)),VT2) ) ).

fof('T-subst-abs-2',axiom,
    ! [VT,VC,Vx,Ve,Vy,VS,VT2] :
      ( ( Vx != Vy
        & ~ visFreeVar(Vy,Ve)
        & vtcheck(VC,Ve,VT)
        & vtcheck(vbind(Vx,VT,VC),vabs(Vy,VS,veabs),VT2) )
     => vtcheck(VC,vsubst(Vx,Ve,vabs(Vy,VS,veabs)),VT2) ) ).

fof('T-subst-abs-3',axiom,
    ! [VT,VC,Vx,Ve,Vy,VS,VT2] :
      ( ( Vx != Vy
        & visFreeVar(Vy,Ve)
        & vtcheck(VC,Ve,VT)
        & vtcheck(vbind(Vx,VT,VC),vabs(Vy,VS,veabs),VT2) )
     => vtcheck(VC,vsubst(Vx,Ve,vabs(Vy,VS,veabs)),VT2) ) ).

fof('T-subst-abs',conjecture,
    ! [VT,VC,Vx,Ve,Vy,VS,VT2] :
      ( ( vtcheck(VC,Ve,VT)
        & vtcheck(vbind(Vx,VT,VC),vabs(Vy,VS,veabs),VT2) )
     => vtcheck(VC,vsubst(Vx,Ve,vabs(Vy,VS,veabs)),VT2) ) ).

%------------------------------------------------------------------------------