Theorem brfi1uzind 14523

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 14524) 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.

Step	Hyp	Ref	Expression
1		brfi1uzind.r	. . . 4 ⊢ Rel 𝐺
2	1	brrelex12i 5704	. . 3 ⊢ (𝑉𝐺𝐸 → (𝑉 ∈ V ∧ 𝐸 ∈ V))
3		simpl 486	. . . . 5 ⊢ ((𝑉 ∈ V ∧ 𝐸 ∈ V) → 𝑉 ∈ V)
4		simplr 778	. . . . . 6 ⊢ (((𝑉 ∈ V ∧ 𝐸 ∈ V) ∧ 𝑎 = 𝑉) → 𝐸 ∈ V)
5		breq12 5107	. . . . . . 7 ⊢ ((𝑎 = 𝑉 ∧ 𝑏 = 𝐸) → (𝑎𝐺𝑏 ↔ 𝑉𝐺𝐸))
6	5	adantll 724	. . . . . 6 ⊢ ((((𝑉 ∈ V ∧ 𝐸 ∈ V) ∧ 𝑎 = 𝑉) ∧ 𝑏 = 𝐸) → (𝑎𝐺𝑏 ↔ 𝑉𝐺𝐸))
7	4, 6	sbcied 3789	. . . . 5 ⊢ (((𝑉 ∈ V ∧ 𝐸 ∈ V) ∧ 𝑎 = 𝑉) → ([𝐸 / 𝑏]𝑎𝐺𝑏 ↔ 𝑉𝐺𝐸))
8	3, 7	sbcied 3789	. . . 4 ⊢ ((𝑉 ∈ V ∧ 𝐸 ∈ V) → ([𝑉 / 𝑎][𝐸 / 𝑏]𝑎𝐺𝑏 ↔ 𝑉𝐺𝐸))
9	8	biimprcd 252	. . 3 ⊢ (𝑉𝐺𝐸 → ((𝑉 ∈ V ∧ 𝐸 ∈ V) → [𝑉 / 𝑎][𝐸 / 𝑏]𝑎𝐺𝑏))
10	2, 9	mpd 15	. 2 ⊢ (𝑉𝐺𝐸 → [𝑉 / 𝑎][𝐸 / 𝑏]𝑎𝐺𝑏)
11		brfi1uzind.f	. . 3 ⊢ 𝐹 ∈ V
12		brfi1uzind.l	. . 3 ⊢ 𝐿 ∈ ℕ0
13		brfi1uzind.1	. . 3 ⊢ ((𝑣 = 𝑉 ∧ 𝑒 = 𝐸) → (𝜓 ↔ 𝜑))
14		brfi1uzind.2	. . 3 ⊢ ((𝑣 = 𝑤 ∧ 𝑒 = 𝑓) → (𝜓 ↔ 𝜃))
15		vex 3460	. . . . 5 ⊢ 𝑣 ∈ V
16		vex 3460	. . . . 5 ⊢ 𝑒 ∈ V
17		breq12 5107	. . . . 5 ⊢ ((𝑎 = 𝑣 ∧ 𝑏 = 𝑒) → (𝑎𝐺𝑏 ↔ 𝑣𝐺𝑒))
18	15, 16, 17	sbc2ie 3821	. . . 4 ⊢ ([𝑣 / 𝑎][𝑒 / 𝑏]𝑎𝐺𝑏 ↔ 𝑣𝐺𝑒)
19		brfi1uzind.3	. . . . 5 ⊢ ((𝑣𝐺𝑒 ∧ 𝑛 ∈ 𝑣) → (𝑣 ∖ {𝑛})𝐺𝐹)
20	15	difexi 5288	. . . . . 6 ⊢ (𝑣 ∖ {𝑛}) ∈ V
21		breq12 5107	. . . . . 6 ⊢ ((𝑎 = (𝑣 ∖ {𝑛}) ∧ 𝑏 = 𝐹) → (𝑎𝐺𝑏 ↔ (𝑣 ∖ {𝑛})𝐺𝐹))
22	20, 11, 21	sbc2ie 3821	. . . . 5 ⊢ ([(𝑣 ∖ {𝑛}) / 𝑎][𝐹 / 𝑏]𝑎𝐺𝑏 ↔ (𝑣 ∖ {𝑛})𝐺𝐹)
23	19, 22	sylibr 236	. . . 4 ⊢ ((𝑣𝐺𝑒 ∧ 𝑛 ∈ 𝑣) → [(𝑣 ∖ {𝑛}) / 𝑎][𝐹 / 𝑏]𝑎𝐺𝑏)
24	18, 23	sylanb 590	. . 3 ⊢ (([𝑣 / 𝑎][𝑒 / 𝑏]𝑎𝐺𝑏 ∧ 𝑛 ∈ 𝑣) → [(𝑣 ∖ {𝑛}) / 𝑎][𝐹 / 𝑏]𝑎𝐺𝑏)
25		brfi1uzind.4	. . 3 ⊢ ((𝑤 = (𝑣 ∖ {𝑛}) ∧ 𝑓 = 𝐹) → (𝜃 ↔ 𝜒))
26		brfi1uzind.base	. . . 4 ⊢ ((𝑣𝐺𝑒 ∧ (♯‘𝑣) = 𝐿) → 𝜓)
27	18, 26	sylanb 590	. . 3 ⊢ (([𝑣 / 𝑎][𝑒 / 𝑏]𝑎𝐺𝑏 ∧ (♯‘𝑣) = 𝐿) → 𝜓)
28	18	3anbi1i 1171	. . . . 5 ⊢ (([𝑣 / 𝑎][𝑒 / 𝑏]𝑎𝐺𝑏 ∧ (♯‘𝑣) = (𝑦 + 1) ∧ 𝑛 ∈ 𝑣) ↔ (𝑣𝐺𝑒 ∧ (♯‘𝑣) = (𝑦 + 1) ∧ 𝑛 ∈ 𝑣))
29	28	anbi2i 632	. . . 4 ⊢ (((𝑦 + 1) ∈ ℕ0 ∧ ([𝑣 / 𝑎][𝑒 / 𝑏]𝑎𝐺𝑏 ∧ (♯‘𝑣) = (𝑦 + 1) ∧ 𝑛 ∈ 𝑣)) ↔ ((𝑦 + 1) ∈ ℕ0 ∧ (𝑣𝐺𝑒 ∧ (♯‘𝑣) = (𝑦 + 1) ∧ 𝑛 ∈ 𝑣)))
30		brfi1uzind.step	. . . 4 ⊢ ((((𝑦 + 1) ∈ ℕ0 ∧ (𝑣𝐺𝑒 ∧ (♯‘𝑣) = (𝑦 + 1) ∧ 𝑛 ∈ 𝑣)) ∧ 𝜒) → 𝜓)
31	29, 30	sylanb 590	. . 3 ⊢ ((((𝑦 + 1) ∈ ℕ0 ∧ ([𝑣 / 𝑎][𝑒 / 𝑏]𝑎𝐺𝑏 ∧ (♯‘𝑣) = (𝑦 + 1) ∧ 𝑛 ∈ 𝑣)) ∧ 𝜒) → 𝜓)
32	11, 12, 13, 14, 24, 25, 27, 31	fi1uzind 14522	. 2 ⊢ (([𝑉 / 𝑎][𝐸 / 𝑏]𝑎𝐺𝑏 ∧ 𝑉 ∈ Fin ∧ 𝐿 ≤ (♯‘𝑉)) → 𝜑)
33	10, 32	syl3an1 1177	1 ⊢ ((𝑉𝐺𝐸 ∧ 𝑉 ∈ Fin ∧ 𝐿 ≤ (♯‘𝑉)) → 𝜑)

Syntax hints:   → wi 4   ↔ wb 208   ∧ wa 399   ∧ w3a 1099   = wceq 1562   ∈ wcel 2144  Vcvv 3456  [wsbc 3746   ∖ cdif 3903  {csn 4584   class class class wbr 5102  Rel wrel 5654  ‘cfv 6523  (class class class)co 7398  Fincfn 8929  1c1 11076   + caddc 11078   ≤ cle 11219  ℕ₀cn0 12483  ♯chash 14345

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1817  ax-4 1831  ax-5 1932  ax-6 1989  ax-7 2030  ax-8 2146  ax-9 2154  ax-10 2177  ax-11 2193  ax-12 2214  ax-ext 2736  ax-sep 5248  ax-nul 5258  ax-pow 5324  ax-pr 5392  ax-un 7720  ax-cnex 11131  ax-resscn 11132  ax-1cn 11133  ax-icn 11134  ax-addcl 11135  ax-addrcl 11136  ax-mulcl 11137  ax-mulrcl 11138  ax-mulcom 11139  ax-addass 11140  ax-mulass 11141  ax-distr 11142  ax-i2m1 11143  ax-1ne0 11144  ax-1rid 11145  ax-rnegex 11146  ax-rrecex 11147  ax-cnre 11148  ax-pre-lttri 11149  ax-pre-lttrn 11150  ax-pre-ltadd 11151  ax-pre-mulgt0 11152

This theorem depends on definitions:  df-bi 209  df-an 400  df-or 859  df-3or 1100  df-3an 1101  df-tru 1565  df-fal 1575  df-ex 1802  df-nf 1806  df-sb 2093  df-mo 2568  df-eu 2598  df-clab 2743  df-cleq 2756  df-clel 2839  df-nfc 2913  df-ne 2960  df-nel 3064  df-ral 3079  df-rex 3089  df-reu 3370  df-rab 3417  df-v 3458  df-sbc 3747  df-csb 3855  df-dif 3909  df-un 3911  df-in 3913  df-ss 3923  df-pss 3926  df-nul 4288  df-if 4483  df-pw 4559  df-sn 4585  df-pr 4587  df-op 4591  df-uni 4868  df-int 4908  df-iun 4953  df-br 5103  df-opab 5165  df-mpt 5184  df-tr 5210  df-id 5544  df-eprel 5549  df-po 5557  df-so 5558  df-fr 5602  df-we 5604  df-xp 5655  df-rel 5656  df-cnv 5657  df-co 5658  df-dm 5659  df-rn 5660  df-res 5661  df-ima 5662  df-pred 6290  df-ord 6351  df-on 6352  df-lim 6353  df-suc 6354  df-iota 6479  df-fun 6525  df-fn 6526  df-f 6527  df-f1 6528  df-fo 6529  df-f1o 6530  df-fv 6531  df-riota 7355  df-ov 7401  df-oprab 7402  df-mpo 7403  df-om 7849  df-1st 7972  df-2nd 7973  df-frecs 8264  df-wrecs 8295  df-recs 8344  df-rdg 8383  df-1o 8439  df-oadd 8443  df-er 8680  df-en 8930  df-dom 8931  df-sdom 8932  df-fin 8933  df-dju 9861  df-card 9899  df-pnf 11220  df-mnf 11221  df-xr 11222  df-ltxr 11223  df-le 11224  df-sub 11418  df-neg 11419  df-nn 12213  df-n0 12484  df-xnn0 12557  df-z 12571  df-uz 12842  df-fz 13515  df-hash 14346

This theorem is referenced by:  brfi1ind  14524