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

Theorem rpnnen 13501
Description: The cardinality of the continuum is the same as the powerset of  om. This is a stronger statement than ruc 13517, which only asserts that  RR is uncountable, i.e. has a cardinality larger than  om. The main proof is in two parts, rpnnen1 10976 and rpnnen2 13500, each showing an injection in one direction, and this last part uses sbth 7423 to prove that the sets are equinumerous. By constructing explicit injections, we avoid the use of AC. (Contributed by Mario Carneiro, 13-May-2013.) (Revised by Mario Carneiro, 23-Aug-2014.)
Assertion
Ref Expression
rpnnen  |-  RR  ~~  ~P NN

Proof of Theorem rpnnen
Dummy variables  j 
k  m  n  x  y are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 oveq1 6093 . . . . . 6  |-  ( m  =  n  ->  (
m  /  k )  =  ( n  / 
k ) )
21breq1d 4295 . . . . 5  |-  ( m  =  n  ->  (
( m  /  k
)  <  x  <->  ( n  /  k )  < 
x ) )
32cbvrabv 2965 . . . 4  |-  { m  e.  ZZ  |  ( m  /  k )  < 
x }  =  {
n  e.  ZZ  | 
( n  /  k
)  <  x }
4 oveq2 6094 . . . . . . . . . . 11  |-  ( j  =  k  ->  (
m  /  j )  =  ( m  / 
k ) )
54breq1d 4295 . . . . . . . . . 10  |-  ( j  =  k  ->  (
( m  /  j
)  <  y  <->  ( m  /  k )  < 
y ) )
65rabbidv 2958 . . . . . . . . 9  |-  ( j  =  k  ->  { m  e.  ZZ  |  ( m  /  j )  < 
y }  =  {
m  e.  ZZ  | 
( m  /  k
)  <  y }
)
76supeq1d 7688 . . . . . . . 8  |-  ( j  =  k  ->  sup ( { m  e.  ZZ  |  ( m  / 
j )  <  y } ,  RR ,  <  )  =  sup ( { m  e.  ZZ  |  ( m  / 
k )  <  y } ,  RR ,  <  ) )
8 id 22 . . . . . . . 8  |-  ( j  =  k  ->  j  =  k )
97, 8oveq12d 6104 . . . . . . 7  |-  ( j  =  k  ->  ( sup ( { m  e.  ZZ  |  ( m  /  j )  < 
y } ,  RR ,  <  )  /  j
)  =  ( sup ( { m  e.  ZZ  |  ( m  /  k )  < 
y } ,  RR ,  <  )  /  k
) )
109cbvmptv 4376 . . . . . 6  |-  ( j  e.  NN  |->  ( sup ( { m  e.  ZZ  |  ( m  /  j )  < 
y } ,  RR ,  <  )  /  j
) )  =  ( k  e.  NN  |->  ( sup ( { m  e.  ZZ  |  ( m  /  k )  < 
y } ,  RR ,  <  )  /  k
) )
11 breq2 4289 . . . . . . . . . 10  |-  ( y  =  x  ->  (
( m  /  k
)  <  y  <->  ( m  /  k )  < 
x ) )
1211rabbidv 2958 . . . . . . . . 9  |-  ( y  =  x  ->  { m  e.  ZZ  |  ( m  /  k )  < 
y }  =  {
m  e.  ZZ  | 
( m  /  k
)  <  x }
)
1312supeq1d 7688 . . . . . . . 8  |-  ( y  =  x  ->  sup ( { m  e.  ZZ  |  ( m  / 
k )  <  y } ,  RR ,  <  )  =  sup ( { m  e.  ZZ  |  ( m  / 
k )  <  x } ,  RR ,  <  ) )
1413oveq1d 6101 . . . . . . 7  |-  ( y  =  x  ->  ( sup ( { m  e.  ZZ  |  ( m  /  k )  < 
y } ,  RR ,  <  )  /  k
)  =  ( sup ( { m  e.  ZZ  |  ( m  /  k )  < 
x } ,  RR ,  <  )  /  k
) )
1514mpteq2dv 4372 . . . . . 6  |-  ( y  =  x  ->  (
k  e.  NN  |->  ( sup ( { m  e.  ZZ  |  ( m  /  k )  < 
y } ,  RR ,  <  )  /  k
) )  =  ( k  e.  NN  |->  ( sup ( { m  e.  ZZ  |  ( m  /  k )  < 
x } ,  RR ,  <  )  /  k
) ) )
1610, 15syl5eq 2481 . . . . 5  |-  ( y  =  x  ->  (
j  e.  NN  |->  ( sup ( { m  e.  ZZ  |  ( m  /  j )  < 
y } ,  RR ,  <  )  /  j
) )  =  ( k  e.  NN  |->  ( sup ( { m  e.  ZZ  |  ( m  /  k )  < 
x } ,  RR ,  <  )  /  k
) ) )
1716cbvmptv 4376 . . . 4  |-  ( y  e.  RR  |->  ( j  e.  NN  |->  ( sup ( { m  e.  ZZ  |  ( m  /  j )  < 
y } ,  RR ,  <  )  /  j
) ) )  =  ( x  e.  RR  |->  ( k  e.  NN  |->  ( sup ( { m  e.  ZZ  |  ( m  /  k )  < 
x } ,  RR ,  <  )  /  k
) ) )
183, 17rpnnen1 10976 . . 3  |-  RR  ~<_  ( QQ 
^m  NN )
19 qnnen 13488 . . . . . . 7  |-  QQ  ~~  NN
20 nnex 10320 . . . . . . . 8  |-  NN  e.  _V
2120canth2 7456 . . . . . . 7  |-  NN  ~<  ~P NN
22 ensdomtr 7439 . . . . . . 7  |-  ( ( QQ  ~~  NN  /\  NN  ~<  ~P NN )  ->  QQ  ~<  ~P NN )
2319, 21, 22mp2an 672 . . . . . 6  |-  QQ  ~<  ~P NN
24 sdomdom 7329 . . . . . 6  |-  ( QQ 
~<  ~P NN  ->  QQ  ~<_  ~P NN )
25 mapdom1 7468 . . . . . 6  |-  ( QQ  ~<_  ~P NN  ->  ( QQ  ^m  NN )  ~<_  ( ~P NN  ^m  NN ) )
2623, 24, 25mp2b 10 . . . . 5  |-  ( QQ 
^m  NN )  ~<_  ( ~P NN  ^m  NN )
2720pw2en 7410 . . . . . 6  |-  ~P NN  ~~  ( 2o  ^m  NN )
2820enref 7334 . . . . . 6  |-  NN  ~~  NN
29 mapen 7467 . . . . . 6  |-  ( ( ~P NN  ~~  ( 2o  ^m  NN )  /\  NN  ~~  NN )  -> 
( ~P NN  ^m  NN )  ~~  ( ( 2o  ^m  NN )  ^m  NN ) )
3027, 28, 29mp2an 672 . . . . 5  |-  ( ~P NN  ^m  NN ) 
~~  ( ( 2o 
^m  NN )  ^m  NN )
31 domentr 7360 . . . . 5  |-  ( ( ( QQ  ^m  NN )  ~<_  ( ~P NN  ^m  NN )  /\  ( ~P NN  ^m  NN ) 
~~  ( ( 2o 
^m  NN )  ^m  NN ) )  ->  ( QQ  ^m  NN )  ~<_  ( ( 2o  ^m  NN )  ^m  NN ) )
3226, 30, 31mp2an 672 . . . 4  |-  ( QQ 
^m  NN )  ~<_  ( ( 2o  ^m  NN )  ^m  NN )
33 2onn 7071 . . . . . . 7  |-  2o  e.  om
34 mapxpen 7469 . . . . . . 7  |-  ( ( 2o  e.  om  /\  NN  e.  _V  /\  NN  e.  _V )  ->  (
( 2o  ^m  NN )  ^m  NN )  ~~  ( 2o  ^m  ( NN  X.  NN ) ) )
3533, 20, 20, 34mp3an 1314 . . . . . 6  |-  ( ( 2o  ^m  NN )  ^m  NN )  ~~  ( 2o  ^m  ( NN  X.  NN ) )
3633elexi 2976 . . . . . . . 8  |-  2o  e.  _V
3736enref 7334 . . . . . . 7  |-  2o  ~~  2o
38 xpnnen 13483 . . . . . . 7  |-  ( NN 
X.  NN )  ~~  NN
39 mapen 7467 . . . . . . 7  |-  ( ( 2o  ~~  2o  /\  ( NN  X.  NN )  ~~  NN )  -> 
( 2o  ^m  ( NN  X.  NN ) ) 
~~  ( 2o  ^m  NN ) )
4037, 38, 39mp2an 672 . . . . . 6  |-  ( 2o 
^m  ( NN  X.  NN ) )  ~~  ( 2o  ^m  NN )
4135, 40entri 7355 . . . . 5  |-  ( ( 2o  ^m  NN )  ^m  NN )  ~~  ( 2o  ^m  NN )
4241, 27entr4i 7358 . . . 4  |-  ( ( 2o  ^m  NN )  ^m  NN )  ~~  ~P NN
43 domentr 7360 . . . 4  |-  ( ( ( QQ  ^m  NN )  ~<_  ( ( 2o 
^m  NN )  ^m  NN )  /\  (
( 2o  ^m  NN )  ^m  NN )  ~~  ~P NN )  ->  ( QQ  ^m  NN )  ~<_  ~P NN )
4432, 42, 43mp2an 672 . . 3  |-  ( QQ 
^m  NN )  ~<_  ~P NN
45 domtr 7354 . . 3  |-  ( ( RR  ~<_  ( QQ  ^m  NN )  /\  ( QQ  ^m  NN )  ~<_  ~P NN )  ->  RR  ~<_  ~P NN )
4618, 44, 45mp2an 672 . 2  |-  RR  ~<_  ~P NN
47 elequ2 1761 . . . . . . . 8  |-  ( y  =  x  ->  (
n  e.  y  <->  n  e.  x ) )
4847ifbid 3804 . . . . . . 7  |-  ( y  =  x  ->  if ( n  e.  y ,  ( ( 1  /  3 ) ^
n ) ,  0 )  =  if ( n  e.  x ,  ( ( 1  / 
3 ) ^ n
) ,  0 ) )
4948mpteq2dv 4372 . . . . . 6  |-  ( y  =  x  ->  (
n  e.  NN  |->  if ( n  e.  y ,  ( ( 1  /  3 ) ^
n ) ,  0 ) )  =  ( n  e.  NN  |->  if ( n  e.  x ,  ( ( 1  /  3 ) ^
n ) ,  0 ) ) )
50 elequ1 1759 . . . . . . . 8  |-  ( n  =  k  ->  (
n  e.  x  <->  k  e.  x ) )
51 oveq2 6094 . . . . . . . 8  |-  ( n  =  k  ->  (
( 1  /  3
) ^ n )  =  ( ( 1  /  3 ) ^
k ) )
5250, 51ifbieq1d 3805 . . . . . . 7  |-  ( n  =  k  ->  if ( n  e.  x ,  ( ( 1  /  3 ) ^
n ) ,  0 )  =  if ( k  e.  x ,  ( ( 1  / 
3 ) ^ k
) ,  0 ) )
5352cbvmptv 4376 . . . . . 6  |-  ( n  e.  NN  |->  if ( n  e.  x ,  ( ( 1  / 
3 ) ^ n
) ,  0 ) )  =  ( k  e.  NN  |->  if ( k  e.  x ,  ( ( 1  / 
3 ) ^ k
) ,  0 ) )
5449, 53syl6eq 2485 . . . . 5  |-  ( y  =  x  ->  (
n  e.  NN  |->  if ( n  e.  y ,  ( ( 1  /  3 ) ^
n ) ,  0 ) )  =  ( k  e.  NN  |->  if ( k  e.  x ,  ( ( 1  /  3 ) ^
k ) ,  0 ) ) )
5554cbvmptv 4376 . . . 4  |-  ( y  e.  ~P NN  |->  ( n  e.  NN  |->  if ( n  e.  y ,  ( ( 1  /  3 ) ^
n ) ,  0 ) ) )  =  ( x  e.  ~P NN  |->  ( k  e.  NN  |->  if ( k  e.  x ,  ( ( 1  /  3
) ^ k ) ,  0 ) ) )
5655rpnnen2 13500 . . 3  |-  ~P NN  ~<_  ( 0 [,] 1
)
57 reex 9365 . . . 4  |-  RR  e.  _V
58 unitssre 11424 . . . 4  |-  ( 0 [,] 1 )  C_  RR
59 ssdomg 7347 . . . 4  |-  ( RR  e.  _V  ->  (
( 0 [,] 1
)  C_  RR  ->  ( 0 [,] 1 )  ~<_  RR ) )
6057, 58, 59mp2 9 . . 3  |-  ( 0 [,] 1 )  ~<_  RR
61 domtr 7354 . . 3  |-  ( ( ~P NN  ~<_  ( 0 [,] 1 )  /\  ( 0 [,] 1
)  ~<_  RR )  ->  ~P NN  ~<_  RR )
6256, 60, 61mp2an 672 . 2  |-  ~P NN  ~<_  RR
63 sbth 7423 . 2  |-  ( ( RR  ~<_  ~P NN  /\  ~P NN 
~<_  RR )  ->  RR  ~~ 
~P NN )
6446, 62, 63mp2an 672 1  |-  RR  ~~  ~P NN
Colors of variables: wff setvar class
Syntax hints:    e. wcel 1756   {crab 2713   _Vcvv 2966    C_ wss 3321   ifcif 3784   ~Pcpw 3853   class class class wbr 4285    e. cmpt 4343    X. cxp 4830  (class class class)co 6086   omcom 6471   2oc2o 6906    ^m cmap 7206    ~~ cen 7299    ~<_ cdom 7300    ~< csdm 7301   supcsup 7682   RRcr 9273   0cc0 9274   1c1 9275    < clt 9410    / cdiv 9985   NNcn 10314   3c3 10364   ZZcz 10638   QQcq 10945   [,]cicc 11295   ^cexp 11857
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1591  ax-4 1602  ax-5 1670  ax-6 1708  ax-7 1728  ax-8 1758  ax-9 1760  ax-10 1775  ax-11 1780  ax-12 1792  ax-13 1943  ax-ext 2418  ax-rep 4396  ax-sep 4406  ax-nul 4414  ax-pow 4463  ax-pr 4524  ax-un 6367  ax-inf2 7839  ax-cnex 9330  ax-resscn 9331  ax-1cn 9332  ax-icn 9333  ax-addcl 9334  ax-addrcl 9335  ax-mulcl 9336  ax-mulrcl 9337  ax-mulcom 9338  ax-addass 9339  ax-mulass 9340  ax-distr 9341  ax-i2m1 9342  ax-1ne0 9343  ax-1rid 9344  ax-rnegex 9345  ax-rrecex 9346  ax-cnre 9347  ax-pre-lttri 9348  ax-pre-lttrn 9349  ax-pre-ltadd 9350  ax-pre-mulgt0 9351  ax-pre-sup 9352
This theorem depends on definitions:  df-bi 185  df-or 370  df-an 371  df-3or 966  df-3an 967  df-tru 1372  df-fal 1375  df-ex 1587  df-nf 1590  df-sb 1701  df-eu 2256  df-mo 2257  df-clab 2424  df-cleq 2430  df-clel 2433  df-nfc 2562  df-ne 2602  df-nel 2603  df-ral 2714  df-rex 2715  df-reu 2716  df-rmo 2717  df-rab 2718  df-v 2968  df-sbc 3180  df-csb 3282  df-dif 3324  df-un 3326  df-in 3328  df-ss 3335  df-pss 3337  df-nul 3631  df-if 3785  df-pw 3855  df-sn 3871  df-pr 3873  df-tp 3875  df-op 3877  df-uni 4085  df-int 4122  df-iun 4166  df-br 4286  df-opab 4344  df-mpt 4345  df-tr 4379  df-eprel 4624  df-id 4628  df-po 4633  df-so 4634  df-fr 4671  df-se 4672  df-we 4673  df-ord 4714  df-on 4715  df-lim 4716  df-suc 4717  df-xp 4838  df-rel 4839  df-cnv 4840  df-co 4841  df-dm 4842  df-rn 4843  df-res 4844  df-ima 4845  df-iota 5374  df-fun 5413  df-fn 5414  df-f 5415  df-f1 5416  df-fo 5417  df-f1o 5418  df-fv 5419  df-isom 5420  df-riota 6045  df-ov 6089  df-oprab 6090  df-mpt2 6091  df-om 6472  df-1st 6572  df-2nd 6573  df-recs 6824  df-rdg 6858  df-1o 6912  df-2o 6913  df-oadd 6916  df-omul 6917  df-er 7093  df-map 7208  df-pm 7209  df-en 7303  df-dom 7304  df-sdom 7305  df-fin 7306  df-sup 7683  df-oi 7716  df-card 8101  df-acn 8104  df-pnf 9412  df-mnf 9413  df-xr 9414  df-ltxr 9415  df-le 9416  df-sub 9589  df-neg 9590  df-div 9986  df-nn 10315  df-2 10372  df-3 10373  df-n0 10572  df-z 10639  df-uz 10854  df-q 10946  df-rp 10984  df-ico 11298  df-icc 11299  df-fz 11430  df-fzo 11541  df-fl 11634  df-seq 11799  df-exp 11858  df-hash 12096  df-cj 12580  df-re 12581  df-im 12582  df-sqr 12716  df-abs 12717  df-limsup 12941  df-clim 12958  df-rlim 12959  df-sum 13156
This theorem is referenced by:  rexpen  13502  cpnnen  13503  rucALT  13504  cnso  13521  2ndcredom  19023  opnreen  20377
  Copyright terms: Public domain W3C validator