%--------------------------------------------------------------------------
% File     : SET005+0 : TPTP v7.2.0. Bugfixed v5.4.0.
% Domain   : Set Theory
% Axioms   : Set theory axioms based on NBG set theory
% Version  : [Quaife, 1992] axioms : Reduced & Augmented > Complete.
% English  :

% Refs     : [Qua92] Quaife (1992), Automated Deduction in von Neumann-Bern
%          : [BL+86] Boyer et al. (1986), Set Theory in First-Order Logic:
% Source   : [Qua92]
% Names    :

% Status   : Satisfiable
% Syntax   : Number of formulae    :   43 (  16 unit)
%            Number of atoms       :  100 (  19 equality)
%            Maximal formula depth :    7 (   4 average)
%            Number of connectives :   62 (   5   ~;   3   |;  26   &)
%                                         (  19 <=>;   9  =>;   0  <=;   0 <~>)
%                                         (   0  ~|;   0  ~&)
%            Number of predicates  :    6 (   0 propositional; 1-2 arity)
%            Number of functors    :   26 (   5 constant; 0-3 arity)
%            Number of variables   :   86 (   0 sgn;  81   !;   5   ?)
%            Maximal term depth    :    4 (   1 average)
% SPC      : 

% Comments :
% Bugfixes : v5.4.0 - Fixed compose_defn2, added first_second, added
%            identity_relation.
%--------------------------------------------------------------------------
%----Axiom A-1: Sets are classes (omitted because all objects are
%----classes).
% input_formula(sets_are_classes,axiom,
%     ! [X] :
%       (m(X) => cls(X))).

%----Definition of subclass. By doing this early, following axioms are
%----simplified. See A-2 for a clear example. This is what Mendelson does.
fof(subclass_defn,axiom,
    ( ! [X,Y] :
        ( subclass(X,Y)
      <=> ! [U] :
            ( member(U,X)
           => member(U,Y) ) ) )).

%----Axiom A-2: Elements of classes are sets.
fof(class_elements_are_sets,axiom,
    ( ! [X] : subclass(X,universal_class) )).

%----Axiom A-3: Principle of extensionality. Quaife notes that this is
%----different from the Boyer version. It is the Mendelson version.
fof(extensionality,axiom,
    ( ! [X,Y] :
        ( X = Y
      <=> ( subclass(X,Y)
          & subclass(Y,X) ) ) )).

%----Axiom A-4: Existence of unordered pair
fof(unordered_pair_defn,axiom,
    ( ! [U,X,Y] :
        ( member(U,unordered_pair(X,Y))
      <=> ( member(U,universal_class)
          & ( U = X
            | U = Y ) ) ) )).

%----Quaife says "if I were to do it again I'd use ..."
%----McCune recommends not doing this, so I havn't
% input_formula(unordered_pair1,axiom,(
%     ! [U,X,Y] :
%       ( member(U,unordered_pair(X,Y))
%     <=> ( member(U,universal_class)
%         & ( equal(U,X)
%           | member(U,Y) ) ) )    )).

fof(unordered_pair,axiom,
    ( ! [X,Y] : member(unordered_pair(X,Y),universal_class) )).

%----Definition of singleton set, needed for ordered pair.
fof(singleton_set_defn,axiom,
    ( ! [X] : singleton(X) = unordered_pair(X,X) )).

%----Definition of ordered pair, needed for B-5
fof(ordered_pair_defn,axiom,
    ( ! [X,Y] : ordered_pair(X,Y) = unordered_pair(singleton(X),unordered_pair(X,singleton(Y))) )).

%----This is different from Goedel where it is
% input_formula(ordered_pair,axiom,(
%     ! [X,Y] : equal(ordered_pair(X,Y),unordered_pair(singleton(X),
% unordered_pair(X,Y)))   )).
%----This is motivated in Quaife's book p. 30 Section 3.5.

%----Axiom B-5: Cartesian product (not explicitly defined in Goedel)
%----Brought forward so cross_product can be used in B-1
%----In this and some other axioms, Goedel's axioms use existential
%----quantification rather than explicit definition.
fof(cross_product_defn,axiom,
    ( ! [U,V,X,Y] :
        ( member(ordered_pair(U,V),cross_product(X,Y))
      <=> ( member(U,X)
          & member(V,Y) ) ) )).

%----Added axiom to define first and second, which are introduced as Skolem
%----functions in the CNF versions of theorem OP6.
fof(first_second,axiom,
    ! [X,Y] :
      ( ( member(X,universal_class)
        & member(Y,universal_class) )
     => ( first(ordered_pair(X,Y)) = X
        & second(ordered_pair(X,Y)) = Y ) ) ).

fof(cross_product,axiom,
    ( ! [X,Y,Z] :
        ( member(Z,cross_product(X,Y))
       => Z = ordered_pair(first(Z),second(Z)) ) )).

%----Axiom B-1: Element relation (not explicitly defined in Goedel)
%----This is an example of undoing a simplification made by Quaife for
%----CNF systems (see book p. 28, Section 3.4).
fof(element_relation_defn,axiom,
    ( ! [X,Y] :
        ( member(ordered_pair(X,Y),element_relation)
      <=> ( member(Y,universal_class)
          & member(X,Y) ) ) )).

%----Quaife's version included member(X,universal_class) in the RHS of the
%----<=>, but that's not required as member(X,Y) => member(X,universal_class)
%----The equiavlence of the two forms has been proved.

fof(element_relation,axiom,
    ( subclass(element_relation,cross_product(universal_class,universal_class)) )).

%----Axiom B-2: Intersection (not explicitly defined in Goedel)
fof(intersection,axiom,
    ( ! [X,Y,Z] :
        ( member(Z,intersection(X,Y))
      <=> ( member(Z,X)
          & member(Z,Y) ) ) )).

%----Axiom B-3: Complement (not explicitly defined in Goedel)
fof(complement,axiom,
    ( ! [X,Z] :
        ( member(Z,complement(X))
      <=> ( member(Z,universal_class)
          & ~ member(Z,X) ) ) )).

%----Quaife has the definitions for union and symmetric difference in here
%----(about). I have moved union to later where it is needed. Symmetric
%----difference is not needed for Goedel's axioms, so I have moved it to
%----SET005+1.ax

%----Definition of restrict. Needed for B-4 domain_of
fof(restrict_defn,axiom,
    ( ! [X,XR,Y] : restrict(XR,X,Y) = intersection(XR,cross_product(X,Y)) )).

%----Definition of null_class. Needed for B-4 domain_of
%----This is dependent, but Plaisted says it's unreasonable to omit it.
fof(null_class_defn,axiom,
    ( ! [X] : ~ member(X,null_class) )).

%----Axiom B-4: Domain of (not explicitly defined in Goedel)
fof(domain_of,axiom,
    ( ! [X,Z] :
        ( member(Z,domain_of(X))
      <=> ( member(Z,universal_class)
          & restrict(X,singleton(Z),universal_class) != null_class ) ) )).

%----Axiom B-5 is earlier as it defines cross_product, used in B-1
%----Axiom B-6 is proved as a theorem

%----Axiom B-7: Existence of rotate (not explicitly defined in Goedel)
fof(rotate_defn,axiom,
    ( ! [X,U,V,W] :
        ( member(ordered_pair(ordered_pair(U,V),W),rotate(X))
      <=> ( member(ordered_pair(ordered_pair(U,V),W),cross_product(cross_product(universal_class,universal_class),universal_class))
          & member(ordered_pair(ordered_pair(V,W),U),X) ) ) )).

fof(rotate,axiom,
    ( ! [X] : subclass(rotate(X),cross_product(cross_product(universal_class,universal_class),universal_class)) )).

%----Axiom B-8: Existence of flip (not explicitly defined in Goedel)
fof(flip_defn,axiom,
    ( ! [U,V,W,X] :
        ( member(ordered_pair(ordered_pair(U,V),W),flip(X))
      <=> ( member(ordered_pair(ordered_pair(U,V),W),cross_product(cross_product(universal_class,universal_class),universal_class))
          & member(ordered_pair(ordered_pair(V,U),W),X) ) ) )).

fof(flip,axiom,
    ( ! [X] : subclass(flip(X),cross_product(cross_product(universal_class,universal_class),universal_class)) )).

%----I have removed the definitions of range and domain to SET005+1
%----as they are not needed for Goedel's axioms.

%----Plaisted's definition of union. Needed for successor
fof(union_defn,axiom,
    ( ! [X,Y,Z] :
        ( member(Z,union(X,Y))
      <=> ( member(Z,X)
          | member(Z,Y) ) ) )).

%----This is Quaife's original definition of union, which David Plaisted
%----suggested is unnatural ...
% input_formula(union_defn_quaife,axiom,(
%     ! [X,Y] : equal(union(X,Y),complement(intersection(complement(X),
% complement(Y))))   )).
%----Quaife's definition can be shown equivalent Plaisted's by showing each is
%----equivalent to this one ...
% input_formula(union_defn_geoff,axiom,(
%     ! [X,Y,Z] :
%       ( member(Z,union(X,Y))
%     <=> member(Z,complement(intersection(complement(X),complement(Y)))))   )).
%----as an intermediate

%----Definition of successor. Needed for successor_relation
fof(successor_defn,axiom,
    ( ! [X] : successor(X) = union(X,singleton(X)) )).

%----Definition of successor_relation. Needed for inductive.
fof(successor_relation_defn1,axiom,
    ( subclass(successor_relation,cross_product(universal_class,universal_class)) )).

%----This undoes the Quaife simplification from book p.28 Section 3.4
fof(successor_relation_defn2,axiom,
    ( ! [X,Y] :
        ( member(ordered_pair(X,Y),successor_relation)
      <=> ( member(X,universal_class)
          & member(Y,universal_class)
          & successor(X) = Y ) ) )).

%----Definition of inverse (not explicitly defined in Goedel)
%----Needed for range_of
fof(inverse_defn,axiom,
    ( ! [Y] : inverse(Y) = domain_of(flip(cross_product(Y,universal_class))) )).

%----Definition of range_of. Needed for image.
fof(range_of_defn,axiom,
    ( ! [Z] : range_of(Z) = domain_of(inverse(Z)) )).

%----Definition of image. Needed for inductive.
fof(image_defn,axiom,
    ( ! [X,XR] : image(XR,X) = range_of(restrict(XR,X,universal_class)) )).

%----Definition of inductive. Needed for C-1: Infinity
fof(inductive_defn,axiom,
    ( ! [X] :
        ( inductive(X)
      <=> ( member(null_class,X)
          & subclass(image(successor_relation,X),X) ) ) )).

%----Axiom C-1: Infinity
fof(infinity,axiom,
    ( ? [X] :
        ( member(X,universal_class)
        & inductive(X)
        & ! [Y] :
            ( inductive(Y)
           => subclass(X,Y) ) ) )).

%----Axiom C-2: Sum_class (not explicitly defined in Goedel)
fof(sum_class_defn,axiom,
    ( ! [U,X] :
        ( member(U,sum_class(X))
      <=> ? [Y] :
            ( member(U,Y)
            & member(Y,X) ) ) )).

%----Here is Quaife's original definition of sum_class, which David Plaisted
%----suggested is unnatural ...
%input_formula(sum_class_defn,axiom,(
%    ! [X] : equal(sum_class(X),domain_of(restrict(element_relation,
%universal_class,X)))   )).
%----Yunshan Zhu's sum class definition above has been shown equivalent to
%----the original by a longish sequence of equivalences. Boyer et al. also
%----use (a more complicated version of) the above definition.

fof(sum_class,axiom,
    ( ! [X] :
        ( member(X,universal_class)
       => member(sum_class(X),universal_class) ) )).

%----Axiom C-3: Existence of power_class (not explicitly defined in Goedel)
fof(power_class_defn,axiom,
    ( ! [U,X] :
        ( member(U,power_class(X))
      <=> ( member(U,universal_class)
          & subclass(U,X) ) ) )).

%----Here is Quaife's original definition of power_class, which David Plaisted
%----suggested is unnatural ...
%input_formula(power_class_defn,axiom,(
%    ! [X] : equal(power_class(X),complement(image(element_relation,
%complement(X))))   )).

fof(power_class,axiom,
    ( ! [U] :
        ( member(U,universal_class)
       => member(power_class(U),universal_class) ) )).

%----Definition of compose. Needed for function
fof(compose_defn1,axiom,
    ( ! [XR,YR] : subclass(compose(YR,XR),cross_product(universal_class,universal_class)) )).

%----This undoes the Quaife simplification from book p.28 Section 3.4, and
%----then simplifies that by removing a member(V,universal_class) from the RHS
fof(compose_defn2,axiom,
    ( ! [XR,YR,U,V] :
        ( member(ordered_pair(U,V),compose(YR,XR))
      <=> ( member(U,universal_class)
          & member(V,image(YR,image(XR,singleton(U)))) ) ) )).

%----Definition of single_valued_class. Needed for function
%----Quaife suggests not using this, in his book p.35
%input_formula(single_valued_class_defn,axiom,(
%    ! [X] :
%      ( single_valued_class(X)
%    <=> subclass(compose(X,inverse(X)),identity_relation) )   )).

%----Added definition of identity_relation (missing from Quaife)
fof(identity_relation,axiom,
    ! [Z] :
      ( member(Z,identity_relation)
    <=> ? [X] :
          ( member(X,universal_class)
          & Z = ordered_pair(X,X) ) ) ).

%----Definition of function. Needed for C-4: replacement
fof(function_defn,axiom,
    ( ! [XF] :
        ( function(XF)
      <=> ( subclass(XF,cross_product(universal_class,universal_class))
          & subclass(compose(XF,inverse(XF)),identity_relation) ) ) )).

%----Axiom C-4: Replacement
fof(replacement,axiom,
    ( ! [X,XF] :
        ( ( member(X,universal_class)
          & function(XF) )
       => member(image(XF,X),universal_class) ) )).

%----Definition of disjoint. This is omitted by Quaife
fof(disjoint_defn,axiom,
    ( ! [X,Y] :
        ( disjoint(X,Y)
      <=> ! [U] : ~ ( member(U,X)
            & member(U,Y) ) ) )).

%----Axiom D: Regularity
%----This also provides a definition of the null_class of the form
%----! [X] : ( equal(X,null_class) <= ! [U] : ~ member(U,X) )
fof(regularity,axiom,
    ( ! [X] :
        ( X != null_class
       => ? [U] :
            ( member(U,universal_class)
            & member(U,X)
            & disjoint(U,X) ) ) )).

%----Definition of apply. Needed for universal choice
fof(apply_defn,axiom,
    ( ! [XF,Y] : apply(XF,Y) = sum_class(image(XF,singleton(Y))) )).

%----Axiom E: Universal choice
fof(choice,axiom,
    ( ? [XF] :
        ( function(XF)
        & ! [Y] :
            ( member(Y,universal_class)
           => ( Y = null_class
              | member(apply(XF,Y),Y) ) ) ) )).

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