Theorem mreexmrid 17686

Description: In a Moore system whose closure operator has the exchange property, if a set is independent and an element is not in its closure, then adding the element to the set gives another independent set. Lemma 4.1.5 in [FaureFrolicher] p. 84. (Contributed by David Moews, 1-May-2017.)

Hypotheses

Ref	Expression
mreexmrid.1	⊢ (𝜑 → 𝐴 ∈ (Moore‘𝑋))
mreexmrid.2	⊢ 𝑁 = (mrCls‘𝐴)
mreexmrid.3	⊢ 𝐼 = (mrInd‘𝐴)
mreexmrid.4	⊢ (𝜑 → ∀𝑠 ∈ 𝒫 𝑋∀𝑦 ∈ 𝑋 ∀𝑧 ∈ ((𝑁‘(𝑠 ∪ {𝑦})) ∖ (𝑁‘𝑠))𝑦 ∈ (𝑁‘(𝑠 ∪ {𝑧})))
mreexmrid.5	⊢ (𝜑 → 𝑆 ∈ 𝐼)
mreexmrid.6	⊢ (𝜑 → 𝑌 ∈ 𝑋)
mreexmrid.7	⊢ (𝜑 → ¬ 𝑌 ∈ (𝑁‘𝑆))

Assertion

Ref	Expression
mreexmrid	⊢ (𝜑 → (𝑆 ∪ {𝑌}) ∈ 𝐼)

Distinct variable groups:   𝑋,𝑠,𝑦   𝑆,𝑠,𝑧,𝑦   𝜑,𝑠,𝑦,𝑧   𝑌,𝑠,𝑦,𝑧   𝑁,𝑠,𝑦,𝑧

Allowed substitution hints:   𝐴(𝑦,𝑧,𝑠)   𝐼(𝑦,𝑧,𝑠)   𝑋(𝑧)

Proof of Theorem mreexmrid

Dummy variable 𝑥 is distinct from all other variables.

Step	Hyp	Ref	Expression
1		mreexmrid.2	. 2 ⊢ 𝑁 = (mrCls‘𝐴)
2		mreexmrid.3	. 2 ⊢ 𝐼 = (mrInd‘𝐴)
3		mreexmrid.1	. 2 ⊢ (𝜑 → 𝐴 ∈ (Moore‘𝑋))
4		mreexmrid.5	. . . 4 ⊢ (𝜑 → 𝑆 ∈ 𝐼)
5	2, 3, 4	mrissd 17679	. . 3 ⊢ (𝜑 → 𝑆 ⊆ 𝑋)
6		mreexmrid.6	. . . 4 ⊢ (𝜑 → 𝑌 ∈ 𝑋)
7	6	snssd 4809	. . 3 ⊢ (𝜑 → {𝑌} ⊆ 𝑋)
8	5, 7	unssd 4192	. 2 ⊢ (𝜑 → (𝑆 ∪ {𝑌}) ⊆ 𝑋)
9	3	3ad2ant1 1134	. . . . . . . . . 10 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → 𝐴 ∈ (Moore‘𝑋))
10	9	elfvexd 6945	. . . . . . . . 9 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → 𝑋 ∈ V)
11		mreexmrid.4	. . . . . . . . . 10 ⊢ (𝜑 → ∀𝑠 ∈ 𝒫 𝑋∀𝑦 ∈ 𝑋 ∀𝑧 ∈ ((𝑁‘(𝑠 ∪ {𝑦})) ∖ (𝑁‘𝑠))𝑦 ∈ (𝑁‘(𝑠 ∪ {𝑧})))
12	11	3ad2ant1 1134	. . . . . . . . 9 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → ∀𝑠 ∈ 𝒫 𝑋∀𝑦 ∈ 𝑋 ∀𝑧 ∈ ((𝑁‘(𝑠 ∪ {𝑦})) ∖ (𝑁‘𝑠))𝑦 ∈ (𝑁‘(𝑠 ∪ {𝑧})))
13	4	3ad2ant1 1134	. . . . . . . . . . 11 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → 𝑆 ∈ 𝐼)
14	2, 9, 13	mrissd 17679	. . . . . . . . . 10 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → 𝑆 ⊆ 𝑋)
15	14	ssdifssd 4147	. . . . . . . . 9 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → (𝑆 ∖ {𝑥}) ⊆ 𝑋)
16	6	3ad2ant1 1134	. . . . . . . . 9 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → 𝑌 ∈ 𝑋)
17		simp3 1139	. . . . . . . . . 10 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥})))
18		difundir 4291	. . . . . . . . . . . 12 ⊢ ((𝑆 ∪ {𝑌}) ∖ {𝑥}) = ((𝑆 ∖ {𝑥}) ∪ ({𝑌} ∖ {𝑥}))
19		simp2 1138	. . . . . . . . . . . . . . . 16 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → 𝑥 ∈ 𝑆)
20	3, 1, 5	mrcssidd 17668	. . . . . . . . . . . . . . . . . 18 ⊢ (𝜑 → 𝑆 ⊆ (𝑁‘𝑆))
21		mreexmrid.7	. . . . . . . . . . . . . . . . . 18 ⊢ (𝜑 → ¬ 𝑌 ∈ (𝑁‘𝑆))
22	20, 21	ssneldd 3986	. . . . . . . . . . . . . . . . 17 ⊢ (𝜑 → ¬ 𝑌 ∈ 𝑆)
23	22	3ad2ant1 1134	. . . . . . . . . . . . . . . 16 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → ¬ 𝑌 ∈ 𝑆)
24		nelneq 2865	. . . . . . . . . . . . . . . 16 ⊢ ((𝑥 ∈ 𝑆 ∧ ¬ 𝑌 ∈ 𝑆) → ¬ 𝑥 = 𝑌)
25	19, 23, 24	syl2anc 584	. . . . . . . . . . . . . . 15 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → ¬ 𝑥 = 𝑌)
26		elsni 4643	. . . . . . . . . . . . . . 15 ⊢ (𝑥 ∈ {𝑌} → 𝑥 = 𝑌)
27	25, 26	nsyl 140	. . . . . . . . . . . . . 14 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → ¬ 𝑥 ∈ {𝑌})
28		difsnb 4806	. . . . . . . . . . . . . 14 ⊢ (¬ 𝑥 ∈ {𝑌} ↔ ({𝑌} ∖ {𝑥}) = {𝑌})
29	27, 28	sylib 218	. . . . . . . . . . . . 13 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → ({𝑌} ∖ {𝑥}) = {𝑌})
30	29	uneq2d 4168	. . . . . . . . . . . 12 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → ((𝑆 ∖ {𝑥}) ∪ ({𝑌} ∖ {𝑥})) = ((𝑆 ∖ {𝑥}) ∪ {𝑌}))
31	18, 30	eqtrid 2789	. . . . . . . . . . 11 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → ((𝑆 ∪ {𝑌}) ∖ {𝑥}) = ((𝑆 ∖ {𝑥}) ∪ {𝑌}))
32	31	fveq2d 6910	. . . . . . . . . 10 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥})) = (𝑁‘((𝑆 ∖ {𝑥}) ∪ {𝑌})))
33	17, 32	eleqtrd 2843	. . . . . . . . 9 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → 𝑥 ∈ (𝑁‘((𝑆 ∖ {𝑥}) ∪ {𝑌})))
34	1, 2, 9, 13, 19	ismri2dad 17680	. . . . . . . . 9 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → ¬ 𝑥 ∈ (𝑁‘(𝑆 ∖ {𝑥})))
35	10, 12, 15, 16, 33, 34	mreexd 17685	. . . . . . . 8 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → 𝑌 ∈ (𝑁‘((𝑆 ∖ {𝑥}) ∪ {𝑥})))
36	21	3ad2ant1 1134	. . . . . . . . 9 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → ¬ 𝑌 ∈ (𝑁‘𝑆))
37		undif1 4476	. . . . . . . . . . 11 ⊢ ((𝑆 ∖ {𝑥}) ∪ {𝑥}) = (𝑆 ∪ {𝑥})
38	19	snssd 4809	. . . . . . . . . . . 12 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → {𝑥} ⊆ 𝑆)
39		ssequn2 4189	. . . . . . . . . . . 12 ⊢ ({𝑥} ⊆ 𝑆 ↔ (𝑆 ∪ {𝑥}) = 𝑆)
40	38, 39	sylib 218	. . . . . . . . . . 11 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → (𝑆 ∪ {𝑥}) = 𝑆)
41	37, 40	eqtrid 2789	. . . . . . . . . 10 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → ((𝑆 ∖ {𝑥}) ∪ {𝑥}) = 𝑆)
42	41	fveq2d 6910	. . . . . . . . 9 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → (𝑁‘((𝑆 ∖ {𝑥}) ∪ {𝑥})) = (𝑁‘𝑆))
43	36, 42	neleqtrrd 2864	. . . . . . . 8 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → ¬ 𝑌 ∈ (𝑁‘((𝑆 ∖ {𝑥}) ∪ {𝑥})))
44	35, 43	pm2.65i 194	. . . . . . 7 ⊢ ¬ (𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥})))
45		df-3an 1089	. . . . . . 7 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) ↔ ((𝜑 ∧ 𝑥 ∈ 𝑆) ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))))
46	44, 45	mtbi 322	. . . . . 6 ⊢ ¬ ((𝜑 ∧ 𝑥 ∈ 𝑆) ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥})))
47	46	imnani 400	. . . . 5 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆) → ¬ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥})))
48	47	adantlr 715	. . . 4 ⊢ (((𝜑 ∧ 𝑥 ∈ (𝑆 ∪ {𝑌})) ∧ 𝑥 ∈ 𝑆) → ¬ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥})))
49	26	adantl 481	. . . . . 6 ⊢ (((𝜑 ∧ 𝑥 ∈ (𝑆 ∪ {𝑌})) ∧ 𝑥 ∈ {𝑌}) → 𝑥 = 𝑌)
50	21	ad2antrr 726	. . . . . 6 ⊢ (((𝜑 ∧ 𝑥 ∈ (𝑆 ∪ {𝑌})) ∧ 𝑥 ∈ {𝑌}) → ¬ 𝑌 ∈ (𝑁‘𝑆))
51	49, 50	eqneltrd 2861	. . . . 5 ⊢ (((𝜑 ∧ 𝑥 ∈ (𝑆 ∪ {𝑌})) ∧ 𝑥 ∈ {𝑌}) → ¬ 𝑥 ∈ (𝑁‘𝑆))
52	49	sneqd 4638	. . . . . . . . 9 ⊢ (((𝜑 ∧ 𝑥 ∈ (𝑆 ∪ {𝑌})) ∧ 𝑥 ∈ {𝑌}) → {𝑥} = {𝑌})
53	52	difeq2d 4126	. . . . . . . 8 ⊢ (((𝜑 ∧ 𝑥 ∈ (𝑆 ∪ {𝑌})) ∧ 𝑥 ∈ {𝑌}) → ((𝑆 ∪ {𝑌}) ∖ {𝑥}) = ((𝑆 ∪ {𝑌}) ∖ {𝑌}))
54		difun2 4481	. . . . . . . 8 ⊢ ((𝑆 ∪ {𝑌}) ∖ {𝑌}) = (𝑆 ∖ {𝑌})
55	53, 54	eqtrdi 2793	. . . . . . 7 ⊢ (((𝜑 ∧ 𝑥 ∈ (𝑆 ∪ {𝑌})) ∧ 𝑥 ∈ {𝑌}) → ((𝑆 ∪ {𝑌}) ∖ {𝑥}) = (𝑆 ∖ {𝑌}))
56		difsnb 4806	. . . . . . . . 9 ⊢ (¬ 𝑌 ∈ 𝑆 ↔ (𝑆 ∖ {𝑌}) = 𝑆)
57	22, 56	sylib 218	. . . . . . . 8 ⊢ (𝜑 → (𝑆 ∖ {𝑌}) = 𝑆)
58	57	ad2antrr 726	. . . . . . 7 ⊢ (((𝜑 ∧ 𝑥 ∈ (𝑆 ∪ {𝑌})) ∧ 𝑥 ∈ {𝑌}) → (𝑆 ∖ {𝑌}) = 𝑆)
59	55, 58	eqtrd 2777	. . . . . 6 ⊢ (((𝜑 ∧ 𝑥 ∈ (𝑆 ∪ {𝑌})) ∧ 𝑥 ∈ {𝑌}) → ((𝑆 ∪ {𝑌}) ∖ {𝑥}) = 𝑆)
60	59	fveq2d 6910	. . . . 5 ⊢ (((𝜑 ∧ 𝑥 ∈ (𝑆 ∪ {𝑌})) ∧ 𝑥 ∈ {𝑌}) → (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥})) = (𝑁‘𝑆))
61	51, 60	neleqtrrd 2864	. . . 4 ⊢ (((𝜑 ∧ 𝑥 ∈ (𝑆 ∪ {𝑌})) ∧ 𝑥 ∈ {𝑌}) → ¬ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥})))
62		simpr 484	. . . . 5 ⊢ ((𝜑 ∧ 𝑥 ∈ (𝑆 ∪ {𝑌})) → 𝑥 ∈ (𝑆 ∪ {𝑌}))
63		elun 4153	. . . . 5 ⊢ (𝑥 ∈ (𝑆 ∪ {𝑌}) ↔ (𝑥 ∈ 𝑆 ∨ 𝑥 ∈ {𝑌}))
64	62, 63	sylib 218	. . . 4 ⊢ ((𝜑 ∧ 𝑥 ∈ (𝑆 ∪ {𝑌})) → (𝑥 ∈ 𝑆 ∨ 𝑥 ∈ {𝑌}))
65	48, 61, 64	mpjaodan 961	. . 3 ⊢ ((𝜑 ∧ 𝑥 ∈ (𝑆 ∪ {𝑌})) → ¬ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥})))
66	65	ralrimiva 3146	. 2 ⊢ (𝜑 → ∀𝑥 ∈ (𝑆 ∪ {𝑌}) ¬ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥})))
67	1, 2, 3, 8, 66	ismri2dd 17677	1 ⊢ (𝜑 → (𝑆 ∪ {𝑌}) ∈ 𝐼)

Syntax hints:  ¬ wn 3   → wi 4   ∧ wa 395   ∨ wo 848   ∧ w3a 1087   = wceq 1540   ∈ wcel 2108  ∀wral 3061  Vcvv 3480   ∖ cdif 3948   ∪ cun 3949   ⊆ wss 3951  𝒫 cpw 4600  {csn 4626  ‘cfv 6561  Moorecmre 17625  mrClscmrc 17626  mrIndcmri 17627

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1795  ax-4 1809  ax-5 1910  ax-6 1967  ax-7 2007  ax-8 2110  ax-9 2118  ax-10 2141  ax-11 2157  ax-12 2177  ax-ext 2708  ax-sep 5296  ax-nul 5306  ax-pow 5365  ax-pr 5432  ax-un 7755

This theorem depends on definitions:  df-bi 207  df-an 396  df-or 849  df-3an 1089  df-tru 1543  df-fal 1553  df-ex 1780  df-nf 1784  df-sb 2065  df-mo 2540  df-eu 2569  df-clab 2715  df-cleq 2729  df-clel 2816  df-nfc 2892  df-ne 2941  df-ral 3062  df-rex 3071  df-rab 3437  df-v 3482  df-sbc 3789  df-csb 3900  df-dif 3954  df-un 3956  df-in 3958  df-ss 3968  df-nul 4334  df-if 4526  df-pw 4602  df-sn 4627  df-pr 4629  df-op 4633  df-uni 4908  df-int 4947  df-br 5144  df-opab 5206  df-mpt 5226  df-id 5578  df-xp 5691  df-rel 5692  df-cnv 5693  df-co 5694  df-dm 5695  df-rn 5696  df-res 5697  df-ima 5698  df-iota 6514  df-fun 6563  df-fn 6564  df-f 6565  df-fv 6569  df-mre 17629  df-mrc 17630  df-mri 17631

This theorem is referenced by:  mreexexlem2d  17688