Theorem bitsfi

Description: Every number is associated with a finite set of bits. (Contributed by Mario Carneiro, 5-Sep-2016)

	Ref	Expression
Assertion	bitsfi	⊢ ( 𝑁 ∈ ℕ0 → ( bits ‘ 𝑁 ) ∈ Fin )

Proof

Step	Hyp	Ref	Expression
1		nn0re	⊢ ( 𝑁 ∈ ℕ0 → 𝑁 ∈ ℝ )
2		2re	⊢ 2 ∈ ℝ
3	2	a1i	⊢ ( 𝑁 ∈ ℕ0 → 2 ∈ ℝ )
4		1lt2	⊢ 1 < 2
5	4	a1i	⊢ ( 𝑁 ∈ ℕ0 → 1 < 2 )
6		expnbnd	⊢ ( ( 𝑁 ∈ ℝ ∧ 2 ∈ ℝ ∧ 1 < 2 ) → ∃ 𝑚 ∈ ℕ 𝑁 < ( 2 ↑ 𝑚 ) )
7	1 3 5 6	syl3anc	⊢ ( 𝑁 ∈ ℕ0 → ∃ 𝑚 ∈ ℕ 𝑁 < ( 2 ↑ 𝑚 ) )
8		fzofi	⊢ ( 0 ..^ 𝑚 ) ∈ Fin
9		simpl	⊢ ( ( 𝑁 ∈ ℕ0 ∧ ( 𝑚 ∈ ℕ ∧ 𝑁 < ( 2 ↑ 𝑚 ) ) ) → 𝑁 ∈ ℕ0 )
10		nn0uz	⊢ ℕ0 = ( ℤ≥ ‘ 0 )
11	9 10	eleqtrdi	⊢ ( ( 𝑁 ∈ ℕ0 ∧ ( 𝑚 ∈ ℕ ∧ 𝑁 < ( 2 ↑ 𝑚 ) ) ) → 𝑁 ∈ ( ℤ≥ ‘ 0 ) )
12		2nn	⊢ 2 ∈ ℕ
13	12	a1i	⊢ ( ( 𝑁 ∈ ℕ0 ∧ ( 𝑚 ∈ ℕ ∧ 𝑁 < ( 2 ↑ 𝑚 ) ) ) → 2 ∈ ℕ )
14		simprl	⊢ ( ( 𝑁 ∈ ℕ0 ∧ ( 𝑚 ∈ ℕ ∧ 𝑁 < ( 2 ↑ 𝑚 ) ) ) → 𝑚 ∈ ℕ )
15	14	nnnn0d	⊢ ( ( 𝑁 ∈ ℕ0 ∧ ( 𝑚 ∈ ℕ ∧ 𝑁 < ( 2 ↑ 𝑚 ) ) ) → 𝑚 ∈ ℕ0 )
16	13 15	nnexpcld	⊢ ( ( 𝑁 ∈ ℕ0 ∧ ( 𝑚 ∈ ℕ ∧ 𝑁 < ( 2 ↑ 𝑚 ) ) ) → ( 2 ↑ 𝑚 ) ∈ ℕ )
17	16	nnzd	⊢ ( ( 𝑁 ∈ ℕ0 ∧ ( 𝑚 ∈ ℕ ∧ 𝑁 < ( 2 ↑ 𝑚 ) ) ) → ( 2 ↑ 𝑚 ) ∈ ℤ )
18		simprr	⊢ ( ( 𝑁 ∈ ℕ0 ∧ ( 𝑚 ∈ ℕ ∧ 𝑁 < ( 2 ↑ 𝑚 ) ) ) → 𝑁 < ( 2 ↑ 𝑚 ) )
19		elfzo2	⊢ ( 𝑁 ∈ ( 0 ..^ ( 2 ↑ 𝑚 ) ) ↔ ( 𝑁 ∈ ( ℤ≥ ‘ 0 ) ∧ ( 2 ↑ 𝑚 ) ∈ ℤ ∧ 𝑁 < ( 2 ↑ 𝑚 ) ) )
20	11 17 18 19	syl3anbrc	⊢ ( ( 𝑁 ∈ ℕ0 ∧ ( 𝑚 ∈ ℕ ∧ 𝑁 < ( 2 ↑ 𝑚 ) ) ) → 𝑁 ∈ ( 0 ..^ ( 2 ↑ 𝑚 ) ) )
21	9	nn0zd	⊢ ( ( 𝑁 ∈ ℕ0 ∧ ( 𝑚 ∈ ℕ ∧ 𝑁 < ( 2 ↑ 𝑚 ) ) ) → 𝑁 ∈ ℤ )
22		bitsfzo	⊢ ( ( 𝑁 ∈ ℤ ∧ 𝑚 ∈ ℕ0 ) → ( 𝑁 ∈ ( 0 ..^ ( 2 ↑ 𝑚 ) ) ↔ ( bits ‘ 𝑁 ) ⊆ ( 0 ..^ 𝑚 ) ) )
23	21 15 22	syl2anc	⊢ ( ( 𝑁 ∈ ℕ0 ∧ ( 𝑚 ∈ ℕ ∧ 𝑁 < ( 2 ↑ 𝑚 ) ) ) → ( 𝑁 ∈ ( 0 ..^ ( 2 ↑ 𝑚 ) ) ↔ ( bits ‘ 𝑁 ) ⊆ ( 0 ..^ 𝑚 ) ) )
24	20 23	mpbid	⊢ ( ( 𝑁 ∈ ℕ0 ∧ ( 𝑚 ∈ ℕ ∧ 𝑁 < ( 2 ↑ 𝑚 ) ) ) → ( bits ‘ 𝑁 ) ⊆ ( 0 ..^ 𝑚 ) )
25		ssfi	⊢ ( ( ( 0 ..^ 𝑚 ) ∈ Fin ∧ ( bits ‘ 𝑁 ) ⊆ ( 0 ..^ 𝑚 ) ) → ( bits ‘ 𝑁 ) ∈ Fin )
26	8 24 25	sylancr	⊢ ( ( 𝑁 ∈ ℕ0 ∧ ( 𝑚 ∈ ℕ ∧ 𝑁 < ( 2 ↑ 𝑚 ) ) ) → ( bits ‘ 𝑁 ) ∈ Fin )
27	7 26	rexlimddv	⊢ ( 𝑁 ∈ ℕ0 → ( bits ‘ 𝑁 ) ∈ Fin )