TPTP Axioms File: SET009^0.ax


%------------------------------------------------------------------------------
% File     : SET009^0 : TPTP v7.5.0. Released v3.6.0.
% Domain   : Set Theory
% Axioms   : Binary relations
% Version  : [Nei08] axioms.
% English  : Lots of stuff about binary relations. A binary relation is just
%            anything of type $i > $i > $o. Many properties and some proofs
%            can be found in chapter 2 of [BN99].

% Refs     : [BN99]  Baader & Nipkow (1999), Term Rewriting and All That
%          : [Nei08] Neis (2008), Email to Geoff Sutcliffe
% Source   : [Nei08]
% Names    : rel.ax [Nei08]

% Status   : Satisfiable
% Syntax   : Number of formulae    :   58 (   0 unit;  29 type;  29 defn)
%            Number of atoms       :  561 (  33 equality; 158 variable)
%            Maximal formula depth :   12 (   7 average)
%            Number of connectives :  158 (   4   ~;   4   |;  12   &; 122   @)
%                                         (   0 <=>;  16  =>;   0  <=;   0 <~>)
%                                         (   0  ~|;   0  ~&;   0  !!;   0  ??)
%            Number of type conns  :  197 ( 197   >;   0   *;   0   +)
%            Number of symbols     :   31 (  29   :;   0  :=)
%            Number of variables   :   86 (   0 sgn;  38   !;   5   ?;  43   ^)
%                                         (  86   :;   0  :=;   0  !>;   0  ?*)
% SPC      : 

% Comments :
%------------------------------------------------------------------------------
%----BASICS
%----Subrelation
thf(subrel_type,type,(
    subrel: ( $i > $i > $o ) > ( $i > $i > $o ) > $o )).

thf(subrel,definition,
    ( subrel
    = ( ^ [R: $i > $i > $o,S: $i > $i > $o] :
        ! [X: $i,Y: $i] :
          ( ( R @ X @ Y )
         => ( S @ X @ Y ) ) ) )).

%----Inverse
thf(inv_type,type,(
    inv: ( $i > $i > $o ) > $i > $i > $o )).

thf(inverse,definition,
    ( inv
    = ( ^ [R: $i > $i > $o,X: $i,Y: $i] :
          ( R @ Y @ X ) ) )).

%----IDEMPOTENCY, INFLATION, MONOTONICITY
%----Idempotency
thf(idem_type,type,(
    idem: ( ( $i > $i > $o ) > $i > $i > $o ) > $o )).

thf(idempotent,definition,
    ( idem
    = ( ^ [F: ( $i > $i > $o ) > $i > $i > $o] :
        ! [R: $i > $i > $o] :
          ( ( F @ ( F @ R ) )
          = ( F @ R ) ) ) )).

%----Being inflationary
thf(infl_type,type,(
    infl: ( ( $i > $i > $o ) > $i > $i > $o ) > $o )).

thf(inflationary,definition,
    ( infl
    = ( ^ [F: ( $i > $i > $o ) > $i > $i > $o] :
        ! [R: $i > $i > $o] :
          ( subrel @ R @ ( F @ R ) ) ) )).

%----Monotonicity
thf(mono_type,type,(
    mono: ( ( $i > $i > $o ) > $i > $i > $o ) > $o )).

thf(monotonic,definition,
    ( mono
    = ( ^ [F: ( $i > $i > $o ) > $i > $i > $o] :
        ! [R: $i > $i > $o,S: $i > $i > $o] :
          ( ( subrel @ R @ S )
         => ( subrel @ ( F @ R ) @ ( F @ S ) ) ) ) )).

%----REFLEXIVITY, IRREFLEXIVITY, AND REFLEXIVE CLOSURE
%----Reflexivity
thf(refl_type,type,(
    refl: ( $i > $i > $o ) > $o )).

thf(reflexive,definition,
    ( refl
    = ( ^ [R: $i > $i > $o] :
        ! [X: $i] :
          ( R @ X @ X ) ) )).

%----Irreflexivity
thf(irrefl_type,type,(
    irrefl: ( $i > $i > $o ) > $o )).

thf(irreflexive,definition,
    ( irrefl
    = ( ^ [R: $i > $i > $o] :
        ! [X: $i] :
          ~ ( R @ X @ X ) ) )).

%----Reflexive closure
thf(rc_type,type,(
    rc: ( $i > $i > $o ) > $i > $i > $o )).

thf(reflexive_closure,definition,
    ( rc
    = ( ^ [R: $i > $i > $o,X: $i,Y: $i] :
          ( ( X = Y )
          | ( R @ X @ Y ) ) ) )).

%----SYMMETRY, ANTISYMMETRY, ASYMMETRY, AND SYMMETRIC CLOSURE
%----Symmetry
thf(symm_type,type,(
    symm: ( $i > $i > $o ) > $o )).

thf(symmetric,definition,
    ( symm
    = ( ^ [R: $i > $i > $o] :
        ! [X: $i,Y: $i] :
          ( ( R @ X @ Y )
         => ( R @ Y @ X ) ) ) )).

%----Antisymmetry
thf(antisymm_type,type,(
    antisymm: ( $i > $i > $o ) > $o )).

thf(antisymmetric,definition,
    ( antisymm
    = ( ^ [R: $i > $i > $o] :
        ! [X: $i,Y: $i] :
          ( ( ( R @ X @ Y )
            & ( R @ Y @ X ) )
         => ( X = Y ) ) ) )).

%----Asymmetry
thf(asymm_type,type,(
    asymm: ( $i > $i > $o ) > $o )).

thf(asymmetric,definition,
    ( asymm
    = ( ^ [R: $i > $i > $o] :
        ! [X: $i,Y: $i] :
          ( ( R @ X @ Y )
         => ~ ( R @ Y @ X ) ) ) )).

%----Symmetric closure
thf(sc_type,type,(
    sc: ( $i > $i > $o ) > $i > $i > $o )).

thf(symmetric_closure,definition,
    ( sc
    = ( ^ [R: $i > $i > $o,X: $i,Y: $i] :
          ( ( R @ Y @ X )
          | ( R @ X @ Y ) ) ) )).

%----TRANSITIVITY AND TRANSITIVE CLOSURE
%----Transitivity
thf(trans_type,type,(
    trans: ( $i > $i > $o ) > $o )).

thf(transitive,definition,
    ( trans
    = ( ^ [R: $i > $i > $o] :
        ! [X: $i,Y: $i,Z: $i] :
          ( ( ( R @ X @ Y )
            & ( R @ Y @ Z ) )
         => ( R @ X @ Z ) ) ) )).

%----Transitive closure
thf(tc_type,type,(
    tc: ( $i > $i > $o ) > $i > $i > $o )).

% the transitive closure of R is the smallest transitive
% relation containing R (thanks, Chad!)
thf(transitive_closure,definition,
    ( tc
    = ( ^ [R: $i > $i > $o,X: $i,Y: $i] :
        ! [S: $i > $i > $o] :
          ( ( ( trans @ S )
            & ( subrel @ R @ S ) )
         => ( S @ X @ Y ) ) ) )).

%----TRANSITIVE REFLEXIVE CLOSURE AND TRANSITIVE REFLEXIVE SYMMETRIC CLOSURE
%----Transitive reflexive closure
thf(trc_type,type,(
    trc: ( $i > $i > $o ) > $i > $i > $o )).

thf(transitive_reflexive_closure,definition,
    ( trc
    = ( ^ [R: $i > $i > $o] :
          ( rc @ ( tc @ R ) ) ) )).

%----Transitive reflexive symmetric closure
thf(trsc_type,type,(
    trsc: ( $i > $i > $o ) > $i > $i > $o )).

thf(transitive_reflexive_symmetric_closure,definition,
    ( trsc
    = ( ^ [R: $i > $i > $o] :
          ( sc @ ( rc @ ( tc @ R ) ) ) ) )).

%----ORDERS
%----Being a partial order
thf(po_type,type,(
    po: ( $i > $i > $o ) > $o )).

thf(partial_order,definition,
    ( po
    = ( ^ [R: $i > $i > $o] :
          ( ( refl @ R )
          & ( antisymm @ R )
          & ( trans @ R ) ) ) )).

%----Being a strict (partial) order
thf(so_type,type,(
    so: ( $i > $i > $o ) > $o )).

thf(strict_order,definition,
    ( so
    = ( ^ [R: $i > $i > $o] :
          ( ( asymm @ R )
          & ( trans @ R ) ) ) )).

%----Totality
thf(total_type,type,(
    total: ( $i > $i > $o ) > $o )).

thf(total,definition,
    ( total
    = ( ^ [R: $i > $i > $o] :
        ! [X: $i,Y: $i] :
          ( ( X = Y )
          | ( R @ X @ Y )
          | ( R @ Y @ X ) ) ) )).

%----TERMINATION AND INDUCTION
%----Termination
thf(term_type,type,(
    term: ( $i > $i > $o ) > $o )).

% axiomatisation: any non-empty subset has an R-maximal element
thf(terminating,definition,
    ( term
    = ( ^ [R: $i > $i > $o] :
        ! [A: $i > $o] :
          ( ? [X: $i] :
              ( A @ X )
         => ? [X: $i] :
              ( ( A @ X )
              & ! [Y: $i] :
                  ( ( A @ Y )
                 => ~ ( R @ X @ Y ) ) ) ) ) )).

%----Satisfying the induction principle
thf(ind_type,type,(
    ind: ( $i > $i > $o ) > $o )).

thf(satisfying_the_induction_principle,definition,
    ( ind
    = ( ^ [R: $i > $i > $o] :
        ! [P: $i > $o] :
          ( ! [X: $i] :
              ( ! [Y: $i] :
                  ( ( tc @ R @ X @ Y )
                 => ( P @ Y ) )
             => ( P @ X ) )
         => ! [X: $i] :
              ( P @ X ) ) ) )).

%----NORMALIZATION
%----In normal form
thf(innf_type,type,(
    innf: ( $i > $i > $o ) > $i > $o )).

thf(in_normal_form,definition,
    ( innf
    = ( ^ [R: $i > $i > $o,X: $i] :
          ~ ( ? [Y: $i] :
                ( R @ X @ Y ) ) ) )).

%----Normal form of
thf(nfof_type,type,(
    nfof: ( $i > $i > $o ) > $i > $i > $o )).

thf(normal_form_of,definition,
    ( nfof
    = ( ^ [R: $i > $i > $o,X: $i,Y: $i] :
          ( ( trc @ R @ Y @ X )
          & ( innf @ R @ X ) ) ) )).

%----Normalization
thf(norm_type,type,(
    norm: ( $i > $i > $o ) > $o )).

thf(normalizing,definition,
    ( norm
    = ( ^ [R: $i > $i > $o] :
        ! [X: $i] :
        ? [Y: $i] :
          ( nfof @ R @ Y @ X ) ) )).

%----CONFLUENCE AND FRIENDS
%----Joinability
thf(join_type,type,(
    join: ( $i > $i > $o ) > $i > $i > $o )).

thf(joinable,definition,
    ( join
    = ( ^ [R: $i > $i > $o,X: $i,Y: $i] :
        ? [Z: $i] :
          ( ( trc @ R @ X @ Z )
          & ( trc @ R @ Y @ Z ) ) ) )).

%----Local confluence
thf(lconfl_type,type,(
    lconfl: ( $i > $i > $o ) > $o )).

thf(locally_confluent,definition,
    ( lconfl
    = ( ^ [R: $i > $i > $o] :
        ! [X: $i,Y: $i,Z: $i] :
          ( ( ( R @ X @ Z )
            & ( R @ X @ Y ) )
         => ( join @ R @ Z @ Y ) ) ) )).

%----Semi confluence
thf(sconfl_type,type,(
    sconfl: ( $i > $i > $o ) > $o )).

thf(semi_confluent,definition,
    ( sconfl
    = ( ^ [R: $i > $i > $o] :
        ! [X: $i,Y: $i,Z: $i] :
          ( ( ( R @ X @ Z )
            & ( trc @ R @ X @ Y ) )
         => ( join @ R @ Z @ Y ) ) ) )).

%----Confluence
thf(confl_type,type,(
    confl: ( $i > $i > $o ) > $o )).

thf(confluent,definition,
    ( confl
    = ( ^ [R: $i > $i > $o] :
        ! [X: $i,Y: $i,Z: $i] :
          ( ( ( trc @ R @ X @ Z )
            & ( trc @ R @ X @ Y ) )
         => ( join @ R @ Z @ Y ) ) ) )).

%----Church-Rosser property
thf(cr_type,type,(
    cr: ( $i > $i > $o ) > $o )).

thf(church_rosser,definition,
    ( cr
    = ( ^ [R: $i > $i > $o] :
        ! [X: $i,Y: $i] :
          ( ( trsc @ R @ X @ Y )
         => ( join @ R @ X @ Y ) ) ) )).

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