Theorem qnnen 13305

Description: The rational numbers are countably infinite. Corollary 8.1.23 of [AczelRathjen], p. 75. This is Metamath 100 proof #3. (Contributed by Jim Kingdon, 11-Aug-2023.)

Assertion

Ref	Expression
qnnen	⊢ ℚ ≈ ℕ

Proof of Theorem qnnen

Dummy variables 𝑓 𝑔 𝑝 𝑞 are mutually distinct and distinct from all other variables.

Step	Hyp	Ref	Expression
1		qdceq 10662	. . 3 ⊢ ((𝑝 ∈ ℚ ∧ 𝑞 ∈ ℚ) → DECID 𝑝 = 𝑞)
2	1	rgen2a 2604	. 2 ⊢ ∀𝑝 ∈ ℚ ∀𝑞 ∈ ℚ DECID 𝑝 = 𝑞
3		znnen 13272	. . . . . . . 8 ⊢ ℤ ≈ ℕ
4		nnex 9293	. . . . . . . . 9 ⊢ ℕ ∈ V
5	4	enref 7045	. . . . . . . 8 ⊢ ℕ ≈ ℕ
6		xpen 7139	. . . . . . . 8 ⊢ ((ℤ ≈ ℕ ∧ ℕ ≈ ℕ) → (ℤ × ℕ) ≈ (ℕ × ℕ))
7	3, 5, 6	mp2an 430	. . . . . . 7 ⊢ (ℤ × ℕ) ≈ (ℕ × ℕ)
8		xpnnen 13268	. . . . . . 7 ⊢ (ℕ × ℕ) ≈ ℕ
9	7, 8	entri 7067	. . . . . 6 ⊢ (ℤ × ℕ) ≈ ℕ
10		nnenom 10854	. . . . . 6 ⊢ ℕ ≈ ω
11	9, 10	entri 7067	. . . . 5 ⊢ (ℤ × ℕ) ≈ ω
12	11	ensymi 7063	. . . 4 ⊢ ω ≈ (ℤ × ℕ)
13		bren 7024	. . . 4 ⊢ (ω ≈ (ℤ × ℕ) ↔ ∃𝑔 𝑔:ω–1-1-onto→(ℤ × ℕ))
14	12, 13	mpbi 145	. . 3 ⊢ ∃𝑔 𝑔:ω–1-1-onto→(ℤ × ℕ)
15		f1ofo 5644	. . . . 5 ⊢ (𝑔:ω–1-1-onto→(ℤ × ℕ) → 𝑔:ω–onto→(ℤ × ℕ))
16		divfnzn 10004	. . . . . . . . 9 ⊢ ( / ↾ (ℤ × ℕ)) Fn (ℤ × ℕ)
17		fnfun 5476	. . . . . . . . 9 ⊢ (( / ↾ (ℤ × ℕ)) Fn (ℤ × ℕ) → Fun ( / ↾ (ℤ × ℕ)))
18	16, 17	ax-mp 5	. . . . . . . 8 ⊢ Fun ( / ↾ (ℤ × ℕ))
19		fndm 5478	. . . . . . . . 9 ⊢ (( / ↾ (ℤ × ℕ)) Fn (ℤ × ℕ) → dom ( / ↾ (ℤ × ℕ)) = (ℤ × ℕ))
20		eqimss2 3303	. . . . . . . . 9 ⊢ (dom ( / ↾ (ℤ × ℕ)) = (ℤ × ℕ) → (ℤ × ℕ) ⊆ dom ( / ↾ (ℤ × ℕ)))
21	16, 19, 20	mp2b 8	. . . . . . . 8 ⊢ (ℤ × ℕ) ⊆ dom ( / ↾ (ℤ × ℕ))
22		fores 5623	. . . . . . . 8 ⊢ ((Fun ( / ↾ (ℤ × ℕ)) ∧ (ℤ × ℕ) ⊆ dom ( / ↾ (ℤ × ℕ))) → (( / ↾ (ℤ × ℕ)) ↾ (ℤ × ℕ)):(ℤ × ℕ)–onto→(( / ↾ (ℤ × ℕ)) “ (ℤ × ℕ)))
23	18, 21, 22	mp2an 430	. . . . . . 7 ⊢ (( / ↾ (ℤ × ℕ)) ↾ (ℤ × ℕ)):(ℤ × ℕ)–onto→(( / ↾ (ℤ × ℕ)) “ (ℤ × ℕ))
24		resima 5094	. . . . . . . . 9 ⊢ (( / ↾ (ℤ × ℕ)) “ (ℤ × ℕ)) = ( / “ (ℤ × ℕ))
25		df-q 10003	. . . . . . . . 9 ⊢ ℚ = ( / “ (ℤ × ℕ))
26	24, 25	eqtr4i 2262	. . . . . . . 8 ⊢ (( / ↾ (ℤ × ℕ)) “ (ℤ × ℕ)) = ℚ
27		foeq3 5611	. . . . . . . 8 ⊢ ((( / ↾ (ℤ × ℕ)) “ (ℤ × ℕ)) = ℚ → ((( / ↾ (ℤ × ℕ)) ↾ (ℤ × ℕ)):(ℤ × ℕ)–onto→(( / ↾ (ℤ × ℕ)) “ (ℤ × ℕ)) ↔ (( / ↾ (ℤ × ℕ)) ↾ (ℤ × ℕ)):(ℤ × ℕ)–onto→ℚ))
28	26, 27	ax-mp 5	. . . . . . 7 ⊢ ((( / ↾ (ℤ × ℕ)) ↾ (ℤ × ℕ)):(ℤ × ℕ)–onto→(( / ↾ (ℤ × ℕ)) “ (ℤ × ℕ)) ↔ (( / ↾ (ℤ × ℕ)) ↾ (ℤ × ℕ)):(ℤ × ℕ)–onto→ℚ)
29	23, 28	mpbi 145	. . . . . 6 ⊢ (( / ↾ (ℤ × ℕ)) ↾ (ℤ × ℕ)):(ℤ × ℕ)–onto→ℚ
30		foco 5624	. . . . . 6 ⊢ (((( / ↾ (ℤ × ℕ)) ↾ (ℤ × ℕ)):(ℤ × ℕ)–onto→ℚ ∧ 𝑔:ω–onto→(ℤ × ℕ)) → ((( / ↾ (ℤ × ℕ)) ↾ (ℤ × ℕ)) ∘ 𝑔):ω–onto→ℚ)
31	29, 30	mpan 428	. . . . 5 ⊢ (𝑔:ω–onto→(ℤ × ℕ) → ((( / ↾ (ℤ × ℕ)) ↾ (ℤ × ℕ)) ∘ 𝑔):ω–onto→ℚ)
32		zex 9636	. . . . . . . . 9 ⊢ ℤ ∈ V
33	32, 4	xpex 4889	. . . . . . . 8 ⊢ (ℤ × ℕ) ∈ V
34		resfunexg 5930	. . . . . . . 8 ⊢ ((Fun ( / ↾ (ℤ × ℕ)) ∧ (ℤ × ℕ) ∈ V) → (( / ↾ (ℤ × ℕ)) ↾ (ℤ × ℕ)) ∈ V)
35	18, 33, 34	mp2an 430	. . . . . . 7 ⊢ (( / ↾ (ℤ × ℕ)) ↾ (ℤ × ℕ)) ∈ V
36		vex 2824	. . . . . . 7 ⊢ 𝑔 ∈ V
37	35, 36	coex 5331	. . . . . 6 ⊢ ((( / ↾ (ℤ × ℕ)) ↾ (ℤ × ℕ)) ∘ 𝑔) ∈ V
38		foeq1 5609	. . . . . 6 ⊢ (𝑓 = ((( / ↾ (ℤ × ℕ)) ↾ (ℤ × ℕ)) ∘ 𝑔) → (𝑓:ω–onto→ℚ ↔ ((( / ↾ (ℤ × ℕ)) ↾ (ℤ × ℕ)) ∘ 𝑔):ω–onto→ℚ))
39	37, 38	spcev 2920	. . . . 5 ⊢ (((( / ↾ (ℤ × ℕ)) ↾ (ℤ × ℕ)) ∘ 𝑔):ω–onto→ℚ → ∃𝑓 𝑓:ω–onto→ℚ)
40	15, 31, 39	3syl 17	. . . 4 ⊢ (𝑔:ω–1-1-onto→(ℤ × ℕ) → ∃𝑓 𝑓:ω–onto→ℚ)
41	40	exlimiv 1651	. . 3 ⊢ (∃𝑔 𝑔:ω–1-1-onto→(ℤ × ℕ) → ∃𝑓 𝑓:ω–onto→ℚ)
42	14, 41	ax-mp 5	. 2 ⊢ ∃𝑓 𝑓:ω–onto→ℚ
43	10	ensymi 7063	. . 3 ⊢ ω ≈ ℕ
44		qex 10015	. . . 4 ⊢ ℚ ∈ V
45		nnssq 10012	. . . 4 ⊢ ℕ ⊆ ℚ
46		ssdomg 7059	. . . 4 ⊢ (ℚ ∈ V → (ℕ ⊆ ℚ → ℕ ≼ ℚ))
47	44, 45, 46	mp2 16	. . 3 ⊢ ℕ ≼ ℚ
48		endomtr 7071	. . 3 ⊢ ((ω ≈ ℕ ∧ ℕ ≼ ℚ) → ω ≼ ℚ)
49	43, 47, 48	mp2an 430	. 2 ⊢ ω ≼ ℚ
50		ctinf 13304	. 2 ⊢ (ℚ ≈ ℕ ↔ (∀𝑝 ∈ ℚ ∀𝑞 ∈ ℚ DECID 𝑝 = 𝑞 ∧ ∃𝑓 𝑓:ω–onto→ℚ ∧ ω ≼ ℚ))
51	2, 42, 49, 50	mpbir3an 1210	1 ⊢ ℚ ≈ ℕ

Syntax hints:   ↔ wb 105  DECID wdc 846   = wceq 1402  ∃wex 1545   ∈ wcel 2209  ∀wral 2528  Vcvv 2821   ⊆ wss 3220   class class class wbr 4128  ωcom 4735   × cxp 4770  dom cdm 4772   ↾ cres 4774   “ cima 4775   ∘ ccom 4776  Fun wfun 5369   Fn wfn 5370  –onto→wfo 5373  –1-1-onto→wf1o 5374   ≈ cen 7014   ≼ cdom 7015   / cdiv 8996  ℕcn 9287  ℤcz 9627  ℚcq 10002

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-ia1 106  ax-ia2 107  ax-ia3 108  ax-in1 623  ax-in2 624  ax-io 721  ax-5 1500  ax-7 1501  ax-gen 1502  ax-ie1 1546  ax-ie2 1547  ax-8 1557  ax-10 1558  ax-11 1559  ax-i12 1560  ax-bndl 1562  ax-4 1563  ax-17 1579  ax-i9 1583  ax-ial 1587  ax-i5r 1588  ax-14 2212  ax-ext 2220  ax-coll 4244  ax-sep 4247  ax-nul 4257  ax-pow 4309  ax-pr 4344  ax-un 4576  ax-setind 4682  ax-iinf 4733  ax-cnex 8264  ax-resscn 8265  ax-1cn 8266  ax-1re 8267  ax-icn 8268  ax-addcl 8269  ax-addrcl 8270  ax-mulcl 8271  ax-mulrcl 8272  ax-addcom 8273  ax-mulcom 8274  ax-addass 8275  ax-mulass 8276  ax-distr 8277  ax-i2m1 8278  ax-0lt1 8279  ax-1rid 8280  ax-0id 8281  ax-rnegex 8282  ax-precex 8283  ax-cnre 8284  ax-pre-ltirr 8285  ax-pre-ltwlin 8286  ax-pre-lttrn 8287  ax-pre-apti 8288  ax-pre-ltadd 8289  ax-pre-mulgt0 8290  ax-pre-mulext 8291  ax-arch 8292

This theorem depends on definitions:  df-bi 117  df-dc 847  df-3or 1010  df-3an 1011  df-tru 1405  df-fal 1408  df-xor 1425  df-nf 1514  df-sb 1816  df-eu 2089  df-mo 2090  df-clab 2225  df-cleq 2231  df-clel 2234  df-nfc 2381  df-ne 2421  df-nel 2516  df-ral 2533  df-rex 2534  df-reu 2535  df-rmo 2536  df-rab 2537  df-v 2823  df-sbc 3052  df-csb 3148  df-dif 3222  df-un 3224  df-in 3226  df-ss 3233  df-nul 3521  df-if 3639  df-pw 3690  df-sn 3714  df-pr 3715  df-op 3717  df-uni 3934  df-int 3969  df-iun 4012  df-br 4129  df-opab 4191  df-mpt 4192  df-tr 4228  df-id 4436  df-po 4439  df-iso 4440  df-iord 4509  df-on 4511  df-ilim 4512  df-suc 4514  df-iom 4736  df-xp 4778  df-rel 4779  df-cnv 4780  df-co 4781  df-dm 4782  df-rn 4783  df-res 4784  df-ima 4785  df-iota 5335  df-fun 5377  df-fn 5378  df-f 5379  df-f1 5380  df-fo 5381  df-f1o 5382  df-fv 5383  df-riota 6032  df-ov 6082  df-oprab 6083  df-mpo 6084  df-1st 6368  df-2nd 6369  df-recs 6570  df-frec 6656  df-1o 6681  df-er 6801  df-pm 6919  df-en 7017  df-dom 7018  df-fin 7019  df-dju 7372  df-inl 7381  df-inr 7382  df-case 7418  df-pnf 8356  df-mnf 8357  df-xr 8358  df-ltxr 8359  df-le 8360  df-sub 8493  df-neg 8494  df-reap 8897  df-ap 8904  df-div 8997  df-inn 9288  df-2 9346  df-n0 9547  df-z 9628  df-uz 9905  df-q 10003  df-rp 10038  df-fz 10395  df-fl 10688  df-mod 10743  df-seqfrec 10868  df-exp 10959  df-dvds 12538

This theorem is referenced by: (None)