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

Theorem brfi1uzind 12644
 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 (see brfi1ind 12645) or . (Contributed by Alexander van der Vekens, 7-Jan-2018.)
Hypotheses
Ref Expression
brfi1uzind.r
brfi1uzind.f
brfi1uzind.l
brfi1uzind.1
brfi1uzind.2
brfi1uzind.3
brfi1uzind.4
brfi1uzind.base
brfi1uzind.step
Assertion
Ref Expression
brfi1uzind
Distinct variable groups:   ,,,   ,,,   ,,   ,,,,,,   ,,,   ,,,,   ,,,   ,,   ,,,   ,,,,
Allowed substitution hints:   (,,)   (,)   (,,,)   (,,)   (,,,,,)   (,,)   (,,,)   (,)   (,,)

Proof of Theorem brfi1uzind
Dummy variable is distinct from all other variables.
StepHypRef Expression
1 hashcl 12537 . . . 4
2 df-clel 2417 . . . . 5
3 brfi1uzind.l . . . . . . . . . . . . . . 15
4 nn0z 10960 . . . . . . . . . . . . . . 15
53, 4mp1i 13 . . . . . . . . . . . . . 14
6 nn0z 10960 . . . . . . . . . . . . . . 15
76ad2antlr 731 . . . . . . . . . . . . . 14
8 breq2 4424 . . . . . . . . . . . . . . . . . 18
98eqcoms 2434 . . . . . . . . . . . . . . . . 17
109biimpcd 227 . . . . . . . . . . . . . . . 16
1110adantr 466 . . . . . . . . . . . . . . 15
1211imp 430 . . . . . . . . . . . . . 14
13 eqeq1 2426 . . . . . . . . . . . . . . . . . 18
1413anbi2d 708 . . . . . . . . . . . . . . . . 17
1514imbi1d 318 . . . . . . . . . . . . . . . 16
16152albidv 1759 . . . . . . . . . . . . . . 15
17 eqeq1 2426 . . . . . . . . . . . . . . . . . 18
1817anbi2d 708 . . . . . . . . . . . . . . . . 17
1918imbi1d 318 . . . . . . . . . . . . . . . 16
20192albidv 1759 . . . . . . . . . . . . . . 15
21 eqeq1 2426 . . . . . . . . . . . . . . . . . 18
2221anbi2d 708 . . . . . . . . . . . . . . . . 17
2322imbi1d 318 . . . . . . . . . . . . . . . 16
24232albidv 1759 . . . . . . . . . . . . . . 15
25 eqeq1 2426 . . . . . . . . . . . . . . . . . 18
2625anbi2d 708 . . . . . . . . . . . . . . . . 17
2726imbi1d 318 . . . . . . . . . . . . . . . 16
28272albidv 1759 . . . . . . . . . . . . . . 15
29 eqcom 2431 . . . . . . . . . . . . . . . . . 18
30 brfi1uzind.base . . . . . . . . . . . . . . . . . 18
3129, 30sylan2b 477 . . . . . . . . . . . . . . . . 17
3231gen2 1666 . . . . . . . . . . . . . . . 16
3332a1i 11 . . . . . . . . . . . . . . 15
34 breq12 4425 . . . . . . . . . . . . . . . . . . 19
35 fveq2 5877 . . . . . . . . . . . . . . . . . . . . 21
3635eqeq2d 2436 . . . . . . . . . . . . . . . . . . . 20
3736adantr 466 . . . . . . . . . . . . . . . . . . 19
3834, 37anbi12d 715 . . . . . . . . . . . . . . . . . 18
39 brfi1uzind.2 . . . . . . . . . . . . . . . . . 18
4038, 39imbi12d 321 . . . . . . . . . . . . . . . . 17
4140cbval2v 2083 . . . . . . . . . . . . . . . 16
42 nn0ge0 10895 . . . . . . . . . . . . . . . . . . . . . 22
43 0red 9644 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
44 nn0re 10878 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
453, 44mp1i 13 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
46 zre 10941 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
47 letr 9727 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
4843, 45, 46, 47syl3anc 1264 . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
49 0nn0 10884 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
50 pm3.22 450 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
51 0z 10948 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
52 eluz1 11163 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
5351, 52mp1i 13 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
5450, 53mpbird 235 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
55 eluznn0 11228 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
5649, 54, 55sylancr 667 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
5756ex 435 . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
5848, 57syl6com 36 . . . . . . . . . . . . . . . . . . . . . . . . . . 27
5958ex 435 . . . . . . . . . . . . . . . . . . . . . . . . . 26
6059com14 91 . . . . . . . . . . . . . . . . . . . . . . . . 25
6160pm2.43a 51 . . . . . . . . . . . . . . . . . . . . . . . 24
6261imp 430 . . . . . . . . . . . . . . . . . . . . . . 23
6362com12 32 . . . . . . . . . . . . . . . . . . . . . 22
643, 42, 63mp2b 10 . . . . . . . . . . . . . . . . . . . . 21
65643adant1 1023 . . . . . . . . . . . . . . . . . . . 20
66 eqcom 2431 . . . . . . . . . . . . . . . . . . . . . . 23
67 nn0p1gt0 10899 . . . . . . . . . . . . . . . . . . . . . . . . 25
6867adantr 466 . . . . . . . . . . . . . . . . . . . . . . . 24
69 simpr 462 . . . . . . . . . . . . . . . . . . . . . . . 24
7068, 69breqtrrd 4447 . . . . . . . . . . . . . . . . . . . . . . 23
7166, 70sylan2b 477 . . . . . . . . . . . . . . . . . . . . . 22
7271adantrl 720 . . . . . . . . . . . . . . . . . . . . 21
73 vex 3084 . . . . . . . . . . . . . . . . . . . . . . . 24
74 hashgt0elex 12577 . . . . . . . . . . . . . . . . . . . . . . . . . . 27
75 brfi1uzind.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
7673a1i 11 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
77 simpr 462 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
78 simpl 458 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
79 brfi1indlem 12643 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
8066, 79syl5bi 220 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
8176, 77, 78, 80syl3anc 1264 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
8281imp 430 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
83 peano2nn0 10910 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
8483ad2antrr 730 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
8584ad2antlr 731 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
86 simpr 462 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
87 simplrr 769 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
88 simprlr 771 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
8988adantr 466 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
9086, 87, 893jca 1185 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
9185, 90jca 534 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
92 difexg 4568 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
9373, 92ax-mp 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
94 brfi1uzind.f . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
95 breq12 4425 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
96 eqcom 2431 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
97 fveq2 5877 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
9897eqeq1d 2424 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
9996, 98syl5bb 260 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
10099adantr 466 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
10195, 100anbi12d 715 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
102 brfi1uzind.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
103101, 102imbi12d 321 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
104103spc2gv 3169 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
10593, 94, 104mp2an 676 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
106105expdimp 438 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
107106ad2antrr 730 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
108663anbi2i 1197 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
109108anbi2i 698 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
110 brfi1uzind.step . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
111109, 110sylanb 474 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
11291, 107, 111syl6an 547 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
113112exp41 613 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
114113com15 96 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
115114com23 81 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
11682, 115mpcom 37 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
117116ex 435 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
118117com23 81 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
119118ex 435 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
120119com15 96 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
121120imp 430 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
12275, 121mpd 15 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
123122ex 435 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
124123com4l 87 . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
125124exlimiv 1766 . . . . . . . . . . . . . . . . . . . . . . . . . . 27
12674, 125syl 17 . . . . . . . . . . . . . . . . . . . . . . . . . 26
127126ex 435 . . . . . . . . . . . . . . . . . . . . . . . . 25
128127com25 94 . . . . . . . . . . . . . . . . . . . . . . . 24
12973, 128ax-mp 5 . . . . . . . . . . . . . . . . . . . . . . 23
130129imp 430 . . . . . . . . . . . . . . . . . . . . . 22
131130impcom 431 . . . . . . . . . . . . . . . . . . . . 21
13272, 131mpd 15 . . . . . . . . . . . . . . . . . . . 20
13365, 132sylan 473 . . . . . . . . . . . . . . . . . . 19
134133impancom 441 . . . . . . . . . . . . . . . . . 18
135134alrimivv 1764 . . . . . . . . . . . . . . . . 17
136135ex 435 . . . . . . . . . . . . . . . 16
13741, 136syl5bi 220 . . . . . . . . . . . . . . 15
13816, 20, 24, 28, 33, 137uzind 11027 . . . . . . . . . . . . . 14
1395, 7, 12, 138syl3anc 1264 . . . . . . . . . . . . 13
140 brfi1uzind.r . . . . . . . . . . . . . . . . 17
141140brrelexi 4890 . . . . . . . . . . . . . . . 16
142140brrelex2i 4891 . . . . . . . . . . . . . . . 16
143141, 142jca 534 . . . . . . . . . . . . . . 15
144 breq12 4425 . . . . . . . . . . . . . . . . . . . 20
145 fveq2 5877 . . . . . . . . . . . . . . . . . . . . . 22
146145eqeq2d 2436 . . . . . . . . . . . . . . . . . . . . 21
147146adantr 466 . . . . . . . . . . . . . . . . . . . 20
148144, 147anbi12d 715 . . . . . . . . . . . . . . . . . . 19
149 brfi1uzind.1 . . . . . . . . . . . . . . . . . . 19
150148, 149imbi12d 321 . . . . . . . . . . . . . . . . . 18
151150spc2gv 3169 . . . . . . . . . . . . . . . . 17
152151com23 81 . . . . . . . . . . . . . . . 16
153152expd 437 . . . . . . . . . . . . . . 15
154143, 153mpcom 37 . . . . . . . . . . . . . 14
155154imp 430 . . . . . . . . . . . . 13
156139, 155syl5com 31 . . . . . . . . . . . 12
157156exp31 607 . . . . . . . . . . 11
158157com14 91 . . . . . . . . . 10
159158expcom 436 . . . . . . . . 9
160159com24 90 . . . . . . . 8
161160pm2.43i 49 . . . . . . 7
162161imp 430 . . . . . 6
163162exlimiv 1766 . . . . 5
1642, 163sylbi 198 . . . 4
1651, 164syl 17 . . 3
166165com12 32 . 2
1671663imp 1199 1
 Colors of variables: wff setvar class Syntax hints:   wi 4   wb 187   wa 370   w3a 982  wal 1435   wceq 1437  wex 1659   wcel 1868  cvv 3081   cdif 3433  csn 3996   class class class wbr 4420   wrel 4854  cfv 5597  (class class class)co 6301  cfn 7573  cr 9538  cc0 9539  c1 9540   caddc 9542   clt 9675   cle 9676  cn0 10869  cz 10937  cuz 11159  chash 12514 This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1665  ax-4 1678  ax-5 1748  ax-6 1794  ax-7 1839  ax-8 1870  ax-9 1872  ax-10 1887  ax-11 1892  ax-12 1905  ax-13 2053  ax-ext 2400  ax-rep 4533  ax-sep 4543  ax-nul 4551  ax-pow 4598  ax-pr 4656  ax-un 6593  ax-cnex 9595  ax-resscn 9596  ax-1cn 9597  ax-icn 9598  ax-addcl 9599  ax-addrcl 9600  ax-mulcl 9601  ax-mulrcl 9602  ax-mulcom 9603  ax-addass 9604  ax-mulass 9605  ax-distr 9606  ax-i2m1 9607  ax-1ne0 9608  ax-1rid 9609  ax-rnegex 9610  ax-rrecex 9611  ax-cnre 9612  ax-pre-lttri 9613  ax-pre-lttrn 9614  ax-pre-ltadd 9615  ax-pre-mulgt0 9616 This theorem depends on definitions:  df-bi 188  df-or 371  df-an 372  df-3or 983  df-3an 984  df-tru 1440  df-ex 1660  df-nf 1664  df-sb 1787  df-eu 2269  df-mo 2270  df-clab 2408  df-cleq 2414  df-clel 2417  df-nfc 2572  df-ne 2620  df-nel 2621  df-ral 2780  df-rex 2781  df-reu 2782  df-rmo 2783  df-rab 2784  df-v 3083  df-sbc 3300  df-csb 3396  df-dif 3439  df-un 3441  df-in 3443  df-ss 3450  df-pss 3452  df-nul 3762  df-if 3910  df-pw 3981  df-sn 3997  df-pr 3999  df-tp 4001  df-op 4003  df-uni 4217  df-int 4253  df-iun 4298  df-br 4421  df-opab 4480  df-mpt 4481  df-tr 4516  df-eprel 4760  df-id 4764  df-po 4770  df-so 4771  df-fr 4808  df-we 4810  df-xp 4855  df-rel 4856  df-cnv 4857  df-co 4858  df-dm 4859  df-rn 4860  df-res 4861  df-ima 4862  df-pred 5395  df-ord 5441  df-on 5442  df-lim 5443  df-suc 5444  df-iota 5561  df-fun 5599  df-fn 5600  df-f 5601  df-f1 5602  df-fo 5603  df-f1o 5604  df-fv 5605  df-riota 6263  df-ov 6304  df-oprab 6305  df-mpt2 6306  df-om 6703  df-1st 6803  df-2nd 6804  df-wrecs 7032  df-recs 7094  df-rdg 7132  df-1o 7186  df-oadd 7190  df-er 7367  df-en 7574  df-dom 7575  df-sdom 7576  df-fin 7577  df-card 8374  df-cda 8598  df-pnf 9677  df-mnf 9678  df-xr 9679  df-ltxr 9680  df-le 9681  df-sub 9862  df-neg 9863  df-nn 10610  df-n0 10870  df-z 10938  df-uz 11160  df-fz 11785  df-hash 12515 This theorem is referenced by:  brfi1ind  12645
 Copyright terms: Public domain W3C validator