Theorem indf1ofs 33099

Description: The bijection between finite subsets and the indicator functions with finite support. (Contributed by Thierry Arnoux, 22-Aug-2017.)

Assertion

Ref	Expression
indf1ofs	⊢ (𝑂 ∈ 𝑉 → ((𝟭‘𝑂) ↾ Fin):(𝒫 𝑂 ∩ Fin)–1-1-onto→{𝑓 ∈ ({0, 1} ↑m 𝑂) ∣ (◡𝑓 “ {1}) ∈ Fin})

Distinct variable group:   𝑓,𝑂

Allowed substitution hint:   𝑉(𝑓)

Proof of Theorem indf1ofs

Dummy variables 𝑎 𝑔 are mutually distinct and distinct from all other variables.

Step	Hyp	Ref	Expression
1		indf1o 33097	. . . 4 ⊢ (𝑂 ∈ 𝑉 → (𝟭‘𝑂):𝒫 𝑂–1-1-onto→({0, 1} ↑m 𝑂))
2		f1of1 6809	. . . 4 ⊢ ((𝟭‘𝑂):𝒫 𝑂–1-1-onto→({0, 1} ↑m 𝑂) → (𝟭‘𝑂):𝒫 𝑂–1-1→({0, 1} ↑m 𝑂))
3	1, 2	syl 18	. . 3 ⊢ (𝑂 ∈ 𝑉 → (𝟭‘𝑂):𝒫 𝑂–1-1→({0, 1} ↑m 𝑂))
4		inss1 4191	. . 3 ⊢ (𝒫 𝑂 ∩ Fin) ⊆ 𝒫 𝑂
5		f1ores 6825	. . 3 ⊢ (((𝟭‘𝑂):𝒫 𝑂–1-1→({0, 1} ↑m 𝑂) ∧ (𝒫 𝑂 ∩ Fin) ⊆ 𝒫 𝑂) → ((𝟭‘𝑂) ↾ (𝒫 𝑂 ∩ Fin)):(𝒫 𝑂 ∩ Fin)–1-1-onto→((𝟭‘𝑂) “ (𝒫 𝑂 ∩ Fin)))
6	3, 4, 5	sylancl 597	. 2 ⊢ (𝑂 ∈ 𝑉 → ((𝟭‘𝑂) ↾ (𝒫 𝑂 ∩ Fin)):(𝒫 𝑂 ∩ Fin)–1-1-onto→((𝟭‘𝑂) “ (𝒫 𝑂 ∩ Fin)))
7		resres 5982	. . . 4 ⊢ (((𝟭‘𝑂) ↾ 𝒫 𝑂) ↾ Fin) = ((𝟭‘𝑂) ↾ (𝒫 𝑂 ∩ Fin))
8		f1ofn 6811	. . . . . 6 ⊢ ((𝟭‘𝑂):𝒫 𝑂–1-1-onto→({0, 1} ↑m 𝑂) → (𝟭‘𝑂) Fn 𝒫 𝑂)
9		fnresdm 6644	. . . . . 6 ⊢ ((𝟭‘𝑂) Fn 𝒫 𝑂 → ((𝟭‘𝑂) ↾ 𝒫 𝑂) = (𝟭‘𝑂))
10	1, 8, 9	3syl 19	. . . . 5 ⊢ (𝑂 ∈ 𝑉 → ((𝟭‘𝑂) ↾ 𝒫 𝑂) = (𝟭‘𝑂))
11	10	reseq1d 5968	. . . 4 ⊢ (𝑂 ∈ 𝑉 → (((𝟭‘𝑂) ↾ 𝒫 𝑂) ↾ Fin) = ((𝟭‘𝑂) ↾ Fin))
12	7, 11	eqtr3id 2814	. . 3 ⊢ (𝑂 ∈ 𝑉 → ((𝟭‘𝑂) ↾ (𝒫 𝑂 ∩ Fin)) = ((𝟭‘𝑂) ↾ Fin))
13		eqidd 2766	. . 3 ⊢ (𝑂 ∈ 𝑉 → (𝒫 𝑂 ∩ Fin) = (𝒫 𝑂 ∩ Fin))
14		simpll 778	. . . . . . . . 9 ⊢ (((𝑂 ∈ 𝑉 ∧ 𝑎 ∈ (𝒫 𝑂 ∩ Fin)) ∧ ((𝟭‘𝑂)‘𝑎) = 𝑔) → 𝑂 ∈ 𝑉)
15		simpr 489	. . . . . . . . . . . . . 14 ⊢ ((𝑂 ∈ 𝑉 ∧ 𝑎 ∈ (𝒫 𝑂 ∩ Fin)) → 𝑎 ∈ (𝒫 𝑂 ∩ Fin))
16	4, 15	sselid 3937	. . . . . . . . . . . . 13 ⊢ ((𝑂 ∈ 𝑉 ∧ 𝑎 ∈ (𝒫 𝑂 ∩ Fin)) → 𝑎 ∈ 𝒫 𝑂)
17	16	elpwid 4567	. . . . . . . . . . . 12 ⊢ ((𝑂 ∈ 𝑉 ∧ 𝑎 ∈ (𝒫 𝑂 ∩ Fin)) → 𝑎 ⊆ 𝑂)
18		indf 12215	. . . . . . . . . . . 12 ⊢ ((𝑂 ∈ 𝑉 ∧ 𝑎 ⊆ 𝑂) → ((𝟭‘𝑂)‘𝑎):𝑂⟶{0, 1})
19	17, 18	syldan 602	. . . . . . . . . . 11 ⊢ ((𝑂 ∈ 𝑉 ∧ 𝑎 ∈ (𝒫 𝑂 ∩ Fin)) → ((𝟭‘𝑂)‘𝑎):𝑂⟶{0, 1})
20	19	adantr 485	. . . . . . . . . 10 ⊢ (((𝑂 ∈ 𝑉 ∧ 𝑎 ∈ (𝒫 𝑂 ∩ Fin)) ∧ ((𝟭‘𝑂)‘𝑎) = 𝑔) → ((𝟭‘𝑂)‘𝑎):𝑂⟶{0, 1})
21		simpr 489	. . . . . . . . . . 11 ⊢ (((𝑂 ∈ 𝑉 ∧ 𝑎 ∈ (𝒫 𝑂 ∩ Fin)) ∧ ((𝟭‘𝑂)‘𝑎) = 𝑔) → ((𝟭‘𝑂)‘𝑎) = 𝑔)
22	21	feq1d 6677	. . . . . . . . . 10 ⊢ (((𝑂 ∈ 𝑉 ∧ 𝑎 ∈ (𝒫 𝑂 ∩ Fin)) ∧ ((𝟭‘𝑂)‘𝑎) = 𝑔) → (((𝟭‘𝑂)‘𝑎):𝑂⟶{0, 1} ↔ 𝑔:𝑂⟶{0, 1}))
23	20, 22	mpbid 235	. . . . . . . . 9 ⊢ (((𝑂 ∈ 𝑉 ∧ 𝑎 ∈ (𝒫 𝑂 ∩ Fin)) ∧ ((𝟭‘𝑂)‘𝑎) = 𝑔) → 𝑔:𝑂⟶{0, 1})
24		prex 5400	. . . . . . . . . . 11 ⊢ {0, 1} ∈ V
25		elmapg 8824	. . . . . . . . . . 11 ⊢ (({0, 1} ∈ V ∧ 𝑂 ∈ 𝑉) → (𝑔 ∈ ({0, 1} ↑m 𝑂) ↔ 𝑔:𝑂⟶{0, 1}))
26	24, 25	mpan 702	. . . . . . . . . 10 ⊢ (𝑂 ∈ 𝑉 → (𝑔 ∈ ({0, 1} ↑m 𝑂) ↔ 𝑔:𝑂⟶{0, 1}))
27	26	biimpar 482	. . . . . . . . 9 ⊢ ((𝑂 ∈ 𝑉 ∧ 𝑔:𝑂⟶{0, 1}) → 𝑔 ∈ ({0, 1} ↑m 𝑂))
28	14, 23, 27	syl2anc 595	. . . . . . . 8 ⊢ (((𝑂 ∈ 𝑉 ∧ 𝑎 ∈ (𝒫 𝑂 ∩ Fin)) ∧ ((𝟭‘𝑂)‘𝑎) = 𝑔) → 𝑔 ∈ ({0, 1} ↑m 𝑂))
29	21	cnveqd 5852	. . . . . . . . . 10 ⊢ (((𝑂 ∈ 𝑉 ∧ 𝑎 ∈ (𝒫 𝑂 ∩ Fin)) ∧ ((𝟭‘𝑂)‘𝑎) = 𝑔) → ◡((𝟭‘𝑂)‘𝑎) = ◡𝑔)
30	29	imaeq1d 6052	. . . . . . . . 9 ⊢ (((𝑂 ∈ 𝑉 ∧ 𝑎 ∈ (𝒫 𝑂 ∩ Fin)) ∧ ((𝟭‘𝑂)‘𝑎) = 𝑔) → (◡((𝟭‘𝑂)‘𝑎) “ {1}) = (◡𝑔 “ {1}))
31		indpi1 12223	. . . . . . . . . . . 12 ⊢ ((𝑂 ∈ 𝑉 ∧ 𝑎 ⊆ 𝑂) → (◡((𝟭‘𝑂)‘𝑎) “ {1}) = 𝑎)
32	17, 31	syldan 602	. . . . . . . . . . 11 ⊢ ((𝑂 ∈ 𝑉 ∧ 𝑎 ∈ (𝒫 𝑂 ∩ Fin)) → (◡((𝟭‘𝑂)‘𝑎) “ {1}) = 𝑎)
33		inss2 4192	. . . . . . . . . . . 12 ⊢ (𝒫 𝑂 ∩ Fin) ⊆ Fin
34	33, 15	sselid 3937	. . . . . . . . . . 11 ⊢ ((𝑂 ∈ 𝑉 ∧ 𝑎 ∈ (𝒫 𝑂 ∩ Fin)) → 𝑎 ∈ Fin)
35	32, 34	eqeltrd 2865	. . . . . . . . . 10 ⊢ ((𝑂 ∈ 𝑉 ∧ 𝑎 ∈ (𝒫 𝑂 ∩ Fin)) → (◡((𝟭‘𝑂)‘𝑎) “ {1}) ∈ Fin)
36	35	adantr 485	. . . . . . . . 9 ⊢ (((𝑂 ∈ 𝑉 ∧ 𝑎 ∈ (𝒫 𝑂 ∩ Fin)) ∧ ((𝟭‘𝑂)‘𝑎) = 𝑔) → (◡((𝟭‘𝑂)‘𝑎) “ {1}) ∈ Fin)
37	30, 36	eqeltrrd 2866	. . . . . . . 8 ⊢ (((𝑂 ∈ 𝑉 ∧ 𝑎 ∈ (𝒫 𝑂 ∩ Fin)) ∧ ((𝟭‘𝑂)‘𝑎) = 𝑔) → (◡𝑔 “ {1}) ∈ Fin)
38	28, 37	jca 520	. . . . . . 7 ⊢ (((𝑂 ∈ 𝑉 ∧ 𝑎 ∈ (𝒫 𝑂 ∩ Fin)) ∧ ((𝟭‘𝑂)‘𝑎) = 𝑔) → (𝑔 ∈ ({0, 1} ↑m 𝑂) ∧ (◡𝑔 “ {1}) ∈ Fin))
39	38	rexlimdva2 3168	. . . . . 6 ⊢ (𝑂 ∈ 𝑉 → (∃𝑎 ∈ (𝒫 𝑂 ∩ Fin)((𝟭‘𝑂)‘𝑎) = 𝑔 → (𝑔 ∈ ({0, 1} ↑m 𝑂) ∧ (◡𝑔 “ {1}) ∈ Fin)))
40		cnvimass 6075	. . . . . . . . . 10 ⊢ (◡𝑔 “ {1}) ⊆ dom 𝑔
41	26	biimpa 481	. . . . . . . . . . . 12 ⊢ ((𝑂 ∈ 𝑉 ∧ 𝑔 ∈ ({0, 1} ↑m 𝑂)) → 𝑔:𝑂⟶{0, 1})
42	41	fdmd 6706	. . . . . . . . . . 11 ⊢ ((𝑂 ∈ 𝑉 ∧ 𝑔 ∈ ({0, 1} ↑m 𝑂)) → dom 𝑔 = 𝑂)
43	42	adantrr 729	. . . . . . . . . 10 ⊢ ((𝑂 ∈ 𝑉 ∧ (𝑔 ∈ ({0, 1} ↑m 𝑂) ∧ (◡𝑔 “ {1}) ∈ Fin)) → dom 𝑔 = 𝑂)
44	40, 43	sseqtrid 3981	. . . . . . . . 9 ⊢ ((𝑂 ∈ 𝑉 ∧ (𝑔 ∈ ({0, 1} ↑m 𝑂) ∧ (◡𝑔 “ {1}) ∈ Fin)) → (◡𝑔 “ {1}) ⊆ 𝑂)
45		simprr 784	. . . . . . . . 9 ⊢ ((𝑂 ∈ 𝑉 ∧ (𝑔 ∈ ({0, 1} ↑m 𝑂) ∧ (◡𝑔 “ {1}) ∈ Fin)) → (◡𝑔 “ {1}) ∈ Fin)
46		elfpw 9299	. . . . . . . . 9 ⊢ ((◡𝑔 “ {1}) ∈ (𝒫 𝑂 ∩ Fin) ↔ ((◡𝑔 “ {1}) ⊆ 𝑂 ∧ (◡𝑔 “ {1}) ∈ Fin))
47	44, 45, 46	sylanbrc 594	. . . . . . . 8 ⊢ ((𝑂 ∈ 𝑉 ∧ (𝑔 ∈ ({0, 1} ↑m 𝑂) ∧ (◡𝑔 “ {1}) ∈ Fin)) → (◡𝑔 “ {1}) ∈ (𝒫 𝑂 ∩ Fin))
48		indpreima 33098	. . . . . . . . . . 11 ⊢ ((𝑂 ∈ 𝑉 ∧ 𝑔:𝑂⟶{0, 1}) → 𝑔 = ((𝟭‘𝑂)‘(◡𝑔 “ {1})))
49	48	eqcomd 2771	. . . . . . . . . 10 ⊢ ((𝑂 ∈ 𝑉 ∧ 𝑔:𝑂⟶{0, 1}) → ((𝟭‘𝑂)‘(◡𝑔 “ {1})) = 𝑔)
50	41, 49	syldan 602	. . . . . . . . 9 ⊢ ((𝑂 ∈ 𝑉 ∧ 𝑔 ∈ ({0, 1} ↑m 𝑂)) → ((𝟭‘𝑂)‘(◡𝑔 “ {1})) = 𝑔)
51	50	adantrr 729	. . . . . . . 8 ⊢ ((𝑂 ∈ 𝑉 ∧ (𝑔 ∈ ({0, 1} ↑m 𝑂) ∧ (◡𝑔 “ {1}) ∈ Fin)) → ((𝟭‘𝑂)‘(◡𝑔 “ {1})) = 𝑔)
52		fveqeq2 6880	. . . . . . . . 9 ⊢ (𝑎 = (◡𝑔 “ {1}) → (((𝟭‘𝑂)‘𝑎) = 𝑔 ↔ ((𝟭‘𝑂)‘(◡𝑔 “ {1})) = 𝑔))
53	52	rspcev 3584	. . . . . . . 8 ⊢ (((◡𝑔 “ {1}) ∈ (𝒫 𝑂 ∩ Fin) ∧ ((𝟭‘𝑂)‘(◡𝑔 “ {1})) = 𝑔) → ∃𝑎 ∈ (𝒫 𝑂 ∩ Fin)((𝟭‘𝑂)‘𝑎) = 𝑔)
54	47, 51, 53	syl2anc 595	. . . . . . 7 ⊢ ((𝑂 ∈ 𝑉 ∧ (𝑔 ∈ ({0, 1} ↑m 𝑂) ∧ (◡𝑔 “ {1}) ∈ Fin)) → ∃𝑎 ∈ (𝒫 𝑂 ∩ Fin)((𝟭‘𝑂)‘𝑎) = 𝑔)
55	54	ex 417	. . . . . 6 ⊢ (𝑂 ∈ 𝑉 → ((𝑔 ∈ ({0, 1} ↑m 𝑂) ∧ (◡𝑔 “ {1}) ∈ Fin) → ∃𝑎 ∈ (𝒫 𝑂 ∩ Fin)((𝟭‘𝑂)‘𝑎) = 𝑔))
56	39, 55	impbid 215	. . . . 5 ⊢ (𝑂 ∈ 𝑉 → (∃𝑎 ∈ (𝒫 𝑂 ∩ Fin)((𝟭‘𝑂)‘𝑎) = 𝑔 ↔ (𝑔 ∈ ({0, 1} ↑m 𝑂) ∧ (◡𝑔 “ {1}) ∈ Fin)))
57	1, 8	syl 18	. . . . . 6 ⊢ (𝑂 ∈ 𝑉 → (𝟭‘𝑂) Fn 𝒫 𝑂)
58		fvelimab 6943	. . . . . 6 ⊢ (((𝟭‘𝑂) Fn 𝒫 𝑂 ∧ (𝒫 𝑂 ∩ Fin) ⊆ 𝒫 𝑂) → (𝑔 ∈ ((𝟭‘𝑂) “ (𝒫 𝑂 ∩ Fin)) ↔ ∃𝑎 ∈ (𝒫 𝑂 ∩ Fin)((𝟭‘𝑂)‘𝑎) = 𝑔))
59	57, 4, 58	sylancl 597	. . . . 5 ⊢ (𝑂 ∈ 𝑉 → (𝑔 ∈ ((𝟭‘𝑂) “ (𝒫 𝑂 ∩ Fin)) ↔ ∃𝑎 ∈ (𝒫 𝑂 ∩ Fin)((𝟭‘𝑂)‘𝑎) = 𝑔))
60		cnveq 5850	. . . . . . . . 9 ⊢ (𝑓 = 𝑔 → ◡𝑓 = ◡𝑔)
61	60	imaeq1d 6052	. . . . . . . 8 ⊢ (𝑓 = 𝑔 → (◡𝑓 “ {1}) = (◡𝑔 “ {1}))
62	61	eleq1d 2850	. . . . . . 7 ⊢ (𝑓 = 𝑔 → ((◡𝑓 “ {1}) ∈ Fin ↔ (◡𝑔 “ {1}) ∈ Fin))
63	62	elrab 3653	. . . . . 6 ⊢ (𝑔 ∈ {𝑓 ∈ ({0, 1} ↑m 𝑂) ∣ (◡𝑓 “ {1}) ∈ Fin} ↔ (𝑔 ∈ ({0, 1} ↑m 𝑂) ∧ (◡𝑔 “ {1}) ∈ Fin))
64	63	a1i 11	. . . . 5 ⊢ (𝑂 ∈ 𝑉 → (𝑔 ∈ {𝑓 ∈ ({0, 1} ↑m 𝑂) ∣ (◡𝑓 “ {1}) ∈ Fin} ↔ (𝑔 ∈ ({0, 1} ↑m 𝑂) ∧ (◡𝑔 “ {1}) ∈ Fin)))
65	56, 59, 64	3bitr4d 314	. . . 4 ⊢ (𝑂 ∈ 𝑉 → (𝑔 ∈ ((𝟭‘𝑂) “ (𝒫 𝑂 ∩ Fin)) ↔ 𝑔 ∈ {𝑓 ∈ ({0, 1} ↑m 𝑂) ∣ (◡𝑓 “ {1}) ∈ Fin}))
66	65	eqrdv 2763	. . 3 ⊢ (𝑂 ∈ 𝑉 → ((𝟭‘𝑂) “ (𝒫 𝑂 ∩ Fin)) = {𝑓 ∈ ({0, 1} ↑m 𝑂) ∣ (◡𝑓 “ {1}) ∈ Fin})
67	12, 13, 66	f1oeq123d 6804	. 2 ⊢ (𝑂 ∈ 𝑉 → (((𝟭‘𝑂) ↾ (𝒫 𝑂 ∩ Fin)):(𝒫 𝑂 ∩ Fin)–1-1-onto→((𝟭‘𝑂) “ (𝒫 𝑂 ∩ Fin)) ↔ ((𝟭‘𝑂) ↾ Fin):(𝒫 𝑂 ∩ Fin)–1-1-onto→{𝑓 ∈ ({0, 1} ↑m 𝑂) ∣ (◡𝑓 “ {1}) ∈ Fin}))
68	6, 67	mpbid 235	1 ⊢ (𝑂 ∈ 𝑉 → ((𝟭‘𝑂) ↾ Fin):(𝒫 𝑂 ∩ Fin)–1-1-onto→{𝑓 ∈ ({0, 1} ↑m 𝑂) ∣ (◡𝑓 “ {1}) ∈ Fin})

Syntax hints:   → wi 4   ↔ wb 209   ∧ wa 400   = wceq 1563   ∈ wcel 2145  ∃wrex 3089  {crab 3417  Vcvv 3457   ∩ cin 3906   ⊆ wss 3907  𝒫 cpw 4558  {csn 4585  {cpr 4587  ^◡ccnv 5651  dom cdm 5652   ↾ cres 5654   “ cima 5655   Fn wfn 6520  ⟶wf 6521  –1-1→wf1 6522  –1-1-onto→wf1o 6524  ‘cfv 6525  (class class class)co 7400   ↑_m cmap 8812  Fincfn 8931  0cc0 11088  1c1 11089  𝟭cind 12209

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1818  ax-4 1832  ax-5 1933  ax-6 1990  ax-7 2031  ax-8 2147  ax-9 2155  ax-10 2178  ax-11 2194  ax-12 2215  ax-ext 2737  ax-rep 5232  ax-sep 5251  ax-nul 5261  ax-pow 5327  ax-pr 5395  ax-un 7722  ax-1cn 11146  ax-icn 11147  ax-addcl 11148  ax-addrcl 11149  ax-mulcl 11150  ax-mulrcl 11151  ax-i2m1 11156  ax-1ne0 11157  ax-rnegex 11159  ax-rrecex 11160  ax-cnre 11161

This theorem depends on definitions:  df-bi 210  df-an 401  df-or 861  df-3an 1103  df-tru 1566  df-fal 1576  df-ex 1803  df-nf 1807  df-sb 2094  df-mo 2569  df-eu 2599  df-clab 2744  df-cleq 2757  df-clel 2840  df-nfc 2914  df-ne 2961  df-ral 3080  df-rex 3090  df-reu 3371  df-rab 3418  df-v 3459  df-sbc 3748  df-csb 3856  df-dif 3910  df-un 3912  df-in 3914  df-ss 3924  df-nul 4289  df-if 4484  df-pw 4560  df-sn 4586  df-pr 4588  df-op 4592  df-uni 4869  df-iun 4954  df-br 5106  df-opab 5168  df-mpt 5187  df-id 5547  df-xp 5658  df-rel 5659  df-cnv 5660  df-co 5661  df-dm 5662  df-rn 5663  df-res 5664  df-ima 5665  df-iota 6481  df-fun 6527  df-fn 6528  df-f 6529  df-f1 6530  df-fo 6531  df-f1o 6532  df-fv 6533  df-ov 7403  df-oprab 7404  df-mpo 7405  df-map 8814  df-ind 12210

This theorem is referenced by:  eulerpartgbij  34679