Users' Mathboxes Mathbox for Stefan O'Rear < Previous   Next >
Nearby theorems
Mirrors  >  Home  >  MPE Home  >  Th. List  >   Mathboxes  >  ismrcd1 Structured version   Visualization version   Unicode version

Theorem ismrcd1 35552
Description: Any function from the subsets of a set to itself, which is extensive (satisfies mrcssid 15535), isotone (satisfies mrcss 15534), and idempotent (satisfies mrcidm 15537) has a collection of fixed points which is a Moore collection, and itself is the closure operator for that collection. This can be taken as an alternate definition for the closure operators. This is the first half, ismrcd2 35553 is the second. (Contributed by Stefan O'Rear, 1-Feb-2015.)
Hypotheses
Ref Expression
ismrcd.b  |-  ( ph  ->  B  e.  V )
ismrcd.f  |-  ( ph  ->  F : ~P B --> ~P B )
ismrcd.e  |-  ( (
ph  /\  x  C_  B
)  ->  x  C_  ( F `  x )
)
ismrcd.m  |-  ( (
ph  /\  x  C_  B  /\  y  C_  x )  ->  ( F `  y )  C_  ( F `  x )
)
ismrcd.i  |-  ( (
ph  /\  x  C_  B
)  ->  ( F `  ( F `  x
) )  =  ( F `  x ) )
Assertion
Ref Expression
ismrcd1  |-  ( ph  ->  dom  ( F  i^i  _I  )  e.  (Moore `  B ) )
Distinct variable groups:    ph, x, y   
x, B, y    x, F, y    x, V, y

Proof of Theorem ismrcd1
Dummy variable  z is distinct from all other variables.
StepHypRef Expression
1 inss1 3654 . . . 4  |-  ( F  i^i  _I  )  C_  F
2 dmss 5037 . . . 4  |-  ( ( F  i^i  _I  )  C_  F  ->  dom  ( F  i^i  _I  )  C_  dom  F )
31, 2ax-mp 5 . . 3  |-  dom  ( F  i^i  _I  )  C_  dom  F
4 ismrcd.f . . . 4  |-  ( ph  ->  F : ~P B --> ~P B )
5 fdm 5738 . . . 4  |-  ( F : ~P B --> ~P B  ->  dom  F  =  ~P B )
64, 5syl 17 . . 3  |-  ( ph  ->  dom  F  =  ~P B )
73, 6syl5sseq 3482 . 2  |-  ( ph  ->  dom  ( F  i^i  _I  )  C_  ~P B
)
8 ssid 3453 . . . . . . 7  |-  B  C_  B
9 ismrcd.b . . . . . . . 8  |-  ( ph  ->  B  e.  V )
10 elpwg 3961 . . . . . . . 8  |-  ( B  e.  V  ->  ( B  e.  ~P B  <->  B 
C_  B ) )
119, 10syl 17 . . . . . . 7  |-  ( ph  ->  ( B  e.  ~P B 
<->  B  C_  B )
)
128, 11mpbiri 237 . . . . . 6  |-  ( ph  ->  B  e.  ~P B
)
134, 12ffvelrnd 6028 . . . . 5  |-  ( ph  ->  ( F `  B
)  e.  ~P B
)
1413elpwid 3963 . . . 4  |-  ( ph  ->  ( F `  B
)  C_  B )
15 selpw 3960 . . . . . . 7  |-  ( x  e.  ~P B  <->  x  C_  B
)
16 ismrcd.e . . . . . . 7  |-  ( (
ph  /\  x  C_  B
)  ->  x  C_  ( F `  x )
)
1715, 16sylan2b 478 . . . . . 6  |-  ( (
ph  /\  x  e.  ~P B )  ->  x  C_  ( F `  x
) )
1817ralrimiva 2804 . . . . 5  |-  ( ph  ->  A. x  e.  ~P  B x  C_  ( F `
 x ) )
19 id 22 . . . . . . 7  |-  ( x  =  B  ->  x  =  B )
20 fveq2 5870 . . . . . . 7  |-  ( x  =  B  ->  ( F `  x )  =  ( F `  B ) )
2119, 20sseq12d 3463 . . . . . 6  |-  ( x  =  B  ->  (
x  C_  ( F `  x )  <->  B  C_  ( F `  B )
) )
2221rspcva 3150 . . . . 5  |-  ( ( B  e.  ~P B  /\  A. x  e.  ~P  B x  C_  ( F `
 x ) )  ->  B  C_  ( F `  B )
)
2312, 18, 22syl2anc 667 . . . 4  |-  ( ph  ->  B  C_  ( F `  B ) )
2414, 23eqssd 3451 . . 3  |-  ( ph  ->  ( F `  B
)  =  B )
25 ffn 5733 . . . . 5  |-  ( F : ~P B --> ~P B  ->  F  Fn  ~P B
)
264, 25syl 17 . . . 4  |-  ( ph  ->  F  Fn  ~P B
)
27 fnelfp 6097 . . . 4  |-  ( ( F  Fn  ~P B  /\  B  e.  ~P B )  ->  ( B  e.  dom  ( F  i^i  _I  )  <->  ( F `  B )  =  B ) )
2826, 12, 27syl2anc 667 . . 3  |-  ( ph  ->  ( B  e.  dom  ( F  i^i  _I  )  <->  ( F `  B )  =  B ) )
2924, 28mpbird 236 . 2  |-  ( ph  ->  B  e.  dom  ( F  i^i  _I  ) )
30 simp2 1010 . . . . . . . . . . . . 13  |-  ( (
ph  /\  z  C_  dom  ( F  i^i  _I  )  /\  z  =/=  (/) )  -> 
z  C_  dom  ( F  i^i  _I  ) )
3173ad2ant1 1030 . . . . . . . . . . . . 13  |-  ( (
ph  /\  z  C_  dom  ( F  i^i  _I  )  /\  z  =/=  (/) )  ->  dom  ( F  i^i  _I  )  C_  ~P B )
3230, 31sstrd 3444 . . . . . . . . . . . 12  |-  ( (
ph  /\  z  C_  dom  ( F  i^i  _I  )  /\  z  =/=  (/) )  -> 
z  C_  ~P B
)
33 simp3 1011 . . . . . . . . . . . 12  |-  ( (
ph  /\  z  C_  dom  ( F  i^i  _I  )  /\  z  =/=  (/) )  -> 
z  =/=  (/) )
34 intssuni2 4263 . . . . . . . . . . . 12  |-  ( ( z  C_  ~P B  /\  z  =/=  (/) )  ->  |^| z  C_  U. ~P B )
3532, 33, 34syl2anc 667 . . . . . . . . . . 11  |-  ( (
ph  /\  z  C_  dom  ( F  i^i  _I  )  /\  z  =/=  (/) )  ->  |^| z  C_  U. ~P B )
36 unipw 4653 . . . . . . . . . . 11  |-  U. ~P B  =  B
3735, 36syl6sseq 3480 . . . . . . . . . 10  |-  ( (
ph  /\  z  C_  dom  ( F  i^i  _I  )  /\  z  =/=  (/) )  ->  |^| z  C_  B )
38 intex 4562 . . . . . . . . . . . 12  |-  ( z  =/=  (/)  <->  |^| z  e.  _V )
39 elpwg 3961 . . . . . . . . . . . 12  |-  ( |^| z  e.  _V  ->  (
|^| z  e.  ~P B 
<-> 
|^| z  C_  B
) )
4038, 39sylbi 199 . . . . . . . . . . 11  |-  ( z  =/=  (/)  ->  ( |^| z  e.  ~P B  <->  |^| z  C_  B )
)
41403ad2ant3 1032 . . . . . . . . . 10  |-  ( (
ph  /\  z  C_  dom  ( F  i^i  _I  )  /\  z  =/=  (/) )  -> 
( |^| z  e.  ~P B 
<-> 
|^| z  C_  B
) )
4237, 41mpbird 236 . . . . . . . . 9  |-  ( (
ph  /\  z  C_  dom  ( F  i^i  _I  )  /\  z  =/=  (/) )  ->  |^| z  e.  ~P B )
4342adantr 467 . . . . . . . 8  |-  ( ( ( ph  /\  z  C_ 
dom  ( F  i^i  _I  )  /\  z  =/=  (/) )  /\  x  e.  z )  ->  |^| z  e.  ~P B )
44 ismrcd.m . . . . . . . . . . . 12  |-  ( (
ph  /\  x  C_  B  /\  y  C_  x )  ->  ( F `  y )  C_  ( F `  x )
)
45443expib 1212 . . . . . . . . . . 11  |-  ( ph  ->  ( ( x  C_  B  /\  y  C_  x
)  ->  ( F `  y )  C_  ( F `  x )
) )
4645alrimiv 1775 . . . . . . . . . 10  |-  ( ph  ->  A. y ( ( x  C_  B  /\  y  C_  x )  -> 
( F `  y
)  C_  ( F `  x ) ) )
47463ad2ant1 1030 . . . . . . . . 9  |-  ( (
ph  /\  z  C_  dom  ( F  i^i  _I  )  /\  z  =/=  (/) )  ->  A. y ( ( x 
C_  B  /\  y  C_  x )  ->  ( F `  y )  C_  ( F `  x
) ) )
4847adantr 467 . . . . . . . 8  |-  ( ( ( ph  /\  z  C_ 
dom  ( F  i^i  _I  )  /\  z  =/=  (/) )  /\  x  e.  z )  ->  A. y
( ( x  C_  B  /\  y  C_  x
)  ->  ( F `  y )  C_  ( F `  x )
) )
4932sselda 3434 . . . . . . . . . 10  |-  ( ( ( ph  /\  z  C_ 
dom  ( F  i^i  _I  )  /\  z  =/=  (/) )  /\  x  e.  z )  ->  x  e.  ~P B )
5049elpwid 3963 . . . . . . . . 9  |-  ( ( ( ph  /\  z  C_ 
dom  ( F  i^i  _I  )  /\  z  =/=  (/) )  /\  x  e.  z )  ->  x  C_  B )
51 intss1 4252 . . . . . . . . . 10  |-  ( x  e.  z  ->  |^| z  C_  x )
5251adantl 468 . . . . . . . . 9  |-  ( ( ( ph  /\  z  C_ 
dom  ( F  i^i  _I  )  /\  z  =/=  (/) )  /\  x  e.  z )  ->  |^| z  C_  x )
5350, 52jca 535 . . . . . . . 8  |-  ( ( ( ph  /\  z  C_ 
dom  ( F  i^i  _I  )  /\  z  =/=  (/) )  /\  x  e.  z )  ->  (
x  C_  B  /\  |^| z  C_  x )
)
54 sseq1 3455 . . . . . . . . . . 11  |-  ( y  =  |^| z  -> 
( y  C_  x  <->  |^| z  C_  x )
)
5554anbi2d 711 . . . . . . . . . 10  |-  ( y  =  |^| z  -> 
( ( x  C_  B  /\  y  C_  x
)  <->  ( x  C_  B  /\  |^| z  C_  x
) ) )
56 fveq2 5870 . . . . . . . . . . 11  |-  ( y  =  |^| z  -> 
( F `  y
)  =  ( F `
 |^| z ) )
5756sseq1d 3461 . . . . . . . . . 10  |-  ( y  =  |^| z  -> 
( ( F `  y )  C_  ( F `  x )  <->  ( F `  |^| z
)  C_  ( F `  x ) ) )
5855, 57imbi12d 322 . . . . . . . . 9  |-  ( y  =  |^| z  -> 
( ( ( x 
C_  B  /\  y  C_  x )  ->  ( F `  y )  C_  ( F `  x
) )  <->  ( (
x  C_  B  /\  |^| z  C_  x )  ->  ( F `  |^| z )  C_  ( F `  x )
) ) )
5958spcgv 3136 . . . . . . . 8  |-  ( |^| z  e.  ~P B  ->  ( A. y ( ( x  C_  B  /\  y  C_  x )  ->  ( F `  y )  C_  ( F `  x )
)  ->  ( (
x  C_  B  /\  |^| z  C_  x )  ->  ( F `  |^| z )  C_  ( F `  x )
) ) )
6043, 48, 53, 59syl3c 63 . . . . . . 7  |-  ( ( ( ph  /\  z  C_ 
dom  ( F  i^i  _I  )  /\  z  =/=  (/) )  /\  x  e.  z )  ->  ( F `  |^| z ) 
C_  ( F `  x ) )
6130sselda 3434 . . . . . . . 8  |-  ( ( ( ph  /\  z  C_ 
dom  ( F  i^i  _I  )  /\  z  =/=  (/) )  /\  x  e.  z )  ->  x  e.  dom  ( F  i^i  _I  ) )
62263ad2ant1 1030 . . . . . . . . . 10  |-  ( (
ph  /\  z  C_  dom  ( F  i^i  _I  )  /\  z  =/=  (/) )  ->  F  Fn  ~P B
)
6362adantr 467 . . . . . . . . 9  |-  ( ( ( ph  /\  z  C_ 
dom  ( F  i^i  _I  )  /\  z  =/=  (/) )  /\  x  e.  z )  ->  F  Fn  ~P B )
64 fnelfp 6097 . . . . . . . . 9  |-  ( ( F  Fn  ~P B  /\  x  e.  ~P B )  ->  (
x  e.  dom  ( F  i^i  _I  )  <->  ( F `  x )  =  x ) )
6563, 49, 64syl2anc 667 . . . . . . . 8  |-  ( ( ( ph  /\  z  C_ 
dom  ( F  i^i  _I  )  /\  z  =/=  (/) )  /\  x  e.  z )  ->  (
x  e.  dom  ( F  i^i  _I  )  <->  ( F `  x )  =  x ) )
6661, 65mpbid 214 . . . . . . 7  |-  ( ( ( ph  /\  z  C_ 
dom  ( F  i^i  _I  )  /\  z  =/=  (/) )  /\  x  e.  z )  ->  ( F `  x )  =  x )
6760, 66sseqtrd 3470 . . . . . 6  |-  ( ( ( ph  /\  z  C_ 
dom  ( F  i^i  _I  )  /\  z  =/=  (/) )  /\  x  e.  z )  ->  ( F `  |^| z ) 
C_  x )
6867ralrimiva 2804 . . . . 5  |-  ( (
ph  /\  z  C_  dom  ( F  i^i  _I  )  /\  z  =/=  (/) )  ->  A. x  e.  z 
( F `  |^| z )  C_  x
)
69 ssint 4253 . . . . 5  |-  ( ( F `  |^| z
)  C_  |^| z  <->  A. x  e.  z  ( F `  |^| z )  C_  x )
7068, 69sylibr 216 . . . 4  |-  ( (
ph  /\  z  C_  dom  ( F  i^i  _I  )  /\  z  =/=  (/) )  -> 
( F `  |^| z )  C_  |^| z
)
71183ad2ant1 1030 . . . . 5  |-  ( (
ph  /\  z  C_  dom  ( F  i^i  _I  )  /\  z  =/=  (/) )  ->  A. x  e.  ~P  B x  C_  ( F `
 x ) )
72 id 22 . . . . . . 7  |-  ( x  =  |^| z  ->  x  =  |^| z )
73 fveq2 5870 . . . . . . 7  |-  ( x  =  |^| z  -> 
( F `  x
)  =  ( F `
 |^| z ) )
7472, 73sseq12d 3463 . . . . . 6  |-  ( x  =  |^| z  -> 
( x  C_  ( F `  x )  <->  |^| z  C_  ( F `  |^| z ) ) )
7574rspcva 3150 . . . . 5  |-  ( (
|^| z  e.  ~P B  /\  A. x  e. 
~P  B x  C_  ( F `  x ) )  ->  |^| z  C_  ( F `  |^| z
) )
7642, 71, 75syl2anc 667 . . . 4  |-  ( (
ph  /\  z  C_  dom  ( F  i^i  _I  )  /\  z  =/=  (/) )  ->  |^| z  C_  ( F `
 |^| z ) )
7770, 76eqssd 3451 . . 3  |-  ( (
ph  /\  z  C_  dom  ( F  i^i  _I  )  /\  z  =/=  (/) )  -> 
( F `  |^| z )  =  |^| z )
78 fnelfp 6097 . . . 4  |-  ( ( F  Fn  ~P B  /\  |^| z  e.  ~P B )  ->  ( |^| z  e.  dom  ( F  i^i  _I  )  <->  ( F `  |^| z
)  =  |^| z
) )
7962, 42, 78syl2anc 667 . . 3  |-  ( (
ph  /\  z  C_  dom  ( F  i^i  _I  )  /\  z  =/=  (/) )  -> 
( |^| z  e.  dom  ( F  i^i  _I  )  <->  ( F `  |^| z
)  =  |^| z
) )
8077, 79mpbird 236 . 2  |-  ( (
ph  /\  z  C_  dom  ( F  i^i  _I  )  /\  z  =/=  (/) )  ->  |^| z  e.  dom  ( F  i^i  _I  )
)
817, 29, 80ismred 15520 1  |-  ( ph  ->  dom  ( F  i^i  _I  )  e.  (Moore `  B ) )
Colors of variables: wff setvar class
Syntax hints:    -> wi 4    <-> wb 188    /\ wa 371    /\ w3a 986   A.wal 1444    = wceq 1446    e. wcel 1889    =/= wne 2624   A.wral 2739   _Vcvv 3047    i^i cin 3405    C_ wss 3406   (/)c0 3733   ~Pcpw 3953   U.cuni 4201   |^|cint 4237    _I cid 4747   dom cdm 4837    Fn wfn 5580   -->wf 5581   ` cfv 5585  Moorecmre 15500
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1671  ax-4 1684  ax-5 1760  ax-6 1807  ax-7 1853  ax-8 1891  ax-9 1898  ax-10 1917  ax-11 1922  ax-12 1935  ax-13 2093  ax-ext 2433  ax-sep 4528  ax-nul 4537  ax-pow 4584  ax-pr 4642
This theorem depends on definitions:  df-bi 189  df-or 372  df-an 373  df-3an 988  df-tru 1449  df-ex 1666  df-nf 1670  df-sb 1800  df-eu 2305  df-mo 2306  df-clab 2440  df-cleq 2446  df-clel 2449  df-nfc 2583  df-ne 2626  df-ral 2744  df-rex 2745  df-rab 2748  df-v 3049  df-sbc 3270  df-dif 3409  df-un 3411  df-in 3413  df-ss 3420  df-nul 3734  df-if 3884  df-pw 3955  df-sn 3971  df-pr 3973  df-op 3977  df-uni 4202  df-int 4238  df-br 4406  df-opab 4465  df-mpt 4466  df-id 4752  df-xp 4843  df-rel 4844  df-cnv 4845  df-co 4846  df-dm 4847  df-rn 4848  df-res 4849  df-iota 5549  df-fun 5587  df-fn 5588  df-f 5589  df-fv 5593  df-mre 15504
This theorem is referenced by:  ismrcd2  35553  istopclsd  35554  ismrc  35555
  Copyright terms: Public domain W3C validator