Theorem grictr 47507

Description: Graph isomorphism is transitive. (Contributed by AV, 5-Dec-2022.) (Revised by AV, 3-May-2025.)

Assertion

Ref	Expression
grictr	⊢ ((𝑅 ≃𝑔𝑟 𝑆 ∧ 𝑆 ≃𝑔𝑟 𝑇) → 𝑅 ≃𝑔𝑟 𝑇)

Proof of Theorem grictr

Dummy variables 𝑓 𝑔 are mutually distinct and distinct from all other variables.

Step	Hyp	Ref	Expression
1		brgric 47496	. 2 ⊢ (𝑅 ≃𝑔𝑟 𝑆 ↔ (𝑅 GraphIso 𝑆) ≠ ∅)
2		brgric 47496	. 2 ⊢ (𝑆 ≃𝑔𝑟 𝑇 ↔ (𝑆 GraphIso 𝑇) ≠ ∅)
3		n0 4346	. . 3 ⊢ ((𝑅 GraphIso 𝑆) ≠ ∅ ↔ ∃𝑔 𝑔 ∈ (𝑅 GraphIso 𝑆))
4		n0 4346	. . 3 ⊢ ((𝑆 GraphIso 𝑇) ≠ ∅ ↔ ∃𝑓 𝑓 ∈ (𝑆 GraphIso 𝑇))
5		exdistrv 1952	. . . 4 ⊢ (∃𝑔∃𝑓(𝑔 ∈ (𝑅 GraphIso 𝑆) ∧ 𝑓 ∈ (𝑆 GraphIso 𝑇)) ↔ (∃𝑔 𝑔 ∈ (𝑅 GraphIso 𝑆) ∧ ∃𝑓 𝑓 ∈ (𝑆 GraphIso 𝑇)))
6		grimco 47495	. . . . . . 7 ⊢ ((𝑓 ∈ (𝑆 GraphIso 𝑇) ∧ 𝑔 ∈ (𝑅 GraphIso 𝑆)) → (𝑓 ∘ 𝑔) ∈ (𝑅 GraphIso 𝑇))
7	6	ancoms 457	. . . . . 6 ⊢ ((𝑔 ∈ (𝑅 GraphIso 𝑆) ∧ 𝑓 ∈ (𝑆 GraphIso 𝑇)) → (𝑓 ∘ 𝑔) ∈ (𝑅 GraphIso 𝑇))
8		brgrici 47497	. . . . . 6 ⊢ ((𝑓 ∘ 𝑔) ∈ (𝑅 GraphIso 𝑇) → 𝑅 ≃𝑔𝑟 𝑇)
9	7, 8	syl 17	. . . . 5 ⊢ ((𝑔 ∈ (𝑅 GraphIso 𝑆) ∧ 𝑓 ∈ (𝑆 GraphIso 𝑇)) → 𝑅 ≃𝑔𝑟 𝑇)
10	9	exlimivv 1928	. . . 4 ⊢ (∃𝑔∃𝑓(𝑔 ∈ (𝑅 GraphIso 𝑆) ∧ 𝑓 ∈ (𝑆 GraphIso 𝑇)) → 𝑅 ≃𝑔𝑟 𝑇)
11	5, 10	sylbir 234	. . 3 ⊢ ((∃𝑔 𝑔 ∈ (𝑅 GraphIso 𝑆) ∧ ∃𝑓 𝑓 ∈ (𝑆 GraphIso 𝑇)) → 𝑅 ≃𝑔𝑟 𝑇)
12	3, 4, 11	syl2anb 596	. 2 ⊢ (((𝑅 GraphIso 𝑆) ≠ ∅ ∧ (𝑆 GraphIso 𝑇) ≠ ∅) → 𝑅 ≃𝑔𝑟 𝑇)
13	1, 2, 12	syl2anb 596	1 ⊢ ((𝑅 ≃𝑔𝑟 𝑆 ∧ 𝑆 ≃𝑔𝑟 𝑇) → 𝑅 ≃𝑔𝑟 𝑇)

Syntax hints:   → wi 4   ∧ wa 394  ∃wex 1774   ∈ wcel 2099   ≠ wne 2930  ∅c0 4322   class class class wbr 5145   ∘ ccom 5678  (class class class)co 7416   GraphIso cgrim 47476   ≃_𝑔𝑟 cgric 47477

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1790  ax-4 1804  ax-5 1906  ax-6 1964  ax-7 2004  ax-8 2101  ax-9 2109  ax-10 2130  ax-11 2147  ax-12 2167  ax-ext 2697  ax-sep 5296  ax-nul 5303  ax-pow 5361  ax-pr 5425  ax-un 7738

This theorem depends on definitions:  df-bi 206  df-an 395  df-or 846  df-3an 1086  df-tru 1537  df-fal 1547  df-ex 1775  df-nf 1779  df-sb 2061  df-mo 2529  df-eu 2558  df-clab 2704  df-cleq 2718  df-clel 2803  df-nfc 2878  df-ne 2931  df-ral 3052  df-rex 3061  df-rab 3420  df-v 3464  df-sbc 3776  df-csb 3892  df-dif 3949  df-un 3951  df-in 3953  df-ss 3963  df-nul 4323  df-if 4524  df-pw 4599  df-sn 4624  df-pr 4626  df-op 4630  df-uni 4906  df-iun 4995  df-br 5146  df-opab 5208  df-mpt 5229  df-id 5572  df-xp 5680  df-rel 5681  df-cnv 5682  df-co 5683  df-dm 5684  df-rn 5685  df-res 5686  df-ima 5687  df-suc 6374  df-iota 6498  df-fun 6548  df-fn 6549  df-f 6550  df-f1 6551  df-fo 6552  df-f1o 6553  df-fv 6554  df-ov 7419  df-oprab 7420  df-mpo 7421  df-1st 7995  df-2nd 7996  df-1o 8488  df-map 8849  df-grim 47479  df-gric 47482

This theorem is referenced by:  gricer  47508  grlictr  47541