Theorem mreexmrid 17721

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 17714	. . 3 ⊢ (𝜑 → 𝑆 ⊆ 𝑋)
6		mreexmrid.6	. . . 4 ⊢ (𝜑 → 𝑌 ∈ 𝑋)
7	6	snssd 4754	. . 3 ⊢ (𝜑 → {𝑌} ⊆ 𝑋)
8	5, 7	unssd 4145	. 2 ⊢ (𝜑 → (𝑆 ∪ {𝑌}) ⊆ 𝑋)
9	3	3ad2ant1 1151	. . . . . . . . . 10 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → 𝐴 ∈ (Moore‘𝑋))
10	9	elfvexd 6921	. . . . . . . . 9 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → 𝑋 ∈ V)
11		mreexmrid.4	. . . . . . . . . 10 ⊢ (𝜑 → ∀𝑠 ∈ 𝒫 𝑋∀𝑦 ∈ 𝑋 ∀𝑧 ∈ ((𝑁‘(𝑠 ∪ {𝑦})) ∖ (𝑁‘𝑠))𝑦 ∈ (𝑁‘(𝑠 ∪ {𝑧})))
12	11	3ad2ant1 1151	. . . . . . . . 9 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → ∀𝑠 ∈ 𝒫 𝑋∀𝑦 ∈ 𝑋 ∀𝑧 ∈ ((𝑁‘(𝑠 ∪ {𝑦})) ∖ (𝑁‘𝑠))𝑦 ∈ (𝑁‘(𝑠 ∪ {𝑧})))
13	4	3ad2ant1 1151	. . . . . . . . . . 11 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → 𝑆 ∈ 𝐼)
14	2, 9, 13	mrissd 17714	. . . . . . . . . 10 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → 𝑆 ⊆ 𝑋)
15	14	ssdifssd 4101	. . . . . . . . 9 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → (𝑆 ∖ {𝑥}) ⊆ 𝑋)
16	6	3ad2ant1 1151	. . . . . . . . 9 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → 𝑌 ∈ 𝑋)
17		simp3 1156	. . . . . . . . . 10 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥})))
18		difundir 4244	. . . . . . . . . . . 12 ⊢ ((𝑆 ∪ {𝑌}) ∖ {𝑥}) = ((𝑆 ∖ {𝑥}) ∪ ({𝑌} ∖ {𝑥}))
19		simp2 1155	. . . . . . . . . . . . . . . 16 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → 𝑥 ∈ 𝑆)
20	3, 1, 5	mrcssidd 17703	. . . . . . . . . . . . . . . . . 18 ⊢ (𝜑 → 𝑆 ⊆ (𝑁‘𝑆))
21		mreexmrid.7	. . . . . . . . . . . . . . . . . 18 ⊢ (𝜑 → ¬ 𝑌 ∈ (𝑁‘𝑆))
22	20, 21	ssneldd 3941	. . . . . . . . . . . . . . . . 17 ⊢ (𝜑 → ¬ 𝑌 ∈ 𝑆)
23	22	3ad2ant1 1151	. . . . . . . . . . . . . . . 16 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → ¬ 𝑌 ∈ 𝑆)
24		nelneq 2889	. . . . . . . . . . . . . . . 16 ⊢ ((𝑥 ∈ 𝑆 ∧ ¬ 𝑌 ∈ 𝑆) → ¬ 𝑥 = 𝑌)
25	19, 23, 24	syl2anc 596	. . . . . . . . . . . . . . 15 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → ¬ 𝑥 = 𝑌)
26		elsni 4608	. . . . . . . . . . . . . . 15 ⊢ (𝑥 ∈ {𝑌} → 𝑥 = 𝑌)
27	25, 26	nsyl 141	. . . . . . . . . . . . . 14 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → ¬ 𝑥 ∈ {𝑌})
28		difsnb 4776	. . . . . . . . . . . . . 14 ⊢ (¬ 𝑥 ∈ {𝑌} ↔ ({𝑌} ∖ {𝑥}) = {𝑌})
29	27, 28	sylib 221	. . . . . . . . . . . . 13 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → ({𝑌} ∖ {𝑥}) = {𝑌})
30	29	uneq2d 4122	. . . . . . . . . . . 12 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → ((𝑆 ∖ {𝑥}) ∪ ({𝑌} ∖ {𝑥})) = ((𝑆 ∖ {𝑥}) ∪ {𝑌}))
31	18, 30	eqtrid 2812	. . . . . . . . . . 11 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → ((𝑆 ∪ {𝑌}) ∖ {𝑥}) = ((𝑆 ∖ {𝑥}) ∪ {𝑌}))
32	31	fveq2d 6889	. . . . . . . . . 10 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥})) = (𝑁‘((𝑆 ∖ {𝑥}) ∪ {𝑌})))
33	17, 32	eleqtrd 2867	. . . . . . . . 9 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → 𝑥 ∈ (𝑁‘((𝑆 ∖ {𝑥}) ∪ {𝑌})))
34	1, 2, 9, 13, 19	ismri2dad 17715	. . . . . . . . 9 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → ¬ 𝑥 ∈ (𝑁‘(𝑆 ∖ {𝑥})))
35	10, 12, 15, 16, 33, 34	mreexd 17720	. . . . . . . 8 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → 𝑌 ∈ (𝑁‘((𝑆 ∖ {𝑥}) ∪ {𝑥})))
36	21	3ad2ant1 1151	. . . . . . . . 9 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → ¬ 𝑌 ∈ (𝑁‘𝑆))
37		undif1 4437	. . . . . . . . . . 11 ⊢ ((𝑆 ∖ {𝑥}) ∪ {𝑥}) = (𝑆 ∪ {𝑥})
38	19	snssd 4754	. . . . . . . . . . . 12 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → {𝑥} ⊆ 𝑆)
39		ssequn2 4142	. . . . . . . . . . . 12 ⊢ ({𝑥} ⊆ 𝑆 ↔ (𝑆 ∪ {𝑥}) = 𝑆)
40	38, 39	sylib 221	. . . . . . . . . . 11 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → (𝑆 ∪ {𝑥}) = 𝑆)
41	37, 40	eqtrid 2812	. . . . . . . . . 10 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → ((𝑆 ∖ {𝑥}) ∪ {𝑥}) = 𝑆)
42	41	fveq2d 6889	. . . . . . . . 9 ⊢ ((𝜑 ∧ 𝑥 ∈ 𝑆 ∧ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥}))) → (𝑁‘((𝑆 ∖ {𝑥}) ∪ {𝑥})) = (𝑁‘𝑆))
43	36, 42	neleqtrrd 2888	. . . . . . . 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 2885	. . . . 5 ⊢ (((𝜑 ∧ 𝑥 ∈ (𝑆 ∪ {𝑌})) ∧ 𝑥 ∈ {𝑌}) → ¬ 𝑥 ∈ (𝑁‘𝑆))
52	49	sneqd 4603	. . . . . . . . 9 ⊢ (((𝜑 ∧ 𝑥 ∈ (𝑆 ∪ {𝑌})) ∧ 𝑥 ∈ {𝑌}) → {𝑥} = {𝑌})
53	52	difeq2d 4081	. . . . . . . 8 ⊢ (((𝜑 ∧ 𝑥 ∈ (𝑆 ∪ {𝑌})) ∧ 𝑥 ∈ {𝑌}) → ((𝑆 ∪ {𝑌}) ∖ {𝑥}) = ((𝑆 ∪ {𝑌}) ∖ {𝑌}))
54		difun2 4444	. . . . . . . 8 ⊢ ((𝑆 ∪ {𝑌}) ∖ {𝑌}) = (𝑆 ∖ {𝑌})
55	53, 54	eqtrdi 2816	. . . . . . 7 ⊢ (((𝜑 ∧ 𝑥 ∈ (𝑆 ∪ {𝑌})) ∧ 𝑥 ∈ {𝑌}) → ((𝑆 ∪ {𝑌}) ∖ {𝑥}) = (𝑆 ∖ {𝑌}))
56		difsnb 4776	. . . . . . . . 9 ⊢ (¬ 𝑌 ∈ 𝑆 ↔ (𝑆 ∖ {𝑌}) = 𝑆)
57	22, 56	sylib 221	. . . . . . . 8 ⊢ (𝜑 → (𝑆 ∖ {𝑌}) = 𝑆)
58	57	ad2antrr 739	. . . . . . 7 ⊢ (((𝜑 ∧ 𝑥 ∈ (𝑆 ∪ {𝑌})) ∧ 𝑥 ∈ {𝑌}) → (𝑆 ∖ {𝑌}) = 𝑆)
59	55, 58	eqtrd 2800	. . . . . 6 ⊢ (((𝜑 ∧ 𝑥 ∈ (𝑆 ∪ {𝑌})) ∧ 𝑥 ∈ {𝑌}) → ((𝑆 ∪ {𝑌}) ∖ {𝑥}) = 𝑆)
60	59	fveq2d 6889	. . . . 5 ⊢ (((𝜑 ∧ 𝑥 ∈ (𝑆 ∪ {𝑌})) ∧ 𝑥 ∈ {𝑌}) → (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥})) = (𝑁‘𝑆))
61	51, 60	neleqtrrd 2888	. . . 4 ⊢ (((𝜑 ∧ 𝑥 ∈ (𝑆 ∪ {𝑌})) ∧ 𝑥 ∈ {𝑌}) → ¬ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥})))
62		elun 4107	. . . . 5 ⊢ (𝑥 ∈ (𝑆 ∪ {𝑌}) ↔ (𝑥 ∈ 𝑆 ∨ 𝑥 ∈ {𝑌}))
63	62	bilani 510	. . . 4 ⊢ ((𝜑 ∧ 𝑥 ∈ (𝑆 ∪ {𝑌})) → (𝑥 ∈ 𝑆 ∨ 𝑥 ∈ {𝑌}))
64	48, 61, 63	mpjaodan 973	. . 3 ⊢ ((𝜑 ∧ 𝑥 ∈ (𝑆 ∪ {𝑌})) → ¬ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥})))
65	64	ralrimiva 3159	. 2 ⊢ (𝜑 → ∀𝑥 ∈ (𝑆 ∪ {𝑌}) ¬ 𝑥 ∈ (𝑁‘((𝑆 ∪ {𝑌}) ∖ {𝑥})))
66	1, 2, 3, 8, 65	ismri2dd 17712	1 ⊢ (𝜑 → (𝑆 ∪ {𝑌}) ∈ 𝐼)

This proof depends on syntax axioms:  ¬ wn 3   → wi 4   ∧ wa 401   ∨ wo 861   ∧ w3a 1103   = wceq 1570   ∈ wcel 2146  ∀wral 3081  Vcvv 3457   ∖ cdif 3903   ∪ cun 3904   ⊆ wss 3906  𝒫 cpw 4564  {csn 4591  ‘cfv 6540  Moorecmre 17656  mrClscmrc 17657  mrIndcmri 17658

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 1943  ax-6 2000  ax-7 2041  ax-8 2148  ax-9 2156  ax-10 2179  ax-11 2195  ax-12 2216  ax-ext 2737  ax-sep 5259  ax-nul 5271  ax-pow 5338  ax-pr 5406  ax-un 7742

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 2100  df-mo 2569  df-eu 2599  df-clab 2744  df-cleq 2757  df-clel 2840  df-nfc 2914  df-ne 2961  df-ral 3082  df-rex 3092  df-rab 3419  df-v 3459  df-sbc 3747  df-csb 3855  df-dif 3909  df-un 3911  df-in 3913  df-ss 3923  df-nul 4287  df-if 4490  df-pw 4566  df-sn 4592  df-pr 4594  df-op 4598  df-uni 4875  df-int 4915  df-br 5112  df-opab 5176  df-mpt 5195  df-id 5558  df-xp 5669  df-rel 5670  df-cnv 5671  df-co 5672  df-dm 5673  df-rn 5674  df-res 5675  df-ima 5676  df-iota 6496  df-fun 6542  df-fn 6543  df-f 6544  df-fv 6548  df-mre 17660  df-mrc 17661  df-mri 17662

This theorem is used by:  mreexexlem2d  17723