Theorem mreexmrid 17867

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 17860	. . 3 ⊢ (𝜑 → 𝑆 ⊆ 𝑋)
6		mreexmrid.6	. . . 4 ⊢ (𝜑 → 𝑌 ∈ 𝑋)
7	6	snssd 4749	. . 3 ⊢ (𝜑 → {𝑌} ⊆ 𝑋)
8	5, 7	unssd 4193	. 2 ⊢ (𝜑 → (𝑆 ∪ {𝑌}) ⊆ 𝑋)
9	3	3ad2ant1 1151	. . . . . . . . . 10 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → 𝐴 ∈ (Moore‘𝑋))
10	9	elfvexd 6952	. . . . . . . . 9 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → 𝑋 ∈ V)
11		mreexmrid.4	. . . . . . . . . 10 ⊢ (𝜑 → ∀𝑠 ∈ 𝒫 𝑋∀𝑦 ∈ 𝑋 ∀𝑧 ∈ ((𝑁‘(𝑠 ∪ {𝑦})) ∖ (𝑁‘𝑠))𝑦 ∈ (𝑁‘(𝑠 ∪ {𝑧})))
12	11	3ad2ant1 1151	. . . . . . . . 9 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → ∀𝑠 ∈ 𝒫 𝑋∀𝑦 ∈ 𝑋 ∀𝑧 ∈ ((𝑁‘(𝑠 ∪ {𝑦})) ∖ (𝑁‘𝑠))𝑦 ∈ (𝑁‘(𝑠 ∪ {𝑧})))
13	4	3ad2ant1 1151	. . . . . . . . . . 11 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → 𝑆 ∈ 𝐼)
14	2, 9, 13	mrissd 17860	. . . . . . . . . 10 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → 𝑆 ⊆ 𝑋)
15	14	ssdifssd 4086	. . . . . . . . 9 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → (𝑆 ∖ {𝑥}) ⊆ 𝑋)
16	6	3ad2ant1 1151	. . . . . . . . 9 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → 𝑌 ∈ 𝑋)
17		simp3 1156	. . . . . . . . . 10 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥})))
18		difundir 4239	. . . . . . . . . . . 12 ⊢ ((𝑆 ∪ {𝑌}) ∖ {𝑥}) = ((𝑆 ∖ {𝑥}) ∪ ({𝑌} ∖ {𝑥}))
19		simp2 1155	. . . . . . . . . . . . . . . 16 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → 𝑥 ∈ 𝑆)
20	3, 1, 5	mrcssidd 17849	. . . . . . . . . . . . . . . . . 18 ⊢ (𝜑 → 𝑆 ⊆ (𝑁‘𝑆))
21		mreexmrid.7	. . . . . . . . . . . . . . . . . 18 ⊢ (𝜑 → ¬ 𝑌 ∈ (𝑁‘𝑆))
22	20, 21	ssneldd 3916	. . . . . . . . . . . . . . . . 17 ⊢ (𝜑 → ¬ 𝑌 ∈ 𝑆)
23	22	3ad2ant1 1151	. . . . . . . . . . . . . . . 16 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → ¬ 𝑌 ∈ 𝑆)
24		nelneq 2888	. . . . . . . . . . . . . . . 16 ⊢ ((𝑥 ∈ 𝑆 ∧ ¬ 𝑌 ∈ 𝑆) → ¬ 𝑥 = 𝑌)
25	19, 23, 24	syl2anc 596	. . . . . . . . . . . . . . 15 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → ¬ 𝑥 = 𝑌)
26		elsni 4601	. . . . . . . . . . . . . . 15 ⊢ (𝑥 ∈ {𝑌} → 𝑥 = 𝑌)
27	25, 26	nsyl 141	. . . . . . . . . . . . . 14 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → ¬ 𝑥 ∈ {𝑌})
28		difsnb 4771	. . . . . . . . . . . . . 14 ⊢ (¬ 𝑥 ∈ {𝑌} ↔ ({𝑌} ∖ {𝑥}) = {𝑌})
29	27, 28	sylib 221	. . . . . . . . . . . . 13 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → ({𝑌} ∖ {𝑥}) = {𝑌})
30	29	uneq2d 4170	. . . . . . . . . . . 12 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → ((𝑆 ∖ {𝑥}) ∪ ({𝑌} ∖ {𝑥})) = ((𝑆 ∖ {𝑥}) ∪ {𝑌}))
31	18, 30	eqtrid 2810	. . . . . . . . . . 11 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → ((𝑆 ∪ {𝑌}) ∖ {𝑥}) = ((𝑆 ∖ {𝑥}) ∪ {𝑌}))
32	31	fveq2d 6920	. . . . . . . . . 10 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥})) = (𝑁‘((𝑆 ∖ {𝑥}) ∪ {𝑌})))
33	17, 32	eleqtrd 2866	. . . . . . . . 9 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → 𝑥 ∈ (𝑁‘((𝑆 ∖ {𝑥}) ∪ {𝑌})))
34	1, 2, 9, 13, 19	ismri2dad 17861	. . . . . . . . 9 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → ¬ 𝑥 ∈ (𝑁‘(𝑆 ∖ {𝑥})))
35	10, 12, 15, 16, 33, 34	mreexd 17866	. . . . . . . 8 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → 𝑌 ∈ (𝑁‘((𝑆 ∖ {𝑥}) ∪ {𝑥})))
36	21	3ad2ant1 1151	. . . . . . . . 9 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → ¬ 𝑌 ∈ (𝑁‘𝑆))
37		undif1 4433	. . . . . . . . . . 11 ⊢ ((𝑆 ∖ {𝑥}) ∪ {𝑥}) = (𝑆 ∪ {𝑥})
38	19	snssd 4749	. . . . . . . . . . . 12 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → {𝑥} ⊆ 𝑆)
39		ssequn2 4190	. . . . . . . . . . . 12 ⊢ ({𝑥} ⊆ 𝑆 ↔ (𝑆 ∪ {𝑥}) = 𝑆)
40	38, 39	sylib 221	. . . . . . . . . . 11 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → (𝑆 ∪ {𝑥}) = 𝑆)
41	37, 40	eqtrid 2810	. . . . . . . . . 10 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → ((𝑆 ∖ {𝑥}) ∪ {𝑥}) = 𝑆)
42	41	fveq2d 6920	. . . . . . . . 9 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → (𝑁‘((𝑆 ∖ {𝑥}) ∪ {𝑥})) = (𝑁‘𝑆))
43	36, 42	neleqtrrd 2887	. . . . . . . 8 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → ¬ 𝑌 ∈ (𝑁‘((𝑆 ∖ {𝑥}) ∪ {𝑥})))
44	35, 43	pm2.65i 196	. . . . . . 7 ⊢ ¬ (𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥})))
45		df-3an 1105	. . . . . . 7 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) ↔ ((𝜑 ∧ 𝑥 ∈ 𝑆) ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))))
46	44, 45	mtbi 325	. . . . . 6 ⊢ ¬ ((𝜑 ∧ 𝑥 ∈ 𝑆) ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥})))
47	46	imnani 406	. . . . 5 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆) → ¬ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥})))
48	47	adantlr 728	. . . 4 ⊢ (((𝜑 ∧ 𝑥 ∈ (𝑆 ∪ {𝑌})) ∧ 𝑥 ∈ 𝑆) → ¬ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥})))
49	26	adantl 487	. . . . . 6 ⊢ (((𝜑 ∧ 𝑥 ∈ (𝑆 ∪ {𝑌})) ∧ 𝑥 ∈ {𝑌}) → 𝑥 = 𝑌)
50	21	ad2antrr 739	. . . . . 6 ⊢ (((𝜑 ∧ 𝑥 ∈ (𝑆 ∪ {𝑌})) ∧ 𝑥 ∈ {𝑌}) → ¬ 𝑌 ∈ (𝑁‘𝑆))
51	49, 50	eqneltrd 2884	. . . . 5 ⊢ (((𝜑 ∧ 𝑥 ∈ (𝑆 ∪ {𝑌})) ∧ 𝑥 ∈ {𝑌}) → ¬ 𝑥 ∈ (𝑁‘𝑆))
52	49	sneqd 4596	. . . . . . . . 9 ⊢ (((𝜑 ∧ 𝑥 ∈ (𝑆 ∪ {𝑌})) ∧ 𝑥 ∈ {𝑌}) → {𝑥} = {𝑌})
53	52	difeq2d 4066	. . . . . . . 8 ⊢ (((𝜑 ∧ 𝑥 ∈ (𝑆 ∪ {𝑌})) ∧ 𝑥 ∈ {𝑌}) → ((𝑆 ∪ {𝑌}) ∖ {𝑥}) = ((𝑆 ∪ {𝑌}) ∖ {𝑌}))
54		difun2 4440	. . . . . . . 8 ⊢ ((𝑆 ∪ {𝑌}) ∖ {𝑌}) = (𝑆 ∖ {𝑌})
55	53, 54	eqtrdi 2814	. . . . . . 7 ⊢ (((𝜑 ∧ 𝑥 ∈ (𝑆 ∪ {𝑌})) ∧ 𝑥 ∈ {𝑌}) → ((𝑆 ∪ {𝑌}) ∖ {𝑥}) = (𝑆 ∖ {𝑌}))
56		difsnb 4771	. . . . . . . . 9 ⊢ (¬ 𝑌 ∈ 𝑆 ↔ (𝑆 ∖ {𝑌}) = 𝑆)
57	22, 56	sylib 221	. . . . . . . 8 ⊢ (𝜑 → (𝑆 ∖ {𝑌}) = 𝑆)
58	57	ad2antrr 739	. . . . . . 7 ⊢ (((𝜑 ∧ 𝑥 ∈ (𝑆 ∪ {𝑌})) ∧ 𝑥 ∈ {𝑌}) → (𝑆 ∖ {𝑌}) = 𝑆)
59	55, 58	eqtrd 2798	. . . . . 6 ⊢ (((𝜑 ∧ 𝑥 ∈ (𝑆 ∪ {𝑌})) ∧ 𝑥 ∈ {𝑌}) → ((𝑆 ∪ {𝑌}) ∖ {𝑥}) = 𝑆)
60	59	fveq2d 6920	. . . . 5 ⊢ (((𝜑 ∧ 𝑥 ∈ (𝑆 ∪ {𝑌})) ∧ 𝑥 ∈ {𝑌}) → (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥})) = (𝑁‘𝑆))
61	51, 60	neleqtrrd 2887	. . . 4 ⊢ (((𝜑 ∧ 𝑥 ∈ (𝑆 ∪ {𝑌})) ∧ 𝑥 ∈ {𝑌}) → ¬ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥})))
62		elun 4155	. . . . 5 ⊢ (𝑥 ∈ (𝑆 ∪ {𝑌}) ↔ (𝑥 ∈ 𝑆 ∨ 𝑥 ∈ {𝑌}))
63	62	bilani 510	. . . 4 ⊢ ((𝜑 ∧ 𝑥 ∈ (𝑆 ∪ {𝑌})) → (𝑥 ∈ 𝑆 ∨ 𝑥 ∈ {𝑌}))
64	48, 61, 63	mpjaodan 973	. . 3 ⊢ ((𝜑 ∧ 𝑥 ∈ (𝑆 ∪ {𝑌})) → ¬ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥})))
65	64	ralrimiva 3158	. 2 ⊢ (𝜑 → ∀𝑥 ∈ (𝑆 ∪ {𝑌}) ¬ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥})))
66	1, 2, 3, 8, 65	ismri2dd 17858	1 ⊢ (𝜑 → (𝑆 ∪ {𝑌}) ∈ 𝐼)

This proof depends on syntax axioms:  ¬ wn 3   → wi 4   ∧ wa 401   ∨ wo 861   ∧ w3a 1103   = wceq 1570   ∈ wcel 2147  ∀wral 3080  Vcvv 3454   ⊆ wss 3900   ∖ cdif 4048   ∪ cun 4152  𝒫 cpw 4560  {csn 4588  ‘cfv 6566  Moorecmre 17802  mrClscmrc 17803  mrIndcmri 17804

This proof depends on axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1828  ax-4 1842  ax-5 1945  ax-6 2002  ax-7 2043  ax-8 2149  ax-9 2157  ax-10 2180  ax-11 2197  ax-12 2216  ax-ext 2735  ax-sep 5255  ax-nul 5266  ax-pow 5334  ax-pr 5398  ax-un 7783

This proof depends on definitions:  df-bi 210  df-an 402  df-or 862  df-3an 1105  df-tru 1573  df-fal 1583  df-ex 1813  df-nf 1817  df-sb 2102  df-mo 2567  df-eu 2597  df-clab 2742  df-cleq 2755  df-clel 2839  df-nfc 2913  df-ne 2960  df-ral 3081  df-rex 3091  df-rab 3417  df-v 3456  df-sbc 3743  df-csb 3852  df-ss 3901  df-dif 4050  df-in 4094  df-un 4154  df-nul 4282  df-if 4486  df-pw 4562  df-sn 4589  df-pr 4591  df-op 4841  df-uni 4873  df-int 4913  df-br 5109  df-opab 5174  df-mpt 5193  df-id 5553  df-xp 5664  df-rel 5665  df-cnv 5666  df-co 5667  df-dm 5668  df-rn 5669  df-res 5670  df-ima 5671  df-iota 6520  df-fun 6568  df-fn 6569  df-f 6570  df-fv 6574  df-mre 17806  df-mrc 17807  df-mri 17808

This theorem is used by:  mreexexlem2d  17869