## TPTP Axioms File: SET009^0.ax

```%------------------------------------------------------------------------------
% File     : SET009^0 : TPTP v8.1.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 (  29 unt;  29 typ;  29 def)
%            Number of atoms       :   91 (  33 equ;   0 cnn)
%            Maximal formula atoms :    1 (   1 avg)
%            Number of connectives :  158 (   4   ~;   4   |;  12   &; 122   @)
%                                         (   0 <=>;  16  =>;   0  <=;   0 <~>)
%            Maximal formula depth :    1 (   1 avg; 122 nst)
%            Number of types       :    2 (   0 usr)
%            Number of type conns  :  197 ( 197   >;   0   *;   0   +;   0  <<)
%            Number of symbols     :   30 (  29 usr;   0 con; 1-3 aty)
%            Number of variables   :   86 (  43   ^  38   !;   5   ?;  86   :)
% 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 ) ) ) ) ).

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