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      :

%------------------------------------------------------------------------------
%----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 ) ) ) )).

%------------------------------------------------------------------------------
```