MPE Home Metamath Proof Explorer < Previous   Next >
Nearby theorems
Mirrors  >  Home  >  MPE Home  >  Th. List  >  brfi1uzind Structured version   Visualization version   GIF version

Theorem brfi1uzind 13500
Description: Properties of a binary relation with a finite first component with at least L elements, proven by finite induction on the size of the first component. This theorem can be applied for graphs (as binary relation between the set of vertices and an edge function) with a finite number of vertices, usually with 𝐿 = 0 (see brfi1ind 13501) or 𝐿 = 1. (Contributed by Alexander van der Vekens, 7-Jan-2018.) (Proof shortened by AV, 23-Oct-2020.) (Revised by AV, 28-Mar-2021.)
Hypotheses
Ref Expression
brfi1uzind.r Rel 𝐺
brfi1uzind.f 𝐹 ∈ V
brfi1uzind.l 𝐿 ∈ ℕ0
brfi1uzind.1 ((𝑣 = 𝑉𝑒 = 𝐸) → (𝜓𝜑))
brfi1uzind.2 ((𝑣 = 𝑤𝑒 = 𝑓) → (𝜓𝜃))
brfi1uzind.3 ((𝑣𝐺𝑒𝑛𝑣) → (𝑣 ∖ {𝑛})𝐺𝐹)
brfi1uzind.4 ((𝑤 = (𝑣 ∖ {𝑛}) ∧ 𝑓 = 𝐹) → (𝜃𝜒))
brfi1uzind.base ((𝑣𝐺𝑒 ∧ (♯‘𝑣) = 𝐿) → 𝜓)
brfi1uzind.step ((((𝑦 + 1) ∈ ℕ0 ∧ (𝑣𝐺𝑒 ∧ (♯‘𝑣) = (𝑦 + 1) ∧ 𝑛𝑣)) ∧ 𝜒) → 𝜓)
Assertion
Ref Expression
brfi1uzind ((𝑉𝐺𝐸𝑉 ∈ Fin ∧ 𝐿 ≤ (♯‘𝑉)) → 𝜑)
Distinct variable groups:   𝑒,𝐸,𝑛,𝑣   𝑓,𝐹,𝑤   𝑒,𝐺,𝑓,𝑛,𝑣,𝑤,𝑦   𝑒,𝐿,𝑛,𝑣,𝑦   𝑒,𝑉,𝑛,𝑣   𝜓,𝑓,𝑛,𝑤,𝑦   𝜃,𝑒,𝑛,𝑣   𝜒,𝑓,𝑤   𝜑,𝑒,𝑛,𝑣
Allowed substitution hints:   𝜑(𝑦,𝑤,𝑓)   𝜓(𝑣,𝑒)   𝜒(𝑦,𝑣,𝑒,𝑛)   𝜃(𝑦,𝑤,𝑓)   𝐸(𝑦,𝑤,𝑓)   𝐹(𝑦,𝑣,𝑒,𝑛)   𝐿(𝑤,𝑓)   𝑉(𝑦,𝑤,𝑓)

Proof of Theorem brfi1uzind
Dummy variables 𝑎 𝑏 are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 brfi1uzind.r . . . 4 Rel 𝐺
2 brrelex12 5362 . . . 4 ((Rel 𝐺𝑉𝐺𝐸) → (𝑉 ∈ V ∧ 𝐸 ∈ V))
31, 2mpan 673 . . 3 (𝑉𝐺𝐸 → (𝑉 ∈ V ∧ 𝐸 ∈ V))
4 simpl 470 . . . . 5 ((𝑉 ∈ V ∧ 𝐸 ∈ V) → 𝑉 ∈ V)
5 simplr 776 . . . . . 6 (((𝑉 ∈ V ∧ 𝐸 ∈ V) ∧ 𝑎 = 𝑉) → 𝐸 ∈ V)
6 breq12 4856 . . . . . . 7 ((𝑎 = 𝑉𝑏 = 𝐸) → (𝑎𝐺𝑏𝑉𝐺𝐸))
76adantll 696 . . . . . 6 ((((𝑉 ∈ V ∧ 𝐸 ∈ V) ∧ 𝑎 = 𝑉) ∧ 𝑏 = 𝐸) → (𝑎𝐺𝑏𝑉𝐺𝐸))
85, 7sbcied 3677 . . . . 5 (((𝑉 ∈ V ∧ 𝐸 ∈ V) ∧ 𝑎 = 𝑉) → ([𝐸 / 𝑏]𝑎𝐺𝑏𝑉𝐺𝐸))
94, 8sbcied 3677 . . . 4 ((𝑉 ∈ V ∧ 𝐸 ∈ V) → ([𝑉 / 𝑎][𝐸 / 𝑏]𝑎𝐺𝑏𝑉𝐺𝐸))
109biimprcd 241 . . 3 (𝑉𝐺𝐸 → ((𝑉 ∈ V ∧ 𝐸 ∈ V) → [𝑉 / 𝑎][𝐸 / 𝑏]𝑎𝐺𝑏))
113, 10mpd 15 . 2 (𝑉𝐺𝐸[𝑉 / 𝑎][𝐸 / 𝑏]𝑎𝐺𝑏)
12 brfi1uzind.f . . 3 𝐹 ∈ V
13 brfi1uzind.l . . 3 𝐿 ∈ ℕ0
14 brfi1uzind.1 . . 3 ((𝑣 = 𝑉𝑒 = 𝐸) → (𝜓𝜑))
15 brfi1uzind.2 . . 3 ((𝑣 = 𝑤𝑒 = 𝑓) → (𝜓𝜃))
16 vex 3401 . . . . 5 𝑣 ∈ V
17 vex 3401 . . . . 5 𝑒 ∈ V
18 breq12 4856 . . . . 5 ((𝑎 = 𝑣𝑏 = 𝑒) → (𝑎𝐺𝑏𝑣𝐺𝑒))
1916, 17, 18sbc2ie 3708 . . . 4 ([𝑣 / 𝑎][𝑒 / 𝑏]𝑎𝐺𝑏𝑣𝐺𝑒)
20 brfi1uzind.3 . . . . 5 ((𝑣𝐺𝑒𝑛𝑣) → (𝑣 ∖ {𝑛})𝐺𝐹)
21 difexg 5010 . . . . . . 7 (𝑣 ∈ V → (𝑣 ∖ {𝑛}) ∈ V)
2216, 21ax-mp 5 . . . . . 6 (𝑣 ∖ {𝑛}) ∈ V
2312elexi 3414 . . . . . 6 𝐹 ∈ V
24 breq12 4856 . . . . . 6 ((𝑎 = (𝑣 ∖ {𝑛}) ∧ 𝑏 = 𝐹) → (𝑎𝐺𝑏 ↔ (𝑣 ∖ {𝑛})𝐺𝐹))
2522, 23, 24sbc2ie 3708 . . . . 5 ([(𝑣 ∖ {𝑛}) / 𝑎][𝐹 / 𝑏]𝑎𝐺𝑏 ↔ (𝑣 ∖ {𝑛})𝐺𝐹)
2620, 25sylibr 225 . . . 4 ((𝑣𝐺𝑒𝑛𝑣) → [(𝑣 ∖ {𝑛}) / 𝑎][𝐹 / 𝑏]𝑎𝐺𝑏)
2719, 26sylanb 572 . . 3 (([𝑣 / 𝑎][𝑒 / 𝑏]𝑎𝐺𝑏𝑛𝑣) → [(𝑣 ∖ {𝑛}) / 𝑎][𝐹 / 𝑏]𝑎𝐺𝑏)
28 brfi1uzind.4 . . 3 ((𝑤 = (𝑣 ∖ {𝑛}) ∧ 𝑓 = 𝐹) → (𝜃𝜒))
29 brfi1uzind.base . . . 4 ((𝑣𝐺𝑒 ∧ (♯‘𝑣) = 𝐿) → 𝜓)
3019, 29sylanb 572 . . 3 (([𝑣 / 𝑎][𝑒 / 𝑏]𝑎𝐺𝑏 ∧ (♯‘𝑣) = 𝐿) → 𝜓)
31193anbi1i 1189 . . . . 5 (([𝑣 / 𝑎][𝑒 / 𝑏]𝑎𝐺𝑏 ∧ (♯‘𝑣) = (𝑦 + 1) ∧ 𝑛𝑣) ↔ (𝑣𝐺𝑒 ∧ (♯‘𝑣) = (𝑦 + 1) ∧ 𝑛𝑣))
3231anbi2i 611 . . . 4 (((𝑦 + 1) ∈ ℕ0 ∧ ([𝑣 / 𝑎][𝑒 / 𝑏]𝑎𝐺𝑏 ∧ (♯‘𝑣) = (𝑦 + 1) ∧ 𝑛𝑣)) ↔ ((𝑦 + 1) ∈ ℕ0 ∧ (𝑣𝐺𝑒 ∧ (♯‘𝑣) = (𝑦 + 1) ∧ 𝑛𝑣)))
33 brfi1uzind.step . . . 4 ((((𝑦 + 1) ∈ ℕ0 ∧ (𝑣𝐺𝑒 ∧ (♯‘𝑣) = (𝑦 + 1) ∧ 𝑛𝑣)) ∧ 𝜒) → 𝜓)
3432, 33sylanb 572 . . 3 ((((𝑦 + 1) ∈ ℕ0 ∧ ([𝑣 / 𝑎][𝑒 / 𝑏]𝑎𝐺𝑏 ∧ (♯‘𝑣) = (𝑦 + 1) ∧ 𝑛𝑣)) ∧ 𝜒) → 𝜓)
3512, 13, 14, 15, 27, 28, 30, 34fi1uzind 13499 . 2 (([𝑉 / 𝑎][𝐸 / 𝑏]𝑎𝐺𝑏𝑉 ∈ Fin ∧ 𝐿 ≤ (♯‘𝑉)) → 𝜑)
3611, 35syl3an1 1195 1 ((𝑉𝐺𝐸𝑉 ∈ Fin ∧ 𝐿 ≤ (♯‘𝑉)) → 𝜑)
Colors of variables: wff setvar class
Syntax hints:  wi 4  wb 197  wa 384  w3a 1100   = wceq 1637  wcel 2157  Vcvv 3398  [wsbc 3640  cdif 3773  {csn 4377   class class class wbr 4851  Rel wrel 5323  cfv 6104  (class class class)co 6877  Fincfn 8195  1c1 10225   + caddc 10227  cle 10363  0cn0 11562  chash 13340
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1877  ax-4 1894  ax-5 2001  ax-6 2069  ax-7 2105  ax-8 2159  ax-9 2166  ax-10 2186  ax-11 2202  ax-12 2215  ax-13 2422  ax-ext 2791  ax-rep 4971  ax-sep 4982  ax-nul 4990  ax-pow 5042  ax-pr 5103  ax-un 7182  ax-cnex 10280  ax-resscn 10281  ax-1cn 10282  ax-icn 10283  ax-addcl 10284  ax-addrcl 10285  ax-mulcl 10286  ax-mulrcl 10287  ax-mulcom 10288  ax-addass 10289  ax-mulass 10290  ax-distr 10291  ax-i2m1 10292  ax-1ne0 10293  ax-1rid 10294  ax-rnegex 10295  ax-rrecex 10296  ax-cnre 10297  ax-pre-lttri 10298  ax-pre-lttrn 10299  ax-pre-ltadd 10300  ax-pre-mulgt0 10301
This theorem depends on definitions:  df-bi 198  df-an 385  df-or 866  df-3or 1101  df-3an 1102  df-tru 1641  df-ex 1860  df-nf 1864  df-sb 2062  df-mo 2635  df-eu 2638  df-clab 2800  df-cleq 2806  df-clel 2809  df-nfc 2944  df-ne 2986  df-nel 3089  df-ral 3108  df-rex 3109  df-reu 3110  df-rmo 3111  df-rab 3112  df-v 3400  df-sbc 3641  df-csb 3736  df-dif 3779  df-un 3781  df-in 3783  df-ss 3790  df-pss 3792  df-nul 4124  df-if 4287  df-pw 4360  df-sn 4378  df-pr 4380  df-tp 4382  df-op 4384  df-uni 4638  df-int 4677  df-iun 4721  df-br 4852  df-opab 4914  df-mpt 4931  df-tr 4954  df-id 5226  df-eprel 5231  df-po 5239  df-so 5240  df-fr 5277  df-we 5279  df-xp 5324  df-rel 5325  df-cnv 5326  df-co 5327  df-dm 5328  df-rn 5329  df-res 5330  df-ima 5331  df-pred 5900  df-ord 5946  df-on 5947  df-lim 5948  df-suc 5949  df-iota 6067  df-fun 6106  df-fn 6107  df-f 6108  df-f1 6109  df-fo 6110  df-f1o 6111  df-fv 6112  df-riota 6838  df-ov 6880  df-oprab 6881  df-mpt2 6882  df-om 7299  df-1st 7401  df-2nd 7402  df-wrecs 7645  df-recs 7707  df-rdg 7745  df-1o 7799  df-oadd 7803  df-er 7982  df-en 8196  df-dom 8197  df-sdom 8198  df-fin 8199  df-card 9051  df-cda 9278  df-pnf 10364  df-mnf 10365  df-xr 10366  df-ltxr 10367  df-le 10368  df-sub 10556  df-neg 10557  df-nn 11309  df-n0 11563  df-xnn0 11633  df-z 11647  df-uz 11908  df-fz 12553  df-hash 13341
This theorem is referenced by:  brfi1ind  13501
  Copyright terms: Public domain W3C validator