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

Theorem marypha1 7945
 Description: (Philip) Hall's marriage theorem, sufficiency: a finite relation contains an injection if there is no subset of its domain which would be forced to violate the pigeonhole principle. (Contributed by Stefan O'Rear, 20-Feb-2015.)
Hypotheses
Ref Expression
marypha1.a
marypha1.b
marypha1.c
marypha1.d
Assertion
Ref Expression
marypha1
Distinct variable groups:   ,,   ,,   ,,
Allowed substitution hints:   (,)

Proof of Theorem marypha1
Dummy variables are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 elpwi 3959 . . . . 5
2 marypha1.d . . . . 5
31, 2sylan2 477 . . . 4
43ralrimiva 2801 . . 3
5 marypha1.c . . . . 5
6 marypha1.a . . . . . . 7
7 marypha1.b . . . . . . 7
8 xpexg 6590 . . . . . . 7
96, 7, 8syl2anc 666 . . . . . 6
10 elpw2g 4565 . . . . . 6
119, 10syl 17 . . . . 5
125, 11mpbird 236 . . . 4
13 xpeq2 4848 . . . . . . . . 9
1413pweqd 3955 . . . . . . . 8
1514raleqdv 2992 . . . . . . 7
1615imbi2d 318 . . . . . 6
17 marypha1lem 7944 . . . . . . 7
1817com12 32 . . . . . 6
1916, 18vtoclga 3112 . . . . 5
207, 6, 19sylc 62 . . . 4
21 imaeq1 5162 . . . . . . . 8
2221breq2d 4413 . . . . . . 7
2322ralbidv 2826 . . . . . 6
24 pweq 3953 . . . . . . 7
2524rexeqdv 2993 . . . . . 6
2623, 25imbi12d 322 . . . . 5
2726rspcva 3147 . . . 4
2812, 20, 27syl2anc 666 . . 3
294, 28mpd 15 . 2
30 elpwi 3959 . . . . . . 7
3130, 5sylan9ssr 3445 . . . . . 6
32 rnss 5062 . . . . . 6
3331, 32syl 17 . . . . 5
34 rnxpss 5268 . . . . 5
3533, 34syl6ss 3443 . . . 4
36 f1ssr 5783 . . . . 5
3736expcom 437 . . . 4
3835, 37syl 17 . . 3
3938reximdva 2861 . 2
4029, 39mpd 15 1
 Colors of variables: wff setvar class Syntax hints:   wi 4   wb 188   wa 371   wceq 1443   wcel 1886  wral 2736  wrex 2737  cvv 3044   wss 3403  cpw 3950   class class class wbr 4401   cxp 4831   crn 4834  cima 4836  wf1 5578   cdom 7564  cfn 7566 This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1668  ax-4 1681  ax-5 1757  ax-6 1804  ax-7 1850  ax-8 1888  ax-9 1895  ax-10 1914  ax-11 1919  ax-12 1932  ax-13 2090  ax-ext 2430  ax-sep 4524  ax-nul 4533  ax-pow 4580  ax-pr 4638  ax-un 6580 This theorem depends on definitions:  df-bi 189  df-or 372  df-an 373  df-3or 985  df-3an 986  df-tru 1446  df-ex 1663  df-nf 1667  df-sb 1797  df-eu 2302  df-mo 2303  df-clab 2437  df-cleq 2443  df-clel 2446  df-nfc 2580  df-ne 2623  df-ral 2741  df-rex 2742  df-rab 2745  df-v 3046  df-sbc 3267  df-dif 3406  df-un 3408  df-in 3410  df-ss 3417  df-pss 3419  df-nul 3731  df-if 3881  df-pw 3952  df-sn 3968  df-pr 3970  df-tp 3972  df-op 3974  df-uni 4198  df-br 4402  df-opab 4461  df-tr 4497  df-eprel 4744  df-id 4748  df-po 4754  df-so 4755  df-fr 4792  df-we 4794  df-xp 4839  df-rel 4840  df-cnv 4841  df-co 4842  df-dm 4843  df-rn 4844  df-res 4845  df-ima 4846  df-ord 5425  df-on 5426  df-lim 5427  df-suc 5428  df-iota 5545  df-fun 5583  df-fn 5584  df-f 5585  df-f1 5586  df-fo 5587  df-f1o 5588  df-fv 5589  df-om 6690  df-1o 7179  df-er 7360  df-en 7567  df-dom 7568  df-sdom 7569  df-fin 7570 This theorem is referenced by:  marypha2  7950
 Copyright terms: Public domain W3C validator