Users' Mathboxes Mathbox for Jeff Madsen < Previous   Next >
Nearby theorems
Mirrors  >  Home  >  MPE Home  >  Th. List  >   Mathboxes  >  sdc Structured version   Unicode version

Theorem sdc 28787
Description: Strong dependent choice. Suppose we may choose an element of 
A such that property  ps holds, and suppose that if we have already chosen the first  k elements (represented here by a function from  1 ... k to  A), we may choose another element so that all  k  +  1 elements taken together have property  ps. Then there exists an infinite sequence of elements of  A such that the first  n terms of this sequence satisfy  ps for all  n. This theorem allows us to construct infinite seqeunces where each term depends on all the previous terms in the sequence. (Contributed by Jeff Madsen, 2-Sep-2009.) (Proof shortened by Mario Carneiro, 3-Jun-2014.)
Hypotheses
Ref Expression
sdc.1  |-  Z  =  ( ZZ>= `  M )
sdc.2  |-  ( g  =  ( f  |`  ( M ... n ) )  ->  ( ps  <->  ch ) )
sdc.3  |-  ( n  =  M  ->  ( ps 
<->  ta ) )
sdc.4  |-  ( n  =  k  ->  ( ps 
<->  th ) )
sdc.5  |-  ( ( g  =  h  /\  n  =  ( k  +  1 ) )  ->  ( ps  <->  si )
)
sdc.6  |-  ( ph  ->  A  e.  V )
sdc.7  |-  ( ph  ->  M  e.  ZZ )
sdc.8  |-  ( ph  ->  E. g ( g : { M } --> A  /\  ta ) )
sdc.9  |-  ( (
ph  /\  k  e.  Z )  ->  (
( g : ( M ... k ) --> A  /\  th )  ->  E. h ( h : ( M ... ( k  +  1 ) ) --> A  /\  g  =  ( h  |`  ( M ... k
) )  /\  si ) ) )
Assertion
Ref Expression
sdc  |-  ( ph  ->  E. f ( f : Z --> A  /\  A. n  e.  Z  ch ) )
Distinct variable groups:    f, g, h, k, n, A    f, M, g, h, k, n    ch, g    ps, f, h, k    si, f, g, n    ph, n    th, n    h, V    ta, h, k, n   
f, Z, g, h, k, n    ph, g, h, k
Allowed substitution hints:    ph( f)    ps( g, n)    ch( f, h, k, n)    th( f,
g, h, k)    ta( f, g)    si( h, k)    V( f, g, k, n)

Proof of Theorem sdc
Dummy variables  j  x  y are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 sdc.1 . 2  |-  Z  =  ( ZZ>= `  M )
2 sdc.2 . 2  |-  ( g  =  ( f  |`  ( M ... n ) )  ->  ( ps  <->  ch ) )
3 sdc.3 . 2  |-  ( n  =  M  ->  ( ps 
<->  ta ) )
4 sdc.4 . 2  |-  ( n  =  k  ->  ( ps 
<->  th ) )
5 sdc.5 . 2  |-  ( ( g  =  h  /\  n  =  ( k  +  1 ) )  ->  ( ps  <->  si )
)
6 sdc.6 . 2  |-  ( ph  ->  A  e.  V )
7 sdc.7 . 2  |-  ( ph  ->  M  e.  ZZ )
8 sdc.8 . 2  |-  ( ph  ->  E. g ( g : { M } --> A  /\  ta ) )
9 sdc.9 . 2  |-  ( (
ph  /\  k  e.  Z )  ->  (
( g : ( M ... k ) --> A  /\  th )  ->  E. h ( h : ( M ... ( k  +  1 ) ) --> A  /\  g  =  ( h  |`  ( M ... k
) )  /\  si ) ) )
10 eqid 2454 . 2  |-  { g  |  E. n  e.  Z  ( g : ( M ... n
) --> A  /\  ps ) }  =  {
g  |  E. n  e.  Z  ( g : ( M ... n ) --> A  /\  ps ) }
11 eqid 2454 . . . 4  |-  Z  =  Z
12 oveq2 6207 . . . . . . . 8  |-  ( n  =  k  ->  ( M ... n )  =  ( M ... k
) )
1312feq2d 5654 . . . . . . 7  |-  ( n  =  k  ->  (
g : ( M ... n ) --> A  <-> 
g : ( M ... k ) --> A ) )
1413, 4anbi12d 710 . . . . . 6  |-  ( n  =  k  ->  (
( g : ( M ... n ) --> A  /\  ps )  <->  ( g : ( M ... k ) --> A  /\  th ) ) )
1514cbvrexv 3052 . . . . 5  |-  ( E. n  e.  Z  ( g : ( M ... n ) --> A  /\  ps )  <->  E. k  e.  Z  ( g : ( M ... k ) --> A  /\  th ) )
1615abbii 2588 . . . 4  |-  { g  |  E. n  e.  Z  ( g : ( M ... n
) --> A  /\  ps ) }  =  {
g  |  E. k  e.  Z  ( g : ( M ... k ) --> A  /\  th ) }
17 eqid 2454 . . . 4  |-  { h  |  E. k  e.  Z  ( h : ( M ... ( k  +  1 ) ) --> A  /\  f  =  ( h  |`  ( M ... k ) )  /\  si ) }  =  { h  |  E. k  e.  Z  ( h : ( M ... ( k  +  1 ) ) --> A  /\  f  =  ( h  |`  ( M ... k ) )  /\  si ) }
1811, 16, 17mpt2eq123i 6257 . . 3  |-  ( j  e.  Z ,  f  e.  { g  |  E. n  e.  Z  ( g : ( M ... n ) --> A  /\  ps ) }  |->  { h  |  E. k  e.  Z  ( h : ( M ... ( k  +  1 ) ) --> A  /\  f  =  ( h  |`  ( M ... k ) )  /\  si ) } )  =  ( j  e.  Z ,  f  e.  { g  |  E. k  e.  Z  ( g : ( M ... k ) --> A  /\  th ) }  |->  { h  |  E. k  e.  Z  ( h : ( M ... ( k  +  1 ) ) --> A  /\  f  =  ( h  |`  ( M ... k ) )  /\  si ) } )
19 eqidd 2455 . . . 4  |-  ( j  =  y  ->  { h  |  E. k  e.  Z  ( h : ( M ... ( k  +  1 ) ) --> A  /\  f  =  ( h  |`  ( M ... k ) )  /\  si ) }  =  { h  |  E. k  e.  Z  ( h : ( M ... ( k  +  1 ) ) --> A  /\  f  =  ( h  |`  ( M ... k ) )  /\  si ) } )
20 eqeq1 2458 . . . . . . 7  |-  ( f  =  x  ->  (
f  =  ( h  |`  ( M ... k
) )  <->  x  =  ( h  |`  ( M ... k ) ) ) )
21203anbi2d 1295 . . . . . 6  |-  ( f  =  x  ->  (
( h : ( M ... ( k  +  1 ) ) --> A  /\  f  =  ( h  |`  ( M ... k ) )  /\  si )  <->  ( h : ( M ... ( k  +  1 ) ) --> A  /\  x  =  ( h  |`  ( M ... k
) )  /\  si ) ) )
2221rexbidv 2864 . . . . 5  |-  ( f  =  x  ->  ( E. k  e.  Z  ( h : ( M ... ( k  +  1 ) ) --> A  /\  f  =  ( h  |`  ( M ... k ) )  /\  si )  <->  E. k  e.  Z  ( h : ( M ... ( k  +  1 ) ) --> A  /\  x  =  ( h  |`  ( M ... k
) )  /\  si ) ) )
2322abbidv 2590 . . . 4  |-  ( f  =  x  ->  { h  |  E. k  e.  Z  ( h : ( M ... ( k  +  1 ) ) --> A  /\  f  =  ( h  |`  ( M ... k ) )  /\  si ) }  =  { h  |  E. k  e.  Z  ( h : ( M ... ( k  +  1 ) ) --> A  /\  x  =  ( h  |`  ( M ... k ) )  /\  si ) } )
2419, 23cbvmpt2v 6274 . . 3  |-  ( j  e.  Z ,  f  e.  { g  |  E. n  e.  Z  ( g : ( M ... n ) --> A  /\  ps ) }  |->  { h  |  E. k  e.  Z  ( h : ( M ... ( k  +  1 ) ) --> A  /\  f  =  ( h  |`  ( M ... k ) )  /\  si ) } )  =  ( y  e.  Z ,  x  e.  { g  |  E. n  e.  Z  (
g : ( M ... n ) --> A  /\  ps ) } 
|->  { h  |  E. k  e.  Z  (
h : ( M ... ( k  +  1 ) ) --> A  /\  x  =  ( h  |`  ( M ... k ) )  /\  si ) } )
2518, 24eqtr3i 2485 . 2  |-  ( j  e.  Z ,  f  e.  { g  |  E. k  e.  Z  ( g : ( M ... k ) --> A  /\  th ) }  |->  { h  |  E. k  e.  Z  ( h : ( M ... ( k  +  1 ) ) --> A  /\  f  =  ( h  |`  ( M ... k ) )  /\  si ) } )  =  ( y  e.  Z ,  x  e.  { g  |  E. n  e.  Z  (
g : ( M ... n ) --> A  /\  ps ) } 
|->  { h  |  E. k  e.  Z  (
h : ( M ... ( k  +  1 ) ) --> A  /\  x  =  ( h  |`  ( M ... k ) )  /\  si ) } )
261, 2, 3, 4, 5, 6, 7, 8, 9, 10, 25sdclem1 28786 1  |-  ( ph  ->  E. f ( f : Z --> A  /\  A. n  e.  Z  ch ) )
Colors of variables: wff setvar class
Syntax hints:    -> wi 4    <-> wb 184    /\ wa 369    /\ w3a 965    = wceq 1370   E.wex 1587    e. wcel 1758   {cab 2439   A.wral 2798   E.wrex 2799   {csn 3984    |` cres 4949   -->wf 5521   ` cfv 5525  (class class class)co 6199    |-> cmpt2 6201   1c1 9393    + caddc 9395   ZZcz 10756   ZZ>=cuz 10971   ...cfz 11553
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1592  ax-4 1603  ax-5 1671  ax-6 1710  ax-7 1730  ax-8 1760  ax-9 1762  ax-10 1777  ax-11 1782  ax-12 1794  ax-13 1955  ax-ext 2432  ax-rep 4510  ax-sep 4520  ax-nul 4528  ax-pow 4577  ax-pr 4638  ax-un 6481  ax-inf2 7957  ax-dc 8725  ax-cnex 9448  ax-resscn 9449  ax-1cn 9450  ax-icn 9451  ax-addcl 9452  ax-addrcl 9453  ax-mulcl 9454  ax-mulrcl 9455  ax-mulcom 9456  ax-addass 9457  ax-mulass 9458  ax-distr 9459  ax-i2m1 9460  ax-1ne0 9461  ax-1rid 9462  ax-rnegex 9463  ax-rrecex 9464  ax-cnre 9465  ax-pre-lttri 9466  ax-pre-lttrn 9467  ax-pre-ltadd 9468  ax-pre-mulgt0 9469
This theorem depends on definitions:  df-bi 185  df-or 370  df-an 371  df-3or 966  df-3an 967  df-tru 1373  df-ex 1588  df-nf 1591  df-sb 1703  df-eu 2266  df-mo 2267  df-clab 2440  df-cleq 2446  df-clel 2449  df-nfc 2604  df-ne 2649  df-nel 2650  df-ral 2803  df-rex 2804  df-reu 2805  df-rab 2807  df-v 3078  df-sbc 3293  df-csb 3395  df-dif 3438  df-un 3440  df-in 3442  df-ss 3449  df-pss 3451  df-nul 3745  df-if 3899  df-pw 3969  df-sn 3985  df-pr 3987  df-tp 3989  df-op 3991  df-uni 4199  df-iun 4280  df-br 4400  df-opab 4458  df-mpt 4459  df-tr 4493  df-eprel 4739  df-id 4743  df-po 4748  df-so 4749  df-fr 4786  df-we 4788  df-ord 4829  df-on 4830  df-lim 4831  df-suc 4832  df-xp 4953  df-rel 4954  df-cnv 4955  df-co 4956  df-dm 4957  df-rn 4958  df-res 4959  df-ima 4960  df-iota 5488  df-fun 5527  df-fn 5528  df-f 5529  df-f1 5530  df-fo 5531  df-f1o 5532  df-fv 5533  df-riota 6160  df-ov 6202  df-oprab 6203  df-mpt2 6204  df-om 6586  df-1st 6686  df-2nd 6687  df-recs 6941  df-rdg 6975  df-1o 7029  df-er 7210  df-map 7325  df-en 7420  df-dom 7421  df-sdom 7422  df-pnf 9530  df-mnf 9531  df-xr 9532  df-ltxr 9533  df-le 9534  df-sub 9707  df-neg 9708  df-nn 10433  df-n0 10690  df-z 10757  df-uz 10972  df-fz 11554
This theorem is referenced by: (None)
  Copyright terms: Public domain W3C validator