Theorem indf1ofs 31894

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 31892	. . . 4 ⊢ (𝑂 ∈ 𝑉 → (𝟭‘𝑂):𝒫 𝑂–1-1-onto→({0, 1} ↑m 𝑂))
2		f1of1 6699	. . . 4 ⊢ ((𝟭‘𝑂):𝒫 𝑂–1-1-onto→({0, 1} ↑m 𝑂) → (𝟭‘𝑂):𝒫 𝑂–1-1→({0, 1} ↑m 𝑂))
3	1, 2	syl 17	. . 3 ⊢ (𝑂 ∈ 𝑉 → (𝟭‘𝑂):𝒫 𝑂–1-1→({0, 1} ↑m 𝑂))
4		inss1 4159	. . 3 ⊢ (𝒫 𝑂 ∩ Fin) ⊆ 𝒫 𝑂
5		f1ores 6714	. . 3 ⊢ (((𝟭‘𝑂):𝒫 𝑂–1-1→({0, 1} ↑m 𝑂) ∧ (𝒫 𝑂 ∩ Fin) ⊆ 𝒫 𝑂) → ((𝟭‘𝑂) ↾ (𝒫 𝑂 ∩ Fin)):(𝒫 𝑂 ∩ Fin)–1-1-onto→((𝟭‘𝑂) “ (𝒫 𝑂 ∩ Fin)))
6	3, 4, 5	sylancl 585	. 2 ⊢ (𝑂 ∈ 𝑉 → ((𝟭‘𝑂) ↾ (𝒫 𝑂 ∩ Fin)):(𝒫 𝑂 ∩ Fin)–1-1-onto→((𝟭‘𝑂) “ (𝒫 𝑂 ∩ Fin)))
7		resres 5893	. . . 4 ⊢ (((𝟭‘𝑂) ↾ 𝒫 𝑂) ↾ Fin) = ((𝟭‘𝑂) ↾ (𝒫 𝑂 ∩ Fin))
8		f1ofn 6701	. . . . . 6 ⊢ ((𝟭‘𝑂):𝒫 𝑂–1-1-onto→({0, 1} ↑m 𝑂) → (𝟭‘𝑂) Fn 𝒫 𝑂)
9		fnresdm 6535	. . . . . 6 ⊢ ((𝟭‘𝑂) Fn 𝒫 𝑂 → ((𝟭‘𝑂) ↾ 𝒫 𝑂) = (𝟭‘𝑂))
10	1, 8, 9	3syl 18	. . . . 5 ⊢ (𝑂 ∈ 𝑉 → ((𝟭‘𝑂) ↾ 𝒫 𝑂) = (𝟭‘𝑂))
11	10	reseq1d 5879	. . . 4 ⊢ (𝑂 ∈ 𝑉 → (((𝟭‘𝑂) ↾ 𝒫 𝑂) ↾ Fin) = ((𝟭‘𝑂) ↾ Fin))
12	7, 11	eqtr3id 2793	. . 3 ⊢ (𝑂 ∈ 𝑉 → ((𝟭‘𝑂) ↾ (𝒫 𝑂 ∩ Fin)) = ((𝟭‘𝑂) ↾ Fin))
13		eqidd 2739	. . 3 ⊢ (𝑂 ∈ 𝑉 → (𝒫 𝑂 ∩ Fin) = (𝒫 𝑂 ∩ Fin))
14		simpll 763	. . . . . . . . 9 ⊢ (((𝑂 ∈ 𝑉 ∧ 𝑎 ∈ (𝒫 𝑂 ∩ Fin)) ∧ ((𝟭‘𝑂)‘𝑎) = 𝑔) → 𝑂 ∈ 𝑉)
15		simpr 484	. . . . . . . . . . . . . 14 ⊢ ((𝑂 ∈ 𝑉 ∧ 𝑎 ∈ (𝒫 𝑂 ∩ Fin)) → 𝑎 ∈ (𝒫 𝑂 ∩ Fin))
16	4, 15	sselid 3915	. . . . . . . . . . . . 13 ⊢ ((𝑂 ∈ 𝑉 ∧ 𝑎 ∈ (𝒫 𝑂 ∩ Fin)) → 𝑎 ∈ 𝒫 𝑂)
17	16	elpwid 4541	. . . . . . . . . . . 12 ⊢ ((𝑂 ∈ 𝑉 ∧ 𝑎 ∈ (𝒫 𝑂 ∩ Fin)) → 𝑎 ⊆ 𝑂)
18		indf 31883	. . . . . . . . . . . 12 ⊢ ((𝑂 ∈ 𝑉 ∧ 𝑎 ⊆ 𝑂) → ((𝟭‘𝑂)‘𝑎):𝑂⟶{0, 1})
19	17, 18	syldan 590	. . . . . . . . . . 11 ⊢ ((𝑂 ∈ 𝑉 ∧ 𝑎 ∈ (𝒫 𝑂 ∩ Fin)) → ((𝟭‘𝑂)‘𝑎):𝑂⟶{0, 1})
20	19	adantr 480	. . . . . . . . . 10 ⊢ (((𝑂 ∈ 𝑉 ∧ 𝑎 ∈ (𝒫 𝑂 ∩ Fin)) ∧ ((𝟭‘𝑂)‘𝑎) = 𝑔) → ((𝟭‘𝑂)‘𝑎):𝑂⟶{0, 1})
21		simpr 484	. . . . . . . . . . 11 ⊢ (((𝑂 ∈ 𝑉 ∧ 𝑎 ∈ (𝒫 𝑂 ∩ Fin)) ∧ ((𝟭‘𝑂)‘𝑎) = 𝑔) → ((𝟭‘𝑂)‘𝑎) = 𝑔)
22	21	feq1d 6569	. . . . . . . . . 10 ⊢ (((𝑂 ∈ 𝑉 ∧ 𝑎 ∈ (𝒫 𝑂 ∩ Fin)) ∧ ((𝟭‘𝑂)‘𝑎) = 𝑔) → (((𝟭‘𝑂)‘𝑎):𝑂⟶{0, 1} ↔ 𝑔:𝑂⟶{0, 1}))
23	20, 22	mpbid 231	. . . . . . . . 9 ⊢ (((𝑂 ∈ 𝑉 ∧ 𝑎 ∈ (𝒫 𝑂 ∩ Fin)) ∧ ((𝟭‘𝑂)‘𝑎) = 𝑔) → 𝑔:𝑂⟶{0, 1})
24		prex 5350	. . . . . . . . . . 11 ⊢ {0, 1} ∈ V
25		elmapg 8586	. . . . . . . . . . 11 ⊢ (({0, 1} ∈ V ∧ 𝑂 ∈ 𝑉) → (𝑔 ∈ ({0, 1} ↑m 𝑂) ↔ 𝑔:𝑂⟶{0, 1}))
26	24, 25	mpan 686	. . . . . . . . . 10 ⊢ (𝑂 ∈ 𝑉 → (𝑔 ∈ ({0, 1} ↑m 𝑂) ↔ 𝑔:𝑂⟶{0, 1}))
27	26	biimpar 477	. . . . . . . . 9 ⊢ ((𝑂 ∈ 𝑉 ∧ 𝑔:𝑂⟶{0, 1}) → 𝑔 ∈ ({0, 1} ↑m 𝑂))
28	14, 23, 27	syl2anc 583	. . . . . . . 8 ⊢ (((𝑂 ∈ 𝑉 ∧ 𝑎 ∈ (𝒫 𝑂 ∩ Fin)) ∧ ((𝟭‘𝑂)‘𝑎) = 𝑔) → 𝑔 ∈ ({0, 1} ↑m 𝑂))
29	21	cnveqd 5773	. . . . . . . . . 10 ⊢ (((𝑂 ∈ 𝑉 ∧ 𝑎 ∈ (𝒫 𝑂 ∩ Fin)) ∧ ((𝟭‘𝑂)‘𝑎) = 𝑔) → ◡((𝟭‘𝑂)‘𝑎) = ◡𝑔)
30	29	imaeq1d 5957	. . . . . . . . 9 ⊢ (((𝑂 ∈ 𝑉 ∧ 𝑎 ∈ (𝒫 𝑂 ∩ Fin)) ∧ ((𝟭‘𝑂)‘𝑎) = 𝑔) → (◡((𝟭‘𝑂)‘𝑎) “ {1}) = (◡𝑔 “ {1}))
31		indpi1 31888	. . . . . . . . . . . 12 ⊢ ((𝑂 ∈ 𝑉 ∧ 𝑎 ⊆ 𝑂) → (◡((𝟭‘𝑂)‘𝑎) “ {1}) = 𝑎)
32	17, 31	syldan 590	. . . . . . . . . . 11 ⊢ ((𝑂 ∈ 𝑉 ∧ 𝑎 ∈ (𝒫 𝑂 ∩ Fin)) → (◡((𝟭‘𝑂)‘𝑎) “ {1}) = 𝑎)
33		inss2 4160	. . . . . . . . . . . 12 ⊢ (𝒫 𝑂 ∩ Fin) ⊆ Fin
34	33, 15	sselid 3915	. . . . . . . . . . 11 ⊢ ((𝑂 ∈ 𝑉 ∧ 𝑎 ∈ (𝒫 𝑂 ∩ Fin)) → 𝑎 ∈ Fin)
35	32, 34	eqeltrd 2839	. . . . . . . . . 10 ⊢ ((𝑂 ∈ 𝑉 ∧ 𝑎 ∈ (𝒫 𝑂 ∩ Fin)) → (◡((𝟭‘𝑂)‘𝑎) “ {1}) ∈ Fin)
36	35	adantr 480	. . . . . . . . 9 ⊢ (((𝑂 ∈ 𝑉 ∧ 𝑎 ∈ (𝒫 𝑂 ∩ Fin)) ∧ ((𝟭‘𝑂)‘𝑎) = 𝑔) → (◡((𝟭‘𝑂)‘𝑎) “ {1}) ∈ Fin)
37	30, 36	eqeltrrd 2840	. . . . . . . 8 ⊢ (((𝑂 ∈ 𝑉 ∧ 𝑎 ∈ (𝒫 𝑂 ∩ Fin)) ∧ ((𝟭‘𝑂)‘𝑎) = 𝑔) → (◡𝑔 “ {1}) ∈ Fin)
38	28, 37	jca 511	. . . . . . 7 ⊢ (((𝑂 ∈ 𝑉 ∧ 𝑎 ∈ (𝒫 𝑂 ∩ Fin)) ∧ ((𝟭‘𝑂)‘𝑎) = 𝑔) → (𝑔 ∈ ({0, 1} ↑m 𝑂) ∧ (◡𝑔 “ {1}) ∈ Fin))
39	38	rexlimdva2 3215	. . . . . 6 ⊢ (𝑂 ∈ 𝑉 → (∃𝑎 ∈ (𝒫 𝑂 ∩ Fin)((𝟭‘𝑂)‘𝑎) = 𝑔 → (𝑔 ∈ ({0, 1} ↑m 𝑂) ∧ (◡𝑔 “ {1}) ∈ Fin)))
40		cnvimass 5978	. . . . . . . . . 10 ⊢ (◡𝑔 “ {1}) ⊆ dom 𝑔
41	26	biimpa 476	. . . . . . . . . . . 12 ⊢ ((𝑂 ∈ 𝑉 ∧ 𝑔 ∈ ({0, 1} ↑m 𝑂)) → 𝑔:𝑂⟶{0, 1})
42	41	fdmd 6595	. . . . . . . . . . 11 ⊢ ((𝑂 ∈ 𝑉 ∧ 𝑔 ∈ ({0, 1} ↑m 𝑂)) → dom 𝑔 = 𝑂)
43	42	adantrr 713	. . . . . . . . . 10 ⊢ ((𝑂 ∈ 𝑉 ∧ (𝑔 ∈ ({0, 1} ↑m 𝑂) ∧ (◡𝑔 “ {1}) ∈ Fin)) → dom 𝑔 = 𝑂)
44	40, 43	sseqtrid 3969	. . . . . . . . 9 ⊢ ((𝑂 ∈ 𝑉 ∧ (𝑔 ∈ ({0, 1} ↑m 𝑂) ∧ (◡𝑔 “ {1}) ∈ Fin)) → (◡𝑔 “ {1}) ⊆ 𝑂)
45		simprr 769	. . . . . . . . 9 ⊢ ((𝑂 ∈ 𝑉 ∧ (𝑔 ∈ ({0, 1} ↑m 𝑂) ∧ (◡𝑔 “ {1}) ∈ Fin)) → (◡𝑔 “ {1}) ∈ Fin)
46		elfpw 9051	. . . . . . . . 9 ⊢ ((◡𝑔 “ {1}) ∈ (𝒫 𝑂 ∩ Fin) ↔ ((◡𝑔 “ {1}) ⊆ 𝑂 ∧ (◡𝑔 “ {1}) ∈ Fin))
47	44, 45, 46	sylanbrc 582	. . . . . . . 8 ⊢ ((𝑂 ∈ 𝑉 ∧ (𝑔 ∈ ({0, 1} ↑m 𝑂) ∧ (◡𝑔 “ {1}) ∈ Fin)) → (◡𝑔 “ {1}) ∈ (𝒫 𝑂 ∩ Fin))
48		indpreima 31893	. . . . . . . . . . 11 ⊢ ((𝑂 ∈ 𝑉 ∧ 𝑔:𝑂⟶{0, 1}) → 𝑔 = ((𝟭‘𝑂)‘(◡𝑔 “ {1})))
49	48	eqcomd 2744	. . . . . . . . . 10 ⊢ ((𝑂 ∈ 𝑉 ∧ 𝑔:𝑂⟶{0, 1}) → ((𝟭‘𝑂)‘(◡𝑔 “ {1})) = 𝑔)
50	41, 49	syldan 590	. . . . . . . . 9 ⊢ ((𝑂 ∈ 𝑉 ∧ 𝑔 ∈ ({0, 1} ↑m 𝑂)) → ((𝟭‘𝑂)‘(◡𝑔 “ {1})) = 𝑔)
51	50	adantrr 713	. . . . . . . 8 ⊢ ((𝑂 ∈ 𝑉 ∧ (𝑔 ∈ ({0, 1} ↑m 𝑂) ∧ (◡𝑔 “ {1}) ∈ Fin)) → ((𝟭‘𝑂)‘(◡𝑔 “ {1})) = 𝑔)
52		fveqeq2 6765	. . . . . . . . 9 ⊢ (𝑎 = (◡𝑔 “ {1}) → (((𝟭‘𝑂)‘𝑎) = 𝑔 ↔ ((𝟭‘𝑂)‘(◡𝑔 “ {1})) = 𝑔))
53	52	rspcev 3552	. . . . . . . 8 ⊢ (((◡𝑔 “ {1}) ∈ (𝒫 𝑂 ∩ Fin) ∧ ((𝟭‘𝑂)‘(◡𝑔 “ {1})) = 𝑔) → ∃𝑎 ∈ (𝒫 𝑂 ∩ Fin)((𝟭‘𝑂)‘𝑎) = 𝑔)
54	47, 51, 53	syl2anc 583	. . . . . . 7 ⊢ ((𝑂 ∈ 𝑉 ∧ (𝑔 ∈ ({0, 1} ↑m 𝑂) ∧ (◡𝑔 “ {1}) ∈ Fin)) → ∃𝑎 ∈ (𝒫 𝑂 ∩ Fin)((𝟭‘𝑂)‘𝑎) = 𝑔)
55	54	ex 412	. . . . . 6 ⊢ (𝑂 ∈ 𝑉 → ((𝑔 ∈ ({0, 1} ↑m 𝑂) ∧ (◡𝑔 “ {1}) ∈ Fin) → ∃𝑎 ∈ (𝒫 𝑂 ∩ Fin)((𝟭‘𝑂)‘𝑎) = 𝑔))
56	39, 55	impbid 211	. . . . 5 ⊢ (𝑂 ∈ 𝑉 → (∃𝑎 ∈ (𝒫 𝑂 ∩ Fin)((𝟭‘𝑂)‘𝑎) = 𝑔 ↔ (𝑔 ∈ ({0, 1} ↑m 𝑂) ∧ (◡𝑔 “ {1}) ∈ Fin)))
57	1, 8	syl 17	. . . . . 6 ⊢ (𝑂 ∈ 𝑉 → (𝟭‘𝑂) Fn 𝒫 𝑂)
58		fvelimab 6823	. . . . . 6 ⊢ (((𝟭‘𝑂) Fn 𝒫 𝑂 ∧ (𝒫 𝑂 ∩ Fin) ⊆ 𝒫 𝑂) → (𝑔 ∈ ((𝟭‘𝑂) “ (𝒫 𝑂 ∩ Fin)) ↔ ∃𝑎 ∈ (𝒫 𝑂 ∩ Fin)((𝟭‘𝑂)‘𝑎) = 𝑔))
59	57, 4, 58	sylancl 585	. . . . 5 ⊢ (𝑂 ∈ 𝑉 → (𝑔 ∈ ((𝟭‘𝑂) “ (𝒫 𝑂 ∩ Fin)) ↔ ∃𝑎 ∈ (𝒫 𝑂 ∩ Fin)((𝟭‘𝑂)‘𝑎) = 𝑔))
60		cnveq 5771	. . . . . . . . 9 ⊢ (𝑓 = 𝑔 → ◡𝑓 = ◡𝑔)
61	60	imaeq1d 5957	. . . . . . . 8 ⊢ (𝑓 = 𝑔 → (◡𝑓 “ {1}) = (◡𝑔 “ {1}))
62	61	eleq1d 2823	. . . . . . 7 ⊢ (𝑓 = 𝑔 → ((◡𝑓 “ {1}) ∈ Fin ↔ (◡𝑔 “ {1}) ∈ Fin))
63	62	elrab 3617	. . . . . 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 310	. . . 4 ⊢ (𝑂 ∈ 𝑉 → (𝑔 ∈ ((𝟭‘𝑂) “ (𝒫 𝑂 ∩ Fin)) ↔ 𝑔 ∈ {𝑓 ∈ ({0, 1} ↑m 𝑂) ∣ (◡𝑓 “ {1}) ∈ Fin}))
66	65	eqrdv 2736	. . 3 ⊢ (𝑂 ∈ 𝑉 → ((𝟭‘𝑂) “ (𝒫 𝑂 ∩ Fin)) = {𝑓 ∈ ({0, 1} ↑m 𝑂) ∣ (◡𝑓 “ {1}) ∈ Fin})
67	12, 13, 66	f1oeq123d 6694	. 2 ⊢ (𝑂 ∈ 𝑉 → (((𝟭‘𝑂) ↾ (𝒫 𝑂 ∩ Fin)):(𝒫 𝑂 ∩ Fin)–1-1-onto→((𝟭‘𝑂) “ (𝒫 𝑂 ∩ Fin)) ↔ ((𝟭‘𝑂) ↾ Fin):(𝒫 𝑂 ∩ Fin)–1-1-onto→{𝑓 ∈ ({0, 1} ↑m 𝑂) ∣ (◡𝑓 “ {1}) ∈ Fin}))
68	6, 67	mpbid 231	1 ⊢ (𝑂 ∈ 𝑉 → ((𝟭‘𝑂) ↾ Fin):(𝒫 𝑂 ∩ Fin)–1-1-onto→{𝑓 ∈ ({0, 1} ↑m 𝑂) ∣ (◡𝑓 “ {1}) ∈ Fin})

Syntax hints:   → wi 4   ↔ wb 205   ∧ wa 395   = wceq 1539   ∈ wcel 2108  ∃wrex 3064  {crab 3067  Vcvv 3422   ∩ cin 3882   ⊆ wss 3883  𝒫 cpw 4530  {csn 4558  {cpr 4560  ^◡ccnv 5579  dom cdm 5580   ↾ cres 5582   “ cima 5583   Fn wfn 6413  ⟶wf 6414  –1-1→wf1 6415  –1-1-onto→wf1o 6417  ‘cfv 6418  (class class class)co 7255   ↑_m cmap 8573  Fincfn 8691  0cc0 10802  1c1 10803  𝟭cind 31878

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1799  ax-4 1813  ax-5 1914  ax-6 1972  ax-7 2012  ax-8 2110  ax-9 2118  ax-10 2139  ax-11 2156  ax-12 2173  ax-ext 2709  ax-rep 5205  ax-sep 5218  ax-nul 5225  ax-pow 5283  ax-pr 5347  ax-un 7566  ax-1cn 10860  ax-icn 10861  ax-addcl 10862  ax-addrcl 10863  ax-mulcl 10864  ax-mulrcl 10865  ax-i2m1 10870  ax-1ne0 10871  ax-rnegex 10873  ax-rrecex 10874  ax-cnre 10875

This theorem depends on definitions:  df-bi 206  df-an 396  df-or 844  df-3an 1087  df-tru 1542  df-fal 1552  df-ex 1784  df-nf 1788  df-sb 2069  df-mo 2540  df-eu 2569  df-clab 2716  df-cleq 2730  df-clel 2817  df-nfc 2888  df-ne 2943  df-ral 3068  df-rex 3069  df-reu 3070  df-rab 3072  df-v 3424  df-sbc 3712  df-csb 3829  df-dif 3886  df-un 3888  df-in 3890  df-ss 3900  df-nul 4254  df-if 4457  df-pw 4532  df-sn 4559  df-pr 4561  df-op 4565  df-uni 4837  df-iun 4923  df-br 5071  df-opab 5133  df-mpt 5154  df-id 5480  df-xp 5586  df-rel 5587  df-cnv 5588  df-co 5589  df-dm 5590  df-rn 5591  df-res 5592  df-ima 5593  df-iota 6376  df-fun 6420  df-fn 6421  df-f 6422  df-f1 6423  df-fo 6424  df-f1o 6425  df-fv 6426  df-ov 7258  df-oprab 7259  df-mpo 7260  df-map 8575  df-ind 31879

This theorem is referenced by:  eulerpartgbij  32239