:: Subcategories and Products of Categories
::  by Czes{\l}aw Byli\'nski
::
:: Received May 31, 1990
:: Copyright (c) 1990-2016 Association of Mizar Users
::           (Stowarzyszenie Uzytkownikow Mizara, Bialystok, Poland).
:: This code can be distributed under the GNU General Public Licence
:: version 3.0 or later, or the Creative Commons Attribution-ShareAlike
:: License version 3.0 or later, subject to the binding interpretation
:: detailed in file COPYING.interpretation.
:: See COPYING.GPL and COPYING.CC-BY-SA for the full text of these
:: licenses, or see http://www.gnu.org/licenses/gpl.html and
:: http://creativecommons.org/licenses/by-sa/3.0/.

environ

 vocabularies XBOOLE_0, SUBSET_1, FUNCT_2, FUNCT_1, ZFMISC_1, FUNCT_5, RELAT_1,
      TARSKI, CAT_1, FUNCOP_1, STRUCT_0, GRAPH_1, FUNCT_3, REALSET1, PARTFUN1,
      FUNCT_4, MCART_1, CAT_2, MONOID_0, RELAT_2, BINOP_1;
 notations TARSKI, XBOOLE_0, ZFMISC_1, SUBSET_1, DOMAIN_1, RELAT_1, FUNCT_1,
      FUNCT_2, BINOP_1, PARTFUN1, FUNCT_3, FUNCT_4, FUNCT_5, REALSET1,
      FUNCOP_1, STRUCT_0, GRAPH_1, CAT_1;
 constructors PARTFUN1, BINOP_1, FUNCT_3, FUNCT_4, FUNCT_5, REALSET1, CAT_1,
      FUNCOP_1, RELSET_1;
 registrations XBOOLE_0, SUBSET_1, RELSET_1, REALSET1, CAT_1, STRUCT_0,
      RELAT_1, XTUPLE_0;
 requirements SUBSET, BOOLE;
 definitions TARSKI, CAT_1;
 equalities CAT_1, REALSET1, FUNCOP_1, BINOP_1, GRAPH_1;
 expansions CAT_1;
 theorems TARSKI, ZFMISC_1, MCART_1, DOMAIN_1, FUNCT_1, FUNCT_2, FUNCT_3,
      FUNCT_4, FUNCT_5, PARTFUN1, FUNCOP_1, CAT_1, GRFUNC_1, RELAT_1, RELSET_1,
      XBOOLE_0, XBOOLE_1, XTUPLE_0;
 schemes XBOOLE_0, BINOP_1;

begin

::$CT 4

reserve B,C,D,C9,D9 for Category;

:: Auxiliary theorems on Functors

definition
  let B,C;
  let c be Object of C;
  func B --> c -> Functor of B,C equals
  (the carrier' of B) --> (id c);
  coherence
  proof
    reconsider T = (the carrier' of B) --> id c as Function of the carrier' of
    B,the carrier' of C;
    now
      thus for b being Object of B ex d being Object of C st T.(id b) = id d
      by FUNCOP_1:7;
      thus for f being Morphism of B holds T.(id dom f) = id dom (T.f) & T.(id
      cod f) = id cod (T.f)
      proof
        let f be Morphism of B;
        T.(id cod f) = id c by FUNCOP_1:7;
        then
A1:     T.(id cod f) = id cod id c;
        T.(id dom f) = id c by FUNCOP_1:7;
        then T.(id dom f) = id dom id c;
        hence thesis by A1,FUNCOP_1:7;
      end;
      let f,g be Morphism of B such that
      dom g = cod f;
      Hom(c,c) <> {};
      then
A2:   T.f = id c & (id c)*(id c) = (id c)(*)((id c)) by CAT_1:def 13,FUNCOP_1:7
;
      T.(g(*)f) = id c & T.g = id c by FUNCOP_1:7;
      hence T.(g(*)f) = (T.g)(*)(T.f) by A2;
    end;
    hence thesis by CAT_1:61;
  end;
end;

theorem
  for c being Object of C, b being Object of B holds (Obj (B --> c)).b = c
proof
  let c be Object of C, b be Object of B;
  (B --> c).(id b) = id c by FUNCOP_1:7;
  hence thesis by CAT_1:67;
end;

definition
  let C,D;
  func Funct(C,D) -> set means
  :Def2:
  for x being set holds x in it iff x is Functor of C,D;
  existence
  proof
    defpred P[object] means $1 is Functor of C,D;
    consider F being set such that
A1: for x being object holds x in F iff x in Funcs(the carrier' of C,the
    carrier' of D) & P[x] from XBOOLE_0:sch 1;
    take F;
    let x be set;
    thus x in F implies x is Functor of C,D by A1;
    assume
A2: x is Functor of C,D;
    then x in Funcs(the carrier' of C,the carrier' of D) by FUNCT_2:8;
    hence thesis by A1,A2;
  end;
  uniqueness
  proof
    let F1,F2 be set such that
A3: for x being set holds x in F1 iff x is Functor of C,D and
A4: for x being set holds x in F2 iff x is Functor of C,D;
    now
      let x be object;
      x in F1 iff x is Functor of C,D by A3;
      hence x in F1 iff x in F2 by A4;
    end;
    hence thesis by TARSKI:2;
  end;
end;

registration
  let C,D;
  cluster Funct(C,D) -> non empty;
  coherence
  proof
    set x = the Functor of C,D;
    x in Funct(C,D) by Def2;
    hence thesis;
  end;
end;

definition
  let C,D;
  mode FUNCTOR-DOMAIN of C,D -> non empty set means
    :Def3:
    for x being Element of it holds x is Functor of C,D;
  existence
  proof
    take Funct(C,D);
    thus thesis by Def2;
  end;
end;

definition
  let C,D;
  let F be FUNCTOR-DOMAIN of C,D;
  redefine mode Element of F -> Functor of C,D;
  coherence by Def3;
end;

definition
  let A be non empty set;
  let C,D;
  let F be FUNCTOR-DOMAIN of C,D, T be Function of A,F, x be Element of A;
  redefine func T.x -> Element of F;
  coherence
  proof
    thus T.x is Element of F;
  end;
end;

definition
  let C,D;
  redefine func Funct(C,D) -> FUNCTOR-DOMAIN of C,D;
  coherence
  proof
    let x be Element of Funct(C,D);
    thus thesis by Def2;
  end;
end;

::   Subcategory

definition
  let C;
  mode Subcategory of C -> Category means
    :Def4:
    the carrier of it c= the carrier of C &
     (for a,b being Object of it, a9,b9 being Object of C
        st a = a9 & b = b9
    holds Hom(a,b) c= Hom(a9,b9)) & the Comp of it c= the Comp of C &
    for a being Object of it, a9 being Object of C st a = a9
      holds id a = id a9;
  existence
  proof
    take C;
    thus thesis;
  end;
end;

registration
  let C;
  cluster strict for Subcategory of C;
  existence
  proof
    set c = the Object of C;
    set E = 1Cat(c,id c);
    now
      thus the carrier of E c= the carrier of C
      proof
        let a be object;
        assume a in the carrier of E;
        then a = c by TARSKI:def 1;
        hence thesis;
      end;
      thus for a,b being Object of E, a9,b9 being Object of C st a = a9 & b =
      b9 holds Hom(a,b) c= Hom(a9,b9)
      proof
        let a,b be Object of E, a9,b9 be Object of C;
        assume a = a9 & b = b9;
        then
A1:     a9 = c & b9 = c by TARSKI:def 1;
        let x be object;
        assume x in Hom(a,b);
        then x = id c by TARSKI:def 1;
        hence thesis by A1,CAT_1:27;
      end;
      thus the Comp of E c= the Comp of C
      proof
        reconsider i = id c as Morphism of C;
A2:     Hom(c,c) <> {};
A3:     dom id c = c & cod id c = c;
        then
A4:     [id c,id c] in dom the Comp of C by CAT_1:15;
        the Comp of E = (id c,id c).-->((id c)*(id c))
          .= (id c,id c).-->((id c)(*)i) by A2,CAT_1:def 13
          .= [id c,id c].-->(the Comp of C).(id c,id c) by A3,CAT_1:16;
        hence thesis by A4,FUNCT_4:7;
      end;
      let a be Object of E, a9 be Object of C;
      assume a = a9;
      then a9 = c by TARSKI:def 1;
      hence id a = id a9 by TARSKI:def 1;
    end;
    then E is Subcategory of C by Def4;
    hence thesis;
  end;
end;

reserve E for Subcategory of C;

theorem Th2:
  for e being Object of E holds e is Object of C
proof
  let e be Object of E;
  e in the carrier of E & the carrier of E c= the carrier of C by Def4;
  hence thesis;
end;

theorem Th3:
  the carrier' of E c= the carrier' of C
proof
  let x be object;
  assume x in the carrier' of E;
  then reconsider f = x as Morphism of E;
  set a = dom f, b = cod f;
  reconsider a9 = a, b9 = b as Object of C by Th2;
  f in Hom(a,b) & Hom(a,b) c= Hom(a9,b9) by Def4;
  then f in Hom(a9,b9) & Hom(a9,b9) <> {};
  hence thesis;
end;

theorem Th4:
  for f being Morphism of E holds f is Morphism of C
proof
  let f be Morphism of E;
  f in the carrier' of E & the carrier' of E c= the carrier' of C by Th3;
  hence thesis;
end;

theorem Th5:
  for f being (Morphism of E), f9 being Morphism of C st f = f9
  holds dom f = dom f9 & cod f = cod f9
proof
  let f be (Morphism of E), f9 be Morphism of C such that
A1: f = f9;
  set a = dom f, b = cod f;
  reconsider a9 = a, b9 = b as Object of C by Th2;
  f in Hom(a,b) & Hom(a,b) c= Hom(a9,b9) by Def4;
  hence thesis by A1,CAT_1:1;
end;

theorem
  for a,b being Object of E, a9,b9 being Object of C,f being Morphism of
  a, b st a = a9 & b = b9 & Hom(a,b)<>{} holds f is Morphism of a9,b9
proof
  let a,b be Object of E, a9,b9 be Object of C, f be Morphism of a,b;
  assume a = a9 & b = b9 & Hom(a,b)<>{};
  then f in Hom(a,b) & Hom(a,b) c= Hom(a9,b9) by Def4,CAT_1:def 5;
  then f in Hom(a9,b9) & Hom(a9,b9) <> {};
  hence thesis by CAT_1:def 5;
end;

theorem Th7:
  for f,g being (Morphism of E), f9,g9 being Morphism of C st f =
  f9 & g = g9 & dom g = cod f holds g(*)f = g9(*)f9
proof
  let f,g be (Morphism of E), f9,g9 be Morphism of C such that
A1: f = f9 & g = g9 and
A2: dom g = cod f;
  dom g = dom g9 & cod f = cod f9 by A1,Th5;
  then
A3: g9(*)f9 = (the Comp of C).(g9,f9) by A2,CAT_1:16;
A4: the Comp of E c= the Comp of C by Def4;
  g(*)f = (the Comp of E).(g,f) & [g,f] in dom(the Comp of E)
   by A2,CAT_1:15,16;
  hence thesis by A1,A3,A4,GRFUNC_1:2;
end;

theorem Th8:
  C is Subcategory of C
proof
  thus the carrier of C c= the carrier of C;
  thus thesis;
end;

theorem Th9:
  id E is Functor of E,C
proof
  rng id E c= the carrier' of C by Th3;
  then reconsider
  T = id E as Function of the carrier' of E,the carrier' of C by FUNCT_2:6;
  now
    thus for e being Object of E ex c being Object of C st T.(id e) = id c
    proof
      let e be Object of E;
      reconsider c = e as Object of C by Th2;
      T.(id e) = id e by FUNCT_1:18
        .= id c by Def4;
      hence thesis;
    end;
    thus for f being Morphism of E holds T.(id dom f) = id dom (T.f) & T.(id
    cod f) = id cod (T.f)
    proof
      let f be Morphism of E;
A1:   T.(id dom f) = id dom f by FUNCT_1:18
        .= id dom ((id E).f) by FUNCT_1:18;
A2:   T.(id cod f) = id cod f by FUNCT_1:18
        .= id cod ((id E).f) by FUNCT_1:18;
      dom (T.f) = dom((id E).f) & cod (T.f) = cod((id E).f) by Th5;
      hence thesis by A1,A2,Def4;
    end;
    let f,g be Morphism of E;
A3: T.f = f & T.g = g by FUNCT_1:18;
    assume
A4: dom g = cod f;
    then T.(g(*)f) = ((id E).g)(*)((id E).f) by CAT_1:64;
    hence T.(g(*)f) = (T.g)(*)(T.f) by A4,A3,Th7;
  end;
  hence thesis by CAT_1:61;
end;

definition
  let C,E;
  func incl(E) -> Functor of E,C equals
  id E;
  coherence by Th9;
end;

theorem Th10:
  for a being Object of E holds (Obj incl E).a = a
proof
  let a be Object of E;
  reconsider a9 = a as Object of C by Th2;
  id a9 = id a by Def4
    .= (incl E).(id a) by FUNCT_1:18
    .= id((Obj incl E).a) by CAT_1:68;
  hence thesis by CAT_1:59;
end;

theorem
  for a being Object of E holds (incl E).a = a by Th10;

theorem
  incl E is faithful
proof
  let a,b be Object of E such that
  Hom(a,b) <> {};
  let f1,f2 be Morphism of a,b;
  (incl E).f1 = f1 by FUNCT_1:18;
  hence thesis by FUNCT_1:18;
end;

theorem Th13:
  incl E is full iff for a,b being Object of E, a9,b9 being Object
  of C st a = a9 & b = b9 holds Hom(a,b) = Hom(a9,b9)
proof
  set T = incl E;
  thus T is full implies for a,b being Object of E, a9,b9 being Object of C st
  a = a9 & b = b9 holds Hom(a,b) = Hom(a9,b9)
  proof
    assume
A1: for a,b being Object of E st Hom(T.a,T.b) <> {} for g being
Morphism of T.a,T.b holds Hom(a,b) <> {} & ex f being Morphism of a,b st g = T.
    f;
    let a,b be Object of E, a9,b9 be Object of C such that
A2: a = a9 & b = b9;
    now
      let x be object;
      Hom(a,b) c= Hom(a9,b9) by A2,Def4;
      hence x in Hom(a,b) implies x in Hom(a9,b9);
      assume
A3:   x in Hom(a9,b9);
A4:   T.a = a9 & T.b = b9 by A2,Th10;
      then reconsider g = x as Morphism of T.a,T.b by A3,CAT_1:def 5;
      consider f being Morphism of a,b such that
A5:   g = T.f by A1,A4,A3;
A6:   g = f by A5,FUNCT_1:18;
      Hom(a,b) <> {} by A1,A4,A3;
      hence x in Hom(a,b) by A6,CAT_1:def 5;
    end;
    hence thesis by TARSKI:2;
  end;
  assume
A7: for a,b being Object of E, a9,b9 being Object of C st a = a9 & b =
  b9 holds Hom(a,b) = Hom(a9,b9);
  let a,b be Object of E such that
A8: Hom(T.a,T.b) <> {};
  let g be Morphism of T.a,T.b;
A9: g in Hom(T.a,T.b) by A8,CAT_1:def 5;
A10: a = T.a & b = T.b by Th10;
  hence Hom(a,b) <> {} by A7,A8;
  Hom(a,b) = Hom(T.a,T.b) by A7,A10;
  then reconsider f = g as Morphism of a,b by A9,CAT_1:def 5;
  take f;
  thus thesis by FUNCT_1:18;
end;

definition let D;
  let C be Subcategory of D;
  attr C is full means
:Def6:  for c1,c2 being Object of C, d1,d2 being Object of D
   st c1 = d1 & c2 = d2
  holds Hom(c1,c2) = Hom(d1,d2);
end;

registration let D;
 cluster full for Subcategory of D;
 existence
  proof
    reconsider C = D as Subcategory of D by Th8;
   take C;
   let c1,c2 be Object of C, d1,d2 being Object of D;
   assume c1 = d1 & c2 = d2;
   hence Hom(c1,c2) = Hom(d1,d2);
  end;
end;

theorem
  E is full iff incl(E) is full
by Th13;

theorem Th15:
  for O being non empty Subset of the carrier of C holds union{Hom
  (a,b) where a is Object of C,b is Object of C: a in O & b in O} is non empty
  Subset of the carrier' of C
proof
  let O be non empty Subset of the carrier of C;
  set H = {Hom(a,b) where a is Object of C, b is Object of C: a in O & b in O};
  set M = union H;
A1: M c= the carrier' of C
  proof
    let x be object;
    assume x in M;
    then consider X being set such that
A2: x in X and
A3: X in H by TARSKI:def 4;
    ex a,b being Object of C st X = Hom(a,b) & a in O & b in O by A3;
    hence thesis by A2;
  end;
  now
    set a = the Element of O;
    reconsider a as Object of C;
    id a in Hom(a,a) & Hom(a,a) in H by CAT_1:27;
    then id a in M by TARSKI:def 4;
    hence ex f being set st f in M;
  end;
  hence thesis by A1;
end;

theorem Th16:
  for O being non empty Subset of the carrier of C, M being non
empty set st M = union{Hom(a,b) where a is Object of C,b is Object of C: a in O
& b in O} holds (the Source of C)|M is Function of M,O & (the Target of C)|M is
Function of M,O & (the Comp of C)||M is PartFunc of [:M,M:],M
proof
  let O be non empty Subset of the carrier of C;
  set H = {Hom(a,b) where a is Object of C, b is Object of C: a in O & b in O};
A1: dom the Source of C = the carrier' of C by FUNCT_2:def 1;
  let M be non empty set such that
A2: M = union H;
A3: now
    let f be Morphism of C;
    assume f in M;
    then consider X being set such that
A4: f in X and
A5: X in H by A2,TARSKI:def 4;
    ex a,b being Object of C st X = Hom(a,b) & a in O & b in O by A5;
    hence dom f in O & cod f in O by A4,CAT_1:1;
  end;
  set d = (the Source of C)|M, c = (the Target of C)|M, p = (the Comp of C)||M;
A6: dom the Target of C = the carrier' of C by FUNCT_2:def 1;
A7: dom d = (dom the Source of C) /\ M by RELAT_1:61;
A8: rng d c= O
  proof
    let y be object;
    assume y in rng d;
    then consider x being object such that
A9: x in dom d and
A10: y = d.x by FUNCT_1:def 3;
    reconsider f = x as Morphism of C by A1,A7,A9,XBOOLE_0:def 4;
    d.f = dom f & f in M by A7,A9,FUNCT_1:47,XBOOLE_0:def 4;
    hence thesis by A3,A10;
  end;
A11: M is non empty Subset of the carrier' of C by A2,Th15;
  then
A12: dom c = M by A6,RELAT_1:62;
A13: dom c = (dom the Target of C) /\ M by RELAT_1:61;
A14: rng c c= O
  proof
    let y be object;
    assume y in rng c;
    then consider x being object such that
A15: x in dom c and
A16: y = c.x by FUNCT_1:def 3;
    reconsider f = x as Morphism of C by A6,A13,A15,XBOOLE_0:def 4;
    c.f = cod f & f in M by A13,A15,FUNCT_1:47,XBOOLE_0:def 4;
    hence thesis by A3,A16;
  end;
  dom d = M by A1,A11,RELAT_1:62;
  hence d is Function of M,O & c is Function of M,O by A8,A14,A12,FUNCT_2:def 1
,RELSET_1:4;
A17: dom p = (dom the Comp of C) /\ [:M,M:] by RELAT_1:61;
A18: dom the Comp of C c= [:the carrier' of C,the carrier' of C:] by
RELAT_1:def 18;
  rng p c= M
  proof
    let y be object;
    assume y in rng p;
    then consider x being object such that
A19: x in dom p and
A20: y = p.x by FUNCT_1:def 3;
A21: x in dom the Comp of C by A17,A19,XBOOLE_0:def 4;
    then consider g,f being Morphism of C such that
A22: x = [g,f] by A18,DOMAIN_1:1;
A23: [g,f] in [:M,M:] by A17,A19,A22,XBOOLE_0:def 4;
    then g in M by ZFMISC_1:87;
    then
A24: cod g in O by A3;
    dom g = cod f by A21,A22,CAT_1:15;
    then
A25: dom(g(*)f) = dom f & cod(g(*)f) = cod g by CAT_1:17;
    f in M by A23,ZFMISC_1:87;
    then dom f in O by A3;
    then
A26: Hom(dom(g(*)f),cod(g(*)f)) in H by A24,A25;
A27: g(*)f in Hom(dom(g(*)f),cod(g(*)f ));
    p.x = (the Comp of C).(g,f) by A19,A22,FUNCT_1:47
      .= g(*)f by A21,A22,CAT_1:def 1;
    hence thesis by A2,A20,A26,A27,TARSKI:def 4;
  end;
  hence p is PartFunc of [:M,M:],M by A17,RELSET_1:4,XBOOLE_1:17;
  thus thesis;
end;

registration
  let O, M be non empty set, d,c being Function of M,O, p being PartFunc of [:
  M,M:],M;
  cluster CatStr(#O,M,d,c,p#) -> non void non empty;
  coherence;
end;

Lm1:
  for O being non empty Subset of the carrier of C, M being non empty
set, d,c being Function of M,O, p being PartFunc of [:M,M:],M, i being Function
of O,M st M = union{Hom(a,b) where a is Object of C,b is Object of C: a in O &
b in O} & d = (the Source of C)|M & c = (the Target of C)|M & p = (the Comp of
C)||M
 holds CatStr(#O,M,d,c,p#) is Category
 proof
  let O be non empty Subset of the carrier of C, M be non empty set, d,c be
  Function of M,O, p be PartFunc of [:M,M:],M, i be Function of O,M;
  set H = {Hom(a,b) where a is Object of C, b is Object of C: a in O & b in O};
  assume that
A1: M = union H and
A2: d = (the Source of C)|M and
A3: c = (the Target of C)|M and
A4: p = (the Comp of C)||M;
 set B = CatStr(#O,M,d,c,p#);
A5: now
    let f be Morphism of B;
    consider X being set such that
A6: f in X and
A7: X in H by A1,TARSKI:def 4;
    ex a,b being Object of C st X = Hom(a,b) & a in O & b in O by A7;
    hence f is Morphism of C by A6;
  end;
A8: for f,g being Morphism of B holds [g,f] in dom(p) iff d.g=c.f
  proof
    let f,g be Morphism of B;
     reconsider gg=g, ff=f as Morphism of C by A5;
A9: d.g = dom gg & c.f = cod ff by A2,A3,FUNCT_1:49;
    thus [g,f] in dom(p) implies d.g = c.f
    proof
      assume [g,f] in dom(p);
      then [g,f] in (dom the Comp of C) /\ [:M,M:] by A4,RELAT_1:61;
      then [gg,ff] in (dom the Comp of C) by XBOOLE_0:def 4;
      hence thesis by A9,CAT_1:def 6;
    end;
    assume d.g=c.f;
    then [g,f] in dom the Comp of C by A9,CAT_1:def 6;
    then [g,f] in (dom the Comp of C) /\ [:M,M:] by XBOOLE_0:def 4;
    hence thesis by A4,RELAT_1:61;
  end;
A10:  B is Category-like
    by A8;
A11:  B is transitive
   proof
      thus
 for f,g being Morphism of B st dom g = cod f
    holds dom(g(*)f) = dom f & cod(g(*)f) = cod g
      proof
        let f,g be Morphism of B;
        reconsider ff=f, gg=g as Morphism of C by A5;
A12:    d.g = dom gg & c.f = cod ff by A2,A3,FUNCT_1:49;
        assume
A13:    dom g = cod f;
A14:     [g,f] in dom the Comp of B by A13,A8;
A15:     p.(g,f) = g(*)f by A13,A8,CAT_1:def 1;
A16:     dom p c= dom the Comp of C by A4,RELAT_1:60;
A17:     p.[g,f] = (the Comp of C).(g,f) by A4,A8,A13,FUNCT_1:47
         .= gg(*)ff by A16,A14,CAT_1:def 1;
        thus dom(g(*)f)
           = dom(gg(*)ff) by A17,A2,A15,FUNCT_1:49
          .= dom ff by A13,A12,CAT_1:def 7
          .= dom f by A2,FUNCT_1:49;
        thus cod(g(*)f)
           = cod(gg(*)ff) by A17,A3,A15,FUNCT_1:49
          .= cod gg by A13,A12,CAT_1:def 7
          .= cod g by A3,FUNCT_1:49;
      end;
     end;
A18:   B is associative
     proof
      thus for f,g,h being Morphism of B
        st dom h = cod g & dom g = cod f
      holds h(*)(g(*)f) = (h(*)g)(*)f
      proof
        let f,g,h be Morphism of B;
         reconsider ff=f, gg=g, hh=h as Morphism of C by A5;
        assume that
A19:    dom h = cod g and
A20:    dom g = cod f;
A21:    h(*)g = (the Comp of B).(h,g) by A19,A8,CAT_1:def 1;
A22:    g(*)f = (the Comp of B).(g,f) by A20,A8,CAT_1:def 1;
A23:   dom(h(*)g) = dom g by A11,A19;
A24:    c.g = cod gg & d.g = dom gg by A2,A3,FUNCT_1:49;
A25:    c.f = cod ff by A3,FUNCT_1:49;
A26:    f is Morphism of C & d.h = dom hh by A2,A5,FUNCT_1:49;
A27:     dom gg = d.g by A2,FUNCT_1:49
               .= cod ff by A3,A20,FUNCT_1:49;
       then
A28:    gg(*)ff = (the Comp of C).(gg,ff) by CAT_1:16;
A29:      dom hh = d.h by A2,FUNCT_1:49
         .= cod gg by A3,A19,FUNCT_1:49;
       then
A30:    cod(gg(*)ff) = dom hh by A27,CAT_1:def 7;
A31:    hh(*)gg = (the Comp of C).(hh,gg) by A29,CAT_1:16;
A32:     cod ff= dom(hh(*)gg) by A27,A29,CAT_1:def 7;
A33:    cod(g(*)f) = cod g by A11,A20;
        hence h(*)(g(*)f)
           = (the Comp of B).(h,(the Comp of B).(g,f)) by A22,A19,A8
,CAT_1:def 1
          .= (the Comp of C).[h,p.[g,f]] by A4,A8,A19,A33,A22,FUNCT_1:47
          .= (the Comp of C).(hh,gg(*)ff) by A4,A8,A20,A28,FUNCT_1:47
          .= hh(*)(gg(*)ff) by A30,CAT_1:16
          .= (hh(*)gg)(*)ff
                 by A19,A20,A26,A24,A25,CAT_1:def 8
          .= (the Comp of C).((the Comp of C).(hh,gg),ff)
                 by A31,A32,CAT_1:16
          .= (the Comp of C).[p.[h,g],f] by A4,A8,A19,FUNCT_1:47
          .= (the Comp of B).((the Comp of B).(h,g),f)
                        by A4,A8,A20,A23,A21,FUNCT_1:47
          .= h(*)g(*)f by A21,A20,A8,A23,CAT_1:def 1;
      end;
     end;
A34: B is reflexive
     proof
      let b be Object of B;
       b in O;
       then reconsider bb = b as Object of C;
A35:     Hom(bb,bb) in H;
       id bb in Hom(bb,bb) by CAT_1:27;
       then reconsider ii = id bb as Morphism of B by A35,A1,TARSKI:def 4;
A36:     dom ii = dom id bb by A2,FUNCT_1:49
           .= bb;
       cod ii = cod id bb by A3,FUNCT_1:49
           .= bb;
       then ii in Hom(b,b) by A36;

      hence Hom(b,b)<>{};
     end;
      B is with_identities
     proof let a be Element of B;
       a in O;
       then reconsider aa = a as Object of C;
A37:     Hom(aa,aa) in H;
       id aa in Hom(aa,aa) by CAT_1:27;
       then reconsider ii = id aa as Morphism of B by A37,A1,TARSKI:def 4;
A38:     dom ii = dom id aa by A2,FUNCT_1:49
           .= aa;
A39:     cod ii = cod id aa by A3,FUNCT_1:49
           .= aa;
       then reconsider ii as Morphism of a,a by A38,CAT_1:4;
      take ii;
      let b be Element of B;
       b in O;
       then reconsider bb = b as Object of C;
      thus Hom(a,b)<>{} implies for g being Morphism of a,b holds g(*)ii = g
       proof assume
A40:       Hom(a,b)<>{};
        let g be Morphism of a,b;
         reconsider gg = g as Morphism of C by A5;
A41:       dom gg = dom g by A2,FUNCT_1:49
            .= aa by A40,CAT_1:5;
A42:       cod id aa = aa;
         cod gg = cod g by A3,FUNCT_1:49
            .= bb by A40,CAT_1:5;
         then reconsider gg as Morphism of aa,bb by A41,CAT_1:4;
A43:      dom g = a by A40,CAT_1:5;
        hence g(*)ii = p.(g,ii) by A39,A8,CAT_1:def 1
               .= (the Comp of C).(gg,id aa) by A43,A4,A39,A8,FUNCT_1:47
               .= gg(*)id aa by A41,A42,CAT_1:16
               .= g by A41,CAT_1:22;
       end;
      thus
     Hom(b,a)<>{} implies for f being Morphism of b,a holds ii(*)f = f
       proof assume
A44:       Hom(b,a)<>{};
        let g be Morphism of b,a;
         reconsider gg = g as Morphism of C by A5;
A45:       cod gg = cod g by A3,FUNCT_1:49
            .= aa by A44,CAT_1:5;
A46:       dom id aa = aa;
         dom gg = dom g by A2,FUNCT_1:49
            .= bb by A44,CAT_1:5;
         then reconsider gg as Morphism of bb,aa by A45,CAT_1:4;
A47:       cod g = a by A44,CAT_1:5;
        hence ii(*)g = p.(ii,g) by A38,A8,CAT_1:def 1
               .= (the Comp of C).(id aa,gg) by A4,A47,A38,A8,FUNCT_1:47
               .= (id aa)(*)gg by A45,A46,CAT_1:16
               .= g by A45,CAT_1:21;
       end;
    end;
   hence B is Category by A10,A11,A18,A34;
end;

Lm2:
  for O being non empty Subset of the carrier of C, M being non empty
set, d,c being Function of M,O, p being PartFunc of [:M,M:],M, i being Function
of O,M st M = union{Hom(a,b) where a is Object of C,b is Object of C: a in O &
b in O} & d = (the Source of C)|M & c = (the Target of C)|M & p = (the Comp of
C)||M
  holds CatStr(#O,M,d,c,p#) is Subcategory of C
proof
  let O be non empty Subset of the carrier of C, M be non empty set, d,c be
  Function of M,O, p be PartFunc of [:M,M:],M, i be Function of O,M;
  set H = {Hom(a,b) where a is Object of C, b is Object of C: a in O & b in O};
  assume that
A1: M = union H and
A2: d = (the Source of C)|M and
A3: c = (the Target of C)|M and
A4: p = (the Comp of C)||M;
 set B = CatStr(#O,M,d,c,p#);
A5: now
    let f be Morphism of B;
    consider X being set such that
A6: f in X and
A7: X in H by A1,TARSKI:def 4;
    ex a,b being Object of C st X = Hom(a,b) & a in O & b in O by A7;
    hence f is Morphism of C by A6;
  end;
A8: for a,b being Object of B, a9,b9 being Object of C st a = a9 & b = b9
  holds Hom(a,b) = Hom(a9,b9)
  proof
    let a,b be Object of B, a9,b9 be Object of C such that
A9: a = a9 & b = b9;
    now
      let x be object;
      thus x in Hom(a,b) implies x in Hom(a9,b9)
      proof
        assume
A10:    x in Hom(a,b);
        then reconsider f = x as Morphism of B;
        reconsider f9 = f as Morphism of C by A5;
        cod f = cod f9 by A3,FUNCT_1:49;
        then
A11:    b = cod f9 by A10,CAT_1:1;
        dom f = dom f9 by A2,FUNCT_1:49;
        then a = dom f9 by A10,CAT_1:1;
        hence thesis by A9,A11;
      end;
      assume
A12:  x in Hom(a9,b9);
      then reconsider f9 = x as Morphism of C;
      Hom(a9,b9) in H by A9;
      then reconsider f = f9 as Morphism of B by A1,A12,TARSKI:def 4;
      cod f = cod f9 by A3,FUNCT_1:49;
      then
A13:  cod f = b9 by A12,CAT_1:1;
      dom f = dom f9 by A2,FUNCT_1:49;
      then dom f = a9 by A12,CAT_1:1;
      hence x in Hom(a,b) by A9,A13;
    end;
    hence thesis by TARSKI:2;
  end;
    reconsider B as Category by Lm1,A1,A2,A3,A4;
A14: for a be Object of B, a9 be Object of C st a = a9 holds id a = id a9
    proof let a be Object of B, a9 be Object of C such that
A15:   a = a9;
A16:    Hom(a9,a9) in H by A15;
A17:    id a9 in Hom(a9,a9) by CAT_1:27;
      then reconsider ii = id a9 as Morphism of B by A16,A1,TARSKI:def 4;
A18:     dom ii = dom id a9 by A2,FUNCT_1:49
           .= a9;
A19:     cod ii = cod id a9 by A3,FUNCT_1:49
           .= a9;
      ii in Hom(a,a) by A17,A8,A15;
      then reconsider ii as Morphism of a,a by CAT_1:def 5;
A20: for f,g being Morphism of B holds [g,f] in dom(p) iff d.g=c.f
  proof
    let f,g be Morphism of B;
     reconsider gg=g, ff=f as Morphism of C by A5;
A21: d.g = dom gg & c.f = cod ff by A2,A3,FUNCT_1:49;
    thus [g,f] in dom(p) implies d.g = c.f
    proof
      assume [g,f] in dom(p);
      then [g,f] in (dom the Comp of C) /\ [:M,M:] by A4,RELAT_1:61;
      then [gg,ff] in (dom the Comp of C) by XBOOLE_0:def 4;
      hence thesis by A21,CAT_1:def 6;
    end;
    assume d.g=c.f;
    then [g,f] in dom the Comp of C by A21,CAT_1:def 6;
    then [g,f] in (dom the Comp of C) /\ [:M,M:] by XBOOLE_0:def 4;
    hence thesis by A4,RELAT_1:61;
  end;
      for b being Object of B holds
        (Hom(a,b) <> {} implies
       for f being Morphism of a,b holds f(*)ii = f)
      & (Hom(b,a) <> {} implies
       for f being Morphism of b,a holds ii(*)f = f)
      proof let b be Object of B;
        b in O;
        then reconsider bb = b as Element of C;
       thus Hom(a,b) <> {} implies
        for f being Morphism of a,b holds f(*)ii = f
       proof assume
A22:       Hom(a,b)<>{};
        let g be Morphism of a,b;
         reconsider gg = g as Morphism of C by A5;
A23:       dom gg = dom g by A2,FUNCT_1:49
            .= a9 by A15,A22,CAT_1:5;
A24:       cod id a9 = a9;
         cod gg = cod g by A3,FUNCT_1:49
            .= bb by A22,CAT_1:5;
         then reconsider gg as Morphism of a9,bb by A23,CAT_1:4;
A25:       dom g = a by A22,CAT_1:5;
        hence g(*)ii = p.(g,ii) by A19,A20,A15,CAT_1:def 1
               .= (the Comp of C).(gg,id a9) by A19,A20,A15,A4,A25,FUNCT_1:47
               .= gg(*)id a9 by A23,A24,CAT_1:16
               .= g by A23,CAT_1:22;
       end;
        assume
A26:       Hom(b,a)<>{};
        let g be Morphism of b,a;
         reconsider gg = g as Morphism of C by A5;
A27:       cod gg = cod g by A3,FUNCT_1:49
            .= a9 by A15,A26,CAT_1:5;
A28:       dom id a9 = a9;
         dom gg = dom g by A2,FUNCT_1:49
            .= bb by A26,CAT_1:5;
         then reconsider gg as Morphism of bb,a9 by A27,CAT_1:4;
A29:       cod g = a by A26,CAT_1:5;
        hence ii(*)g = p.(ii,g) by A18,A20,A15,CAT_1:def 1
               .= (the Comp of C).(id a9,gg) by A18,A20,A15,A4,A29,FUNCT_1:47
               .= (id a9)(*)gg by A27,A28,CAT_1:16
               .= g by A27,CAT_1:21;
      end;
     hence id a = id a9 by CAT_1:def 12;
    end;
    ( for a,b being Object of B, a9,b9 being Object of C st a = a9 & b =
    b9 holds Hom(a,b) c= Hom(a9,b9))& the Comp of B c= the Comp of C
       by A4,A8,RELAT_1:59;

    hence thesis by A14,Def4;
end;

theorem
  for O being non empty Subset of the carrier of C, M being non empty
set, d,c being Function of M,O, p being PartFunc of [:M,M:],M, i being Function
of O,M st M = union{Hom(a,b) where a is Object of C,b is Object of C: a in O &
b in O} & d = (the Source of C)|M & c = (the Target of C)|M & p = (the Comp of
C)||M
  holds CatStr(#O,M,d,c,p#) is full Subcategory of C
proof
  let O be non empty Subset of the carrier of C, M be non empty set, d,c be
  Function of M,O, p be PartFunc of [:M,M:],M, i be Function of O,M;
  set H = {Hom(a,b) where a is Object of C, b is Object of C: a in O & b in O};
  assume that
A1: M = union H and
A2: d = (the Source of C)|M and
A3: c = (the Target of C)|M and
A4: p = (the Comp of C)||M;
 set B = CatStr(#O,M,d,c,p#);
A5: now
    let f be Morphism of B;
    consider X being set such that
A6: f in X and
A7: X in H by A1,TARSKI:def 4;
    ex a,b being Object of C st X = Hom(a,b) & a in O & b in O by A7;
    hence f is Morphism of C by A6;
  end;
A8: for a,b being Object of B, a9,b9 being Object of C st a = a9 & b = b9
  holds Hom(a,b) = Hom(a9,b9)
  proof
    let a,b be Object of B, a9,b9 be Object of C such that
A9: a = a9 & b = b9;
    now
      let x be object;
      thus x in Hom(a,b) implies x in Hom(a9,b9)
      proof
        assume
A10:    x in Hom(a,b);
        then reconsider f = x as Morphism of B;
        reconsider f9 = f as Morphism of C by A5;
        cod f = cod f9 by A3,FUNCT_1:49;
        then
A11:    b = cod f9 by A10,CAT_1:1;
        dom f = dom f9 by A2,FUNCT_1:49;
        then a = dom f9 by A10,CAT_1:1;
        hence thesis by A9,A11;
      end;
      assume
A12:  x in Hom(a9,b9);
      then reconsider f9 = x as Morphism of C;
      Hom(a9,b9) in H by A9;
      then reconsider f = f9 as Morphism of B by A1,A12,TARSKI:def 4;
      cod f = cod f9 by A3,FUNCT_1:49;
      then
A13:  cod f = b9 by A12,CAT_1:1;
      dom f = dom f9 by A2,FUNCT_1:49;
      then dom f = a9 by A12,CAT_1:1;
      hence x in Hom(a,b) by A9,A13;
    end;
    hence thesis by TARSKI:2;
  end;
 reconsider B as Subcategory of C by Lm2,A1,A2,A3,A4;
   B is full by A8;
  hence thesis;
end;

theorem
  for O being non empty Subset of the carrier of C, M being non empty
  set , d,c being Function of M,O, p being PartFunc of [:M,M:],M
  st CatStr(#O,M,d,c,p#) is full Subcategory of C
  holds M =
union{Hom(a,b) where a is Object of C,b is Object of C: a in O & b in O} & d =
(the Source of C)|M & c = (the Target of C)|M & p = (the Comp of C)||M
proof
  let O be non empty Subset of the carrier of C, M be non empty set, d,c be
  Function of M,O, p be PartFunc of [:M,M:],M;
  set H = {Hom(a,b) where a is Object of C, b is Object of C: a in O & b in O};
  set B = CatStr(#O,M,d,c,p#);
  assume
A1: B is full Subcategory of C;
A2: for f being Morphism of B holds d.f = (the Source of C).f & c.f = (the
  Target of C).f
  proof
    let f be Morphism of B;
    reconsider f9 = f as Morphism of C by A1,Th4;
    dom f = dom f9 & cod f = cod f9 by A1,Th5;
    hence thesis;
  end;
  now
    let x be object;
    thus x in M implies x in union H
    proof
      assume x in M;
      then reconsider f = x as Morphism of B;
      reconsider f9 = f as Morphism of C by A1,Th4;
      set a9 = dom f9, b9 = cod f9;
      (the Source of B).f = (the Source of C).f9 & (the Target of B).f = (
      the Target of C).f9 by A2;
      then f in Hom(a9,b9) & Hom(a9,b9) in H;
      hence thesis by TARSKI:def 4;
    end;
    assume x in union H;
    then consider X being set such that
A3: x in X and
A4: X in H by TARSKI:def 4;
    consider a9,b9 being Object of C such that
A5: X = Hom(a9,b9) and
A6: a9 in O & b9 in O by A4;
    reconsider a = a9, b = b9 as Object of B by A6;
    Hom(a,b) = Hom(a9,b9) by A1,Def6;
    hence x in M by A3,A5;
  end;
  hence
 M = union H by TARSKI:2;
  then reconsider
  d9 = (the Source of C)|M, c9 = (the Target of C)|M as Function of
  M,O by Th16;
  set p9 = (the Comp of C)||M;
  now
    let f be Element of M;
    d.f = (the Source of C).f by A2;
    hence d.f = d9.f by FUNCT_1:49;
  end;
  hence d = (the Source of C)|M by FUNCT_2:63;
  now
    let f be Element of M;
    c.f = (the Target of C).f by A2;
    hence c.f = c9.f by FUNCT_1:49;
  end;
  hence c = (the Target of C)|M by FUNCT_2:63;
  now
A7: dom p c= [:M,M:] by RELAT_1:def 18;
A8: dom p9 = (dom the Comp of C) /\ [:M,M:] by RELAT_1:61;
    the Comp of B c= the Comp of C by A1,Def4;
    then dom p c= dom the Comp of C by GRFUNC_1:2;
    then
A9: dom p c= dom p9 by A7,A8,XBOOLE_1:19;
    dom p9 c= dom p
    proof
      let x be object;
      assume
A10:  x in dom p9;
      then x in [:M,M:] by A8,XBOOLE_0:def 4;
      then consider g,f being Element of M such that
A11:  x = [g,f] by DOMAIN_1:1;
      reconsider f,g as Morphism of B;
      reconsider f9 = f,g9 = g as Morphism of C by A1,Th4;
      [g,f] in dom the Comp of C by A8,A10,A11,XBOOLE_0:def 4;
      then
A12:  dom g9 = cod f9 by CAT_1:15;
      cod f = cod f9 & dom g = dom g9 by A1,Th5;
      hence thesis by A1,A11,A12,CAT_1:15;
    end;
    hence dom p = dom p9 by A9,XBOOLE_0:def 10;
    let x be object;
    assume
A13: x in dom p;
    then consider g,f being Element of M such that
A14: x = [g,f] by A7,DOMAIN_1:1;
    reconsider f,g as Morphism of B;
A15: dom g = cod f by A1,A13,A14,CAT_1:15;
    reconsider f9 = f,g9 = g as Morphism of C by A1,Th4;
A16: cod f = cod f9 & dom g = dom g9 by A1,Th5;
    p.x = p.(g,f) by A14;
    hence p.x = g(*)f by A1,A15,CAT_1:16
      .= g9(*)f9 by A1,A15,Th7
      .= (the Comp of C).(g9,f9) by A16,A1,A13,A14,CAT_1:15,16
      .= p9.x by A9,A13,A14,FUNCT_1:47;
  end;
  hence p = (the Comp of C)||M by FUNCT_1:2;
end;

:: Product of Categories

definition
  let C,D;
  func [:C,D:] -> Category equals
  CatStr (# [:the carrier of C,the carrier of D:],
     [:the carrier' of C,the carrier' of D:],
     [:the Source of C,the Source of D:],
     [:the Target of C,the Target of D:],
     |:the Comp of C, the Comp of D:| #);
  coherence
  proof
    set O = [:the carrier of C,the carrier of D:],
        M = [:the carrier' of C,the carrier' of D:],
        d = [:the Source of C,the Source of D:],
        c = [:the Target of C,the Target of D:],
        p = |:the Comp of C, the Comp of D:|;
A1: for f,g being Element of M st d.g = c.f holds
    [g`1,f`1] in dom(the Comp of C) & [g`2,f`2] in dom(the Comp of D)
    proof
      let f,g be Element of M;
A2:   d.(g`1,g`2) = [(the Source of C).g`1,(the Source of D).g`2] & c.(f`1
      ,f`2) = [(the Target of C).f`1,(the Target of D).f`2] by FUNCT_3:75;
      assume
A3:   d.g = c.f;
      g = [g`1,g`2] & f = [f`1,f`2] by MCART_1:21;
      then
      dom(g`1) = cod(f`1) &
      dom(g`2) = cod(f`2) by A2,A3,XTUPLE_0:1;
      hence thesis by CAT_1:def 6;
    end;
A4: for f,g being Element of M st [g,f] in dom(p)
    holds dom(g`1) = cod(f`1) & dom(g`2) = cod(f`2)
    proof
      let f,g be Element of M;
      assume
A5:   [g,f] in dom(p);
      g = [g`1,g`2] & f = [f`1,f`2] by MCART_1:21;
      then [g`1,f`1] in dom(the Comp of C) & [g`2,f`2] in dom(the Comp of D)
      by A5,FUNCT_4:54;
      hence thesis by CAT_1:def 6;
    end;
    set B = CatStr(#O,M,d,c,p#);
A6:  B is Category-like
    proof
      let ff,gg be Morphism of B;
       reconsider f = ff, g=gg as Element of M;
A7:   g = [g`1,g`2] & f = [f`1,f`2] by MCART_1:21;
      thus [gg,ff] in dom(the Comp of B) implies
       dom gg = cod ff
      proof
A8:     d.(g`1,g`2) = [dom(g`1),dom(g`2)] & c.(
        f`1,f`2) = [cod(f`1),cod(f`2)] by FUNCT_3:75;
        assume
A9:     [gg,ff] in dom(the Comp of B);
        then dom(g`1) = cod(f`1) by A4;
        hence thesis by A4,A7,A9,A8;
      end;
      assume dom gg = cod ff;
      then [g`1,f`1] in dom(the Comp of C) & [g`2,f`2] in dom(the Comp of D)
      by A1;
      hence thesis by A7,FUNCT_4:54;
    end;
A10:   for f,g being Morphism of B
      holds [g,f] in dom(the Comp of B) iff dom g = cod f by A6;
A11: for f,g being Element of M st d.g = c.f
 holds p.(g,f) = [(the Comp of C).(g`1,f`1),(the Comp of D).(g`2,f`2)]
    proof
      let f,g be Element of M;
      reconsider ff=f, gg=g as Morphism of B;
      assume d.g = c.f;
      then
A12:   dom gg = cod ff;
      g = [g`1,g`2] & f = [f`1,f`2] by MCART_1:21;
      hence thesis by A12,A10,FUNCT_4:55;
    end;
A13: for f,g being Element of M st d.g = c.f
      holds d.(p.(g,f)) = d.f & c.(p.(g,f)) = c.g
    proof
      let f,g be Element of M;
      reconsider ff=f, gg=g as Morphism of B;
A14:  f = [f`1,f`2] & d.(f`1,f`2) = [dom(f`1),dom(f`2)]
              by FUNCT_3:75,MCART_1:21;
      assume
A15:  d.g = c.f;
      then
A16:  (the Comp of C).[g`1,f`1] in the carrier' of C by A1,PARTFUN1:4;
      then
A17:  (the Comp of C).(g`1,f`1) in dom(the Source of C) by FUNCT_2:def 1;
      dom gg = cod ff by A15;
      then
A18:  [gg,ff] in dom(p) by A6;
      then
A19:   dom(g`1) = cod(f`1) by A4;
      then [g`1,f`1] in dom the Comp of C by CAT_1:def 6;
      then
A20:    (the Comp of C).(g`1,f`1) = (g`1)(*)(f`1) by CAT_1:def 1;
A21:  dom((g`1)(*)(f`1)) = dom(f`1) by A19,CAT_1:def 7;
A22:  (the Comp of D).[g`2,f`2] in the carrier' of D by A1,A15,PARTFUN1:4;
      then
A23:  (the Comp of D).(g`2,f`2) in dom(the Source of D) by FUNCT_2:def 1;
A24:  dom(g`2) = cod(f`2) by A4,A18;
      then [g`2,f`2] in dom the Comp of D by CAT_1:def 6;
      then
A25:    (the Comp of D).(g`2,f`2) = (g`2)(*)(f`2) by CAT_1:def 1;
A26:  dom((g`2)(*)(f`2)) = dom(f`2) by A24,CAT_1:def 7;
      thus d.(p.(g,f)) = d.((the Comp of C).(g`1,f`1),(the Comp of D).(g`2,f`2
      )) by A11,A15
        .= d.f by A14,A21,A26,A17,A23,A20,A25,FUNCT_3:def 8;
A27:  g = [g`1,g`2] & c.(g`1,g`2) = [(the Target of C).g`1,(the Target of
      D).g`2] by FUNCT_3:75,MCART_1:21;
A28:  cod((g`2)(*)(f`2)) = cod(g`2) by A24,CAT_1:def 7;
A29:  cod((g`1)(*)(f`1)) = cod(g`1)  by A19,CAT_1:def 7;
A30:  (the Comp of D).(g`2,f`2) in dom(the Target of D) by A22,FUNCT_2:def 1;
A31:  (the Comp of C).(g`1,f`1) in dom(the Target of C) by A16,FUNCT_2:def 1;
      thus c.(p.(g,f))
         = c.((the Comp of C).(g`1,f`1),(the Comp of D).(g`2,f`2)) by A11,A15
        .= c.g by A27,A29,A28,A31,A30,A20,A25,FUNCT_3:def 8;
    end;
A32: B is transitive
   proof
      let ff,gg be Morphism of B;
      reconsider f=ff, g=gg as Element of M;
      assume
A33:   dom gg = cod ff;
       then
A34:   (the Comp of B).(gg,ff) = gg(*)ff by A10,CAT_1:def 1;
      thus dom(gg(*)ff) = dom ff by A13,A33,A34;
      thus cod(gg(*)ff) = cod gg by A13,A33,A34;
   end;
A35: B is associative
    proof
      let ff,gg,hh be Morphism of B;
       reconsider f=ff, g=gg, h=hh as Element of M;
      assume that
A36:  dom hh = cod gg and
A37:  dom gg = cod ff;
A38:  (the Comp of C).[h`1,g`1] in the carrier' of C & (the Comp of D).[h
      `2,g`2] in the carrier' of D by A1,A36,PARTFUN1:4;
      (the Comp of C).[g`1,f`1] in the carrier' of C & (the Comp of D).[g
      `2,f`2] in the carrier' of D by A1,A37,PARTFUN1:4;
      then reconsider
      pgf = [(the Comp of C).[g`1,f`1],(the Comp of D).[g`2,f`2]],
      phg = [(the Comp of C).[h`1,g`1],(the Comp of D).[h`2,g`2]]
        as Element of M by A38,ZFMISC_1:87;
      set pgf2 = pgf`2, phg2 = phg`2;
      set pgf1 = pgf`1, phg1 = phg`1;
A39:  p.(g,f) = [(the Comp of C).(g`1,f`1),(the Comp of D).(g`2,f`2)]
        by A11,A37;
A40:    d.h = c.(p.(g,f)) by A13,A36,A37;
A41:  p.(h,g) = [(the Comp of C).(h`1,g`1),(the Comp of D).(h`2,g`2)]
         by A11,A36;
      [h`2,g`2] in dom(the Comp of D) by A1,A36;
      then
A42:  dom(h`2) = cod(g`2) by CAT_1:def 6;
      [h`1,g`1] in dom(the Comp of C) by A1,A36;
      then
A43:  dom(h`1) = cod(g`1) by CAT_1:def 6;
      [g`2,f`2] in dom(the Comp of D) by A1,A37;
      then
A44:  dom(g`2) = cod(f`2) by CAT_1:def 6;
      [g`1,f`1] in dom(the Comp of C) by A1,A37;
      then
A45:  dom(g`1) = cod(f`1) by CAT_1:def 6;
A46:   d.(p.(h,g)) = c.f by A13,A36,A37;
A47:    pgf`1 = (the Comp of C).(g`1,f`1) &
       phg`1 = (the Comp of C).(h`1,g`1);
A48:    pgf`2 = (the Comp of D).(g`2,f`2) &
       phg`2 = (the Comp of D).(h`2,g`2);
A49:    h`2(*)(g`2(*)f`2) = h`2(*)g`2(*)f`2 by A42,A44,CAT_1:def 8;
A50:     gg(*)ff = p.(g,f) by A37,A10,CAT_1:def 1;
       then
A51:     cod(gg(*)ff) = dom hh by A13,A36,A37;
A52:     hh(*)gg = p.(h,g) by A36,A10,CAT_1:def 1;
       then
A53:     dom(hh(*)gg) = cod ff by A13,A36,A37;
A54:    cod(g`1(*)f`1) = cod g`1 by A45,CAT_1:def 7;
A55:     pgf1 = g`1(*)f`1 by A47,A45,CAT_1:16;
A56:    cod(g`2(*)f`2) = cod g`2 by A44,CAT_1:def 7;
       pgf2 = g`2(*)f`2 by A48,A44,CAT_1:16;
       then
A57:    (the Comp of D).(h`2, pgf2) = h`2(*)(g`2(*)f`2) by A42,A56,CAT_1:16;
A58:    dom(h`1(*)g`1) = dom g`1 by A43,CAT_1:def 7;
A59:     phg1 = h`1(*)g`1 by A47,A43,CAT_1:16;
A60:    dom(h`2(*)g`2) = dom g`2 by A42,CAT_1:def 7;
       phg2 = h`2(*)g`2 by A48,A42,CAT_1:16;
       then
A61:   (the Comp of D).(phg2,f`2) = h`2(*)g`2(*)f`2 by A44,A60,CAT_1:16;
      thus hh(*)(gg(*)ff)
         = p.(h,p.(g,f)) by A51,A50,A10,CAT_1:def 1
        .= [(the Comp of C).(h`1,pgf1), (the Comp of D).(h`2, pgf2)]
                      by A40,A11,A39
        .= [h`1(*)(g`1(*)f`1),h`2(*)(g`2(*)f`2)] by A55,A57,A43,A54,CAT_1:16
        .= [h`1(*)g`1(*)f`1,h`2(*)g`2(*)f`2] by A43,A45,A49,CAT_1:def 8
        .= [(the Comp of C).(phg1,f`1), (the Comp of D).(phg2,f`2)]
                 by A59,A61,A45,A58,CAT_1:16
        .= p.(p.(h,g),f) by A46,A11,A41
        .= (hh(*)gg)(*)ff by A53,A10,A52,CAT_1:def 1;
    end;
A62:  B is reflexive
    proof let b be Element of B;
      reconsider bb=b as Element of O;
      reconsider ii = [id bb`1, id bb`2] as Morphism of B;
A63:    cod ii = c.(id bb`1, id bb`2)
         .= [cod id bb`1,cod id bb`2] by FUNCT_3:75
         .= [bb`1,cod id bb`2]
         .= [bb`1,bb`2]
         .= bb by MCART_1:21;
      dom ii = d.(id bb`1, id bb`2)
         .= [dom id bb`1,dom id bb`2] by FUNCT_3:75
         .= [bb`1,dom id bb`2]
         .= [bb`1,bb`2]
         .= bb by MCART_1:21;
      then [id bb`1,id bb`2] in Hom(b,b) by A63;
     hence Hom(b,b)<>{};
    end;
   B is with_identities
   proof let a be Element of B;
     reconsider aa=a as Element of O;
     reconsider ii = [id aa`1, id aa`2] as Morphism of B;
A64:    cod ii = c.(id aa`1, id aa`2)
         .= [cod id aa`1,cod id aa`2] by FUNCT_3:75
         .= [aa`1,cod id aa`2]
         .= [aa`1,aa`2]
         .= aa by MCART_1:21;
A65:   dom ii = d.(id aa`1, id aa`2)
         .= [dom id aa`1,dom id aa`2] by FUNCT_3:75
         .= [aa`1,dom id aa`2]
         .= [aa`1,aa`2]
         .= aa by MCART_1:21;
     then reconsider ii = [id aa`1, id aa`2] as Morphism of a,a by A64,CAT_1:4;
    take ii;
    let b be Element of B;
    thus Hom(a,b)<>{} implies for g being Morphism of a,b holds g(*)ii = g
     proof assume
A66:     Hom(a,b)<>{};
      let g be Morphism of a,b;
      reconsider gg = g as Element of M;
      cod ii = dom g by A66,A64,CAT_1:5;
      then
A67:   [g,ii] in dom p by A6;
      then
A68:   dom gg`1 = cod [id aa`1, id aa`2]`1 by A4
              .= cod id aa`1;
A69:   (the Comp of C).(gg`1,id aa`1) = (gg`1)(*)id aa`1 by A68,CAT_1:16
             .= gg`1 by A68,CAT_1:22;
A70:   dom gg`2 = cod [id aa`1, id aa`2]`2 by A4,A67
              .= cod id aa`2;
A71:   (the Comp of D).(gg`2,id aa`2) = (gg`2)(*)id aa`2 by A70,CAT_1:16
             .= gg`2 by A70,CAT_1:22;
A72:     cod ii = dom g by A64,A66,CAT_1:5;
       then [g,ii] in dom the Comp of B by A6;
      hence g(*)ii = p.(g,ii) by CAT_1:def 1
            .= [(the Comp of C).(gg`1,[id aa`1, id aa`2]`1),
                (the Comp of D).(gg`2,[id aa`1, id aa`2]`2)]
                         by A11,A72
            .= g by A69,A71,MCART_1:21;
     end;
    assume
A73:     Hom(b,a)<>{};
      let g be Morphism of b,a;
      reconsider gg = g as Element of M;
      dom ii = cod g by A73,A65,CAT_1:5;
      then
A74:   [ii,g] in dom p by A6;
      then
A75:   cod gg`1 = dom [id aa`1, id aa`2]`1 by A4
              .= dom id aa`1;
A76:   (the Comp of C).(id aa`1,gg`1) = (id aa`1)(*)gg`1 by A75,CAT_1:16
             .= gg`1 by A75,CAT_1:21;
A77:   cod gg`2 = dom [id aa`1, id aa`2]`2 by A4,A74
              .= dom id aa`2;
A78:   (the Comp of D).(id aa`2,gg`2) = (id aa`2)(*)gg`2 by A77,CAT_1:16
             .= gg`2 by A77,CAT_1:21;
A79:     dom ii = cod g by A65,A73,CAT_1:5;
       then [ii,g] in dom the Comp of B by A6;
      hence ii(*)g = p.(ii,g) by CAT_1:def 1
            .= [(the Comp of C).([id aa`1, id aa`2]`1,gg`1),
                (the Comp of D).([id aa`1, id aa`2]`2,gg`2)]
                         by A11,A79
            .= g by A76,A78,MCART_1:21;
   end;
    hence thesis by A6,A32,A35,A62;
  end;
end;

theorem
  the carrier of [:C,D:] = [:the carrier of C,the carrier of D:] & the
  carrier' of [:C,D:] = [:the carrier' of C,the carrier' of D:] & the Source of
  [:C,D:] = [:the Source of C,the Source of D:] & the Target of [:C,D:] = [:the
Target of C,the Target of D:] & the Comp of [:C,D:] = |:the Comp of C, the Comp
  of D:|;

definition
  let C,D;
  let c be Object of C;
  let d be Object of D;
  redefine func [c,d] -> Object of [:C,D:];
  coherence
    proof
     thus [c,d] is Object of [:C,D:];
    end;
end;

::$CT

theorem
  for cd being Object of [:C,D:] ex c being Object of C, d being Object
  of D st cd = [c,d] by DOMAIN_1:1;

definition
  let C,D;
  let f be Morphism of C;
  let g be Morphism of D;
  redefine func [f,g] -> Morphism of [:C,D:];
  coherence
   proof
    thus [f,g] is Morphism of [:C,D:];
   end;
end;

::$CT

theorem
  for fg being Morphism of [:C,D:] ex f being (Morphism of C), g being
  Morphism of D st fg = [f,g] by DOMAIN_1:1;

theorem Th22:
  for f being Morphism of C for g being Morphism of D
   holds dom [f,g] = [dom f,dom g] & cod [f,g] = [cod f,cod g]
proof
  let f be Morphism of C;
  let g be Morphism of D;
  thus dom [f,g] = [:the Source of C,the Source of D:].(f,g)
    .= [dom f,dom g] by FUNCT_3:75;
  thus cod [f,g] = [:the Target of C,the Target of D:].(f,g)
    .= [cod f,cod g] by FUNCT_3:75;
end;

theorem Th23:
  for f,f9 being Morphism of C for g,g9 being Morphism of D st dom
  f9 = cod f & dom g9 = cod g holds [f9,g9](*)[f,g] = [f9(*)f,g9(*)g]
proof
  let f,f9 be Morphism of C;
  let g,g9 be Morphism of D;
  assume that
A1: dom f9 = cod f and
A2: dom g9 = cod g;
A3: [f9,f] in dom(the Comp of C) & [g9,g] in dom(the Comp of D) by A1,A2,
CAT_1:15;
  dom [f9,g9] = [dom f9,dom g9] & cod [f,g] = [cod f,cod g] by Th22;
  hence
  [f9,g9](*)[f,g] = |:the Comp of C, the Comp of D:|.([f9,g9],[f,g])
     by A1,A2,CAT_1:16
    .= [(the Comp of C).(f9,f),(the Comp of D).(g9,g)] by A3,FUNCT_4:def 3
    .= [f9(*)f,(the Comp of D).(g9,g)] by A1,CAT_1:16
    .= [f9(*)f,g9(*)g] by A2,CAT_1:16;
end;

theorem Th24:
  for f,f9 being Morphism of C for g,g9 being Morphism of D st dom
  [f9,g9] = cod [f,g] holds [f9,g9](*)[f,g] = [f9(*)f,g9(*)g]
proof
  let f,f9 be Morphism of C;
  let g,g9 be Morphism of D such that
A1: dom [f9,g9] = cod [f,g];
  [dom f9,dom g9] = dom [f9,g9] & cod [f,g] = [cod f,cod g] by Th22;
  then dom f9 = cod f & dom g9 = cod g by A1,XTUPLE_0:1;
  hence thesis by Th23;
end;

theorem Th25:
  for c being Object of C, d being Object of D holds id [c,d] = [id c,id d]
proof
  let c being Object of C;
  let d being Object of D;
A1:  dom [id c,id d] = [dom id c,dom id d] by Th22
     .= [c,dom id d]
     .= [c,d];
    cod [id c,id d] = [cod id c,cod id d] by Th22
     .= [c,cod id d]
     .= [c,d];
   then reconsider m = [id c,id d] as Morphism of [c,d],[c,d] by A1,CAT_1:4;
   for b being Object of [:C,D:] holds
     (Hom([c,d],b) <> {} implies
       for f being Morphism of [c,d],b holds f(*)[id c,id d] = f)
   & (Hom(b,[c,d]) <> {} implies
     for f being Morphism of b,[c,d] holds [id c,id d](*)f = f)
   proof let b be Object of [:C,D:];
    thus Hom([c,d],b) <> {} implies
     for f being Morphism of [c,d],b holds f(*)[id c,id d] = f
      proof assume
A2:     Hom([c,d],b) <> {};
       let f be Morphism of [c,d],b;
        consider fc being (Morphism of C), fd being Morphism of D such that
A3:      f = [fc,fd] by DOMAIN_1:1;
A4:      [c,d] = dom f by A2,CAT_1:5 .= [dom fc,dom fd] by A3,Th22;
        then
A5:      c = dom fc by XTUPLE_0:1;
        then
A6:      cod id c = dom fc;
A7:      d = dom fd by A4,XTUPLE_0:1;
        then cod id d = dom fd;
       hence f(*)[id c,id d] = [fc(*)id c,fd(*)id d] by A3,A6,Th23
            .= [fc,fd(*)id d] by A5,CAT_1:22
            .= f by A3,A7,CAT_1:22;
      end;
    assume
A8:     Hom(b,[c,d]) <> {};
       let f be Morphism of b,[c,d];
        consider fc being (Morphism of C), fd being Morphism of D such that
A9:      f = [fc,fd] by DOMAIN_1:1;
A10:      [c,d] = cod f by A8,CAT_1:5 .= [cod fc,cod fd] by A9,Th22;
        then
A11:      c = cod fc by XTUPLE_0:1;
        then
A12:      dom id c = cod fc;
A13:      d = cod fd by A10,XTUPLE_0:1;
        then dom id d = cod fd;
       hence [id c,id d](*)f = [(id c)(*)fc,(id d)(*)fd] by A9,A12,Th23
            .= [fc,(id d)(*)fd] by A11,CAT_1:21
            .= f by A9,A13,CAT_1:21;
   end;
   then m = id[c,d] by CAT_1:def 12;
  hence thesis;
end;

theorem
  for c,c9 being Object of C, d,d9 being Object of D
   holds Hom([c,d],[c9,d9]) = [:Hom(c,c9),Hom(d,d9):]
proof
  let c,c9 be Object of C, d,d9 be Object of D;
  now
    let x be object;
    thus x in Hom([c,d],[c9,d9]) implies x in [:Hom(c,c9),Hom(d,d9):]
    proof
      assume
A1:   x in Hom([c,d],[c9,d9]);
      then reconsider fg = x as Morphism of [c,d],[c9,d9] by CAT_1:def 5;
A2:   dom fg = [c,d] by A1,CAT_1:1;
A3:   cod fg = [c9,d9] by A1,CAT_1:1;
      consider x1,x2 being object such that
A4:   x1 in the carrier' of C and
A5:   x2 in the carrier' of D and
A6:   fg = [x1,x2] by ZFMISC_1:def 2;
      reconsider g = x2 as Morphism of D by A5;
      reconsider f = x1 as Morphism of C by A4;
A7:   cod fg = [cod f,cod g] by A6,Th22;
      then
A8:   cod f = c9 by A3,XTUPLE_0:1;
A9:   cod g = d9 by A3,A7,XTUPLE_0:1;
A10:  dom fg = [dom f,dom g] by A6,Th22;
      then dom g = d by A2,XTUPLE_0:1;
      then
A11:  g in Hom(d,d9) by A9;
      dom f = c by A2,A10,XTUPLE_0:1;
      then f in Hom(c,c9) by A8;
      hence thesis by A6,A11,ZFMISC_1:87;
    end;
    assume x in [:Hom(c,c9),Hom(d,d9):];
    then consider x1,x2 being object such that
A12: x1 in Hom(c,c9) and
A13: x2 in Hom(d,d9) and
A14: x = [x1,x2] by ZFMISC_1:def 2;
    reconsider g = x2 as Morphism of d,d9 by A13,CAT_1:def 5;
    reconsider f = x1 as Morphism of c,c9 by A12,CAT_1:def 5;
    cod f = c9 & cod g = d9 by A12,A13,CAT_1:1;
    then
A15: cod [f,g] = [c9,d9] by Th22;
    dom f = c & dom g = d by A12,A13,CAT_1:1;
    then dom [f,g] = [c,d] by Th22;
    hence x in Hom([c,d],[c9,d9]) by A14,A15;
  end;
  hence thesis by TARSKI:2;
end;

theorem
  for c,c9 being Object of C, f being Morphism of c,c9, d,d9 being
  Object of D, g being Morphism of d,d9 st Hom(c,c9) <> {} & Hom(d,d9) <> {}
  holds [f,g] is Morphism of [c,d],[c9,d9]
proof
  let c,c9 be Object of C, f be Morphism of c,c9, d,d9 be Object of D, g be
  Morphism of d,d9;
  assume
A1: Hom(c,c9) <> {} & Hom(d,d9) <> {};
  then cod f = c9 & cod g = d9 by CAT_1:5;
  then
A2: cod [f,g] = [c9,d9] by Th22;
  dom f = c & dom g = d by A1,CAT_1:5;
  then dom [f,g] = [c,d] by Th22;
  hence thesis by A2,CAT_1:4;
end;

:: Bifunctors

definition
  let C,C9,D;
  let S being Functor of [:C,C9:],D;
  let m be Morphism of C;
  let m9 be Morphism of C9;
  redefine func S.(m,m9) -> Morphism of D;
  coherence
  proof
    S.(m,m9) = S.[m,m9];
    hence thesis;
  end;
end;

theorem Th28:
  for S being Functor of [:C,C9:],D, c being Object of C holds (
  curry S).(id c) is Functor of C9,D
proof
  let S be Functor of [:C,C9:],D, c be Object of C;
  reconsider S9 = S as Function of [:the carrier' of C,the carrier' of C9:],
  the carrier' of D;
  reconsider T = (curry S9).(id c) as Function of the carrier' of C9,the
  carrier' of D;
  now
    thus for c9 being Object of C9 ex d being Object of D st T.(id c9) = id d
    proof
      let c9 be Object of C9;
      consider d being Object of D such that
A1:   S.(id [c,c9]) = id d by CAT_1:62;
      take d;
      thus T.(id c9) = S.(id c,id c9) by FUNCT_5:69
        .= id d by A1,Th25;
    end;
A2: dom id c = c & cod id c = c;
    thus for f being Morphism of C9 holds T.(id dom f) = id dom (T.f) & T.(id
    cod f) = id cod (T.f)
    proof
      let f be Morphism of C9;
      thus T.(id dom f) = S.(id c,id dom f) by FUNCT_5:69
        .= S.(id [c,dom f]) by Th25
        .= S.(id [dom id c,dom f])
        .= S.(id dom [id c,f]) by Th22
        .= id dom (S.(id c,f)) by CAT_1:63
        .= id dom (T.f) by FUNCT_5:69;
      thus T.(id cod f) = S.(id c,id cod f) by FUNCT_5:69
        .= S.(id [c,cod f]) by Th25
        .= S.(id [cod id c,cod f])
        .= S.(id cod [id c,f]) by Th22
        .= id cod (S.(id c,f)) by CAT_1:63
        .= id cod (T.f) by FUNCT_5:69;
    end;
    let f,g be Morphism of C9 such that
A3: dom g = cod f;
    Hom(c,c) <> {};
    then
A4: (id c)*(id c) = (id c)(*)(id c) by CAT_1:def 13;
A5: dom [id c,g] = [dom id c,dom g] & cod [id c,f] = [cod id c, cod f] by Th22;
    thus T.(g(*)f) = S.((id c)*(id c),g(*)f) by FUNCT_5:69
      .= S.([id c,g](*)[id c,f]) by A3,A2,A4,Th23
      .= (S.(id c,g))(*)(S.(id c,f)) by A3,A5,CAT_1:64
      .= (T.g)(*)(S.(id c,f)) by FUNCT_5:69
      .= (T.g)(*)(T.f) by FUNCT_5:69;
  end;
  hence thesis by CAT_1:61;
end;

theorem Th29:
  for S being Functor of [:C,C9:],D, c9 being Object of C9 holds (
  curry' S).(id c9) is Functor of C,D
proof
  let S be Functor of [:C,C9:],D, c9 be Object of C9;
  reconsider S9 = S as Function of [:the carrier' of C,the carrier' of C9:],
  the carrier' of D;
  reconsider T = (curry' S9).(id c9) as Function of the carrier' of C,the
  carrier' of D;
  now
    thus for c being Object of C ex d being Object of D st T.(id c) = id d
    proof
      let c be Object of C;
      consider d being Object of D such that
A1:   S.(id [c,c9]) = id d by CAT_1:62;
      take d;
      thus T.(id c) = S.(id c,id c9) by FUNCT_5:70
        .= id d by A1,Th25;
    end;
A2: dom id c9 = c9 & cod id c9 = c9;
    thus for f being Morphism of C holds T.(id dom f) = id dom (T.f) & T.(id
    cod f) = id cod (T.f)
    proof
      let f be Morphism of C;
      thus T.(id dom f) = S.(id dom f,id c9) by FUNCT_5:70
        .= S.(id [dom f,c9]) by Th25
        .= S.(id [dom f,dom id c9])
        .= S.(id dom [f,id c9]) by Th22
        .= id dom (S.(f,id c9)) by CAT_1:63
        .= id dom (T.f) by FUNCT_5:70;
      thus T.(id cod f) = S.(id cod f,id c9) by FUNCT_5:70
        .= S.(id [cod f,c9]) by Th25
        .= S.(id [cod f,cod id c9])
        .= S.(id cod [f,id c9]) by Th22
        .= id cod (S.(f,id c9)) by CAT_1:63
        .= id cod (T.f) by FUNCT_5:70;
    end;
    let f,g be Morphism of C such that
A3: dom g = cod f;
    Hom(c9,c9) <> {};
    then
A4: (id c9)*(id c9) = (id c9)(*)(id c9) by CAT_1:def 13;
A5: dom [g,id c9] = [dom g,dom id c9] & cod [f,id c9] = [cod f,cod id c9]
    by Th22;
    thus T.(g(*)f) = S.(g(*)f,(id c9)*(id c9)) by FUNCT_5:70
      .= S.([g,id c9](*)[f,id c9]) by A3,A2,A4,Th23
      .= (S.(g,id c9))(*)(S.(f,id c9)) by A3,A5,CAT_1:64
      .= (T.g)(*)(S.(f,id c9)) by FUNCT_5:70
      .= (T.g)(*)(T.f) by FUNCT_5:70;
  end;
  hence thesis by CAT_1:61;
end;

:: Partial Functors

definition
  let C,C9,D;
  let S be Functor of [:C,C9:],D, c be Object of C;
  func S?-c -> Functor of C9,D equals
  (curry S).(id c);
  coherence by Th28;
end;

theorem
  for S being Functor of [:C,C9:],D, c being Object of C, f being
  Morphism of C9 holds (S?-c).f = S.(id c,f) by FUNCT_5:69;

theorem
  for S being Functor of [:C,C9:],D, c being Object of C, c9 being
  Object of C9 holds (Obj S?-c).c9 = (Obj S).(c,c9)
proof
  let S be Functor of [:C,C9:],D, c be Object of C, c9 be Object of C9;
  (S?-c).(id c9) = S.(id c,id c9) by FUNCT_5:69
    .= S.(id [c,c9]) by Th25
    .= id ((Obj S).[c,c9]) by CAT_1:68;
  hence thesis by CAT_1:67;
end;

definition
  let C,C9,D;
  let S be Functor of [:C,C9:],D, c9 be Object of C9;
  func S-?c9 -> Functor of C,D equals
  (curry' S).(id c9);
  coherence by Th29;
end;

theorem
  for S being Functor of [:C,C9:],D, c9 being Object of C9, f being
  Morphism of C holds (S-?c9).f = S.(f,id c9) by FUNCT_5:70;

theorem
  for S being Functor of [:C,C9:],D, c being Object of C, c9 being
  Object of C9 holds (Obj S-?c9).c = (Obj S).(c,c9)
proof
  let S be Functor of [:C,C9:],D, c be Object of C, c9 be Object of C9;
  (S-?c9).(id c) = S.(id c,id c9) by FUNCT_5:70
    .= S.(id [c,c9]) by Th25
    .= id ((Obj S).[c,c9]) by CAT_1:68;
  hence thesis by CAT_1:67;
end;

theorem
  for L being Function of the carrier of C,Funct(B,D), M being Function
of the carrier of B,Funct(C,D) st ( for c being Object of C,b being Object of B
  holds (M.b).(id c) = (L.c).(id b) ) & ( for f being Morphism of B for g being
Morphism of C
  holds ((M.(cod f)).g)(*)((L.(dom g)).f) = ((L.(cod g)).f)(*)((M.(dom
  f)).g) ) ex S being Functor of [:B,C:],D st for f being Morphism of B for g
  being Morphism of C holds S.(f,g) = ((L.(cod g)).f)(*)((M.(dom f)).g)
proof
  deffunc Mor(Category) = the carrier' of $1;
  let L be Function of the carrier of C,Funct(B,D), M be Function of the
  carrier of B,Funct(C,D) such that
A1: for c being Object of C, b being Object of B holds (M.b).(id c) = (L
  .c).(id b) and
A2: for f being Morphism of B for g being Morphism of C holds ((M.(cod f
  )).g)(*)((L.(dom g)).f) = ((L.(cod g)).f)(*)((M.(dom f)).g);
  deffunc F(Element of Mor(B), Element of Mor(C))
    = ((L.(cod $2)).$1)(*)((M.(dom
  $1)).$2);
  consider S being Function of [:Mor(B),Mor(C):],Mor(D) such that
A3: for f being Morphism of B for g being Morphism of C holds S.(f,g) =
  F(f,g) from BINOP_1:sch 4;
  reconsider T = S as Function of Mor([:B,C:]),Mor(D);
  now
    thus for bc being Object of [:B,C:] ex d being Object of D st T.(id bc) =
    id d
    proof
      let bc be Object of [:B,C:];
      consider b being Object of B, c being Object of C such that
A4:   bc = [b,c] by DOMAIN_1:1;
      consider d being Object of D such that
A5:   (L.c).(id b) = id d by CAT_1:62;
      take d;
      Hom(d,d) <> {};
      then
A6:   (id d)*(id d) = (id d)(*)(id d) by CAT_1:def 13;
A7:   cod id c = c & dom id b = b;
      (L.c).(id b) = (M.b).(id c) by A1;
      then T.(id b,id c) = id d by A3,A5,A6,A7;
      hence thesis by A4,Th25;
    end;
    thus for fg being Morphism of [:B,C:] holds T.(id dom fg) = id dom (T.fg)
    & T.(id cod fg) = id cod (T.fg)
    proof
      let fg be Morphism of [:B,C:];
      consider f being (Morphism of B), g being Morphism of C such that
A8:   fg = [f,g] by DOMAIN_1:1;
      set b = dom f, c = dom g;
      set g9 = id c, f9= id b;
A9:   Hom(dom ((M.b).g),dom ((M.b).g)) <> {};
      id dom ((L.(cod g)).f) = (L.(cod g)).(id dom f) by CAT_1:63
        .= (M.(dom f)).(id cod g) by A1
        .= id cod ((M.(dom f)).g) by CAT_1:63;
      then
A10:  dom ((L.(cod g)).f) = cod ((M.(dom f)).g) by CAT_1:59;
      thus T.(id (dom fg)) = S.(id [b,c]) by A8,Th22
        .= S.(id b,id c) by Th25
        .= ((L.(cod g9)).f9)(*)((M.(dom f9)).g9) by A3
        .= ((L.c).f9)(*)((M.(dom f9)).g9)
        .= ((L.c).f9)(*)((M.b).g9)
        .= ((M.b).g9)(*)((M.b).g9) by A1
        .= (id dom ((M.b).g))(*)((M.b).g9) by CAT_1:63
        .= (id dom ((M.b).g))(*)(id dom((M.b).g)) by CAT_1:63
        .= (id dom ((M.b).g))*(id dom((M.b).g)) by A9,CAT_1:def 13
        .= id dom (((L.(cod g)).f)(*)((M.(dom f)).g)) by A10,CAT_1:17
        .= id dom (S.(f,g)) by A3
        .= id dom(T.fg) by A8;
      set b = cod f, c = cod g;
      set g9 = id c, f9= id b;
A11:  Hom(cod ((L.c).f),cod ((L.c).f)) <> {};
      thus T.(id (cod fg)) = S.(id [b,c]) by A8,Th22
        .= S.(id b,id c) by Th25
        .= ((L.(cod g9)).f9)(*)((M.(dom f9)).g9) by A3
        .= ((L.c).f9)(*)((M.(dom f9)).g9)
        .= ((L.c).f9)(*)((M.(cod f)).g9)
        .= ((L.c).f9)(*)((L.c).f9) by A1
        .= (id cod (((L.c).f))(*)((L.c).f9)) by CAT_1:63
        .= (id cod ((L.c).f))(*)(id cod((L.c).f)) by CAT_1:63
        .= (id cod ((L.c).f))*(id cod ((L.c).f)) by A11,CAT_1:def 13
        .= id cod (((L.(cod g)).f)(*)((M.(dom f)).g)) by A10,CAT_1:17
        .= id cod (S.(f,g)) by A3
        .= id cod (T.fg) by A8;
    end;
    let fg1,fg2 be Morphism of [:B,C:] such that
A12: dom fg2 = cod fg1;
    consider f1 being (Morphism of B), g1 being Morphism of C such that
A13: fg1 = [f1,g1] by DOMAIN_1:1;
    consider f2 being (Morphism of B), g2 being Morphism of C such that
A14: fg2 = [f2,g2] by DOMAIN_1:1;
A15: [cod f1,cod g1] = cod fg1 by A13,Th22;
    set L1 = L.(cod g1), L2 = L.(cod g2), M1 = M.(dom f1), M2 = M.(dom f2);
A16: [dom f2,dom g2] = dom fg2 by A14,Th22;
    then
A17: dom f2 = cod f1 by A12,A15,XTUPLE_0:1;
    then
A18: dom(L2.f2) = cod (L2.f1) by CAT_1:64;
    id dom (L1.f1) = L1.(id dom f1) by CAT_1:63
      .= M1.(id cod g1) by A1
      .= id cod (M1.g1) by CAT_1:63;
    then
A19: dom (L1.f1) = cod (M1.g1) by CAT_1:59;
    then
A20: cod ((L1.f1)(*)(M1.g1)) = cod (L1.f1) by CAT_1:17;
A21: dom g2 = cod g1 by A12,A16,A15,XTUPLE_0:1;
    then
A22: dom(M1.g2) = cod (M1.g1) by CAT_1:64;
    then
A23: cod ((M1.g2)(*)(M1.g1)) = cod(M1.g2) by CAT_1:17;
    id dom (M2.g2) = M2.(id dom g2) by CAT_1:63
      .= L1.(id cod f1) by A1,A17,A21
      .= id cod (L1.f1) by CAT_1:63;
    then
A24: dom (M2.g2) = cod(L1.f1) by CAT_1:59;
    id dom (L2.f2) = L2.(id dom f2) by CAT_1:63
      .= M2.(id cod g2) by A1
      .= id cod (M2.g2) by CAT_1:63;
    then
A25: dom (L2.f2) = cod (M2.g2) by CAT_1:59;
    set f = f2(*)f1, g = g2(*)g1;
    id dom (L2.f1) = L2.(id dom f1) by CAT_1:63
      .= M1.(id cod g2) by A1
      .= id cod (M1.g2) by CAT_1:63;
    then
A26: dom (L2.f1) = cod (M1.g2) by CAT_1:59;
    thus T.(fg2(*)fg1) = S.(f,g) by A12,A13,A14,Th24
      .= ((L.(cod g)).f)(*)((M.(dom f)).g) by A3
      .= ((L.(cod g2)).f)(*)((M.(dom f)).g) by A21,CAT_1:17
      .= ((L.(cod g2)).f)(*)((M.(dom f1)).g) by A17,CAT_1:17
      .= ((L2.f2)(*)(L2.f1))(*)(M1.g) by A17,CAT_1:64
      .= ((L2.f2)(*)(L2.f1))(*)((M1.g2)(*)(M1.g1)) by A21,CAT_1:64
      .= (L2.f2)(*)((L2.f1)(*)((M1.g2)(*)(M1.g1))) by A18,A23,A26,CAT_1:18
      .= (L2.f2)(*)(((L2.f1)(*)(M1.g2))(*)(M1.g1)) by A22,A26,CAT_1:18
      .= (L2.f2)(*)(((M2.g2)(*)(L1.f1))(*)(M1.g1)) by A2,A17,A21
      .= (L2.f2)(*)((M2.g2)(*)((L1.f1)(*)(M1.g1))) by A19,A24,CAT_1:18
      .= ((L2.f2)(*)(M2.g2))(*)((L1.f1)(*)(M1.g1)) by A24,A25,A20,CAT_1:18
      .= ((L2.f2)(*)(M2.g2))(*)(S.(f1,g1)) by A3
      .= (S.(f2,g2))(*)(T.fg1) by A3,A13
      .= (T.fg2)(*)(T.fg1) by A14;
  end;
  then reconsider T as Functor of [:B,C:],D by CAT_1:61;
  take T;
  thus thesis by A3;
end;

theorem
  for L being Function of the carrier of C,Funct(B,D),
      M being Function of the carrier of B,Funct(C,D)
   st ex S being Functor of [:B,C:],D st
    for c being Object of C,b being Object of B
     holds S-?c = L.c & S?-b = M.b
  for f being Morphism of B for g being Morphism of C
   holds ((M.(cod f)).g)(*)((L.(dom g)).f) =
     ((L.(cod g)).f)(*)((M.(dom f)).g)
proof
  let L be Function of the carrier of C,Funct(B,D), M be Function of the
  carrier of B,Funct(C,D);
  given S be Functor of [:B,C:],D such that
A1: for c being Object of C, b being Object of B holds S-?c = L.c & S?-b = M.b;
  let f be Morphism of B;
  let g be Morphism of C;
  dom id cod f = cod f;
  then
A2: dom [id cod f,g] = [cod f,dom g] by Th22;
  cod id dom g = dom g;
  then
A3: cod [f,id dom g] = [cod f, dom g] by Th22;
  cod id dom f = dom f;
  then
A4: cod [id dom f,g] = [dom f,cod g] by Th22;
  dom id cod g = cod g;
  then
A5: dom [f,id cod g] = [dom f,cod g] by Th22;
  thus ((M.(cod f)).g)(*)((L.(dom g)).f)
     = ((S?-(cod f)).g)(*)((L.(dom g)).f) by A1
    .= ((S?-(cod f)).g)(*)((S-?(dom g)).f) by A1
    .= (S.(id cod f,g))(*)((S-?(dom g)).f) by FUNCT_5:69
    .= (S.(id cod f,g))(*)(S.(f,id dom g)) by FUNCT_5:70
    .= S.([id cod f,g](*)[f,id dom g]) by A2,A3,CAT_1:64
    .= S.[(id cod f)(*)f,g(*)(id dom g)] by A2,A3,Th24
    .= S.[f,g(*)(id dom g)] by CAT_1:21
    .= S.[f,g] by CAT_1:22
    .= S.[f(*)(id dom f),g] by CAT_1:22
    .= S.[f(*)(id dom f),(id cod g)(*)g ] by CAT_1:21
    .= S.([f,id cod g](*)[id dom f,g]) by A5,A4,Th24
    .= (S.(f,id cod g))(*)(S.[id dom f,g]) by A5,A4,CAT_1:64
    .= ((S-?(cod g)).f)(*)(S.(id dom f,g)) by FUNCT_5:70
    .= ((S-?(cod g)).f)(*)((S?-(dom f)).g) by FUNCT_5:69
    .= ((L.(cod g)).f)(*)((S?-(dom f)).g) by A1
    .= ((L.(cod g)).f)(*)((M.(dom f)).g) by A1;
end;

definition
  let C,D;
  func pr1(C,D) -> Functor of [:C,D:],C equals
   pr1(the carrier' of C,the carrier' of D);
  coherence
 proof
  reconsider T = pr1(the carrier' of C,the carrier' of D) as Function of the
  carrier' of [:C,D:],the carrier' of C;
  now
    thus for cd being Object of [:C,D:] ex c being Object of C st T.(id cd) =
    id c
    proof
      let cd be Object of [:C,D:];
      consider c being Object of C,d being Object of D such that
A1:   cd = [c,d] by DOMAIN_1:1;
A2:   T.(id c,id d) = id c by FUNCT_3:def 4;
      id cd = [id c,id d] by A1,Th25;
      hence thesis by A2;
    end;
    thus for fg being Morphism of [:C,D:] holds T.(id dom fg) = id dom (T.fg)
    & T.(id cod fg) = id cod (T.fg)
    proof
      let fg be Morphism of [:C,D:];
      consider f being (Morphism of C), g being Morphism of D such that
A3:   fg = [f,g] by DOMAIN_1:1;
      T.(f,g) = T.fg by A3;
      then
A4:   T.fg = f by FUNCT_3:def 4;
      dom [f,g] = [dom f,dom g] by Th22;
      hence T.(id dom fg) = T.(id dom f,id dom g) by A3,Th25
        .= id dom(T.fg) by A4,FUNCT_3:def 4;
      cod [f,g] = [cod f,cod g] by Th22;
      hence T.(id cod fg) = T.(id cod f,id cod g) by A3,Th25
        .= id cod(T.fg) by A4,FUNCT_3:def 4;
    end;
    let fg,fg9 be Morphism of [:C,D:] such that
A5: dom fg9 = cod fg;
    consider f being (Morphism of C), g being Morphism of D such that
A6: fg = [f,g] by DOMAIN_1:1;
    T.(f,g) = T.fg by A6;
    then
A7: T.fg = f by FUNCT_3:def 4;
    consider f9 being (Morphism of C), g9 being Morphism of D such that
A8: fg9 = [f9,g9] by DOMAIN_1:1;
    T.(f9,g9) = T.fg9 by A8;
    then
A9: T.fg9 = f9 by FUNCT_3:def 4;
    dom [f9,g9] = [dom f9,dom g9] & cod [f,g] = [cod f,cod g] by Th22;
    then dom f9 = cod f & dom g9 = cod g by A5,A6,A8,XTUPLE_0:1;
    hence T.(fg9(*)fg) = T.(f9(*)f,g9(*)g) by A6,A8,Th23
      .= (T.fg9)(*)(T.fg) by A9,A7,FUNCT_3:def 4;
  end;
  hence thesis by CAT_1:61;
 end;
  func pr2(C,D) -> Functor of [:C,D:],D equals
   pr2(the carrier' of C,the carrier' of D);
  coherence
 proof
  reconsider T = pr2(the carrier' of C,the carrier' of D)
   as Function of the carrier' of [:C,D:],the carrier' of D;
  now
    thus for cd being Object of [:C,D:] ex d being Object of D st T.(id cd) =
    id d
    proof
      let cd be Object of [:C,D:];
      consider c being Object of C,d being Object of D such that
A10:   cd = [c,d] by DOMAIN_1:1;
A11:   T.(id c,id d) = id d by FUNCT_3:def 5;
      id cd = [id c,id d] by A10,Th25;
      hence thesis by A11;
    end;
    thus for fg being Morphism of [:C,D:] holds T.(id dom fg) = id dom (T.fg)
    & T.(id cod fg) = id cod (T.fg)
    proof
      let fg be Morphism of [:C,D:];
      consider f being (Morphism of C), g being Morphism of D such that
A12:   fg = [f,g] by DOMAIN_1:1;
      T.(f,g) = T.fg by A12;
      then
A13:   T.fg = g by FUNCT_3:def 5;
      dom [f,g] = [dom f,dom g] by Th22;
      hence T.(id dom fg) = T.(id dom f,id dom g) by A12,Th25
        .= id dom(T.fg) by A13,FUNCT_3:def 5;
      cod [f,g] = [cod f,cod g] by Th22;
      hence T.(id cod fg) = T.(id cod f,id cod g) by A12,Th25
        .= id cod(T.fg) by A13,FUNCT_3:def 5;
    end;
    let fg,fg9 be Morphism of [:C,D:] such that
A14: dom fg9 = cod fg;
    consider f being (Morphism of C), g being Morphism of D such that
A15: fg = [f,g] by DOMAIN_1:1;
    T.(f,g) = T.fg by A15;
    then
A16: T.fg = g by FUNCT_3:def 5;
    consider f9 being (Morphism of C), g9 being Morphism of D such that
A17: fg9 = [f9,g9] by DOMAIN_1:1;
    T.(f9,g9) = T.fg9 by A17;
    then
A18: T.fg9 = g9 by FUNCT_3:def 5;
    dom [f9,g9] = [dom f9,dom g9] & cod [f,g] = [cod f,cod g] by Th22;
    then dom f9 = cod f & dom g9 = cod g by A14,A15,A17,XTUPLE_0:1;
    hence T.(fg9(*)fg) = T.(f9(*)f,g9(*)g) by A15,A17,Th23
      .= (T.fg9)(*)(T.fg) by A18,A16,FUNCT_3:def 5;
  end;
  hence thesis by CAT_1:61;
 end;
end;

::$CT 2

theorem
  for c being Object of C, d being Object of D holds (Obj pr1(C,D)).(c,d ) = c
proof
  let c be Object of C, d be Object of D;
  id [c,d] = [id c,id d] & (pr1(C,D)).(id c,id d) = id c by Th25,FUNCT_3:def 4;
  hence thesis by CAT_1:67;
end;

theorem
  for c being Object of C, d being Object of D holds (Obj pr2(C,D)).(c,d ) = d
proof
  let c be Object of C, d be Object of D;
  id [c,d] = [id c,id d] & (pr2(C,D)).(id c,id d) = id d by Th25,FUNCT_3:def 5;
  hence thesis by CAT_1:67;
end;

definition
  let C,D,D9;
  let T be Functor of C,D, T9 be Functor of C,D9;
  redefine func <:T,T9:> -> Functor of C,[:D,D9:];
  coherence
 proof
  reconsider S = <:T,T9:> as
    Function of the carrier' of C,the carrier' of [:D,D9:];
  now
    thus for c being Object of C ex dd9 being Object of [:D,D9:] st S.(id c) =
    id dd9
    proof
      let c be Object of C;
      set d = (Obj T).c, d9 = (Obj T9).c;
      take dd9 = [d,d9];
      thus S.(id c) = [T.(id c),T9.(id c)] by FUNCT_3:59
        .= [id d,T9.(id c)] by CAT_1:68
        .= [id d,id d9] by CAT_1:68
        .= id dd9 by Th25;
    end;
    thus for f being Morphism of C holds S.(id dom f) = id dom (S.f) & S.(id
    cod f) = id cod (S.f)
    proof
      let f be Morphism of C;
      T.(id dom f) = id(dom(T.f)) & T9.(id dom f) = id(dom(T9.f)) by CAT_1:63;
      hence S.(id dom f) = [id(dom(T.f)),id(dom(T9.f))] by FUNCT_3:59
        .= id [dom(T.f),dom(T9.f)] by Th25
        .= id dom[T.f,T9.f] by Th22
        .= id dom (S.f) by FUNCT_3:59;
      T.(id cod f) = id(cod(T.f)) & T9.(id cod f) = id(cod(T9.f)) by CAT_1:63;
      hence S.(id cod f) = [id(cod(T.f)),id(cod(T9.f))] by FUNCT_3:59
        .= id [cod(T.f),cod(T9.f)] by Th25
        .= id cod [T.f,T9.f] by Th22
        .= id cod (S.f) by FUNCT_3:59;
    end;
    let f,g be Morphism of C;
    assume
A1: dom g = cod f;
    then
A2: dom(T.g) = cod(T.f) & dom(T9.g) = cod(T9.f) by CAT_1:64;
    T.(g(*)f) = (T.g)(*)(T.f) & T9.(g(*)f) = (T9.g)(*)(T9.f) by A1,CAT_1:64;
    hence S.(g(*)f) = [(T.g)(*)(T.f),(T9.g)(*)(T9.f)] by FUNCT_3:59
      .= [T.g,T9.g](*)[T.f,T9.f] by A2,Th23
      .= (S.g)(*)[T.f,T9.f] by FUNCT_3:59
      .= (S.g)(*)(S.f) by FUNCT_3:59;
  end;
  hence thesis by CAT_1:61;
end;
end;

::$CT

theorem
  for T being Functor of C,D, T9 being Functor of C,D9, c being Object
  of C holds (Obj <:T,T9:>).c = [(Obj T).c,(Obj T9).c]
proof
  let T be Functor of C,D, T9 be Functor of C,D9, c be Object of C;
A1: T.(id c) = id((Obj T).c) & T9.(id c) = id((Obj T9).c) by CAT_1:68;
  <:T,T9:>.(id c) = [T.(id c),T9.(id c)] & [id((Obj T).c),id((Obj T9).c)]
  = id [(Obj T).c,(Obj T9).c] by Th25,FUNCT_3:59;
  hence thesis by A1,CAT_1:67;
end;

theorem Th39:
  for T being Functor of C,D, T9 being Functor of C9,D9 holds [:T,
  T9:] = <:T*pr1(C,C9),T9*pr2(C,C9):>
proof
  let T be Functor of C,D, T9 be Functor of C9,D9;
  dom T = the carrier' of C & dom T9 = the carrier' of C9 by FUNCT_2:def 1;
  hence thesis by FUNCT_3:66;
end;

definition
  let C,C9,D,D9;
  let T be Functor of C,D, T9 be Functor of C9,D9;
  redefine func [:T,T9:] -> Functor of [:C,C9:],[:D,D9:];
  coherence
 proof
  [:T,T9:] = <:T*pr1(C,C9),T9*pr2(C,C9):> by Th39;
  hence thesis;
 end;
end;

::$CT

theorem
  for T being Functor of C,D, T9 being Functor of C9,D9, c being Object
of C, c9 being Object of C9 holds (Obj [:T,T9:]).(c,c9) = [(Obj T).c,(Obj T9).
  c9]
proof
  let T be Functor of C,D, T9 be Functor of C9,D9;
  let c be Object of C, c9 be Object of C9;
A1: T.(id c) = id((Obj T).c) & T9.(id c9) = id((Obj T9).c9) by CAT_1:68;
A2: [id((Obj T).c),id((Obj T9).c9)] = id [(Obj T).c,(Obj T9).c9] by Th25;
  [:T,T9:].(id c,id c9) = [T.(id c),T9.(id c9)] & [id c,id c9] = id [c,c9]
  by Th25,FUNCT_3:75;
  hence thesis by A1,A2,CAT_1:67;
end;