ssfin4 - Metamath Proof Explorer

	Metamath Proof Explorer		< Previous Next > Nearby theorems
Mirrors > Home > MPE Home > Th. List > ssfin4		Structured version Visualization version GIF version

Theorem ssfin4 10333

Description: Dedekind finite sets have Dedekind finite subsets. (Contributed by Stefan O'Rear, 30-Oct-2014.) (Revised by Mario Carneiro, 6-May-2015.) (Revised by Mario Carneiro, 16-May-2015.)

**Assertion**
Ref	Expression
ssfin4	⊢ ((𝐴 ∈ Fin^IV ∧ 𝐵 ⊆ 𝐴) → 𝐵 ∈ Fin^IV)

Proof of Theorem ssfin4 Dummy variables 𝑐 𝑥 are mutually distinct and distinct from all other variables.

Step	Hyp	Ref	Expression
1		simpll 766	. . . 4 ⊢ (((𝐴 ∈ Fin^IV ∧ 𝐵 ⊆ 𝐴) ∧ (𝑥 ⊊ 𝐵 ∧ 𝑥 ≈ 𝐵)) → 𝐴 ∈ Fin^IV)
2		pssss 4093	. . . . . . . . 9 ⊢ (𝑥 ⊊ 𝐵 → 𝑥 ⊆ 𝐵)
3		simpr 484	. . . . . . . . 9 ⊢ ((𝐴 ∈ Fin^IV ∧ 𝐵 ⊆ 𝐴) → 𝐵 ⊆ 𝐴)
4	2, 3	sylan9ssr 3994	. . . . . . . 8 ⊢ (((𝐴 ∈ Fin^IV ∧ 𝐵 ⊆ 𝐴) ∧ 𝑥 ⊊ 𝐵) → 𝑥 ⊆ 𝐴)
5		difssd 4131	. . . . . . . 8 ⊢ (((𝐴 ∈ Fin^IV ∧ 𝐵 ⊆ 𝐴) ∧ 𝑥 ⊊ 𝐵) → (𝐴 ∖ 𝐵) ⊆ 𝐴)
6	4, 5	unssd 4186	. . . . . . 7 ⊢ (((𝐴 ∈ Fin^IV ∧ 𝐵 ⊆ 𝐴) ∧ 𝑥 ⊊ 𝐵) → (𝑥 ∪ (𝐴 ∖ 𝐵)) ⊆ 𝐴)
7		pssnel 4471	. . . . . . . . 9 ⊢ (𝑥 ⊊ 𝐵 → ∃𝑐(𝑐 ∈ 𝐵 ∧ ¬ 𝑐 ∈ 𝑥))
8	7	adantl 481	. . . . . . . 8 ⊢ (((𝐴 ∈ Fin^IV ∧ 𝐵 ⊆ 𝐴) ∧ 𝑥 ⊊ 𝐵) → ∃𝑐(𝑐 ∈ 𝐵 ∧ ¬ 𝑐 ∈ 𝑥))
9		simpllr 775	. . . . . . . . . . 11 ⊢ ((((𝐴 ∈ Fin^IV ∧ 𝐵 ⊆ 𝐴) ∧ 𝑥 ⊊ 𝐵) ∧ (𝑐 ∈ 𝐵 ∧ ¬ 𝑐 ∈ 𝑥)) → 𝐵 ⊆ 𝐴)
10		simprl 770	. . . . . . . . . . 11 ⊢ ((((𝐴 ∈ Fin^IV ∧ 𝐵 ⊆ 𝐴) ∧ 𝑥 ⊊ 𝐵) ∧ (𝑐 ∈ 𝐵 ∧ ¬ 𝑐 ∈ 𝑥)) → 𝑐 ∈ 𝐵)
11	9, 10	sseldd 3981	. . . . . . . . . 10 ⊢ ((((𝐴 ∈ Fin^IV ∧ 𝐵 ⊆ 𝐴) ∧ 𝑥 ⊊ 𝐵) ∧ (𝑐 ∈ 𝐵 ∧ ¬ 𝑐 ∈ 𝑥)) → 𝑐 ∈ 𝐴)
12		simprr 772	. . . . . . . . . . 11 ⊢ ((((𝐴 ∈ Fin^IV ∧ 𝐵 ⊆ 𝐴) ∧ 𝑥 ⊊ 𝐵) ∧ (𝑐 ∈ 𝐵 ∧ ¬ 𝑐 ∈ 𝑥)) → ¬ 𝑐 ∈ 𝑥)
13		elndif 4127	. . . . . . . . . . . 12 ⊢ (𝑐 ∈ 𝐵 → ¬ 𝑐 ∈ (𝐴 ∖ 𝐵))
14	13	ad2antrl 727	. . . . . . . . . . 11 ⊢ ((((𝐴 ∈ Fin^IV ∧ 𝐵 ⊆ 𝐴) ∧ 𝑥 ⊊ 𝐵) ∧ (𝑐 ∈ 𝐵 ∧ ¬ 𝑐 ∈ 𝑥)) → ¬ 𝑐 ∈ (𝐴 ∖ 𝐵))
15		ioran 982	. . . . . . . . . . . 12 ⊢ (¬ (𝑐 ∈ 𝑥 ∨ 𝑐 ∈ (𝐴 ∖ 𝐵)) ↔ (¬ 𝑐 ∈ 𝑥 ∧ ¬ 𝑐 ∈ (𝐴 ∖ 𝐵)))
16		elun 4147	. . . . . . . . . . . 12 ⊢ (𝑐 ∈ (𝑥 ∪ (𝐴 ∖ 𝐵)) ↔ (𝑐 ∈ 𝑥 ∨ 𝑐 ∈ (𝐴 ∖ 𝐵)))
17	15, 16	xchnxbir 333	. . . . . . . . . . 11 ⊢ (¬ 𝑐 ∈ (𝑥 ∪ (𝐴 ∖ 𝐵)) ↔ (¬ 𝑐 ∈ 𝑥 ∧ ¬ 𝑐 ∈ (𝐴 ∖ 𝐵)))
18	12, 14, 17	sylanbrc 582	. . . . . . . . . 10 ⊢ ((((𝐴 ∈ Fin^IV ∧ 𝐵 ⊆ 𝐴) ∧ 𝑥 ⊊ 𝐵) ∧ (𝑐 ∈ 𝐵 ∧ ¬ 𝑐 ∈ 𝑥)) → ¬ 𝑐 ∈ (𝑥 ∪ (𝐴 ∖ 𝐵)))
19		nelneq2 2854	. . . . . . . . . 10 ⊢ ((𝑐 ∈ 𝐴 ∧ ¬ 𝑐 ∈ (𝑥 ∪ (𝐴 ∖ 𝐵))) → ¬ 𝐴 = (𝑥 ∪ (𝐴 ∖ 𝐵)))
20	11, 18, 19	syl2anc 583	. . . . . . . . 9 ⊢ ((((𝐴 ∈ Fin^IV ∧ 𝐵 ⊆ 𝐴) ∧ 𝑥 ⊊ 𝐵) ∧ (𝑐 ∈ 𝐵 ∧ ¬ 𝑐 ∈ 𝑥)) → ¬ 𝐴 = (𝑥 ∪ (𝐴 ∖ 𝐵)))
21		eqcom 2735	. . . . . . . . 9 ⊢ (𝐴 = (𝑥 ∪ (𝐴 ∖ 𝐵)) ↔ (𝑥 ∪ (𝐴 ∖ 𝐵)) = 𝐴)
22	20, 21	sylnib 328	. . . . . . . 8 ⊢ ((((𝐴 ∈ Fin^IV ∧ 𝐵 ⊆ 𝐴) ∧ 𝑥 ⊊ 𝐵) ∧ (𝑐 ∈ 𝐵 ∧ ¬ 𝑐 ∈ 𝑥)) → ¬ (𝑥 ∪ (𝐴 ∖ 𝐵)) = 𝐴)
23	8, 22	exlimddv 1931	. . . . . . 7 ⊢ (((𝐴 ∈ Fin^IV ∧ 𝐵 ⊆ 𝐴) ∧ 𝑥 ⊊ 𝐵) → ¬ (𝑥 ∪ (𝐴 ∖ 𝐵)) = 𝐴)
24		dfpss2 4083	. . . . . . 7 ⊢ ((𝑥 ∪ (𝐴 ∖ 𝐵)) ⊊ 𝐴 ↔ ((𝑥 ∪ (𝐴 ∖ 𝐵)) ⊆ 𝐴 ∧ ¬ (𝑥 ∪ (𝐴 ∖ 𝐵)) = 𝐴))
25	6, 23, 24	sylanbrc 582	. . . . . 6 ⊢ (((𝐴 ∈ Fin^IV ∧ 𝐵 ⊆ 𝐴) ∧ 𝑥 ⊊ 𝐵) → (𝑥 ∪ (𝐴 ∖ 𝐵)) ⊊ 𝐴)
26	25	adantrr 716	. . . . 5 ⊢ (((𝐴 ∈ Fin^IV ∧ 𝐵 ⊆ 𝐴) ∧ (𝑥 ⊊ 𝐵 ∧ 𝑥 ≈ 𝐵)) → (𝑥 ∪ (𝐴 ∖ 𝐵)) ⊊ 𝐴)
27		simprr 772	. . . . . . 7 ⊢ (((𝐴 ∈ Fin^IV ∧ 𝐵 ⊆ 𝐴) ∧ (𝑥 ⊊ 𝐵 ∧ 𝑥 ≈ 𝐵)) → 𝑥 ≈ 𝐵)
28		difexg 5329	. . . . . . . 8 ⊢ (𝐴 ∈ Fin^IV → (𝐴 ∖ 𝐵) ∈ V)
29		enrefg 9004	. . . . . . . 8 ⊢ ((𝐴 ∖ 𝐵) ∈ V → (𝐴 ∖ 𝐵) ≈ (𝐴 ∖ 𝐵))
30	1, 28, 29	3syl 18	. . . . . . 7 ⊢ (((𝐴 ∈ Fin^IV ∧ 𝐵 ⊆ 𝐴) ∧ (𝑥 ⊊ 𝐵 ∧ 𝑥 ≈ 𝐵)) → (𝐴 ∖ 𝐵) ≈ (𝐴 ∖ 𝐵))
31	2	ad2antrl 727	. . . . . . . . . 10 ⊢ (((𝐴 ∈ Fin^IV ∧ 𝐵 ⊆ 𝐴) ∧ (𝑥 ⊊ 𝐵 ∧ 𝑥 ≈ 𝐵)) → 𝑥 ⊆ 𝐵)
32		ssinss1 4238	. . . . . . . . . 10 ⊢ (𝑥 ⊆ 𝐵 → (𝑥 ∩ 𝐴) ⊆ 𝐵)
33	31, 32	syl 17	. . . . . . . . 9 ⊢ (((𝐴 ∈ Fin^IV ∧ 𝐵 ⊆ 𝐴) ∧ (𝑥 ⊊ 𝐵 ∧ 𝑥 ≈ 𝐵)) → (𝑥 ∩ 𝐴) ⊆ 𝐵)
34		inssdif0 4370	. . . . . . . . 9 ⊢ ((𝑥 ∩ 𝐴) ⊆ 𝐵 ↔ (𝑥 ∩ (𝐴 ∖ 𝐵)) = ∅)
35	33, 34	sylib 217	. . . . . . . 8 ⊢ (((𝐴 ∈ Fin^IV ∧ 𝐵 ⊆ 𝐴) ∧ (𝑥 ⊊ 𝐵 ∧ 𝑥 ≈ 𝐵)) → (𝑥 ∩ (𝐴 ∖ 𝐵)) = ∅)
36		disjdif 4472	. . . . . . . 8 ⊢ (𝐵 ∩ (𝐴 ∖ 𝐵)) = ∅
37	35, 36	jctir 520	. . . . . . 7 ⊢ (((𝐴 ∈ Fin^IV ∧ 𝐵 ⊆ 𝐴) ∧ (𝑥 ⊊ 𝐵 ∧ 𝑥 ≈ 𝐵)) → ((𝑥 ∩ (𝐴 ∖ 𝐵)) = ∅ ∧ (𝐵 ∩ (𝐴 ∖ 𝐵)) = ∅))
38		unen 9070	. . . . . . 7 ⊢ (((𝑥 ≈ 𝐵 ∧ (𝐴 ∖ 𝐵) ≈ (𝐴 ∖ 𝐵)) ∧ ((𝑥 ∩ (𝐴 ∖ 𝐵)) = ∅ ∧ (𝐵 ∩ (𝐴 ∖ 𝐵)) = ∅)) → (𝑥 ∪ (𝐴 ∖ 𝐵)) ≈ (𝐵 ∪ (𝐴 ∖ 𝐵)))
39	27, 30, 37, 38	syl21anc 837	. . . . . 6 ⊢ (((𝐴 ∈ Fin^IV ∧ 𝐵 ⊆ 𝐴) ∧ (𝑥 ⊊ 𝐵 ∧ 𝑥 ≈ 𝐵)) → (𝑥 ∪ (𝐴 ∖ 𝐵)) ≈ (𝐵 ∪ (𝐴 ∖ 𝐵)))
40		simplr 768	. . . . . . 7 ⊢ (((𝐴 ∈ Fin^IV ∧ 𝐵 ⊆ 𝐴) ∧ (𝑥 ⊊ 𝐵 ∧ 𝑥 ≈ 𝐵)) → 𝐵 ⊆ 𝐴)
41		undif 4482	. . . . . . 7 ⊢ (𝐵 ⊆ 𝐴 ↔ (𝐵 ∪ (𝐴 ∖ 𝐵)) = 𝐴)
42	40, 41	sylib 217	. . . . . 6 ⊢ (((𝐴 ∈ Fin^IV ∧ 𝐵 ⊆ 𝐴) ∧ (𝑥 ⊊ 𝐵 ∧ 𝑥 ≈ 𝐵)) → (𝐵 ∪ (𝐴 ∖ 𝐵)) = 𝐴)
43	39, 42	breqtrd 5174	. . . . 5 ⊢ (((𝐴 ∈ Fin^IV ∧ 𝐵 ⊆ 𝐴) ∧ (𝑥 ⊊ 𝐵 ∧ 𝑥 ≈ 𝐵)) → (𝑥 ∪ (𝐴 ∖ 𝐵)) ≈ 𝐴)
44		fin4i 10321	. . . . 5 ⊢ (((𝑥 ∪ (𝐴 ∖ 𝐵)) ⊊ 𝐴 ∧ (𝑥 ∪ (𝐴 ∖ 𝐵)) ≈ 𝐴) → ¬ 𝐴 ∈ Fin^IV)
45	26, 43, 44	syl2anc 583	. . . 4 ⊢ (((𝐴 ∈ Fin^IV ∧ 𝐵 ⊆ 𝐴) ∧ (𝑥 ⊊ 𝐵 ∧ 𝑥 ≈ 𝐵)) → ¬ 𝐴 ∈ Fin^IV)
46	1, 45	pm2.65da 816	. . 3 ⊢ ((𝐴 ∈ Fin^IV ∧ 𝐵 ⊆ 𝐴) → ¬ (𝑥 ⊊ 𝐵 ∧ 𝑥 ≈ 𝐵))
47	46	nexdv 1932	. 2 ⊢ ((𝐴 ∈ Fin^IV ∧ 𝐵 ⊆ 𝐴) → ¬ ∃𝑥(𝑥 ⊊ 𝐵 ∧ 𝑥 ≈ 𝐵))
48		ssexg 5323	. . . 4 ⊢ ((𝐵 ⊆ 𝐴 ∧ 𝐴 ∈ Fin^IV) → 𝐵 ∈ V)
49	48	ancoms 458	. . 3 ⊢ ((𝐴 ∈ Fin^IV ∧ 𝐵 ⊆ 𝐴) → 𝐵 ∈ V)
50		isfin4 10320	. . 3 ⊢ (𝐵 ∈ V → (𝐵 ∈ Fin^IV ↔ ¬ ∃𝑥(𝑥 ⊊ 𝐵 ∧ 𝑥 ≈ 𝐵)))
51	49, 50	syl 17	. 2 ⊢ ((𝐴 ∈ Fin^IV ∧ 𝐵 ⊆ 𝐴) → (𝐵 ∈ Fin^IV ↔ ¬ ∃𝑥(𝑥 ⊊ 𝐵 ∧ 𝑥 ≈ 𝐵)))
52	47, 51	mpbird 257	1 ⊢ ((𝐴 ∈ Fin^IV ∧ 𝐵 ⊆ 𝐴) → 𝐵 ∈ Fin^IV)

Colors of variables: wff setvar class

Syntax hints: ¬ wn 3 → wi 4 ↔ wb 205 ∧ wa 395 ∨ wo 846 = wceq 1534 ∃wex 1774 ∈ wcel 2099 Vcvv 3471 ∖ cdif 3944 ∪ cun 3945 ∩ cin 3946 ⊆ wss 3947 ⊊ wpss 3948 ∅c0 4323 class class class wbr 5148 ≈ cen 8960 Fin^IVcfin4 10303

This theorem was proved from axioms: ax-mp 5 ax-1 6 ax-2 7 ax-3 8 ax-gen 1790 ax-4 1804 ax-5 1906 ax-6 1964 ax-7 2004 ax-8 2101 ax-9 2109 ax-10 2130 ax-12 2167 ax-ext 2699 ax-sep 5299 ax-nul 5306 ax-pow 5365 ax-pr 5429 ax-un 7740

This theorem depends on definitions: df-bi 206 df-an 396 df-or 847 df-3an 1087 df-tru 1537 df-fal 1547 df-ex 1775 df-nf 1779 df-sb 2061 df-mo 2530 df-eu 2559 df-clab 2706 df-cleq 2720 df-clel 2806 df-ne 2938 df-ral 3059 df-rex 3068 df-rab 3430 df-v 3473 df-dif 3950 df-un 3952 df-in 3954 df-ss 3964 df-pss 3966 df-nul 4324 df-if 4530 df-pw 4605 df-sn 4630 df-pr 4632 df-op 4636 df-uni 4909 df-br 5149 df-opab 5211 df-id 5576 df-xp 5684 df-rel 5685 df-cnv 5686 df-co 5687 df-dm 5688 df-rn 5689 df-res 5690 df-ima 5691 df-fun 6550 df-fn 6551 df-f 6552 df-f1 6553 df-fo 6554 df-f1o 6555 df-en 8964 df-fin4 10310

This theorem is referenced by: domfin4 10334

W3C validator

	
		OSZAR »