Theorem frrlem1 33125

Description: Lemma for founded recursion. The final item we are interested in is the union of acceptable functions 𝐵. This lemma just changes bound variables for later use. (Contributed by Paul Chapman, 21-Apr-2012.)

Hypothesis

Ref	Expression
frrlem1.1	⊢ 𝐵 = {𝑓 ∣ ∃𝑥(𝑓 Fn 𝑥 ∧ (𝑥 ⊆ 𝐴 ∧ ∀𝑦 ∈ 𝑥 Pred(𝑅, 𝐴, 𝑦) ⊆ 𝑥) ∧ ∀𝑦 ∈ 𝑥 (𝑓‘𝑦) = (𝑦𝐺(𝑓 ↾ Pred(𝑅, 𝐴, 𝑦))))}

Assertion

Ref	Expression
frrlem1	⊢ 𝐵 = {𝑔 ∣ ∃𝑧(𝑔 Fn 𝑧 ∧ (𝑧 ⊆ 𝐴 ∧ ∀𝑤 ∈ 𝑧 Pred(𝑅, 𝐴, 𝑤) ⊆ 𝑧) ∧ ∀𝑤 ∈ 𝑧 (𝑔‘𝑤) = (𝑤𝐺(𝑔 ↾ Pred(𝑅, 𝐴, 𝑤))))}

Distinct variable groups:   𝐴,𝑓,𝑔,𝑤,𝑥,𝑦,𝑧   𝑓,𝐺,𝑔,𝑤,𝑥,𝑦,𝑧   𝑅,𝑓,𝑔,𝑤,𝑥,𝑦,𝑧

Allowed substitution hints:   𝐵(𝑥,𝑦,𝑧,𝑤,𝑓,𝑔)

Proof of Theorem frrlem1

Step	Hyp	Ref	Expression
1		frrlem1.1	. 2 ⊢ 𝐵 = {𝑓 ∣ ∃𝑥(𝑓 Fn 𝑥 ∧ (𝑥 ⊆ 𝐴 ∧ ∀𝑦 ∈ 𝑥 Pred(𝑅, 𝐴, 𝑦) ⊆ 𝑥) ∧ ∀𝑦 ∈ 𝑥 (𝑓‘𝑦) = (𝑦𝐺(𝑓 ↾ Pred(𝑅, 𝐴, 𝑦))))}
2		fneq1 6446	. . . . . 6 ⊢ (𝑓 = 𝑔 → (𝑓 Fn 𝑥 ↔ 𝑔 Fn 𝑥))
3		fveq1 6671	. . . . . . . 8 ⊢ (𝑓 = 𝑔 → (𝑓‘𝑦) = (𝑔‘𝑦))
4		reseq1 5849	. . . . . . . . 9 ⊢ (𝑓 = 𝑔 → (𝑓 ↾ Pred(𝑅, 𝐴, 𝑦)) = (𝑔 ↾ Pred(𝑅, 𝐴, 𝑦)))
5	4	oveq2d 7174	. . . . . . . 8 ⊢ (𝑓 = 𝑔 → (𝑦𝐺(𝑓 ↾ Pred(𝑅, 𝐴, 𝑦))) = (𝑦𝐺(𝑔 ↾ Pred(𝑅, 𝐴, 𝑦))))
6	3, 5	eqeq12d 2839	. . . . . . 7 ⊢ (𝑓 = 𝑔 → ((𝑓‘𝑦) = (𝑦𝐺(𝑓 ↾ Pred(𝑅, 𝐴, 𝑦))) ↔ (𝑔‘𝑦) = (𝑦𝐺(𝑔 ↾ Pred(𝑅, 𝐴, 𝑦)))))
7	6	ralbidv 3199	. . . . . 6 ⊢ (𝑓 = 𝑔 → (∀𝑦 ∈ 𝑥 (𝑓‘𝑦) = (𝑦𝐺(𝑓 ↾ Pred(𝑅, 𝐴, 𝑦))) ↔ ∀𝑦 ∈ 𝑥 (𝑔‘𝑦) = (𝑦𝐺(𝑔 ↾ Pred(𝑅, 𝐴, 𝑦)))))
8	2, 7	3anbi13d 1434	. . . . 5 ⊢ (𝑓 = 𝑔 → ((𝑓 Fn 𝑥 ∧ (𝑥 ⊆ 𝐴 ∧ ∀𝑦 ∈ 𝑥 Pred(𝑅, 𝐴, 𝑦) ⊆ 𝑥) ∧ ∀𝑦 ∈ 𝑥 (𝑓‘𝑦) = (𝑦𝐺(𝑓 ↾ Pred(𝑅, 𝐴, 𝑦)))) ↔ (𝑔 Fn 𝑥 ∧ (𝑥 ⊆ 𝐴 ∧ ∀𝑦 ∈ 𝑥 Pred(𝑅, 𝐴, 𝑦) ⊆ 𝑥) ∧ ∀𝑦 ∈ 𝑥 (𝑔‘𝑦) = (𝑦𝐺(𝑔 ↾ Pred(𝑅, 𝐴, 𝑦))))))
9	8	exbidv 1922	. . . 4 ⊢ (𝑓 = 𝑔 → (∃𝑥(𝑓 Fn 𝑥 ∧ (𝑥 ⊆ 𝐴 ∧ ∀𝑦 ∈ 𝑥 Pred(𝑅, 𝐴, 𝑦) ⊆ 𝑥) ∧ ∀𝑦 ∈ 𝑥 (𝑓‘𝑦) = (𝑦𝐺(𝑓 ↾ Pred(𝑅, 𝐴, 𝑦)))) ↔ ∃𝑥(𝑔 Fn 𝑥 ∧ (𝑥 ⊆ 𝐴 ∧ ∀𝑦 ∈ 𝑥 Pred(𝑅, 𝐴, 𝑦) ⊆ 𝑥) ∧ ∀𝑦 ∈ 𝑥 (𝑔‘𝑦) = (𝑦𝐺(𝑔 ↾ Pred(𝑅, 𝐴, 𝑦))))))
10		fneq2 6447	. . . . . 6 ⊢ (𝑥 = 𝑧 → (𝑔 Fn 𝑥 ↔ 𝑔 Fn 𝑧))
11		sseq1 3994	. . . . . . 7 ⊢ (𝑥 = 𝑧 → (𝑥 ⊆ 𝐴 ↔ 𝑧 ⊆ 𝐴))
12		sseq2 3995	. . . . . . . . 9 ⊢ (𝑥 = 𝑧 → (Pred(𝑅, 𝐴, 𝑦) ⊆ 𝑥 ↔ Pred(𝑅, 𝐴, 𝑦) ⊆ 𝑧))
13	12	raleqbi1dv 3405	. . . . . . . 8 ⊢ (𝑥 = 𝑧 → (∀𝑦 ∈ 𝑥 Pred(𝑅, 𝐴, 𝑦) ⊆ 𝑥 ↔ ∀𝑦 ∈ 𝑧 Pred(𝑅, 𝐴, 𝑦) ⊆ 𝑧))
14		predeq3 6154	. . . . . . . . . 10 ⊢ (𝑦 = 𝑤 → Pred(𝑅, 𝐴, 𝑦) = Pred(𝑅, 𝐴, 𝑤))
15	14	sseq1d 4000	. . . . . . . . 9 ⊢ (𝑦 = 𝑤 → (Pred(𝑅, 𝐴, 𝑦) ⊆ 𝑧 ↔ Pred(𝑅, 𝐴, 𝑤) ⊆ 𝑧))
16	15	cbvralvw 3451	. . . . . . . 8 ⊢ (∀𝑦 ∈ 𝑧 Pred(𝑅, 𝐴, 𝑦) ⊆ 𝑧 ↔ ∀𝑤 ∈ 𝑧 Pred(𝑅, 𝐴, 𝑤) ⊆ 𝑧)
17	13, 16	syl6bb 289	. . . . . . 7 ⊢ (𝑥 = 𝑧 → (∀𝑦 ∈ 𝑥 Pred(𝑅, 𝐴, 𝑦) ⊆ 𝑥 ↔ ∀𝑤 ∈ 𝑧 Pred(𝑅, 𝐴, 𝑤) ⊆ 𝑧))
18	11, 17	anbi12d 632	. . . . . 6 ⊢ (𝑥 = 𝑧 → ((𝑥 ⊆ 𝐴 ∧ ∀𝑦 ∈ 𝑥 Pred(𝑅, 𝐴, 𝑦) ⊆ 𝑥) ↔ (𝑧 ⊆ 𝐴 ∧ ∀𝑤 ∈ 𝑧 Pred(𝑅, 𝐴, 𝑤) ⊆ 𝑧)))
19		raleq 3407	. . . . . . 7 ⊢ (𝑥 = 𝑧 → (∀𝑦 ∈ 𝑥 (𝑔‘𝑦) = (𝑦𝐺(𝑔 ↾ Pred(𝑅, 𝐴, 𝑦))) ↔ ∀𝑦 ∈ 𝑧 (𝑔‘𝑦) = (𝑦𝐺(𝑔 ↾ Pred(𝑅, 𝐴, 𝑦)))))
20		fveq2 6672	. . . . . . . . 9 ⊢ (𝑦 = 𝑤 → (𝑔‘𝑦) = (𝑔‘𝑤))
21		id 22	. . . . . . . . . 10 ⊢ (𝑦 = 𝑤 → 𝑦 = 𝑤)
22	14	reseq2d 5855	. . . . . . . . . 10 ⊢ (𝑦 = 𝑤 → (𝑔 ↾ Pred(𝑅, 𝐴, 𝑦)) = (𝑔 ↾ Pred(𝑅, 𝐴, 𝑤)))
23	21, 22	oveq12d 7176	. . . . . . . . 9 ⊢ (𝑦 = 𝑤 → (𝑦𝐺(𝑔 ↾ Pred(𝑅, 𝐴, 𝑦))) = (𝑤𝐺(𝑔 ↾ Pred(𝑅, 𝐴, 𝑤))))
24	20, 23	eqeq12d 2839	. . . . . . . 8 ⊢ (𝑦 = 𝑤 → ((𝑔‘𝑦) = (𝑦𝐺(𝑔 ↾ Pred(𝑅, 𝐴, 𝑦))) ↔ (𝑔‘𝑤) = (𝑤𝐺(𝑔 ↾ Pred(𝑅, 𝐴, 𝑤)))))
25	24	cbvralvw 3451	. . . . . . 7 ⊢ (∀𝑦 ∈ 𝑧 (𝑔‘𝑦) = (𝑦𝐺(𝑔 ↾ Pred(𝑅, 𝐴, 𝑦))) ↔ ∀𝑤 ∈ 𝑧 (𝑔‘𝑤) = (𝑤𝐺(𝑔 ↾ Pred(𝑅, 𝐴, 𝑤))))
26	19, 25	syl6bb 289	. . . . . 6 ⊢ (𝑥 = 𝑧 → (∀𝑦 ∈ 𝑥 (𝑔‘𝑦) = (𝑦𝐺(𝑔 ↾ Pred(𝑅, 𝐴, 𝑦))) ↔ ∀𝑤 ∈ 𝑧 (𝑔‘𝑤) = (𝑤𝐺(𝑔 ↾ Pred(𝑅, 𝐴, 𝑤)))))
27	10, 18, 26	3anbi123d 1432	. . . . 5 ⊢ (𝑥 = 𝑧 → ((𝑔 Fn 𝑥 ∧ (𝑥 ⊆ 𝐴 ∧ ∀𝑦 ∈ 𝑥 Pred(𝑅, 𝐴, 𝑦) ⊆ 𝑥) ∧ ∀𝑦 ∈ 𝑥 (𝑔‘𝑦) = (𝑦𝐺(𝑔 ↾ Pred(𝑅, 𝐴, 𝑦)))) ↔ (𝑔 Fn 𝑧 ∧ (𝑧 ⊆ 𝐴 ∧ ∀𝑤 ∈ 𝑧 Pred(𝑅, 𝐴, 𝑤) ⊆ 𝑧) ∧ ∀𝑤 ∈ 𝑧 (𝑔‘𝑤) = (𝑤𝐺(𝑔 ↾ Pred(𝑅, 𝐴, 𝑤))))))
28	27	cbvexvw 2044	. . . 4 ⊢ (∃𝑥(𝑔 Fn 𝑥 ∧ (𝑥 ⊆ 𝐴 ∧ ∀𝑦 ∈ 𝑥 Pred(𝑅, 𝐴, 𝑦) ⊆ 𝑥) ∧ ∀𝑦 ∈ 𝑥 (𝑔‘𝑦) = (𝑦𝐺(𝑔 ↾ Pred(𝑅, 𝐴, 𝑦)))) ↔ ∃𝑧(𝑔 Fn 𝑧 ∧ (𝑧 ⊆ 𝐴 ∧ ∀𝑤 ∈ 𝑧 Pred(𝑅, 𝐴, 𝑤) ⊆ 𝑧) ∧ ∀𝑤 ∈ 𝑧 (𝑔‘𝑤) = (𝑤𝐺(𝑔 ↾ Pred(𝑅, 𝐴, 𝑤)))))
29	9, 28	syl6bb 289	. . 3 ⊢ (𝑓 = 𝑔 → (∃𝑥(𝑓 Fn 𝑥 ∧ (𝑥 ⊆ 𝐴 ∧ ∀𝑦 ∈ 𝑥 Pred(𝑅, 𝐴, 𝑦) ⊆ 𝑥) ∧ ∀𝑦 ∈ 𝑥 (𝑓‘𝑦) = (𝑦𝐺(𝑓 ↾ Pred(𝑅, 𝐴, 𝑦)))) ↔ ∃𝑧(𝑔 Fn 𝑧 ∧ (𝑧 ⊆ 𝐴 ∧ ∀𝑤 ∈ 𝑧 Pred(𝑅, 𝐴, 𝑤) ⊆ 𝑧) ∧ ∀𝑤 ∈ 𝑧 (𝑔‘𝑤) = (𝑤𝐺(𝑔 ↾ Pred(𝑅, 𝐴, 𝑤))))))
30	29	cbvabv 2891	. 2 ⊢ {𝑓 ∣ ∃𝑥(𝑓 Fn 𝑥 ∧ (𝑥 ⊆ 𝐴 ∧ ∀𝑦 ∈ 𝑥 Pred(𝑅, 𝐴, 𝑦) ⊆ 𝑥) ∧ ∀𝑦 ∈ 𝑥 (𝑓‘𝑦) = (𝑦𝐺(𝑓 ↾ Pred(𝑅, 𝐴, 𝑦))))} = {𝑔 ∣ ∃𝑧(𝑔 Fn 𝑧 ∧ (𝑧 ⊆ 𝐴 ∧ ∀𝑤 ∈ 𝑧 Pred(𝑅, 𝐴, 𝑤) ⊆ 𝑧) ∧ ∀𝑤 ∈ 𝑧 (𝑔‘𝑤) = (𝑤𝐺(𝑔 ↾ Pred(𝑅, 𝐴, 𝑤))))}
31	1, 30	eqtri 2846	1 ⊢ 𝐵 = {𝑔 ∣ ∃𝑧(𝑔 Fn 𝑧 ∧ (𝑧 ⊆ 𝐴 ∧ ∀𝑤 ∈ 𝑧 Pred(𝑅, 𝐴, 𝑤) ⊆ 𝑧) ∧ ∀𝑤 ∈ 𝑧 (𝑔‘𝑤) = (𝑤𝐺(𝑔 ↾ Pred(𝑅, 𝐴, 𝑤))))}

Syntax hints:   ∧ wa 398   ∧ w3a 1083   = wceq 1537  ∃wex 1780  {cab 2801  ∀wral 3140   ⊆ wss 3938   ↾ cres 5559  Predcpred 6149   Fn wfn 6352  ‘cfv 6357  (class class class)co 7158

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1796  ax-4 1810  ax-5 1911  ax-6 1970  ax-7 2015  ax-8 2116  ax-9 2124  ax-10 2145  ax-11 2161  ax-12 2177  ax-ext 2795

This theorem depends on definitions:  df-bi 209  df-an 399  df-or 844  df-3an 1085  df-tru 1540  df-ex 1781  df-nf 1785  df-sb 2070  df-clab 2802  df-cleq 2816  df-clel 2895  df-nfc 2965  df-ral 3145  df-rab 3149  df-v 3498  df-dif 3941  df-un 3943  df-in 3945  df-ss 3954  df-nul 4294  df-if 4470  df-sn 4570  df-pr 4572  df-op 4576  df-uni 4841  df-br 5069  df-opab 5131  df-xp 5563  df-rel 5564  df-cnv 5565  df-co 5566  df-dm 5567  df-rn 5568  df-res 5569  df-ima 5570  df-pred 6150  df-iota 6316  df-fun 6359  df-fn 6360  df-fv 6365  df-ov 7161

This theorem is referenced by:  frrlem2  33126  frrlem3  33127  frrlem4  33128  frrlem8  33132  frrlem12  33136  frrlem13  33137  fpr1  33141  fpr2  33142  frr1  33146  frr2  33147