Theorem bnj1522

Description: Well-founded recursion, part 3 of 3. The proof has been taken from Chapter 4 of Don Monk's notes on Set Theory. See http://euclid.colorado.edu/~monkd/setth.pdf . (Contributed by Jonathan Ben-Naim, 3-Jun-2011) (New usage is discouraged.)

	Ref	Expression
Hypotheses	bnj1522.1	⊢ 𝐵 = { 𝑑 ∣ ( 𝑑 ⊆ 𝐴 ∧ ∀ 𝑥 ∈ 𝑑 pred ( 𝑥 , 𝐴 , 𝑅 ) ⊆ 𝑑 ) }
	bnj1522.2	⊢ 𝑌 = ⟨ 𝑥 , ( 𝑓 ↾ pred ( 𝑥 , 𝐴 , 𝑅 ) ) ⟩
	bnj1522.3	⊢ 𝐶 = { 𝑓 ∣ ∃ 𝑑 ∈ 𝐵 ( 𝑓 Fn 𝑑 ∧ ∀ 𝑥 ∈ 𝑑 ( 𝑓 ‘ 𝑥 ) = ( 𝐺 ‘ 𝑌 ) ) }
	bnj1522.4	⊢ 𝐹 = ∪ 𝐶
Assertion	bnj1522	⊢ ( ( 𝑅 FrSe 𝐴 ∧ 𝐻 Fn 𝐴 ∧ ∀ 𝑥 ∈ 𝐴 ( 𝐻 ‘ 𝑥 ) = ( 𝐺 ‘ ⟨ 𝑥 , ( 𝐻 ↾ pred ( 𝑥 , 𝐴 , 𝑅 ) ) ⟩ ) ) → 𝐹 = 𝐻 )

Proof

Step	Hyp	Ref	Expression
1		bnj1522.1	⊢ 𝐵 = { 𝑑 ∣ ( 𝑑 ⊆ 𝐴 ∧ ∀ 𝑥 ∈ 𝑑 pred ( 𝑥 , 𝐴 , 𝑅 ) ⊆ 𝑑 ) }
2		bnj1522.2	⊢ 𝑌 = ⟨ 𝑥 , ( 𝑓 ↾ pred ( 𝑥 , 𝐴 , 𝑅 ) ) ⟩
3		bnj1522.3	⊢ 𝐶 = { 𝑓 ∣ ∃ 𝑑 ∈ 𝐵 ( 𝑓 Fn 𝑑 ∧ ∀ 𝑥 ∈ 𝑑 ( 𝑓 ‘ 𝑥 ) = ( 𝐺 ‘ 𝑌 ) ) }
4		bnj1522.4	⊢ 𝐹 = ∪ 𝐶
5		biid	⊢ ( ( 𝑅 FrSe 𝐴 ∧ 𝐻 Fn 𝐴 ∧ ∀ 𝑥 ∈ 𝐴 ( 𝐻 ‘ 𝑥 ) = ( 𝐺 ‘ ⟨ 𝑥 , ( 𝐻 ↾ pred ( 𝑥 , 𝐴 , 𝑅 ) ) ⟩ ) ) ↔ ( 𝑅 FrSe 𝐴 ∧ 𝐻 Fn 𝐴 ∧ ∀ 𝑥 ∈ 𝐴 ( 𝐻 ‘ 𝑥 ) = ( 𝐺 ‘ ⟨ 𝑥 , ( 𝐻 ↾ pred ( 𝑥 , 𝐴 , 𝑅 ) ) ⟩ ) ) )
6		biid	⊢ ( ( ( 𝑅 FrSe 𝐴 ∧ 𝐻 Fn 𝐴 ∧ ∀ 𝑥 ∈ 𝐴 ( 𝐻 ‘ 𝑥 ) = ( 𝐺 ‘ ⟨ 𝑥 , ( 𝐻 ↾ pred ( 𝑥 , 𝐴 , 𝑅 ) ) ⟩ ) ) ∧ 𝐹 ≠ 𝐻 ) ↔ ( ( 𝑅 FrSe 𝐴 ∧ 𝐻 Fn 𝐴 ∧ ∀ 𝑥 ∈ 𝐴 ( 𝐻 ‘ 𝑥 ) = ( 𝐺 ‘ ⟨ 𝑥 , ( 𝐻 ↾ pred ( 𝑥 , 𝐴 , 𝑅 ) ) ⟩ ) ) ∧ 𝐹 ≠ 𝐻 ) )
7		biid	⊢ ( ( ( ( 𝑅 FrSe 𝐴 ∧ 𝐻 Fn 𝐴 ∧ ∀ 𝑥 ∈ 𝐴 ( 𝐻 ‘ 𝑥 ) = ( 𝐺 ‘ ⟨ 𝑥 , ( 𝐻 ↾ pred ( 𝑥 , 𝐴 , 𝑅 ) ) ⟩ ) ) ∧ 𝐹 ≠ 𝐻 ) ∧ 𝑥 ∈ 𝐴 ∧ ( 𝐹 ‘ 𝑥 ) ≠ ( 𝐻 ‘ 𝑥 ) ) ↔ ( ( ( 𝑅 FrSe 𝐴 ∧ 𝐻 Fn 𝐴 ∧ ∀ 𝑥 ∈ 𝐴 ( 𝐻 ‘ 𝑥 ) = ( 𝐺 ‘ ⟨ 𝑥 , ( 𝐻 ↾ pred ( 𝑥 , 𝐴 , 𝑅 ) ) ⟩ ) ) ∧ 𝐹 ≠ 𝐻 ) ∧ 𝑥 ∈ 𝐴 ∧ ( 𝐹 ‘ 𝑥 ) ≠ ( 𝐻 ‘ 𝑥 ) ) )
8		eqid	⊢ { 𝑥 ∈ 𝐴 ∣ ( 𝐹 ‘ 𝑥 ) ≠ ( 𝐻 ‘ 𝑥 ) } = { 𝑥 ∈ 𝐴 ∣ ( 𝐹 ‘ 𝑥 ) ≠ ( 𝐻 ‘ 𝑥 ) }
9		biid	⊢ ( ( ( ( ( 𝑅 FrSe 𝐴 ∧ 𝐻 Fn 𝐴 ∧ ∀ 𝑥 ∈ 𝐴 ( 𝐻 ‘ 𝑥 ) = ( 𝐺 ‘ ⟨ 𝑥 , ( 𝐻 ↾ pred ( 𝑥 , 𝐴 , 𝑅 ) ) ⟩ ) ) ∧ 𝐹 ≠ 𝐻 ) ∧ 𝑥 ∈ 𝐴 ∧ ( 𝐹 ‘ 𝑥 ) ≠ ( 𝐻 ‘ 𝑥 ) ) ∧ 𝑦 ∈ { 𝑥 ∈ 𝐴 ∣ ( 𝐹 ‘ 𝑥 ) ≠ ( 𝐻 ‘ 𝑥 ) } ∧ ∀ 𝑧 ∈ { 𝑥 ∈ 𝐴 ∣ ( 𝐹 ‘ 𝑥 ) ≠ ( 𝐻 ‘ 𝑥 ) } ¬ 𝑧 𝑅 𝑦 ) ↔ ( ( ( ( 𝑅 FrSe 𝐴 ∧ 𝐻 Fn 𝐴 ∧ ∀ 𝑥 ∈ 𝐴 ( 𝐻 ‘ 𝑥 ) = ( 𝐺 ‘ ⟨ 𝑥 , ( 𝐻 ↾ pred ( 𝑥 , 𝐴 , 𝑅 ) ) ⟩ ) ) ∧ 𝐹 ≠ 𝐻 ) ∧ 𝑥 ∈ 𝐴 ∧ ( 𝐹 ‘ 𝑥 ) ≠ ( 𝐻 ‘ 𝑥 ) ) ∧ 𝑦 ∈ { 𝑥 ∈ 𝐴 ∣ ( 𝐹 ‘ 𝑥 ) ≠ ( 𝐻 ‘ 𝑥 ) } ∧ ∀ 𝑧 ∈ { 𝑥 ∈ 𝐴 ∣ ( 𝐹 ‘ 𝑥 ) ≠ ( 𝐻 ‘ 𝑥 ) } ¬ 𝑧 𝑅 𝑦 ) )
10	1 2 3 4 5 6 7 8 9	bnj1523	⊢ ( ( 𝑅 FrSe 𝐴 ∧ 𝐻 Fn 𝐴 ∧ ∀ 𝑥 ∈ 𝐴 ( 𝐻 ‘ 𝑥 ) = ( 𝐺 ‘ ⟨ 𝑥 , ( 𝐻 ↾ pred ( 𝑥 , 𝐴 , 𝑅 ) ) ⟩ ) ) → 𝐹 = 𝐻 )