MPE Home Metamath Proof Explorer < Previous   Next >
Nearby theorems
Mirrors  >  Home  >  MPE Home  >  Th. List  >  wfr1 Structured version   Visualization version   GIF version

Theorem wfr1 7600
Description: The Principle of Well-Founded Recursion, part 1 of 3. We start with an arbitrary function 𝐺. Then, using a base class 𝐴 and a well-ordering 𝑅 of 𝐴, we define a function 𝐹. This function is said to be defined by "well-founded recursion." The purpose of these three theorems is to demonstrate the properties of 𝐹. We begin by showing that 𝐹 is a function over 𝐴. (Contributed by Scott Fenton, 22-Apr-2011.) (Revised by Mario Carneiro, 26-Jun-2015.)
Hypotheses
Ref Expression
wfr1.1 𝑅 We 𝐴
wfr1.2 𝑅 Se 𝐴
wfr1.3 𝐹 = wrecs(𝑅, 𝐴, 𝐺)
Assertion
Ref Expression
wfr1 𝐹 Fn 𝐴

Proof of Theorem wfr1
Dummy variable 𝑧 is distinct from all other variables.
StepHypRef Expression
1 wfr1.1 . . 3 𝑅 We 𝐴
2 wfr1.2 . . 3 𝑅 Se 𝐴
3 wfr1.3 . . 3 𝐹 = wrecs(𝑅, 𝐴, 𝐺)
41, 2, 3wfrfun 7592 . 2 Fun 𝐹
5 eqid 2758 . . 3 (𝐹 ∪ {⟨𝑧, (𝐺‘(𝐹 ↾ Pred(𝑅, 𝐴, 𝑧)))⟩}) = (𝐹 ∪ {⟨𝑧, (𝐺‘(𝐹 ↾ Pred(𝑅, 𝐴, 𝑧)))⟩})
61, 2, 3, 5wfrlem16 7597 . 2 dom 𝐹 = 𝐴
7 df-fn 6050 . 2 (𝐹 Fn 𝐴 ↔ (Fun 𝐹 ∧ dom 𝐹 = 𝐴))
84, 6, 7mpbir2an 993 1 𝐹 Fn 𝐴
Colors of variables: wff setvar class
Syntax hints:   = wceq 1630  cun 3711  {csn 4319  cop 4325   Se wse 5221   We wwe 5222  dom cdm 5264  cres 5266  Predcpred 5838  Fun wfun 6041   Fn wfn 6042  cfv 6047  wrecscwrecs 7573
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1869  ax-4 1884  ax-5 1986  ax-6 2052  ax-7 2088  ax-8 2139  ax-9 2146  ax-10 2166  ax-11 2181  ax-12 2194  ax-13 2389  ax-ext 2738  ax-rep 4921  ax-sep 4931  ax-nul 4939  ax-pow 4990  ax-pr 5053  ax-un 7112
This theorem depends on definitions:  df-bi 197  df-or 384  df-an 385  df-3or 1073  df-3an 1074  df-tru 1633  df-ex 1852  df-nf 1857  df-sb 2045  df-eu 2609  df-mo 2610  df-clab 2745  df-cleq 2751  df-clel 2754  df-nfc 2889  df-ne 2931  df-ral 3053  df-rex 3054  df-reu 3055  df-rmo 3056  df-rab 3057  df-v 3340  df-sbc 3575  df-csb 3673  df-dif 3716  df-un 3718  df-in 3720  df-ss 3727  df-nul 4057  df-if 4229  df-sn 4320  df-pr 4322  df-op 4326  df-uni 4587  df-iun 4672  df-br 4803  df-opab 4863  df-mpt 4880  df-id 5172  df-po 5185  df-so 5186  df-fr 5223  df-se 5224  df-we 5225  df-xp 5270  df-rel 5271  df-cnv 5272  df-co 5273  df-dm 5274  df-rn 5275  df-res 5276  df-ima 5277  df-pred 5839  df-iota 6010  df-fun 6049  df-fn 6050  df-f 6051  df-f1 6052  df-fo 6053  df-f1o 6054  df-fv 6055  df-wrecs 7574
This theorem is referenced by:  wfr3  7602  tfr1ALT  7663  bpolylem  14976
  Copyright terms: Public domain W3C validator