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

Theorem nninfisol 7077
Description: Finite elements of ℕ are isolated. That is, given a natural number and any element of ℕ, it is decidable whether the natural number (when converted to an element of ℕ) is equal to the given element of ℕ. Stated in an online post by Martin Escardo. One way to understand this theorem is that you do not need to look at an unbounded number of elements of the sequence  X to decide whether it is equal to  N (in fact, you only need to look at two elements and  N tells you where to look). (Contributed by BJ and Jim Kingdon, 12-Sep-2024.)
Assertion
Ref Expression
nninfisol  |-  ( ( N  e.  om  /\  X  e. )  -> DECID  ( i  e.  om  |->  if ( i  e.  N ,  1o ,  (/) ) )  =  X )
Distinct variable groups:    i, N    i, X

Proof of Theorem nninfisol
StepHypRef Expression
1 simpllr 524 . . . 4  |-  ( ( ( ( N  e. 
om  /\  X  e. )  /\  ( X `  N )  =  (/) )  /\  N  =  (/) )  ->  X  e. )
2 simplr 520 . . . 4  |-  ( ( ( ( N  e. 
om  /\  X  e. )  /\  ( X `  N )  =  (/) )  /\  N  =  (/) )  ->  ( X `  N )  =  (/) )
3 simplll 523 . . . 4  |-  ( ( ( ( N  e. 
om  /\  X  e. )  /\  ( X `  N )  =  (/) )  /\  N  =  (/) )  ->  N  e.  om )
4 simpr 109 . . . 4  |-  ( ( ( ( N  e. 
om  /\  X  e. )  /\  ( X `  N )  =  (/) )  /\  N  =  (/) )  ->  N  =  (/) )
51, 2, 3, 4nninfisollem0 7074 . . 3  |-  ( ( ( ( N  e. 
om  /\  X  e. )  /\  ( X `  N )  =  (/) )  /\  N  =  (/) )  -> DECID  ( i  e.  om  |->  if ( i  e.  N ,  1o ,  (/) ) )  =  X )
6 simp-4r 532 . . . . 5  |-  ( ( ( ( ( N  e.  om  /\  X  e. )  /\  ( X `  N )  =  (/) )  /\  -.  N  =  (/) )  /\  ( X `  U. N )  =  (/) )  ->  X  e. )
7 simpllr 524 . . . . 5  |-  ( ( ( ( ( N  e.  om  /\  X  e. )  /\  ( X `  N )  =  (/) )  /\  -.  N  =  (/) )  /\  ( X `  U. N )  =  (/) )  ->  ( X `  N )  =  (/) )
8 simp-4l 531 . . . . 5  |-  ( ( ( ( ( N  e.  om  /\  X  e. )  /\  ( X `  N )  =  (/) )  /\  -.  N  =  (/) )  /\  ( X `  U. N )  =  (/) )  ->  N  e.  om )
9 simpr 109 . . . . . . 7  |-  ( ( ( ( N  e. 
om  /\  X  e. )  /\  ( X `  N )  =  (/) )  /\  -.  N  =  (/) )  ->  -.  N  =  (/) )
109neqned 2334 . . . . . 6  |-  ( ( ( ( N  e. 
om  /\  X  e. )  /\  ( X `  N )  =  (/) )  /\  -.  N  =  (/) )  ->  N  =/=  (/) )
1110adantr 274 . . . . 5  |-  ( ( ( ( ( N  e.  om  /\  X  e. )  /\  ( X `  N )  =  (/) )  /\  -.  N  =  (/) )  /\  ( X `  U. N )  =  (/) )  ->  N  =/=  (/) )
12 simpr 109 . . . . 5  |-  ( ( ( ( ( N  e.  om  /\  X  e. )  /\  ( X `  N )  =  (/) )  /\  -.  N  =  (/) )  /\  ( X `  U. N )  =  (/) )  ->  ( X `  U. N )  =  (/) )
136, 7, 8, 11, 12nninfisollemne 7075 . . . 4  |-  ( ( ( ( ( N  e.  om  /\  X  e. )  /\  ( X `  N )  =  (/) )  /\  -.  N  =  (/) )  /\  ( X `  U. N )  =  (/) )  -> DECID  ( i  e.  om  |->  if ( i  e.  N ,  1o ,  (/) ) )  =  X )
14 simp-4r 532 . . . . 5  |-  ( ( ( ( ( N  e.  om  /\  X  e. )  /\  ( X `  N )  =  (/) )  /\  -.  N  =  (/) )  /\  ( X `  U. N )  =  1o )  ->  X  e. )
15 simpllr 524 . . . . 5  |-  ( ( ( ( ( N  e.  om  /\  X  e. )  /\  ( X `  N )  =  (/) )  /\  -.  N  =  (/) )  /\  ( X `  U. N )  =  1o )  -> 
( X `  N
)  =  (/) )
16 simp-4l 531 . . . . 5  |-  ( ( ( ( ( N  e.  om  /\  X  e. )  /\  ( X `  N )  =  (/) )  /\  -.  N  =  (/) )  /\  ( X `  U. N )  =  1o )  ->  N  e.  om )
1710adantr 274 . . . . 5  |-  ( ( ( ( ( N  e.  om  /\  X  e. )  /\  ( X `  N )  =  (/) )  /\  -.  N  =  (/) )  /\  ( X `  U. N )  =  1o )  ->  N  =/=  (/) )
18 simpr 109 . . . . 5  |-  ( ( ( ( ( N  e.  om  /\  X  e. )  /\  ( X `  N )  =  (/) )  /\  -.  N  =  (/) )  /\  ( X `  U. N )  =  1o )  -> 
( X `  U. N )  =  1o )
1914, 15, 16, 17, 18nninfisollemeq 7076 . . . 4  |-  ( ( ( ( ( N  e.  om  /\  X  e. )  /\  ( X `  N )  =  (/) )  /\  -.  N  =  (/) )  /\  ( X `  U. N )  =  1o )  -> DECID  (
i  e.  om  |->  if ( i  e.  N ,  1o ,  (/) ) )  =  X )
20 nninff 7067 . . . . . . . . 9  |-  ( X  e.  ->  X : om --> 2o )
2120adantl 275 . . . . . . . 8  |-  ( ( N  e.  om  /\  X  e. )  ->  X : om
--> 2o )
22 nnpredcl 4583 . . . . . . . . 9  |-  ( N  e.  om  ->  U. N  e.  om )
2322adantr 274 . . . . . . . 8  |-  ( ( N  e.  om  /\  X  e. )  ->  U. N  e. 
om )
2421, 23ffvelrnd 5604 . . . . . . 7  |-  ( ( N  e.  om  /\  X  e. )  ->  ( X `  U. N )  e.  2o )
25 df2o3 6378 . . . . . . 7  |-  2o  =  { (/) ,  1o }
2624, 25eleqtrdi 2250 . . . . . 6  |-  ( ( N  e.  om  /\  X  e. )  ->  ( X `  U. N )  e. 
{ (/) ,  1o }
)
27 elpri 3583 . . . . . 6  |-  ( ( X `  U. N
)  e.  { (/) ,  1o }  ->  (
( X `  U. N )  =  (/)  \/  ( X `  U. N )  =  1o ) )
2826, 27syl 14 . . . . 5  |-  ( ( N  e.  om  /\  X  e. )  ->  ( ( X `  U. N )  =  (/)  \/  ( X `  U. N )  =  1o ) )
2928ad2antrr 480 . . . 4  |-  ( ( ( ( N  e. 
om  /\  X  e. )  /\  ( X `  N )  =  (/) )  /\  -.  N  =  (/) )  -> 
( ( X `  U. N )  =  (/)  \/  ( X `  U. N )  =  1o ) )
3013, 19, 29mpjaodan 788 . . 3  |-  ( ( ( ( N  e. 
om  /\  X  e. )  /\  ( X `  N )  =  (/) )  /\  -.  N  =  (/) )  -> DECID  (
i  e.  om  |->  if ( i  e.  N ,  1o ,  (/) ) )  =  X )
31 nndceq0 4578 . . . . 5  |-  ( N  e.  om  -> DECID  N  =  (/) )
32 exmiddc 822 . . . . 5  |-  (DECID  N  =  (/)  ->  ( N  =  (/)  \/  -.  N  =  (/) ) )
3331, 32syl 14 . . . 4  |-  ( N  e.  om  ->  ( N  =  (/)  \/  -.  N  =  (/) ) )
3433ad2antrr 480 . . 3  |-  ( ( ( N  e.  om  /\  X  e. )  /\  ( X `
 N )  =  (/) )  ->  ( N  =  (/)  \/  -.  N  =  (/) ) )
355, 30, 34mpjaodan 788 . 2  |-  ( ( ( N  e.  om  /\  X  e. )  /\  ( X `
 N )  =  (/) )  -> DECID  ( i  e.  om  |->  if ( i  e.  N ,  1o ,  (/) ) )  =  X )
36 1n0 6380 . . . . . 6  |-  1o  =/=  (/)
3736neii 2329 . . . . 5  |-  -.  1o  =  (/)
38 simpr 109 . . . . . . . 8  |-  ( ( ( ( N  e. 
om  /\  X  e. )  /\  ( X `  N )  =  1o )  /\  ( i  e.  om  |->  if ( i  e.  N ,  1o ,  (/) ) )  =  X )  -> 
( i  e.  om  |->  if ( i  e.  N ,  1o ,  (/) ) )  =  X )
3938fveq1d 5471 . . . . . . 7  |-  ( ( ( ( N  e. 
om  /\  X  e. )  /\  ( X `  N )  =  1o )  /\  ( i  e.  om  |->  if ( i  e.  N ,  1o ,  (/) ) )  =  X )  -> 
( ( i  e. 
om  |->  if ( i  e.  N ,  1o ,  (/) ) ) `  N )  =  ( X `  N ) )
40 eqid 2157 . . . . . . . . . 10  |-  ( i  e.  om  |->  if ( i  e.  N ,  1o ,  (/) ) )  =  ( i  e. 
om  |->  if ( i  e.  N ,  1o ,  (/) ) )
41 eleq1 2220 . . . . . . . . . . 11  |-  ( i  =  N  ->  (
i  e.  N  <->  N  e.  N ) )
4241ifbid 3526 . . . . . . . . . 10  |-  ( i  =  N  ->  if ( i  e.  N ,  1o ,  (/) )  =  if ( N  e.  N ,  1o ,  (/) ) )
43 id 19 . . . . . . . . . 10  |-  ( N  e.  om  ->  N  e.  om )
44 nnord 4572 . . . . . . . . . . . . 13  |-  ( N  e.  om  ->  Ord  N )
45 ordirr 4502 . . . . . . . . . . . . 13  |-  ( Ord 
N  ->  -.  N  e.  N )
4644, 45syl 14 . . . . . . . . . . . 12  |-  ( N  e.  om  ->  -.  N  e.  N )
4746iffalsed 3515 . . . . . . . . . . 11  |-  ( N  e.  om  ->  if ( N  e.  N ,  1o ,  (/) )  =  (/) )
48 peano1 4554 . . . . . . . . . . 11  |-  (/)  e.  om
4947, 48eqeltrdi 2248 . . . . . . . . . 10  |-  ( N  e.  om  ->  if ( N  e.  N ,  1o ,  (/) )  e. 
om )
5040, 42, 43, 49fvmptd3 5562 . . . . . . . . 9  |-  ( N  e.  om  ->  (
( i  e.  om  |->  if ( i  e.  N ,  1o ,  (/) ) ) `
 N )  =  if ( N  e.  N ,  1o ,  (/) ) )
5150, 47eqtrd 2190 . . . . . . . 8  |-  ( N  e.  om  ->  (
( i  e.  om  |->  if ( i  e.  N ,  1o ,  (/) ) ) `
 N )  =  (/) )
5251ad3antrrr 484 . . . . . . 7  |-  ( ( ( ( N  e. 
om  /\  X  e. )  /\  ( X `  N )  =  1o )  /\  ( i  e.  om  |->  if ( i  e.  N ,  1o ,  (/) ) )  =  X )  -> 
( ( i  e. 
om  |->  if ( i  e.  N ,  1o ,  (/) ) ) `  N )  =  (/) )
53 simplr 520 . . . . . . 7  |-  ( ( ( ( N  e. 
om  /\  X  e. )  /\  ( X `  N )  =  1o )  /\  ( i  e.  om  |->  if ( i  e.  N ,  1o ,  (/) ) )  =  X )  -> 
( X `  N
)  =  1o )
5439, 52, 533eqtr3rd 2199 . . . . . 6  |-  ( ( ( ( N  e. 
om  /\  X  e. )  /\  ( X `  N )  =  1o )  /\  ( i  e.  om  |->  if ( i  e.  N ,  1o ,  (/) ) )  =  X )  ->  1o  =  (/) )
5554ex 114 . . . . 5  |-  ( ( ( N  e.  om  /\  X  e. )  /\  ( X `
 N )  =  1o )  ->  (
( i  e.  om  |->  if ( i  e.  N ,  1o ,  (/) ) )  =  X  ->  1o  =  (/) ) )
5637, 55mtoi 654 . . . 4  |-  ( ( ( N  e.  om  /\  X  e. )  /\  ( X `
 N )  =  1o )  ->  -.  ( i  e.  om  |->  if ( i  e.  N ,  1o ,  (/) ) )  =  X )
5756olcd 724 . . 3  |-  ( ( ( N  e.  om  /\  X  e. )  /\  ( X `
 N )  =  1o )  ->  (
( i  e.  om  |->  if ( i  e.  N ,  1o ,  (/) ) )  =  X  \/  -.  ( i  e.  om  |->  if ( i  e.  N ,  1o ,  (/) ) )  =  X ) )
58 df-dc 821 . . 3  |-  (DECID  ( i  e.  om  |->  if ( i  e.  N ,  1o ,  (/) ) )  =  X  <->  ( (
i  e.  om  |->  if ( i  e.  N ,  1o ,  (/) ) )  =  X  \/  -.  ( i  e.  om  |->  if ( i  e.  N ,  1o ,  (/) ) )  =  X ) )
5957, 58sylibr 133 . 2  |-  ( ( ( N  e.  om  /\  X  e. )  /\  ( X `
 N )  =  1o )  -> DECID  ( i  e.  om  |->  if ( i  e.  N ,  1o ,  (/) ) )  =  X )
60 simpl 108 . . . . 5  |-  ( ( N  e.  om  /\  X  e. )  ->  N  e.  om )
6121, 60ffvelrnd 5604 . . . 4  |-  ( ( N  e.  om  /\  X  e. )  ->  ( X `  N )  e.  2o )
6261, 25eleqtrdi 2250 . . 3  |-  ( ( N  e.  om  /\  X  e. )  ->  ( X `  N )  e.  { (/)
,  1o } )
63 elpri 3583 . . 3  |-  ( ( X `  N )  e.  { (/) ,  1o }  ->  ( ( X `
 N )  =  (/)  \/  ( X `  N )  =  1o ) )
6462, 63syl 14 . 2  |-  ( ( N  e.  om  /\  X  e. )  ->  ( ( X `  N )  =  (/)  \/  ( X `
 N )  =  1o ) )
6535, 59, 64mpjaodan 788 1  |-  ( ( N  e.  om  /\  X  e. )  -> DECID  ( i  e.  om  |->  if ( i  e.  N ,  1o ,  (/) ) )  =  X )
Colors of variables: wff set class
Syntax hints:   -. wn 3    -> wi 4    /\ wa 103    \/ wo 698  DECID wdc 820    = wceq 1335    e. wcel 2128    =/= wne 2327   (/)c0 3394   ifcif 3505   {cpr 3561   U.cuni 3773    |-> cmpt 4026   Ord word 4323   omcom 4550   -->wf 5167   ` cfv 5171   1oc1o 6357   2oc2o 6358  ℕxnninf 7064
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-ia1 105  ax-ia2 106  ax-ia3 107  ax-in1 604  ax-in2 605  ax-io 699  ax-5 1427  ax-7 1428  ax-gen 1429  ax-ie1 1473  ax-ie2 1474  ax-8 1484  ax-10 1485  ax-11 1486  ax-i12 1487  ax-bndl 1489  ax-4 1490  ax-17 1506  ax-i9 1510  ax-ial 1514  ax-i5r 1515  ax-13 2130  ax-14 2131  ax-ext 2139  ax-sep 4083  ax-nul 4091  ax-pow 4136  ax-pr 4170  ax-un 4394  ax-setind 4497  ax-iinf 4548
This theorem depends on definitions:  df-bi 116  df-dc 821  df-3or 964  df-3an 965  df-tru 1338  df-fal 1341  df-nf 1441  df-sb 1743  df-eu 2009  df-mo 2010  df-clab 2144  df-cleq 2150  df-clel 2153  df-nfc 2288  df-ne 2328  df-ral 2440  df-rex 2441  df-rab 2444  df-v 2714  df-sbc 2938  df-csb 3032  df-dif 3104  df-un 3106  df-in 3108  df-ss 3115  df-nul 3395  df-if 3506  df-pw 3545  df-sn 3566  df-pr 3567  df-op 3569  df-uni 3774  df-int 3809  df-br 3967  df-opab 4027  df-mpt 4028  df-tr 4064  df-id 4254  df-iord 4327  df-on 4329  df-suc 4332  df-iom 4551  df-xp 4593  df-rel 4594  df-cnv 4595  df-co 4596  df-dm 4597  df-rn 4598  df-iota 5136  df-fun 5173  df-fn 5174  df-f 5175  df-fv 5179  df-ov 5828  df-oprab 5829  df-mpo 5830  df-1o 6364  df-2o 6365  df-map 6596  df-nninf 7065
This theorem is referenced by: (None)
  Copyright terms: Public domain W3C validator