Theorem mreexmrid 17701

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 17694	. . 3 ⊢ (𝜑 → 𝑆 ⊆ 𝑋)
6		mreexmrid.6	. . . 4 ⊢ (𝜑 → 𝑌 ∈ 𝑋)
7	6	snssd 4834	. . 3 ⊢ (𝜑 → {𝑌} ⊆ 𝑋)
8	5, 7	unssd 4215	. 2 ⊢ (𝜑 → (𝑆 ∪ {𝑌}) ⊆ 𝑋)
9	3	3ad2ant1 1133	. . . . . . . . . 10 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → 𝐴 ∈ (Moore‘𝑋))
10	9	elfvexd 6959	. . . . . . . . 9 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → 𝑋 ∈ V)
11		mreexmrid.4	. . . . . . . . . 10 ⊢ (𝜑 → ∀𝑠 ∈ 𝒫 𝑋∀𝑦 ∈ 𝑋 ∀𝑧 ∈ ((𝑁‘(𝑠 ∪ {𝑦})) ∖ (𝑁‘𝑠))𝑦 ∈ (𝑁‘(𝑠 ∪ {𝑧})))
12	11	3ad2ant1 1133	. . . . . . . . 9 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → ∀𝑠 ∈ 𝒫 𝑋∀𝑦 ∈ 𝑋 ∀𝑧 ∈ ((𝑁‘(𝑠 ∪ {𝑦})) ∖ (𝑁‘𝑠))𝑦 ∈ (𝑁‘(𝑠 ∪ {𝑧})))
13	4	3ad2ant1 1133	. . . . . . . . . . 11 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → 𝑆 ∈ 𝐼)
14	2, 9, 13	mrissd 17694	. . . . . . . . . 10 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → 𝑆 ⊆ 𝑋)
15	14	ssdifssd 4170	. . . . . . . . 9 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → (𝑆 ∖ {𝑥}) ⊆ 𝑋)
16	6	3ad2ant1 1133	. . . . . . . . 9 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → 𝑌 ∈ 𝑋)
17		simp3 1138	. . . . . . . . . 10 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥})))
18		difundir 4310	. . . . . . . . . . . 12 ⊢ ((𝑆 ∪ {𝑌}) ∖ {𝑥}) = ((𝑆 ∖ {𝑥}) ∪ ({𝑌} ∖ {𝑥}))
19		simp2 1137	. . . . . . . . . . . . . . . 16 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → 𝑥 ∈ 𝑆)
20	3, 1, 5	mrcssidd 17683	. . . . . . . . . . . . . . . . . 18 ⊢ (𝜑 → 𝑆 ⊆ (𝑁‘𝑆))
21		mreexmrid.7	. . . . . . . . . . . . . . . . . 18 ⊢ (𝜑 → ¬ 𝑌 ∈ (𝑁‘𝑆))
22	20, 21	ssneldd 4011	. . . . . . . . . . . . . . . . 17 ⊢ (𝜑 → ¬ 𝑌 ∈ 𝑆)
23	22	3ad2ant1 1133	. . . . . . . . . . . . . . . 16 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → ¬ 𝑌 ∈ 𝑆)
24		nelneq 2868	. . . . . . . . . . . . . . . 16 ⊢ ((𝑥 ∈ 𝑆 ∧ ¬ 𝑌 ∈ 𝑆) → ¬ 𝑥 = 𝑌)
25	19, 23, 24	syl2anc 583	. . . . . . . . . . . . . . 15 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → ¬ 𝑥 = 𝑌)
26		elsni 4665	. . . . . . . . . . . . . . 15 ⊢ (𝑥 ∈ {𝑌} → 𝑥 = 𝑌)
27	25, 26	nsyl 140	. . . . . . . . . . . . . 14 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → ¬ 𝑥 ∈ {𝑌})
28		difsnb 4831	. . . . . . . . . . . . . 14 ⊢ (¬ 𝑥 ∈ {𝑌} ↔ ({𝑌} ∖ {𝑥}) = {𝑌})
29	27, 28	sylib 218	. . . . . . . . . . . . 13 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → ({𝑌} ∖ {𝑥}) = {𝑌})
30	29	uneq2d 4191	. . . . . . . . . . . 12 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → ((𝑆 ∖ {𝑥}) ∪ ({𝑌} ∖ {𝑥})) = ((𝑆 ∖ {𝑥}) ∪ {𝑌}))
31	18, 30	eqtrid 2792	. . . . . . . . . . 11 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → ((𝑆 ∪ {𝑌}) ∖ {𝑥}) = ((𝑆 ∖ {𝑥}) ∪ {𝑌}))
32	31	fveq2d 6924	. . . . . . . . . 10 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥})) = (𝑁‘((𝑆 ∖ {𝑥}) ∪ {𝑌})))
33	17, 32	eleqtrd 2846	. . . . . . . . 9 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → 𝑥 ∈ (𝑁‘((𝑆 ∖ {𝑥}) ∪ {𝑌})))
34	1, 2, 9, 13, 19	ismri2dad 17695	. . . . . . . . 9 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → ¬ 𝑥 ∈ (𝑁‘(𝑆 ∖ {𝑥})))
35	10, 12, 15, 16, 33, 34	mreexd 17700	. . . . . . . 8 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → 𝑌 ∈ (𝑁‘((𝑆 ∖ {𝑥}) ∪ {𝑥})))
36	21	3ad2ant1 1133	. . . . . . . . 9 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → ¬ 𝑌 ∈ (𝑁‘𝑆))
37		undif1 4499	. . . . . . . . . . 11 ⊢ ((𝑆 ∖ {𝑥}) ∪ {𝑥}) = (𝑆 ∪ {𝑥})
38	19	snssd 4834	. . . . . . . . . . . 12 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → {𝑥} ⊆ 𝑆)
39		ssequn2 4212	. . . . . . . . . . . 12 ⊢ ({𝑥} ⊆ 𝑆 ↔ (𝑆 ∪ {𝑥}) = 𝑆)
40	38, 39	sylib 218	. . . . . . . . . . 11 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → (𝑆 ∪ {𝑥}) = 𝑆)
41	37, 40	eqtrid 2792	. . . . . . . . . 10 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → ((𝑆 ∖ {𝑥}) ∪ {𝑥}) = 𝑆)
42	41	fveq2d 6924	. . . . . . . . 9 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → (𝑁‘((𝑆 ∖ {𝑥}) ∪ {𝑥})) = (𝑁‘𝑆))
43	36, 42	neleqtrrd 2867	. . . . . . . 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 714	. . . 4 ⊢ (((𝜑 ∧ 𝑥 ∈ (𝑆 ∪ {𝑌})) ∧ 𝑥 ∈ 𝑆) → ¬ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥})))
49	26	adantl 481	. . . . . 6 ⊢ (((𝜑 ∧ 𝑥 ∈ (𝑆 ∪ {𝑌})) ∧ 𝑥 ∈ {𝑌}) → 𝑥 = 𝑌)
50	21	ad2antrr 725	. . . . . 6 ⊢ (((𝜑 ∧ 𝑥 ∈ (𝑆 ∪ {𝑌})) ∧ 𝑥 ∈ {𝑌}) → ¬ 𝑌 ∈ (𝑁‘𝑆))
51	49, 50	eqneltrd 2864	. . . . 5 ⊢ (((𝜑 ∧ 𝑥 ∈ (𝑆 ∪ {𝑌})) ∧ 𝑥 ∈ {𝑌}) → ¬ 𝑥 ∈ (𝑁‘𝑆))
52	49	sneqd 4660	. . . . . . . . 9 ⊢ (((𝜑 ∧ 𝑥 ∈ (𝑆 ∪ {𝑌})) ∧ 𝑥 ∈ {𝑌}) → {𝑥} = {𝑌})
53	52	difeq2d 4149	. . . . . . . 8 ⊢ (((𝜑 ∧ 𝑥 ∈ (𝑆 ∪ {𝑌})) ∧ 𝑥 ∈ {𝑌}) → ((𝑆 ∪ {𝑌}) ∖ {𝑥}) = ((𝑆 ∪ {𝑌}) ∖ {𝑌}))
54		difun2 4504	. . . . . . . 8 ⊢ ((𝑆 ∪ {𝑌}) ∖ {𝑌}) = (𝑆 ∖ {𝑌})
55	53, 54	eqtrdi 2796	. . . . . . 7 ⊢ (((𝜑 ∧ 𝑥 ∈ (𝑆 ∪ {𝑌})) ∧ 𝑥 ∈ {𝑌}) → ((𝑆 ∪ {𝑌}) ∖ {𝑥}) = (𝑆 ∖ {𝑌}))
56		difsnb 4831	. . . . . . . . 9 ⊢ (¬ 𝑌 ∈ 𝑆 ↔ (𝑆 ∖ {𝑌}) = 𝑆)
57	22, 56	sylib 218	. . . . . . . 8 ⊢ (𝜑 → (𝑆 ∖ {𝑌}) = 𝑆)
58	57	ad2antrr 725	. . . . . . 7 ⊢ (((𝜑 ∧ 𝑥 ∈ (𝑆 ∪ {𝑌})) ∧ 𝑥 ∈ {𝑌}) → (𝑆 ∖ {𝑌}) = 𝑆)
59	55, 58	eqtrd 2780	. . . . . 6 ⊢ (((𝜑 ∧ 𝑥 ∈ (𝑆 ∪ {𝑌})) ∧ 𝑥 ∈ {𝑌}) → ((𝑆 ∪ {𝑌}) ∖ {𝑥}) = 𝑆)
60	59	fveq2d 6924	. . . . 5 ⊢ (((𝜑 ∧ 𝑥 ∈ (𝑆 ∪ {𝑌})) ∧ 𝑥 ∈ {𝑌}) → (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥})) = (𝑁‘𝑆))
61	51, 60	neleqtrrd 2867	. . . 4 ⊢ (((𝜑 ∧ 𝑥 ∈ (𝑆 ∪ {𝑌})) ∧ 𝑥 ∈ {𝑌}) → ¬ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥})))
62		simpr 484	. . . . 5 ⊢ ((𝜑 ∧ 𝑥 ∈ (𝑆 ∪ {𝑌})) → 𝑥 ∈ (𝑆 ∪ {𝑌}))
63		elun 4176	. . . . 5 ⊢ (𝑥 ∈ (𝑆 ∪ {𝑌}) ↔ (𝑥 ∈ 𝑆 ∨ 𝑥 ∈ {𝑌}))
64	62, 63	sylib 218	. . . 4 ⊢ ((𝜑 ∧ 𝑥 ∈ (𝑆 ∪ {𝑌})) → (𝑥 ∈ 𝑆 ∨ 𝑥 ∈ {𝑌}))
65	48, 61, 64	mpjaodan 959	. . 3 ⊢ ((𝜑 ∧ 𝑥 ∈ (𝑆 ∪ {𝑌})) → ¬ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥})))
66	65	ralrimiva 3152	. 2 ⊢ (𝜑 → ∀𝑥 ∈ (𝑆 ∪ {𝑌}) ¬ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥})))
67	1, 2, 3, 8, 66	ismri2dd 17692	1 ⊢ (𝜑 → (𝑆 ∪ {𝑌}) ∈ 𝐼)

Syntax hints:  ¬ wn 3   → wi 4   ∧ wa 395   ∨ wo 846   ∧ w3a 1087   = wceq 1537   ∈ wcel 2108  ∀wral 3067  Vcvv 3488   ∖ cdif 3973   ∪ cun 3974   ⊆ wss 3976  𝒫 cpw 4622  {csn 4648  ‘cfv 6573  Moorecmre 17640  mrClscmrc 17641  mrIndcmri 17642

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1793  ax-4 1807  ax-5 1909  ax-6 1967  ax-7 2007  ax-8 2110  ax-9 2118  ax-10 2141  ax-11 2158  ax-12 2178  ax-ext 2711  ax-sep 5317  ax-nul 5324  ax-pow 5383  ax-pr 5447  ax-un 7770

This theorem depends on definitions:  df-bi 207  df-an 396  df-or 847  df-3an 1089  df-tru 1540  df-fal 1550  df-ex 1778  df-nf 1782  df-sb 2065  df-mo 2543  df-eu 2572  df-clab 2718  df-cleq 2732  df-clel 2819  df-nfc 2895  df-ne 2947  df-ral 3068  df-rex 3077  df-rab 3444  df-v 3490  df-sbc 3805  df-csb 3922  df-dif 3979  df-un 3981  df-in 3983  df-ss 3993  df-nul 4353  df-if 4549  df-pw 4624  df-sn 4649  df-pr 4651  df-op 4655  df-uni 4932  df-int 4971  df-br 5167  df-opab 5229  df-mpt 5250  df-id 5593  df-xp 5706  df-rel 5707  df-cnv 5708  df-co 5709  df-dm 5710  df-rn 5711  df-res 5712  df-ima 5713  df-iota 6525  df-fun 6575  df-fn 6576  df-f 6577  df-fv 6581  df-mre 17644  df-mrc 17645  df-mri 17646

This theorem is referenced by:  mreexexlem2d  17703