Theorem tfrlem16 8434

Description: Lemma for finite recursion. Without assuming ax-rep 5278, we can show that the domain of the constructed function is a limit ordinal, and hence contains all the finite ordinals. (Contributed by Mario Carneiro, 14-Nov-2014.)

Hypothesis

Ref	Expression
tfrlem.1	⊢ 𝐴 = {𝑓 ∣ ∃𝑥 ∈ On (𝑓 Fn 𝑥 ∧ ∀𝑦 ∈ 𝑥 (𝑓‘𝑦) = (𝐹‘(𝑓 ↾ 𝑦)))}

Assertion

Ref	Expression
tfrlem16	⊢ Lim dom recs(𝐹)

Distinct variable group:   𝑥,𝑓,𝑦,𝐹

Allowed substitution hints:   𝐴(𝑥,𝑦,𝑓)

Proof of Theorem tfrlem16

Dummy variable 𝑧 is distinct from all other variables.

Step	Hyp	Ref	Expression
1		tfrlem.1	. . . 4 ⊢ 𝐴 = {𝑓 ∣ ∃𝑥 ∈ On (𝑓 Fn 𝑥 ∧ ∀𝑦 ∈ 𝑥 (𝑓‘𝑦) = (𝐹‘(𝑓 ↾ 𝑦)))}
2	1	tfrlem8 8425	. . 3 ⊢ Ord dom recs(𝐹)
3		ordzsl 7867	. . 3 ⊢ (Ord dom recs(𝐹) ↔ (dom recs(𝐹) = ∅ ∨ ∃𝑧 ∈ On dom recs(𝐹) = suc 𝑧 ∨ Lim dom recs(𝐹)))
4	2, 3	mpbi 230	. 2 ⊢ (dom recs(𝐹) = ∅ ∨ ∃𝑧 ∈ On dom recs(𝐹) = suc 𝑧 ∨ Lim dom recs(𝐹))
5		res0 6000	. . . . . . 7 ⊢ (recs(𝐹) ↾ ∅) = ∅
6		0ex 5306	. . . . . . 7 ⊢ ∅ ∈ V
7	5, 6	eqeltri 2836	. . . . . 6 ⊢ (recs(𝐹) ↾ ∅) ∈ V
8		0elon 6437	. . . . . . 7 ⊢ ∅ ∈ On
9	1	tfrlem15 8433	. . . . . . 7 ⊢ (∅ ∈ On → (∅ ∈ dom recs(𝐹) ↔ (recs(𝐹) ↾ ∅) ∈ V))
10	8, 9	ax-mp 5	. . . . . 6 ⊢ (∅ ∈ dom recs(𝐹) ↔ (recs(𝐹) ↾ ∅) ∈ V)
11	7, 10	mpbir 231	. . . . 5 ⊢ ∅ ∈ dom recs(𝐹)
12	11	n0ii 4342	. . . 4 ⊢ ¬ dom recs(𝐹) = ∅
13	12	pm2.21i 119	. . 3 ⊢ (dom recs(𝐹) = ∅ → Lim dom recs(𝐹))
14	1	tfrlem13 8431	. . . . 5 ⊢ ¬ recs(𝐹) ∈ V
15		simpr 484	. . . . . . . . . 10 ⊢ ((𝑧 ∈ On ∧ dom recs(𝐹) = suc 𝑧) → dom recs(𝐹) = suc 𝑧)
16		df-suc 6389	. . . . . . . . . 10 ⊢ suc 𝑧 = (𝑧 ∪ {𝑧})
17	15, 16	eqtrdi 2792	. . . . . . . . 9 ⊢ ((𝑧 ∈ On ∧ dom recs(𝐹) = suc 𝑧) → dom recs(𝐹) = (𝑧 ∪ {𝑧}))
18	17	reseq2d 5996	. . . . . . . 8 ⊢ ((𝑧 ∈ On ∧ dom recs(𝐹) = suc 𝑧) → (recs(𝐹) ↾ dom recs(𝐹)) = (recs(𝐹) ↾ (𝑧 ∪ {𝑧})))
19	1	tfrlem6 8423	. . . . . . . . 9 ⊢ Rel recs(𝐹)
20		resdm 6043	. . . . . . . . 9 ⊢ (Rel recs(𝐹) → (recs(𝐹) ↾ dom recs(𝐹)) = recs(𝐹))
21	19, 20	ax-mp 5	. . . . . . . 8 ⊢ (recs(𝐹) ↾ dom recs(𝐹)) = recs(𝐹)
22		resundi 6010	. . . . . . . 8 ⊢ (recs(𝐹) ↾ (𝑧 ∪ {𝑧})) = ((recs(𝐹) ↾ 𝑧) ∪ (recs(𝐹) ↾ {𝑧}))
23	18, 21, 22	3eqtr3g 2799	. . . . . . 7 ⊢ ((𝑧 ∈ On ∧ dom recs(𝐹) = suc 𝑧) → recs(𝐹) = ((recs(𝐹) ↾ 𝑧) ∪ (recs(𝐹) ↾ {𝑧})))
24		vex 3483	. . . . . . . . . . 11 ⊢ 𝑧 ∈ V
25	24	sucid 6465	. . . . . . . . . 10 ⊢ 𝑧 ∈ suc 𝑧
26	25, 15	eleqtrrid 2847	. . . . . . . . 9 ⊢ ((𝑧 ∈ On ∧ dom recs(𝐹) = suc 𝑧) → 𝑧 ∈ dom recs(𝐹))
27	1	tfrlem9a 8427	. . . . . . . . 9 ⊢ (𝑧 ∈ dom recs(𝐹) → (recs(𝐹) ↾ 𝑧) ∈ V)
28	26, 27	syl 17	. . . . . . . 8 ⊢ ((𝑧 ∈ On ∧ dom recs(𝐹) = suc 𝑧) → (recs(𝐹) ↾ 𝑧) ∈ V)
29		snex 5435	. . . . . . . . 9 ⊢ {⟨𝑧, (recs(𝐹)‘𝑧)⟩} ∈ V
30	1	tfrlem7 8424	. . . . . . . . . 10 ⊢ Fun recs(𝐹)
31		funressn 7178	. . . . . . . . . 10 ⊢ (Fun recs(𝐹) → (recs(𝐹) ↾ {𝑧}) ⊆ {⟨𝑧, (recs(𝐹)‘𝑧)⟩})
32	30, 31	ax-mp 5	. . . . . . . . 9 ⊢ (recs(𝐹) ↾ {𝑧}) ⊆ {⟨𝑧, (recs(𝐹)‘𝑧)⟩}
33	29, 32	ssexi 5321	. . . . . . . 8 ⊢ (recs(𝐹) ↾ {𝑧}) ∈ V
34		unexg 7764	. . . . . . . 8 ⊢ (((recs(𝐹) ↾ 𝑧) ∈ V ∧ (recs(𝐹) ↾ {𝑧}) ∈ V) → ((recs(𝐹) ↾ 𝑧) ∪ (recs(𝐹) ↾ {𝑧})) ∈ V)
35	28, 33, 34	sylancl 586	. . . . . . 7 ⊢ ((𝑧 ∈ On ∧ dom recs(𝐹) = suc 𝑧) → ((recs(𝐹) ↾ 𝑧) ∪ (recs(𝐹) ↾ {𝑧})) ∈ V)
36	23, 35	eqeltrd 2840	. . . . . 6 ⊢ ((𝑧 ∈ On ∧ dom recs(𝐹) = suc 𝑧) → recs(𝐹) ∈ V)
37	36	rexlimiva 3146	. . . . 5 ⊢ (∃𝑧 ∈ On dom recs(𝐹) = suc 𝑧 → recs(𝐹) ∈ V)
38	14, 37	mto 197	. . . 4 ⊢ ¬ ∃𝑧 ∈ On dom recs(𝐹) = suc 𝑧
39	38	pm2.21i 119	. . 3 ⊢ (∃𝑧 ∈ On dom recs(𝐹) = suc 𝑧 → Lim dom recs(𝐹))
40		id 22	. . 3 ⊢ (Lim dom recs(𝐹) → Lim dom recs(𝐹))
41	13, 39, 40	3jaoi 1429	. 2 ⊢ ((dom recs(𝐹) = ∅ ∨ ∃𝑧 ∈ On dom recs(𝐹) = suc 𝑧 ∨ Lim dom recs(𝐹)) → Lim dom recs(𝐹))
42	4, 41	ax-mp 5	1 ⊢ Lim dom recs(𝐹)

Syntax hints:   ↔ wb 206   ∧ wa 395   ∨ w3o 1085   = wceq 1539   ∈ wcel 2107  {cab 2713  ∀wral 3060  ∃wrex 3069  Vcvv 3479   ∪ cun 3948   ⊆ wss 3950  ∅c0 4332  {csn 4625  ⟨cop 4631  dom cdm 5684   ↾ cres 5686  Rel wrel 5689  Ord word 6382  Oncon0 6383  Lim wlim 6384  suc csuc 6385  Fun wfun 6554   Fn wfn 6555  ‘cfv 6560  recscrecs 8411

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1794  ax-4 1808  ax-5 1909  ax-6 1966  ax-7 2006  ax-8 2109  ax-9 2117  ax-10 2140  ax-11 2156  ax-12 2176  ax-ext 2707  ax-sep 5295  ax-nul 5305  ax-pr 5431  ax-un 7756

This theorem depends on definitions:  df-bi 207  df-an 396  df-or 848  df-3or 1087  df-3an 1088  df-tru 1542  df-fal 1552  df-ex 1779  df-nf 1783  df-sb 2064  df-mo 2539  df-eu 2568  df-clab 2714  df-cleq 2728  df-clel 2815  df-nfc 2891  df-ne 2940  df-ral 3061  df-rex 3070  df-reu 3380  df-rab 3436  df-v 3481  df-sbc 3788  df-csb 3899  df-dif 3953  df-un 3955  df-in 3957  df-ss 3967  df-pss 3970  df-nul 4333  df-if 4525  df-pw 4601  df-sn 4626  df-pr 4628  df-op 4632  df-uni 4907  df-iun 4992  df-br 5143  df-opab 5205  df-mpt 5225  df-tr 5259  df-id 5577  df-eprel 5583  df-po 5591  df-so 5592  df-fr 5636  df-we 5638  df-xp 5690  df-rel 5691  df-cnv 5692  df-co 5693  df-dm 5694  df-rn 5695  df-res 5696  df-ima 5697  df-pred 6320  df-ord 6386  df-on 6387  df-lim 6388  df-suc 6389  df-iota 6513  df-fun 6562  df-fn 6563  df-f 6564  df-f1 6565  df-fo 6566  df-f1o 6567  df-fv 6568  df-ov 7435  df-2nd 8016  df-frecs 8307  df-wrecs 8338  df-recs 8412

This theorem is referenced by:  tfr1a  8435