ILE Home Intuitionistic Logic Explorer < Previous   Next >
Nearby theorems
Mirrors  >  Home  >  ILE Home  >  Th. List  >  lgsquadlem3 Unicode version

Theorem lgsquadlem3 16454
Description: Lemma for lgsquad 16455. (Contributed by Mario Carneiro, 18-Jun-2015.)
Hypotheses
Ref Expression
lgseisen.1  |-  ( ph  ->  P  e.  ( Prime  \  { 2 } ) )
lgseisen.2  |-  ( ph  ->  Q  e.  ( Prime  \  { 2 } ) )
lgseisen.3  |-  ( ph  ->  P  =/=  Q )
lgsquad.4  |-  M  =  ( ( P  - 
1 )  /  2
)
lgsquad.5  |-  N  =  ( ( Q  - 
1 )  /  2
)
lgsquad.6  |-  S  =  { <. x ,  y
>.  |  ( (
x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N ) )  /\  ( y  x.  P )  <  (
x  x.  Q ) ) }
Assertion
Ref Expression
lgsquadlem3  |-  ( ph  ->  ( ( P  /L Q )  x.  ( Q  /L
P ) )  =  (  -u 1 ^ ( M  x.  N )
) )
Distinct variable groups:    x, y, P    ph, x, y    y, M   
x, N, y    x, Q, y    x, S    x, M    y, S

Proof of Theorem lgsquadlem3
Dummy variables  w  z  j are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 lgseisen.2 . . . . 5  |-  ( ph  ->  Q  e.  ( Prime  \  { 2 } ) )
2 lgseisen.1 . . . . 5  |-  ( ph  ->  P  e.  ( Prime  \  { 2 } ) )
3 lgseisen.3 . . . . . 6  |-  ( ph  ->  P  =/=  Q )
43necomd 2506 . . . . 5  |-  ( ph  ->  Q  =/=  P )
5 lgsquad.5 . . . . 5  |-  N  =  ( ( Q  - 
1 )  /  2
)
6 lgsquad.4 . . . . 5  |-  M  =  ( ( P  - 
1 )  /  2
)
7 eleq1w 2299 . . . . . . . . . 10  |-  ( x  =  z  ->  (
x  e.  ( 1 ... M )  <->  z  e.  ( 1 ... M
) ) )
8 eleq1w 2299 . . . . . . . . . 10  |-  ( y  =  w  ->  (
y  e.  ( 1 ... N )  <->  w  e.  ( 1 ... N
) ) )
97, 8bi2anan9 614 . . . . . . . . 9  |-  ( ( x  =  z  /\  y  =  w )  ->  ( ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) )  <->  ( z  e.  ( 1 ... M
)  /\  w  e.  ( 1 ... N
) ) ) )
109biancomd 271 . . . . . . . 8  |-  ( ( x  =  z  /\  y  =  w )  ->  ( ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) )  <->  ( w  e.  ( 1 ... N
)  /\  z  e.  ( 1 ... M
) ) ) )
11 oveq1 6098 . . . . . . . . 9  |-  ( x  =  z  ->  (
x  x.  Q )  =  ( z  x.  Q ) )
12 oveq1 6098 . . . . . . . . 9  |-  ( y  =  w  ->  (
y  x.  P )  =  ( w  x.  P ) )
1311, 12breqan12d 4147 . . . . . . . 8  |-  ( ( x  =  z  /\  y  =  w )  ->  ( ( x  x.  Q )  <  (
y  x.  P )  <-> 
( z  x.  Q
)  <  ( w  x.  P ) ) )
1410, 13anbi12d 477 . . . . . . 7  |-  ( ( x  =  z  /\  y  =  w )  ->  ( ( ( x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N
) )  /\  (
x  x.  Q )  <  ( y  x.  P ) )  <->  ( (
w  e.  ( 1 ... N )  /\  z  e.  ( 1 ... M ) )  /\  ( z  x.  Q )  <  (
w  x.  P ) ) ) )
1514ancoms 268 . . . . . 6  |-  ( ( y  =  w  /\  x  =  z )  ->  ( ( ( x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N
) )  /\  (
x  x.  Q )  <  ( y  x.  P ) )  <->  ( (
w  e.  ( 1 ... N )  /\  z  e.  ( 1 ... M ) )  /\  ( z  x.  Q )  <  (
w  x.  P ) ) ) )
1615cbvopabv 4204 . . . . 5  |-  { <. y ,  x >.  |  ( ( x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N ) )  /\  ( x  x.  Q )  < 
( y  x.  P
) ) }  =  { <. w ,  z
>.  |  ( (
w  e.  ( 1 ... N )  /\  z  e.  ( 1 ... M ) )  /\  ( z  x.  Q )  <  (
w  x.  P ) ) }
171, 2, 4, 5, 6, 16lgsquadlem2 16453 . . . 4  |-  ( ph  ->  ( P  /L
Q )  =  ( 
-u 1 ^ (♯ `  { <. y ,  x >.  |  ( ( x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N
) )  /\  (
x  x.  Q )  <  ( y  x.  P ) ) } ) ) )
18 relopabv 4906 . . . . . . . 8  |-  Rel  { <. x ,  y >.  |  ( ( x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N
) )  /\  (
x  x.  Q )  <  ( y  x.  P ) ) }
19 eqid 2238 . . . . . . . . 9  |-  { <. x ,  y >.  |  ( ( x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N ) )  /\  ( x  x.  Q )  < 
( y  x.  P
) ) }  =  { <. x ,  y
>.  |  ( (
x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N ) )  /\  ( x  x.  Q )  <  (
y  x.  P ) ) }
20 1zzd 9684 . . . . . . . . . 10  |-  ( ph  ->  1  e.  ZZ )
212, 6gausslemma2dlem0b 16425 . . . . . . . . . . 11  |-  ( ph  ->  M  e.  NN )
2221nnzd 9781 . . . . . . . . . 10  |-  ( ph  ->  M  e.  ZZ )
2320, 22fzfigd 10892 . . . . . . . . 9  |-  ( ph  ->  ( 1 ... M
)  e.  Fin )
241, 5gausslemma2dlem0b 16425 . . . . . . . . . . 11  |-  ( ph  ->  N  e.  NN )
2524nnzd 9781 . . . . . . . . . 10  |-  ( ph  ->  N  e.  ZZ )
2620, 25fzfigd 10892 . . . . . . . . 9  |-  ( ph  ->  ( 1 ... N
)  e.  Fin )
27 elfznn 10480 . . . . . . . . . . . . . 14  |-  ( x  e.  ( 1 ... M )  ->  x  e.  NN )
2827ad2antrl 494 . . . . . . . . . . . . 13  |-  ( (
ph  /\  ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) ) )  ->  x  e.  NN )
291eldifad 3231 . . . . . . . . . . . . . . 15  |-  ( ph  ->  Q  e.  Prime )
3029adantr 276 . . . . . . . . . . . . . 14  |-  ( (
ph  /\  ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) ) )  ->  Q  e.  Prime )
31 prmnn 12916 . . . . . . . . . . . . . 14  |-  ( Q  e.  Prime  ->  Q  e.  NN )
3230, 31syl 14 . . . . . . . . . . . . 13  |-  ( (
ph  /\  ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) ) )  ->  Q  e.  NN )
3328, 32nnmulcld 9366 . . . . . . . . . . . 12  |-  ( (
ph  /\  ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) ) )  -> 
( x  x.  Q
)  e.  NN )
3433nnzd 9781 . . . . . . . . . . 11  |-  ( (
ph  /\  ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) ) )  -> 
( x  x.  Q
)  e.  ZZ )
35 elfznn 10480 . . . . . . . . . . . . . 14  |-  ( y  e.  ( 1 ... N )  ->  y  e.  NN )
3635ad2antll 495 . . . . . . . . . . . . 13  |-  ( (
ph  /\  ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) ) )  -> 
y  e.  NN )
372gausslemma2dlem0a 16424 . . . . . . . . . . . . . 14  |-  ( ph  ->  P  e.  NN )
3837adantr 276 . . . . . . . . . . . . 13  |-  ( (
ph  /\  ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) ) )  ->  P  e.  NN )
3936, 38nnmulcld 9366 . . . . . . . . . . . 12  |-  ( (
ph  /\  ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) ) )  -> 
( y  x.  P
)  e.  NN )
4039nnzd 9781 . . . . . . . . . . 11  |-  ( (
ph  /\  ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) ) )  -> 
( y  x.  P
)  e.  ZZ )
41 zdclt 9735 . . . . . . . . . . 11  |-  ( ( ( x  x.  Q
)  e.  ZZ  /\  ( y  x.  P
)  e.  ZZ )  -> DECID 
( x  x.  Q
)  <  ( y  x.  P ) )
4234, 40, 41syl2anc 415 . . . . . . . . . 10  |-  ( (
ph  /\  ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) ) )  -> DECID  (
x  x.  Q )  <  ( y  x.  P ) )
4342ralrimivva 2632 . . . . . . . . 9  |-  ( ph  ->  A. x  e.  ( 1 ... M ) A. y  e.  ( 1 ... N )DECID  ( x  x.  Q )  <  ( y  x.  P ) )
4419, 23, 26, 43opabfi 7256 . . . . . . . 8  |-  ( ph  ->  { <. x ,  y
>.  |  ( (
x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N ) )  /\  ( x  x.  Q )  <  (
y  x.  P ) ) }  e.  Fin )
45 cnven 7105 . . . . . . . 8  |-  ( ( Rel  { <. x ,  y >.  |  ( ( x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N ) )  /\  ( x  x.  Q )  < 
( y  x.  P
) ) }  /\  {
<. x ,  y >.  |  ( ( x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N
) )  /\  (
x  x.  Q )  <  ( y  x.  P ) ) }  e.  Fin )  ->  { <. x ,  y
>.  |  ( (
x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N ) )  /\  ( x  x.  Q )  <  (
y  x.  P ) ) }  ~~  `' { <. x ,  y
>.  |  ( (
x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N ) )  /\  ( x  x.  Q )  <  (
y  x.  P ) ) } )
4618, 44, 45sylancr 418 . . . . . . 7  |-  ( ph  ->  { <. x ,  y
>.  |  ( (
x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N ) )  /\  ( x  x.  Q )  <  (
y  x.  P ) ) }  ~~  `' { <. x ,  y
>.  |  ( (
x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N ) )  /\  ( x  x.  Q )  <  (
y  x.  P ) ) } )
47 cnvopab 5195 . . . . . . 7  |-  `' { <. x ,  y >.  |  ( ( x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N
) )  /\  (
x  x.  Q )  <  ( y  x.  P ) ) }  =  { <. y ,  x >.  |  (
( x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N ) )  /\  ( x  x.  Q )  < 
( y  x.  P
) ) }
4846, 47breqtrdi 4172 . . . . . 6  |-  ( ph  ->  { <. x ,  y
>.  |  ( (
x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N ) )  /\  ( x  x.  Q )  <  (
y  x.  P ) ) }  ~~  { <. y ,  x >.  |  ( ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) )  /\  (
x  x.  Q )  <  ( y  x.  P ) ) } )
491, 2, 4, 5, 6, 16lgsquadlemsfi 16450 . . . . . . 7  |-  ( ph  ->  { <. y ,  x >.  |  ( ( x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N
) )  /\  (
x  x.  Q )  <  ( y  x.  P ) ) }  e.  Fin )
50 hashen 11248 . . . . . . 7  |-  ( ( { <. x ,  y
>.  |  ( (
x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N ) )  /\  ( x  x.  Q )  <  (
y  x.  P ) ) }  e.  Fin  /\ 
{ <. y ,  x >.  |  ( ( x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N
) )  /\  (
x  x.  Q )  <  ( y  x.  P ) ) }  e.  Fin )  -> 
( (♯ `  { <. x ,  y >.  |  ( ( x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N
) )  /\  (
x  x.  Q )  <  ( y  x.  P ) ) } )  =  (♯ `  { <. y ,  x >.  |  ( ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) )  /\  (
x  x.  Q )  <  ( y  x.  P ) ) } )  <->  { <. x ,  y
>.  |  ( (
x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N ) )  /\  ( x  x.  Q )  <  (
y  x.  P ) ) }  ~~  { <. y ,  x >.  |  ( ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) )  /\  (
x  x.  Q )  <  ( y  x.  P ) ) } ) )
5144, 49, 50syl2anc 415 . . . . . 6  |-  ( ph  ->  ( (♯ `  { <. x ,  y >.  |  ( ( x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N
) )  /\  (
x  x.  Q )  <  ( y  x.  P ) ) } )  =  (♯ `  { <. y ,  x >.  |  ( ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) )  /\  (
x  x.  Q )  <  ( y  x.  P ) ) } )  <->  { <. x ,  y
>.  |  ( (
x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N ) )  /\  ( x  x.  Q )  <  (
y  x.  P ) ) }  ~~  { <. y ,  x >.  |  ( ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) )  /\  (
x  x.  Q )  <  ( y  x.  P ) ) } ) )
5248, 51mpbird 167 . . . . 5  |-  ( ph  ->  (♯ `  { <. x ,  y >.  |  ( ( x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N ) )  /\  ( x  x.  Q )  < 
( y  x.  P
) ) } )  =  (♯ `  { <. y ,  x >.  |  ( ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) )  /\  (
x  x.  Q )  <  ( y  x.  P ) ) } ) )
5352oveq2d 6107 . . . 4  |-  ( ph  ->  (  -u 1 ^ (♯ `  { <. x ,  y
>.  |  ( (
x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N ) )  /\  ( x  x.  Q )  <  (
y  x.  P ) ) } ) )  =  (  -u 1 ^ (♯ `  { <. y ,  x >.  |  (
( x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N ) )  /\  ( x  x.  Q )  < 
( y  x.  P
) ) } ) ) )
5417, 53eqtr4d 2274 . . 3  |-  ( ph  ->  ( P  /L
Q )  =  ( 
-u 1 ^ (♯ `  { <. x ,  y
>.  |  ( (
x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N ) )  /\  ( x  x.  Q )  <  (
y  x.  P ) ) } ) ) )
55 lgsquad.6 . . . 4  |-  S  =  { <. x ,  y
>.  |  ( (
x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N ) )  /\  ( y  x.  P )  <  (
x  x.  Q ) ) }
562, 1, 3, 6, 5, 55lgsquadlem2 16453 . . 3  |-  ( ph  ->  ( Q  /L
P )  =  ( 
-u 1 ^ (♯ `  S ) ) )
5754, 56oveq12d 6109 . 2  |-  ( ph  ->  ( ( P  /L Q )  x.  ( Q  /L
P ) )  =  ( (  -u 1 ^ (♯ `  { <. x ,  y >.  |  ( ( x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N ) )  /\  ( x  x.  Q )  < 
( y  x.  P
) ) } ) )  x.  (  -u
1 ^ (♯ `  S
) ) ) )
58 neg1cn 9422 . . . 4  |-  -u 1  e.  CC
5958a1i 9 . . 3  |-  ( ph  -> 
-u 1  e.  CC )
602, 1, 3, 6, 5, 55lgsquadlemsfi 16450 . . . 4  |-  ( ph  ->  S  e.  Fin )
61 hashcl 11245 . . . 4  |-  ( S  e.  Fin  ->  (♯ `  S )  e.  NN0 )
6260, 61syl 14 . . 3  |-  ( ph  ->  (♯ `  S )  e.  NN0 )
63 hashcl 11245 . . . 4  |-  ( {
<. x ,  y >.  |  ( ( x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N
) )  /\  (
x  x.  Q )  <  ( y  x.  P ) ) }  e.  Fin  ->  (♯ `  { <. x ,  y
>.  |  ( (
x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N ) )  /\  ( x  x.  Q )  <  (
y  x.  P ) ) } )  e. 
NN0 )
6444, 63syl 14 . . 3  |-  ( ph  ->  (♯ `  { <. x ,  y >.  |  ( ( x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N ) )  /\  ( x  x.  Q )  < 
( y  x.  P
) ) } )  e.  NN0 )
6559, 62, 64expaddd 11137 . 2  |-  ( ph  ->  (  -u 1 ^ (
(♯ `  { <. x ,  y >.  |  ( ( x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N ) )  /\  ( x  x.  Q )  < 
( y  x.  P
) ) } )  +  (♯ `  S
) ) )  =  ( (  -u 1 ^ (♯ `  { <. x ,  y >.  |  ( ( x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N ) )  /\  ( x  x.  Q )  < 
( y  x.  P
) ) } ) )  x.  (  -u
1 ^ (♯ `  S
) ) ) )
6624adantr 276 . . . . . . . . . . . . . . . . . . 19  |-  ( (
ph  /\  ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) ) )  ->  N  e.  NN )
6766nnzd 9781 . . . . . . . . . . . . . . . . . 18  |-  ( (
ph  /\  ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) ) )  ->  N  e.  ZZ )
68 prmz 12917 . . . . . . . . . . . . . . . . . . . 20  |-  ( Q  e.  Prime  ->  Q  e.  ZZ )
6930, 68syl 14 . . . . . . . . . . . . . . . . . . 19  |-  ( (
ph  /\  ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) ) )  ->  Q  e.  ZZ )
70 peano2zm 9695 . . . . . . . . . . . . . . . . . . 19  |-  ( Q  e.  ZZ  ->  ( Q  -  1 )  e.  ZZ )
7169, 70syl 14 . . . . . . . . . . . . . . . . . 18  |-  ( (
ph  /\  ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) ) )  -> 
( Q  -  1 )  e.  ZZ )
7266nnred 9330 . . . . . . . . . . . . . . . . . . 19  |-  ( (
ph  /\  ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) ) )  ->  N  e.  RR )
7371zred 9782 . . . . . . . . . . . . . . . . . . 19  |-  ( (
ph  /\  ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) ) )  -> 
( Q  -  1 )  e.  RR )
74 prmuz2 12938 . . . . . . . . . . . . . . . . . . . . . . . 24  |-  ( Q  e.  Prime  ->  Q  e.  ( ZZ>= `  2 )
)
7530, 74syl 14 . . . . . . . . . . . . . . . . . . . . . . 23  |-  ( (
ph  /\  ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) ) )  ->  Q  e.  ( ZZ>= ` 
2 ) )
76 uz2m1nn 10024 . . . . . . . . . . . . . . . . . . . . . . 23  |-  ( Q  e.  ( ZZ>= `  2
)  ->  ( Q  -  1 )  e.  NN )
7775, 76syl 14 . . . . . . . . . . . . . . . . . . . . . 22  |-  ( (
ph  /\  ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) ) )  -> 
( Q  -  1 )  e.  NN )
7877nnrpd 10115 . . . . . . . . . . . . . . . . . . . . 21  |-  ( (
ph  /\  ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) ) )  -> 
( Q  -  1 )  e.  RR+ )
79 rphalflt 10104 . . . . . . . . . . . . . . . . . . . . 21  |-  ( ( Q  -  1 )  e.  RR+  ->  ( ( Q  -  1 )  /  2 )  < 
( Q  -  1 ) )
8078, 79syl 14 . . . . . . . . . . . . . . . . . . . 20  |-  ( (
ph  /\  ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) ) )  -> 
( ( Q  - 
1 )  /  2
)  <  ( Q  -  1 ) )
815, 80eqbrtrid 4166 . . . . . . . . . . . . . . . . . . 19  |-  ( (
ph  /\  ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) ) )  ->  N  <  ( Q  - 
1 ) )
8272, 73, 81ltled 8456 . . . . . . . . . . . . . . . . . 18  |-  ( (
ph  /\  ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) ) )  ->  N  <_  ( Q  - 
1 ) )
83 eluz2 9946 . . . . . . . . . . . . . . . . . 18  |-  ( ( Q  -  1 )  e.  ( ZZ>= `  N
)  <->  ( N  e.  ZZ  /\  ( Q  -  1 )  e.  ZZ  /\  N  <_ 
( Q  -  1 ) ) )
8467, 71, 82, 83syl3anbrc 1212 . . . . . . . . . . . . . . . . 17  |-  ( (
ph  /\  ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) ) )  -> 
( Q  -  1 )  e.  ( ZZ>= `  N ) )
85 fzss2 10490 . . . . . . . . . . . . . . . . 17  |-  ( ( Q  -  1 )  e.  ( ZZ>= `  N
)  ->  ( 1 ... N )  C_  ( 1 ... ( Q  -  1 ) ) )
8684, 85syl 14 . . . . . . . . . . . . . . . 16  |-  ( (
ph  /\  ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) ) )  -> 
( 1 ... N
)  C_  ( 1 ... ( Q  - 
1 ) ) )
87 simprr 537 . . . . . . . . . . . . . . . 16  |-  ( (
ph  /\  ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) ) )  -> 
y  e.  ( 1 ... N ) )
8886, 87sseldd 3249 . . . . . . . . . . . . . . 15  |-  ( (
ph  /\  ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) ) )  -> 
y  e.  ( 1 ... ( Q  - 
1 ) ) )
89 fzm1ndvds 12651 . . . . . . . . . . . . . . 15  |-  ( ( Q  e.  NN  /\  y  e.  ( 1 ... ( Q  - 
1 ) ) )  ->  -.  Q  ||  y
)
9032, 88, 89syl2anc 415 . . . . . . . . . . . . . 14  |-  ( (
ph  /\  ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) ) )  ->  -.  Q  ||  y )
914adantr 276 . . . . . . . . . . . . . . . 16  |-  ( (
ph  /\  ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) ) )  ->  Q  =/=  P )
922eldifad 3231 . . . . . . . . . . . . . . . . . 18  |-  ( ph  ->  P  e.  Prime )
9392adantr 276 . . . . . . . . . . . . . . . . 17  |-  ( (
ph  /\  ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) ) )  ->  P  e.  Prime )
94 prmrp 12952 . . . . . . . . . . . . . . . . 17  |-  ( ( Q  e.  Prime  /\  P  e.  Prime )  ->  (
( Q  gcd  P
)  =  1  <->  Q  =/=  P ) )
9530, 93, 94syl2anc 415 . . . . . . . . . . . . . . . 16  |-  ( (
ph  /\  ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) ) )  -> 
( ( Q  gcd  P )  =  1  <->  Q  =/=  P ) )
9691, 95mpbird 167 . . . . . . . . . . . . . . 15  |-  ( (
ph  /\  ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) ) )  -> 
( Q  gcd  P
)  =  1 )
97 prmz 12917 . . . . . . . . . . . . . . . . 17  |-  ( P  e.  Prime  ->  P  e.  ZZ )
9893, 97syl 14 . . . . . . . . . . . . . . . 16  |-  ( (
ph  /\  ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) ) )  ->  P  e.  ZZ )
99 elfzelz 10448 . . . . . . . . . . . . . . . . 17  |-  ( y  e.  ( 1 ... N )  ->  y  e.  ZZ )
10099ad2antll 495 . . . . . . . . . . . . . . . 16  |-  ( (
ph  /\  ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) ) )  -> 
y  e.  ZZ )
101 coprmdvds 12898 . . . . . . . . . . . . . . . 16  |-  ( ( Q  e.  ZZ  /\  P  e.  ZZ  /\  y  e.  ZZ )  ->  (
( Q  ||  ( P  x.  y )  /\  ( Q  gcd  P
)  =  1 )  ->  Q  ||  y
) )
10269, 98, 100, 101syl3anc 1278 . . . . . . . . . . . . . . 15  |-  ( (
ph  /\  ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) ) )  -> 
( ( Q  ||  ( P  x.  y
)  /\  ( Q  gcd  P )  =  1 )  ->  Q  ||  y
) )
10396, 102mpan2d 432 . . . . . . . . . . . . . 14  |-  ( (
ph  /\  ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) ) )  -> 
( Q  ||  ( P  x.  y )  ->  Q  ||  y ) )
10490, 103mtod 673 . . . . . . . . . . . . 13  |-  ( (
ph  /\  ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) ) )  ->  -.  Q  ||  ( P  x.  y ) )
10538nncnd 9331 . . . . . . . . . . . . . . 15  |-  ( (
ph  /\  ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) ) )  ->  P  e.  CC )
10636nncnd 9331 . . . . . . . . . . . . . . 15  |-  ( (
ph  /\  ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) ) )  -> 
y  e.  CC )
107105, 106mulcomd 8357 . . . . . . . . . . . . . 14  |-  ( (
ph  /\  ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) ) )  -> 
( P  x.  y
)  =  ( y  x.  P ) )
108107breq2d 4143 . . . . . . . . . . . . 13  |-  ( (
ph  /\  ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) ) )  -> 
( Q  ||  ( P  x.  y )  <->  Q 
||  ( y  x.  P ) ) )
109104, 108mtbid 683 . . . . . . . . . . . 12  |-  ( (
ph  /\  ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) ) )  ->  -.  Q  ||  ( y  x.  P ) )
110 elfzelz 10448 . . . . . . . . . . . . . . . 16  |-  ( x  e.  ( 1 ... M )  ->  x  e.  ZZ )
111110ad2antrl 494 . . . . . . . . . . . . . . 15  |-  ( (
ph  /\  ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) ) )  ->  x  e.  ZZ )
112 dvdsmul2 12609 . . . . . . . . . . . . . . 15  |-  ( ( x  e.  ZZ  /\  Q  e.  ZZ )  ->  Q  ||  ( x  x.  Q ) )
113111, 69, 112syl2anc 415 . . . . . . . . . . . . . 14  |-  ( (
ph  /\  ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) ) )  ->  Q  ||  ( x  x.  Q ) )
114 breq2 4135 . . . . . . . . . . . . . 14  |-  ( ( x  x.  Q )  =  ( y  x.  P )  ->  ( Q  ||  ( x  x.  Q )  <->  Q  ||  (
y  x.  P ) ) )
115113, 114syl5ibcom 155 . . . . . . . . . . . . 13  |-  ( (
ph  /\  ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) ) )  -> 
( ( x  x.  Q )  =  ( y  x.  P )  ->  Q  ||  (
y  x.  P ) ) )
116115necon3bd 2463 . . . . . . . . . . . 12  |-  ( (
ph  /\  ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) ) )  -> 
( -.  Q  ||  ( y  x.  P
)  ->  ( x  x.  Q )  =/=  (
y  x.  P ) ) )
117109, 116mpd 13 . . . . . . . . . . 11  |-  ( (
ph  /\  ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) ) )  -> 
( x  x.  Q
)  =/=  ( y  x.  P ) )
118 nnq 10052 . . . . . . . . . . . . 13  |-  ( ( x  x.  Q )  e.  NN  ->  (
x  x.  Q )  e.  QQ )
11933, 118syl 14 . . . . . . . . . . . 12  |-  ( (
ph  /\  ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) ) )  -> 
( x  x.  Q
)  e.  QQ )
120 nnq 10052 . . . . . . . . . . . . 13  |-  ( ( y  x.  P )  e.  NN  ->  (
y  x.  P )  e.  QQ )
12139, 120syl 14 . . . . . . . . . . . 12  |-  ( (
ph  /\  ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) ) )  -> 
( y  x.  P
)  e.  QQ )
122 qlttri2 10060 . . . . . . . . . . . 12  |-  ( ( ( x  x.  Q
)  e.  QQ  /\  ( y  x.  P
)  e.  QQ )  ->  ( ( x  x.  Q )  =/=  ( y  x.  P
)  <->  ( ( x  x.  Q )  < 
( y  x.  P
)  \/  ( y  x.  P )  < 
( x  x.  Q
) ) ) )
123119, 121, 122syl2anc 415 . . . . . . . . . . 11  |-  ( (
ph  /\  ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) ) )  -> 
( ( x  x.  Q )  =/=  (
y  x.  P )  <-> 
( ( x  x.  Q )  <  (
y  x.  P )  \/  ( y  x.  P )  <  (
x  x.  Q ) ) ) )
124117, 123mpbid 147 . . . . . . . . . 10  |-  ( (
ph  /\  ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) ) )  -> 
( ( x  x.  Q )  <  (
y  x.  P )  \/  ( y  x.  P )  <  (
x  x.  Q ) ) )
125124ex 115 . . . . . . . . 9  |-  ( ph  ->  ( ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) )  ->  (
( x  x.  Q
)  <  ( y  x.  P )  \/  (
y  x.  P )  <  ( x  x.  Q ) ) ) )
126125pm4.71rd 398 . . . . . . . 8  |-  ( ph  ->  ( ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) )  <->  ( (
( x  x.  Q
)  <  ( y  x.  P )  \/  (
y  x.  P )  <  ( x  x.  Q ) )  /\  ( x  e.  (
1 ... M )  /\  y  e.  ( 1 ... N ) ) ) ) )
127 ancom 266 . . . . . . . 8  |-  ( ( ( ( x  x.  Q )  <  (
y  x.  P )  \/  ( y  x.  P )  <  (
x  x.  Q ) )  /\  ( x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N
) ) )  <->  ( (
x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N ) )  /\  ( ( x  x.  Q )  < 
( y  x.  P
)  \/  ( y  x.  P )  < 
( x  x.  Q
) ) ) )
128126, 127bitr2di 197 . . . . . . 7  |-  ( ph  ->  ( ( ( x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N
) )  /\  (
( x  x.  Q
)  <  ( y  x.  P )  \/  (
y  x.  P )  <  ( x  x.  Q ) ) )  <-> 
( x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N ) ) ) )
129128opabbidv 4198 . . . . . 6  |-  ( ph  ->  { <. x ,  y
>.  |  ( (
x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N ) )  /\  ( ( x  x.  Q )  < 
( y  x.  P
)  \/  ( y  x.  P )  < 
( x  x.  Q
) ) ) }  =  { <. x ,  y >.  |  ( x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N ) ) } )
130 unopab 4211 . . . . . . 7  |-  ( {
<. x ,  y >.  |  ( ( x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N
) )  /\  (
x  x.  Q )  <  ( y  x.  P ) ) }  u.  { <. x ,  y >.  |  ( ( x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N ) )  /\  ( y  x.  P )  < 
( x  x.  Q
) ) } )  =  { <. x ,  y >.  |  ( ( ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) )  /\  (
x  x.  Q )  <  ( y  x.  P ) )  \/  ( ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) )  /\  (
y  x.  P )  <  ( x  x.  Q ) ) ) }
13155uneq2i 3380 . . . . . . 7  |-  ( {
<. x ,  y >.  |  ( ( x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N
) )  /\  (
x  x.  Q )  <  ( y  x.  P ) ) }  u.  S )  =  ( { <. x ,  y >.  |  ( ( x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N ) )  /\  ( x  x.  Q )  < 
( y  x.  P
) ) }  u.  {
<. x ,  y >.  |  ( ( x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N
) )  /\  (
y  x.  P )  <  ( x  x.  Q ) ) } )
132 andi 830 . . . . . . . 8  |-  ( ( ( x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N ) )  /\  ( ( x  x.  Q )  <  ( y  x.  P )  \/  (
y  x.  P )  <  ( x  x.  Q ) ) )  <-> 
( ( ( x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N
) )  /\  (
x  x.  Q )  <  ( y  x.  P ) )  \/  ( ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) )  /\  (
y  x.  P )  <  ( x  x.  Q ) ) ) )
133132opabbii 4199 . . . . . . 7  |-  { <. x ,  y >.  |  ( ( x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N ) )  /\  ( ( x  x.  Q )  <  ( y  x.  P )  \/  (
y  x.  P )  <  ( x  x.  Q ) ) ) }  =  { <. x ,  y >.  |  ( ( ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) )  /\  (
x  x.  Q )  <  ( y  x.  P ) )  \/  ( ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) )  /\  (
y  x.  P )  <  ( x  x.  Q ) ) ) }
134130, 131, 1333eqtr4i 2269 . . . . . 6  |-  ( {
<. x ,  y >.  |  ( ( x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N
) )  /\  (
x  x.  Q )  <  ( y  x.  P ) ) }  u.  S )  =  { <. x ,  y
>.  |  ( (
x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N ) )  /\  ( ( x  x.  Q )  < 
( y  x.  P
)  \/  ( y  x.  P )  < 
( x  x.  Q
) ) ) }
135 df-xp 4782 . . . . . 6  |-  ( ( 1 ... M )  X.  ( 1 ... N ) )  =  { <. x ,  y
>.  |  ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) ) }
136129, 134, 1353eqtr4g 2296 . . . . 5  |-  ( ph  ->  ( { <. x ,  y >.  |  ( ( x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N ) )  /\  ( x  x.  Q )  < 
( y  x.  P
) ) }  u.  S )  =  ( ( 1 ... M
)  X.  ( 1 ... N ) ) )
137136fveq2d 5705 . . . 4  |-  ( ph  ->  (♯ `  ( { <. x ,  y >.  |  ( ( x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N
) )  /\  (
x  x.  Q )  <  ( y  x.  P ) ) }  u.  S ) )  =  (♯ `  (
( 1 ... M
)  X.  ( 1 ... N ) ) ) )
138 inopab 4914 . . . . . . 7  |-  ( {
<. x ,  y >.  |  ( ( x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N
) )  /\  (
x  x.  Q )  <  ( y  x.  P ) ) }  i^i  { <. x ,  y >.  |  ( ( x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N ) )  /\  ( y  x.  P )  < 
( x  x.  Q
) ) } )  =  { <. x ,  y >.  |  ( ( ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) )  /\  (
x  x.  Q )  <  ( y  x.  P ) )  /\  ( ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) )  /\  (
y  x.  P )  <  ( x  x.  Q ) ) ) }
13955ineq2i 3429 . . . . . . 7  |-  ( {
<. x ,  y >.  |  ( ( x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N
) )  /\  (
x  x.  Q )  <  ( y  x.  P ) ) }  i^i  S )  =  ( { <. x ,  y >.  |  ( ( x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N ) )  /\  ( x  x.  Q )  < 
( y  x.  P
) ) }  i^i  {
<. x ,  y >.  |  ( ( x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N
) )  /\  (
y  x.  P )  <  ( x  x.  Q ) ) } )
140 anandi 598 . . . . . . . 8  |-  ( ( ( x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N ) )  /\  ( ( x  x.  Q )  <  ( y  x.  P )  /\  (
y  x.  P )  <  ( x  x.  Q ) ) )  <-> 
( ( ( x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N
) )  /\  (
x  x.  Q )  <  ( y  x.  P ) )  /\  ( ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) )  /\  (
y  x.  P )  <  ( x  x.  Q ) ) ) )
141140opabbii 4199 . . . . . . 7  |-  { <. x ,  y >.  |  ( ( x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N ) )  /\  ( ( x  x.  Q )  <  ( y  x.  P )  /\  (
y  x.  P )  <  ( x  x.  Q ) ) ) }  =  { <. x ,  y >.  |  ( ( ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) )  /\  (
x  x.  Q )  <  ( y  x.  P ) )  /\  ( ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) )  /\  (
y  x.  P )  <  ( x  x.  Q ) ) ) }
142138, 139, 1413eqtr4i 2269 . . . . . 6  |-  ( {
<. x ,  y >.  |  ( ( x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N
) )  /\  (
x  x.  Q )  <  ( y  x.  P ) ) }  i^i  S )  =  { <. x ,  y
>.  |  ( (
x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N ) )  /\  ( ( x  x.  Q )  < 
( y  x.  P
)  /\  ( y  x.  P )  <  (
x  x.  Q ) ) ) }
14333nnred 9330 . . . . . . . . . . . . 13  |-  ( (
ph  /\  ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) ) )  -> 
( x  x.  Q
)  e.  RR )
14439nnred 9330 . . . . . . . . . . . . 13  |-  ( (
ph  /\  ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) ) )  -> 
( y  x.  P
)  e.  RR )
145 ltnsym2 8426 . . . . . . . . . . . . 13  |-  ( ( ( x  x.  Q
)  e.  RR  /\  ( y  x.  P
)  e.  RR )  ->  -.  ( (
x  x.  Q )  <  ( y  x.  P )  /\  (
y  x.  P )  <  ( x  x.  Q ) ) )
146143, 144, 145syl2anc 415 . . . . . . . . . . . 12  |-  ( (
ph  /\  ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) ) )  ->  -.  ( ( x  x.  Q )  <  (
y  x.  P )  /\  ( y  x.  P )  <  (
x  x.  Q ) ) )
147146ex 115 . . . . . . . . . . 11  |-  ( ph  ->  ( ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) )  ->  -.  ( ( x  x.  Q )  <  (
y  x.  P )  /\  ( y  x.  P )  <  (
x  x.  Q ) ) ) )
148 imnan 701 . . . . . . . . . . 11  |-  ( ( ( x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N ) )  ->  -.  (
( x  x.  Q
)  <  ( y  x.  P )  /\  (
y  x.  P )  <  ( x  x.  Q ) ) )  <->  -.  ( ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) )  /\  (
( x  x.  Q
)  <  ( y  x.  P )  /\  (
y  x.  P )  <  ( x  x.  Q ) ) ) )
149147, 148sylib 122 . . . . . . . . . 10  |-  ( ph  ->  -.  ( ( x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N
) )  /\  (
( x  x.  Q
)  <  ( y  x.  P )  /\  (
y  x.  P )  <  ( x  x.  Q ) ) ) )
150149nexdv 1996 . . . . . . . . 9  |-  ( ph  ->  -.  E. y ( ( x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N ) )  /\  ( ( x  x.  Q )  <  ( y  x.  P )  /\  (
y  x.  P )  <  ( x  x.  Q ) ) ) )
151150nexdv 1996 . . . . . . . 8  |-  ( ph  ->  -.  E. x E. y ( ( x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N
) )  /\  (
( x  x.  Q
)  <  ( y  x.  P )  /\  (
y  x.  P )  <  ( x  x.  Q ) ) ) )
152 opabm 4425 . . . . . . . 8  |-  ( E. j  j  e.  { <. x ,  y >.  |  ( ( x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N
) )  /\  (
( x  x.  Q
)  <  ( y  x.  P )  /\  (
y  x.  P )  <  ( x  x.  Q ) ) ) }  <->  E. x E. y
( ( x  e.  ( 1 ... M
)  /\  y  e.  ( 1 ... N
) )  /\  (
( x  x.  Q
)  <  ( y  x.  P )  /\  (
y  x.  P )  <  ( x  x.  Q ) ) ) )
153151, 152sylnibr 688 . . . . . . 7  |-  ( ph  ->  -.  E. j  j  e.  { <. x ,  y >.  |  ( ( x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N ) )  /\  ( ( x  x.  Q )  <  ( y  x.  P )  /\  (
y  x.  P )  <  ( x  x.  Q ) ) ) } )
154 notm0 3542 . . . . . . 7  |-  ( -. 
E. j  j  e. 
{ <. x ,  y
>.  |  ( (
x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N ) )  /\  ( ( x  x.  Q )  < 
( y  x.  P
)  /\  ( y  x.  P )  <  (
x  x.  Q ) ) ) }  <->  { <. x ,  y >.  |  ( ( x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N ) )  /\  ( ( x  x.  Q )  <  ( y  x.  P )  /\  (
y  x.  P )  <  ( x  x.  Q ) ) ) }  =  (/) )
155153, 154sylib 122 . . . . . 6  |-  ( ph  ->  { <. x ,  y
>.  |  ( (
x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N ) )  /\  ( ( x  x.  Q )  < 
( y  x.  P
)  /\  ( y  x.  P )  <  (
x  x.  Q ) ) ) }  =  (/) )
156142, 155eqtrid 2283 . . . . 5  |-  ( ph  ->  ( { <. x ,  y >.  |  ( ( x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N ) )  /\  ( x  x.  Q )  < 
( y  x.  P
) ) }  i^i  S )  =  (/) )
157 hashun 11270 . . . . 5  |-  ( ( { <. x ,  y
>.  |  ( (
x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N ) )  /\  ( x  x.  Q )  <  (
y  x.  P ) ) }  e.  Fin  /\  S  e.  Fin  /\  ( { <. x ,  y
>.  |  ( (
x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N ) )  /\  ( x  x.  Q )  <  (
y  x.  P ) ) }  i^i  S
)  =  (/) )  -> 
(♯ `  ( { <. x ,  y >.  |  ( ( x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N ) )  /\  ( x  x.  Q )  < 
( y  x.  P
) ) }  u.  S ) )  =  ( (♯ `  { <. x ,  y >.  |  ( ( x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N
) )  /\  (
x  x.  Q )  <  ( y  x.  P ) ) } )  +  (♯ `  S
) ) )
15844, 60, 156, 157syl3anc 1278 . . . 4  |-  ( ph  ->  (♯ `  ( { <. x ,  y >.  |  ( ( x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N
) )  /\  (
x  x.  Q )  <  ( y  x.  P ) ) }  u.  S ) )  =  ( (♯ `  { <. x ,  y >.  |  ( ( x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N
) )  /\  (
x  x.  Q )  <  ( y  x.  P ) ) } )  +  (♯ `  S
) ) )
159 hashxp 11292 . . . . . 6  |-  ( ( ( 1 ... M
)  e.  Fin  /\  ( 1 ... N
)  e.  Fin )  ->  (♯ `  ( (
1 ... M )  X.  ( 1 ... N
) ) )  =  ( (♯ `  (
1 ... M ) )  x.  (♯ `  (
1 ... N ) ) ) )
16023, 26, 159syl2anc 415 . . . . 5  |-  ( ph  ->  (♯ `  ( (
1 ... M )  X.  ( 1 ... N
) ) )  =  ( (♯ `  (
1 ... M ) )  x.  (♯ `  (
1 ... N ) ) ) )
16121nnnn0d 9633 . . . . . . 7  |-  ( ph  ->  M  e.  NN0 )
162 hashfz1 11247 . . . . . . 7  |-  ( M  e.  NN0  ->  (♯ `  (
1 ... M ) )  =  M )
163161, 162syl 14 . . . . . 6  |-  ( ph  ->  (♯ `  ( 1 ... M ) )  =  M )
16424nnnn0d 9633 . . . . . . 7  |-  ( ph  ->  N  e.  NN0 )
165 hashfz1 11247 . . . . . . 7  |-  ( N  e.  NN0  ->  (♯ `  (
1 ... N ) )  =  N )
166164, 165syl 14 . . . . . 6  |-  ( ph  ->  (♯ `  ( 1 ... N ) )  =  N )
167163, 166oveq12d 6109 . . . . 5  |-  ( ph  ->  ( (♯ `  (
1 ... M ) )  x.  (♯ `  (
1 ... N ) ) )  =  ( M  x.  N ) )
168160, 167eqtrd 2271 . . . 4  |-  ( ph  ->  (♯ `  ( (
1 ... M )  X.  ( 1 ... N
) ) )  =  ( M  x.  N
) )
169137, 158, 1683eqtr3d 2279 . . 3  |-  ( ph  ->  ( (♯ `  { <. x ,  y >.  |  ( ( x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N
) )  /\  (
x  x.  Q )  <  ( y  x.  P ) ) } )  +  (♯ `  S
) )  =  ( M  x.  N ) )
170169oveq2d 6107 . 2  |-  ( ph  ->  (  -u 1 ^ (
(♯ `  { <. x ,  y >.  |  ( ( x  e.  ( 1 ... M )  /\  y  e.  ( 1 ... N ) )  /\  ( x  x.  Q )  < 
( y  x.  P
) ) } )  +  (♯ `  S
) ) )  =  (  -u 1 ^ ( M  x.  N )
) )
17157, 65, 1703eqtr2d 2277 1  |-  ( ph  ->  ( ( P  /L Q )  x.  ( Q  /L
P ) )  =  (  -u 1 ^ ( M  x.  N )
) )
Colors of variables:    wff set class
This proof depends on syntax axioms:   -. wn 3    -> wi 4    /\ wa 104    <-> wb 105    \/ wo 720  DECID wdc 846    = wceq 1402   E.wex 1545    e. wcel 2209    =/= wne 2420    \ cdif 3217    u. cun 3218    i^i cin 3219    C_ wss 3220   (/)c0 3520   {csn 3709   class class class wbr 4131   {copab 4192    X. cxp 4774   `'ccnv 4775   Rel wrel 4781   ` cfv 5383  (class class class)co 6091    ~~ cen 7029   Fincfn 7031   CCcc 8187   RRcr 8188   1c1 8190    + caddc 8192    x. cmul 8194    < clt 8370    <_ cle 8371    - cmin 8508    -ucneg 8509    / cdiv 9014   NNcn 9317   2c2 9368   NN0cn0 9578   ZZcz 9657   ZZ>=cuz 9940   QQcq 10038   RR+crp 10074   ...cfz 10431   ^cexp 10999  ♯chash 11239    || cdvds 12582    gcd cgcd 12758   Primecprime 12913    /Lclgs 16372
This proof depends on axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-ia1 106  ax-ia2 107  ax-ia3 108  ax-in1 623  ax-in2 624  ax-io 721  ax-5 1500  ax-7 1501  ax-gen 1502  ax-ie1 1546  ax-ie2 1547  ax-8 1557  ax-10 1558  ax-11 1559  ax-i12 1560  ax-bndl 1562  ax-4 1563  ax-17 1579  ax-i9 1583  ax-ial 1587  ax-i5r 1588  ax-14 2212  ax-ext 2220  ax-coll 4248  ax-sep 4251  ax-nul 4261  ax-pow 4313  ax-pr 4348  ax-un 4580  ax-setind 4686  ax-iinf 4737  ax-cnex 8280  ax-resscn 8281  ax-1cn 8282  ax-1re 8283  ax-icn 8284  ax-addcl 8285  ax-addrcl 8286  ax-mulcl 8287  ax-mulrcl 8288  ax-addcom 8289  ax-mulcom 8290  ax-addass 8291  ax-mulass 8292  ax-distr 8293  ax-i2m1 8294  ax-0lt1 8295  ax-1rid 8296  ax-0id 8297  ax-rnegex 8298  ax-precex 8299  ax-cnre 8300  ax-pre-ltirr 8301  ax-pre-ltwlin 8302  ax-pre-lttrn 8303  ax-pre-apti 8304  ax-pre-ltadd 8305  ax-pre-mulgt0 8306  ax-pre-mulext 8307  ax-arch 8308  ax-caucvg 8309  ax-addf 8311  ax-mulf 8312
This proof depends on definitions:  df-bi 117  df-stab 843  df-dc 847  df-3or 1010  df-3an 1011  df-tru 1405  df-fal 1408  df-xor 1425  df-nf 1514  df-sb 1816  df-eu 2089  df-mo 2090  df-clab 2225  df-cleq 2231  df-clel 2234  df-nfc 2381  df-ne 2421  df-nel 2516  df-ral 2533  df-rex 2534  df-reu 2535  df-rmo 2536  df-rab 2537  df-v 2823  df-sbc 3052  df-csb 3148  df-dif 3222  df-un 3224  df-in 3226  df-ss 3233  df-nul 3521  df-if 3639  df-pw 3690  df-sn 3715  df-pr 3716  df-tp 3717  df-op 3718  df-uni 3936  df-int 3971  df-iun 4014  df-disj 4107  df-br 4132  df-opab 4194  df-mpt 4195  df-tr 4232  df-id 4440  df-po 4443  df-iso 4444  df-iord 4513  df-on 4515  df-ilim 4516  df-suc 4518  df-iom 4740  df-xp 4782  df-rel 4783  df-cnv 4784  df-co 4785  df-dm 4786  df-rn 4787  df-res 4788  df-ima 4789  df-iota 5343  df-fun 5385  df-fn 5386  df-f 5387  df-f1 5388  df-fo 5389  df-f1o 5390  df-fv 5391  df-isom 5392  df-riota 6044  df-ov 6094  df-oprab 6095  df-mpo 6096  df-of 6308  df-1st 6381  df-2nd 6382  df-tpos 6524  df-recs 6584  df-irdg 6649  df-frec 6670  df-1o 6695  df-2o 6696  df-oadd 6699  df-er 6815  df-ec 6817  df-qs 6821  df-map 6932  df-en 7032  df-dom 7033  df-fin 7034  df-sup 7334  df-inf 7335  df-pnf 8372  df-mnf 8373  df-xr 8374  df-ltxr 8375  df-le 8376  df-sub 8510  df-neg 8511  df-reap 8915  df-ap 8922  df-div 9015  df-inn 9318  df-2 9376  df-3 9377  df-4 9378  df-5 9379  df-6 9380  df-7 9381  df-8 9382  df-9 9383  df-n0 9579  df-z 9658  df-dec 9792  df-uz 9941  df-q 10039  df-rp 10075  df-fz 10432  df-fzo 10570  df-fl 10725  df-mod 10784  df-seqfrec 10909  df-exp 11000  df-ihash 11240  df-cj 11632  df-re 11633  df-im 11634  df-rsqrt 11789  df-abs 11790  df-clim 12073  df-sumdc 12148  df-proddc 12346  df-dvds 12583  df-gcd 12759  df-prm 12914  df-phi 13021  df-pc 13096  df-struct 13415  df-ndx 13416  df-slot 13417  df-base 13419  df-sets 13420  df-iress 13421  df-plusg 13506  df-mulr 13507  df-starv 13508  df-sca 13509  df-vsca 13510  df-ip 13511  df-tset 13512  df-ple 13513  df-ds 13515  df-unif 13516  df-0g 13674  df-gzsum 13675  df-topgen 13676  df-iimas 13686  df-qus 13687  df-mgm 13738  df-sgrp 13779  df-mnd 13792  df-mhm 13828  df-submnd 13829  df-grp 13870  df-minusg 13871  df-sbg 13872  df-mulg 13985  df-subg 14035  df-nsg 14036  df-eqg 14037  df-ghm 14106  df-cmn 14182  df-abl 14183  df-gsumfi 14244  df-mgp 14329  df-rng 14343  df-ur 14374  df-srg 14379  df-ring 14413  df-cring 14414  df-oppr 14486  df-dvdsr 14508  df-unit 14509  df-invr 14541  df-dvr 14552  df-rhm 14572  df-nzr 14600  df-subrg 14640  df-domn 14681  df-idom 14682  df-lmod 14739  df-lssm 14804  df-lsp 14838  df-sra 14886  df-rgmod 14887  df-lidl 14920  df-rsp 14921  df-2idl 14951  df-bl 14997  df-mopn 14998  df-fg 15000  df-metu 15001  df-cnfld 15008  df-zring 15040  df-zrh 15063  df-zn 15065  df-lgs 16373
This theorem is used by:  lgsquad  16455
  Copyright terms: Public domain W3C validator