TPTP Problem File: COM132+2.p
View Solutions
- Solve Problem
%------------------------------------------------------------------------------
% File : COM132+2 : TPTP v8.2.0. Released v6.4.0.
% Domain : Computing Theory
% Problem : T-subst-abs-3 step in progress/preservation proof
% Version : 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-3 [Gre15]
% Status : Theorem
% Rating : 0.72 v8.2.0, 0.75 v8.1.0, 0.67 v7.5.0, 0.75 v7.4.0, 0.63 v7.3.0, 0.69 v7.1.0, 0.61 v7.0.0, 0.70 v6.4.0
% Syntax : Number of formulae : 53 ( 6 unt; 0 def)
% Number of atoms : 242 ( 171 equ)
% Maximal formula atoms : 33 ( 4 avg)
% Number of connectives : 221 ( 32 ~; 11 |; 100 &)
% ( 0 <=>; 78 =>; 0 <=; 0 <~>)
% Maximal formula depth : 23 ( 8 avg)
% Maximal term depth : 5 ( 1 avg)
% Number of predicates : 7 ( 5 usr; 1 prp; 0-3 aty)
% Number of functors : 13 ( 13 usr; 3 con; 0-3 aty)
% Number of variables : 275 ( 232 !; 43 ?)
% SPC : FOF_THM_RFO_SEQ
% Comments : Generated by Veritas: https://github.com/stg-tud/type-pragmatics
% : This is the original reduced version.
%------------------------------------------------------------------------------
fof('EQ-var',axiom,
! [VVar0,VVar1] :
( ( vvar(VVar0) = vvar(VVar1)
=> VVar0 = VVar1 )
& ( VVar0 = VVar1
=> vvar(VVar0) = vvar(VVar1) ) ) ).
fof('EQ-abs',axiom,
! [VVar0,VTyp0,VExp0,VVar1,VTyp1,VExp1] :
( ( vabs(VVar0,VTyp0,VExp0) = vabs(VVar1,VTyp1,VExp1)
=> ( VVar0 = VVar1
& VTyp0 = VTyp1
& VExp0 = VExp1 ) )
& ( ( VVar0 = VVar1
& VTyp0 = VTyp1
& VExp0 = VExp1 )
=> vabs(VVar0,VTyp0,VExp0) = vabs(VVar1,VTyp1,VExp1) ) ) ).
fof('EQ-app',axiom,
! [VExp0,VExp1,VExp2,VExp3] :
( ( vapp(VExp0,VExp1) = vapp(VExp2,VExp3)
=> ( VExp0 = VExp2
& VExp1 = VExp3 ) )
& ( ( VExp0 = VExp2
& VExp1 = VExp3 )
=> vapp(VExp0,VExp1) = vapp(VExp2,VExp3) ) ) ).
fof('DIFF-var-abs',axiom,
! [VVar0,VVar1,VTyp0,VExp0] : vvar(VVar0) != vabs(VVar1,VTyp0,VExp0) ).
fof('DIFF-var-app',axiom,
! [VVar0,VExp0,VExp1] : vvar(VVar0) != vapp(VExp0,VExp1) ).
fof('DIFF-abs-app',axiom,
! [VVar0,VTyp0,VExp0,VExp1,VExp2] : vabs(VVar0,VTyp0,VExp0) != vapp(VExp1,VExp2) ).
fof(isValue0,axiom,
! [Vx,VS,Ve,VExp0] :
( VExp0 = vabs(Vx,VS,Ve)
=> visValue(VExp0) ) ).
fof(isValue1,axiom,
! [Vx,VExp0] :
( VExp0 = vvar(Vx)
=> ~ visValue(VExp0) ) ).
fof(isValue2,axiom,
! [Ve1,Ve2,VExp0] :
( VExp0 = vapp(Ve1,Ve2)
=> ~ visValue(VExp0) ) ).
fof(isFreeVar0,axiom,
! [VVar0,VExp0,Vx,Vv] :
( ( VVar0 = Vv
& VExp0 = vvar(Vx) )
=> ( ( Vx = Vv
=> visFreeVar(VVar0,VExp0) )
& ( visFreeVar(VVar0,VExp0)
=> Vx = Vv ) ) ) ).
fof(isFreeVar1,axiom,
! [VT,VVar0,VExp0,Vx,Vv,Ve] :
( ( VVar0 = Vv
& VExp0 = vabs(Vx,VT,Ve) )
=> ( ( ( Vx != Vv
& visFreeVar(Vv,Ve) )
=> visFreeVar(VVar0,VExp0) )
& ( visFreeVar(VVar0,VExp0)
=> ( Vx != Vv
& visFreeVar(Vv,Ve) ) ) ) ) ).
fof(isFreeVar2,axiom,
! [VVar0,VExp0,Ve1,Vv,Ve2] :
( ( VVar0 = Vv
& VExp0 = vapp(Ve1,Ve2) )
=> ( ( ( visFreeVar(Vv,Ve1)
| visFreeVar(Vv,Ve2) )
=> visFreeVar(VVar0,VExp0) )
& ( visFreeVar(VVar0,VExp0)
=> ( visFreeVar(Vv,Ve1)
| visFreeVar(Vv,Ve2) ) ) ) ) ).
fof('EQ-empty',axiom,
( ( vempty = vempty
=> $true )
& ( $true
=> vempty = vempty ) ) ).
fof('EQ-bind',axiom,
! [VVar0,VTyp0,VCtx0,VVar1,VTyp1,VCtx1] :
( ( vbind(VVar0,VTyp0,VCtx0) = vbind(VVar1,VTyp1,VCtx1)
=> ( VVar0 = VVar1
& VTyp0 = VTyp1
& VCtx0 = VCtx1 ) )
& ( ( VVar0 = VVar1
& VTyp0 = VTyp1
& VCtx0 = VCtx1 )
=> vbind(VVar0,VTyp0,VCtx0) = vbind(VVar1,VTyp1,VCtx1) ) ) ).
fof('EQ-noType',axiom,
( ( vnoType = vnoType
=> $true )
& ( $true
=> vnoType = vnoType ) ) ).
fof('EQ-someType',axiom,
! [VTyp0,VTyp1] :
( ( vsomeType(VTyp0) = vsomeType(VTyp1)
=> VTyp0 = VTyp1 )
& ( VTyp0 = VTyp1
=> vsomeType(VTyp0) = vsomeType(VTyp1) ) ) ).
fof('DIFF-empty-bind',axiom,
! [VVar0,VTyp0,VCtx0] : vempty != vbind(VVar0,VTyp0,VCtx0) ).
fof('DIFF-noType-someType',axiom,
! [VTyp0] : vnoType != vsomeType(VTyp0) ).
fof(isSomeType0,axiom,
! [VOptTyp0] :
( VOptTyp0 = vnoType
=> ~ visSomeType(VOptTyp0) ) ).
fof(isSomeType1,axiom,
! [Ve,VOptTyp0] :
( VOptTyp0 = vsomeType(Ve)
=> visSomeType(VOptTyp0) ) ).
fof(getSomeType0,axiom,
! [VOptTyp0,RESULT,Ve] :
( VOptTyp0 = vsomeType(Ve)
=> ( RESULT = vgetSomeType(VOptTyp0)
=> RESULT = Ve ) ) ).
fof(lookup0,axiom,
! [Vx,VVar0,VCtx0,RESULT] :
( ( VVar0 = Vx
& VCtx0 = vempty )
=> ( RESULT = vlookup(VVar0,VCtx0)
=> RESULT = vnoType ) ) ).
fof(lookup1,axiom,
! [VC,Vx,Vy,VVar0,VCtx0,RESULT,VTy] :
( ( VVar0 = Vx
& VCtx0 = vbind(Vy,VTy,VC) )
=> ( Vx = Vy
=> ( RESULT = vlookup(VVar0,VCtx0)
=> RESULT = vsomeType(VTy) ) ) ) ).
fof(lookup2,axiom,
! [VTy,Vy,VVar0,VCtx0,RESULT,Vx,VC] :
( ( VVar0 = Vx
& VCtx0 = vbind(Vy,VTy,VC) )
=> ( Vx != Vy
=> ( RESULT = vlookup(VVar0,VCtx0)
=> RESULT = vlookup(Vx,VC) ) ) ) ).
fof('lookup-INV',axiom,
! [VVar0,VCtx0,RESULT] :
( vlookup(VVar0,VCtx0) = RESULT
=> ( ? [Vx] :
( VVar0 = Vx
& VCtx0 = vempty
& RESULT = vnoType )
| ? [VC,Vx,Vy,VTy] :
( VVar0 = Vx
& VCtx0 = vbind(Vy,VTy,VC)
& Vx = Vy
& RESULT = vsomeType(VTy) )
| ? [VTy,Vy,Vx,VC] :
( VVar0 = Vx
& VCtx0 = vbind(Vy,VTy,VC)
& Vx != Vy
& RESULT = vlookup(Vx,VC) ) ) ) ).
fof('T-Context-Duplicate',axiom,
! [Vy,VTy,Vx,VTx,VC,Ve,VT] :
( ( Vx = Vy
& vtcheck(vbind(Vx,VTx,vbind(Vy,VTy,VC)),Ve,VT) )
=> vtcheck(vbind(Vx,VTx,VC),Ve,VT) ) ).
fof('T-Context-Swap',axiom,
! [Vy,VTy,Vx,VTx,VC,Ve,VT] :
( ( Vx != Vy
& vtcheck(vbind(Vx,VTx,vbind(Vy,VTy,VC)),Ve,VT) )
=> vtcheck(vbind(Vy,VTy,vbind(Vx,VTx,VC)),Ve,VT) ) ).
fof('gensym-is-fresh',axiom,
! [Vv,Ve] :
( vgensym(Ve) = Vv
=> ~ visFreeVar(Vv,Ve) ) ).
fof(subst0,axiom,
! [Vx,Vy,VVar0,VExp0,VExp1,RESULT,Ve] :
( ( VVar0 = Vx
& VExp0 = Ve
& VExp1 = vvar(Vy) )
=> ( Vx = Vy
=> ( RESULT = vsubst(VVar0,VExp0,VExp1)
=> RESULT = Ve ) ) ) ).
fof(subst1,axiom,
! [Ve,Vx,VVar0,VExp0,VExp1,RESULT,Vy] :
( ( VVar0 = Vx
& VExp0 = Ve
& VExp1 = vvar(Vy) )
=> ( Vx != Vy
=> ( RESULT = vsubst(VVar0,VExp0,VExp1)
=> RESULT = vvar(Vy) ) ) ) ).
fof(subst2,axiom,
! [VVar0,VExp0,VExp1,RESULT,Ve1,Vx,Ve,Ve2] :
( ( VVar0 = Vx
& VExp0 = Ve
& VExp1 = vapp(Ve1,Ve2) )
=> ( RESULT = vsubst(VVar0,VExp0,VExp1)
=> RESULT = vapp(vsubst(Vx,Ve,Ve1),vsubst(Vx,Ve,Ve2)) ) ) ).
fof(subst3,axiom,
! [Ve,Vx,VVar0,VExp0,VExp1,RESULT,Vy,VT,Ve1] :
( ( VVar0 = Vx
& VExp0 = Ve
& VExp1 = vabs(Vy,VT,Ve1) )
=> ( Vx = Vy
=> ( RESULT = vsubst(VVar0,VExp0,VExp1)
=> RESULT = vabs(Vy,VT,Ve1) ) ) ) ).
fof(subst4,axiom,
! [VVar0,VExp0,VExp1,RESULT,Vx,Ve,VT,Vy,Vfresh,Ve1] :
( ( VVar0 = Vx
& VExp0 = Ve
& VExp1 = vabs(Vy,VT,Ve1) )
=> ( ( Vx != Vy
& visFreeVar(Vy,Ve)
& Vfresh = vgensym(vapp(vapp(Ve,Ve1),vvar(Vx))) )
=> ( RESULT = vsubst(VVar0,VExp0,VExp1)
=> RESULT = vsubst(Vx,Ve,vabs(Vfresh,VT,vsubst(Vy,vvar(Vfresh),Ve1))) ) ) ) ).
fof(subst5,axiom,
! [VVar0,VExp0,VExp1,RESULT,Vy,VT,Vx,Ve,Ve1] :
( ( VVar0 = Vx
& VExp0 = Ve
& VExp1 = vabs(Vy,VT,Ve1) )
=> ( ( Vx != Vy
& ~ visFreeVar(Vy,Ve) )
=> ( RESULT = vsubst(VVar0,VExp0,VExp1)
=> RESULT = vabs(Vy,VT,vsubst(Vx,Ve,Ve1)) ) ) ) ).
fof('subst-INV',axiom,
! [VVar0,VExp0,VExp1,RESULT] :
( vsubst(VVar0,VExp0,VExp1) = RESULT
=> ( ? [Vx,Vy,Ve] :
( VVar0 = Vx
& VExp0 = Ve
& VExp1 = vvar(Vy)
& Vx = Vy
& RESULT = Ve )
| ? [Ve,Vx,Vy] :
( VVar0 = Vx
& VExp0 = Ve
& VExp1 = vvar(Vy)
& Vx != Vy
& RESULT = vvar(Vy) )
| ? [Ve1,Vx,Ve,Ve2] :
( VVar0 = Vx
& VExp0 = Ve
& VExp1 = vapp(Ve1,Ve2)
& RESULT = vapp(vsubst(Vx,Ve,Ve1),vsubst(Vx,Ve,Ve2)) )
| ? [Ve,Vx,Vy,VT,Ve1] :
( VVar0 = Vx
& VExp0 = Ve
& VExp1 = vabs(Vy,VT,Ve1)
& Vx = Vy
& RESULT = vabs(Vy,VT,Ve1) )
| ? [Vx,Ve,VT,Vy,Vfresh,Ve1] :
( VVar0 = Vx
& VExp0 = Ve
& VExp1 = vabs(Vy,VT,Ve1)
& Vx != Vy
& visFreeVar(Vy,Ve)
& Vfresh = vgensym(vapp(vapp(Ve,Ve1),vvar(Vx)))
& RESULT = vsubst(Vx,Ve,vabs(Vfresh,VT,vsubst(Vy,vvar(Vfresh),Ve1))) )
| ? [Vy,VT,Vx,Ve,Ve1] :
( VVar0 = Vx
& VExp0 = Ve
& VExp1 = vabs(Vy,VT,Ve1)
& Vx != Vy
& ~ visFreeVar(Vy,Ve)
& RESULT = vabs(Vy,VT,vsubst(Vx,Ve,Ve1)) ) ) ) ).
fof('EQ-arrow',axiom,
! [VTyp0,VTyp1,VTyp2,VTyp3] :
( ( varrow(VTyp0,VTyp1) = varrow(VTyp2,VTyp3)
=> ( VTyp0 = VTyp2
& VTyp1 = VTyp3 ) )
& ( ( VTyp0 = VTyp2
& VTyp1 = VTyp3 )
=> varrow(VTyp0,VTyp1) = varrow(VTyp2,VTyp3) ) ) ).
fof('T-var',axiom,
! [VC,Vx,VT] :
( vlookup(Vx,VC) = vsomeType(VT)
=> vtcheck(VC,vvar(Vx),VT) ) ).
fof('T-abs',axiom,
! [VC,Vx,Ve,VS,VT] :
( vtcheck(vbind(Vx,VS,VC),Ve,VT)
=> vtcheck(VC,vabs(Vx,VS,Ve),varrow(VS,VT)) ) ).
fof('T-app',axiom,
! [VS,VC,Ve1,Ve2,VT] :
( ( vtcheck(VC,Ve1,varrow(VS,VT))
& vtcheck(VC,Ve2,VS) )
=> vtcheck(VC,vapp(Ve1,Ve2),VT) ) ).
fof('T-inv',axiom,
! [Ve,VT,VC] :
( vtcheck(VC,Ve,VT)
=> ( ? [Vx] :
( Ve = vvar(Vx)
& vlookup(Vx,VC) = vsomeType(VT) )
| ? [Vx,Ve2,VT1,VT2] :
( Ve = vabs(Vx,VT1,Ve2)
& VT = varrow(VT1,VT2)
& vtcheck(vbind(Vx,VT1,VC),Ve2,VT2) )
| ? [Ve1,Ve2,VS] :
( Ve = vapp(Ve1,Ve2)
& vtcheck(VC,Ve1,varrow(VS,VT))
& vtcheck(VC,Ve2,VS) ) ) ) ).
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('alpha-equiv-refl',axiom,
! [Ve] : valphaEquivalent(Ve,Ve) ).
fof('alpha-equiv-sym',axiom,
! [Ve2,Ve1] :
( valphaEquivalent(Ve1,Ve2)
=> valphaEquivalent(Ve2,Ve1) ) ).
fof('alpha-equiv-trans',axiom,
! [Ve2,Ve1,Ve3] :
( ( valphaEquivalent(Ve1,Ve2)
& valphaEquivalent(Ve2,Ve3) )
=> valphaEquivalent(Ve1,Ve3) ) ).
fof('alpha-equiv-subst-abs',axiom,
! [VS,Vx,Vy,Ve] :
( ~ visFreeVar(Vy,Ve)
=> valphaEquivalent(vabs(Vx,VS,Ve),vabs(Vy,VS,vsubst(Vx,vvar(Vy),Ve))) ) ).
fof('alpha-equiv-typing',axiom,
! [Ve,VC,Ve1,VT] :
( ( vtcheck(VC,Ve,VT)
& valphaEquivalent(Ve,Ve1) )
=> vtcheck(VC,Ve1,VT) ) ).
fof('alpha-equiv-FreeVar',axiom,
! [Ve,Vx,Ve1] :
( ( ~ visFreeVar(Vx,Ve)
& valphaEquivalent(Ve,Ve1) )
=> ~ visFreeVar(Vx,Ve1) ) ).
fof('T-subst-abs-2-gen',axiom,
! [VT,VC,Vx,Ve,Vy,VS,Ve1,VT2] :
( ( Vx != Vy
& ~ visFreeVar(Vy,Ve)
& 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('fresh-unequal-var-3',axiom,
! [Ve,Ve1,Vx,Vfresh] :
( Vfresh = vgensym(vapp(vapp(Ve,Ve1),vvar(Vx)))
=> Vx != Vfresh ) ).
fof('fresh-free-2',axiom,
! [Ve,Vx,Vfresh,Ve1] :
( Vfresh = vgensym(vapp(vapp(Ve,Ve1),vvar(Vx)))
=> ~ visFreeVar(Vfresh,Ve1) ) ).
fof('T-subst-abs-3',conjecture,
! [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) ) ).
%------------------------------------------------------------------------------