Metamath Proof Explorer

Theorem fnse

Description: Condition for the well-order in fnwe to be set-like. (Contributed by Mario Carneiro, 25-Jun-2015)

Ref Expression
Hypotheses fnse.1 ⊢ 𝑇 = { ⟨ 𝑥 , 𝑦 ⟩ ∣ ( ( 𝑥 ∈ 𝐴 ∧ 𝑦 ∈ 𝐴 ) ∧ ( ( 𝐹 ‘ 𝑥 ) 𝑅 ( 𝐹 ‘ 𝑦 ) ∨ ( ( 𝐹 ‘ 𝑥 ) = ( 𝐹 ‘ 𝑦 ) ∧ 𝑥 𝑆 𝑦 ) ) ) }
fnse.2 ⊢ ( 𝜑 → 𝐹 : 𝐴 ⟶ 𝐵 )
fnse.3 ⊢ ( 𝜑 → 𝑅 Se 𝐵 )
fnse.4 ⊢ ( 𝜑 → ( ◡ 𝐹 “ 𝑤 ) ∈ V )
Assertion fnse ( 𝜑 → 𝑇 Se 𝐴 )

Proof

Step Hyp Ref Expression
1 fnse.1 ⊢ 𝑇 = { ⟨ 𝑥 , 𝑦 ⟩ ∣ ( ( 𝑥 ∈ 𝐴 ∧ 𝑦 ∈ 𝐴 ) ∧ ( ( 𝐹 ‘ 𝑥 ) 𝑅 ( 𝐹 ‘ 𝑦 ) ∨ ( ( 𝐹 ‘ 𝑥 ) = ( 𝐹 ‘ 𝑦 ) ∧ 𝑥 𝑆 𝑦 ) ) ) }
2 fnse.2 ⊢ ( 𝜑 → 𝐹 : 𝐴 ⟶ 𝐵 )
3 fnse.3 ⊢ ( 𝜑 → 𝑅 Se 𝐵 )
4 fnse.4 ⊢ ( 𝜑 → ( ◡ 𝐹 “ 𝑤 ) ∈ V )
5 2 ffvelcdmda ⊢ ( ( 𝜑 ∧ 𝑧 ∈ 𝐴 ) → ( 𝐹 ‘ 𝑧 ) ∈ 𝐵 )
6 seex ⊢ ( ( 𝑅 Se 𝐵 ∧ ( 𝐹 ‘ 𝑧 ) ∈ 𝐵 ) → { 𝑢 ∈ 𝐵 ∣ 𝑢 𝑅 ( 𝐹 ‘ 𝑧 ) } ∈ V )
7 3 5 6 syl2an2r ⊢ ( ( 𝜑 ∧ 𝑧 ∈ 𝐴 ) → { 𝑢 ∈ 𝐵 ∣ 𝑢 𝑅 ( 𝐹 ‘ 𝑧 ) } ∈ V )
8 snex ⊢ { ( 𝐹 ‘ 𝑧 ) } ∈ V
9 unexg ⊢ ( ( { 𝑢 ∈ 𝐵 ∣ 𝑢 𝑅 ( 𝐹 ‘ 𝑧 ) } ∈ V ∧ { ( 𝐹 ‘ 𝑧 ) } ∈ V ) → ( { 𝑢 ∈ 𝐵 ∣ 𝑢 𝑅 ( 𝐹 ‘ 𝑧 ) } ∪ { ( 𝐹 ‘ 𝑧 ) } ) ∈ V )
10 7 8 9 sylancl ⊢ ( ( 𝜑 ∧ 𝑧 ∈ 𝐴 ) → ( { 𝑢 ∈ 𝐵 ∣ 𝑢 𝑅 ( 𝐹 ‘ 𝑧 ) } ∪ { ( 𝐹 ‘ 𝑧 ) } ) ∈ V )
11 imaeq2 ⊢ ( 𝑤 = ( { 𝑢 ∈ 𝐵 ∣ 𝑢 𝑅 ( 𝐹 ‘ 𝑧 ) } ∪ { ( 𝐹 ‘ 𝑧 ) } ) → ( ◡ 𝐹 “ 𝑤 ) = ( ◡ 𝐹 “ ( { 𝑢 ∈ 𝐵 ∣ 𝑢 𝑅 ( 𝐹 ‘ 𝑧 ) } ∪ { ( 𝐹 ‘ 𝑧 ) } ) ) )
12 11 eleq1d ⊢ ( 𝑤 = ( { 𝑢 ∈ 𝐵 ∣ 𝑢 𝑅 ( 𝐹 ‘ 𝑧 ) } ∪ { ( 𝐹 ‘ 𝑧 ) } ) → ( ( ◡ 𝐹 “ 𝑤 ) ∈ V ↔ ( ◡ 𝐹 “ ( { 𝑢 ∈ 𝐵 ∣ 𝑢 𝑅 ( 𝐹 ‘ 𝑧 ) } ∪ { ( 𝐹 ‘ 𝑧 ) } ) ) ∈ V ) )
13 12 imbi2d ⊢ ( 𝑤 = ( { 𝑢 ∈ 𝐵 ∣ 𝑢 𝑅 ( 𝐹 ‘ 𝑧 ) } ∪ { ( 𝐹 ‘ 𝑧 ) } ) → ( ( 𝜑 → ( ◡ 𝐹 “ 𝑤 ) ∈ V ) ↔ ( 𝜑 → ( ◡ 𝐹 “ ( { 𝑢 ∈ 𝐵 ∣ 𝑢 𝑅 ( 𝐹 ‘ 𝑧 ) } ∪ { ( 𝐹 ‘ 𝑧 ) } ) ) ∈ V ) ) )
14 13 4 vtoclg ⊢ ( ( { 𝑢 ∈ 𝐵 ∣ 𝑢 𝑅 ( 𝐹 ‘ 𝑧 ) } ∪ { ( 𝐹 ‘ 𝑧 ) } ) ∈ V → ( 𝜑 → ( ◡ 𝐹 “ ( { 𝑢 ∈ 𝐵 ∣ 𝑢 𝑅 ( 𝐹 ‘ 𝑧 ) } ∪ { ( 𝐹 ‘ 𝑧 ) } ) ) ∈ V ) )
15 14 impcom ⊢ ( ( 𝜑 ∧ ( { 𝑢 ∈ 𝐵 ∣ 𝑢 𝑅 ( 𝐹 ‘ 𝑧 ) } ∪ { ( 𝐹 ‘ 𝑧 ) } ) ∈ V ) → ( ◡ 𝐹 “ ( { 𝑢 ∈ 𝐵 ∣ 𝑢 𝑅 ( 𝐹 ‘ 𝑧 ) } ∪ { ( 𝐹 ‘ 𝑧 ) } ) ) ∈ V )
16 10 15 syldan ⊢ ( ( 𝜑 ∧ 𝑧 ∈ 𝐴 ) → ( ◡ 𝐹 “ ( { 𝑢 ∈ 𝐵 ∣ 𝑢 𝑅 ( 𝐹 ‘ 𝑧 ) } ∪ { ( 𝐹 ‘ 𝑧 ) } ) ) ∈ V )
17 inss2 ⊢ ( 𝐴 ∩ ( ◡ 𝑇 “ { 𝑧 } ) ) ⊆ ( ◡ 𝑇 “ { 𝑧 } )
18 vex ⊢ 𝑤 ∈ V
19 18 eliniseg ⊢ ( 𝑧 ∈ V → ( 𝑤 ∈ ( ◡ 𝑇 “ { 𝑧 } ) ↔ 𝑤 𝑇 𝑧 ) )
20 19 elv ⊢ ( 𝑤 ∈ ( ◡ 𝑇 “ { 𝑧 } ) ↔ 𝑤 𝑇 𝑧 )
21 fveq2 ⊢ ( 𝑥 = 𝑤 → ( 𝐹 ‘ 𝑥 ) = ( 𝐹 ‘ 𝑤 ) )
22 fveq2 ⊢ ( 𝑦 = 𝑧 → ( 𝐹 ‘ 𝑦 ) = ( 𝐹 ‘ 𝑧 ) )
23 21 22 breqan12d ⊢ ( ( 𝑥 = 𝑤 ∧ 𝑦 = 𝑧 ) → ( ( 𝐹 ‘ 𝑥 ) 𝑅 ( 𝐹 ‘ 𝑦 ) ↔ ( 𝐹 ‘ 𝑤 ) 𝑅 ( 𝐹 ‘ 𝑧 ) ) )
24 21 22 eqeqan12d ⊢ ( ( 𝑥 = 𝑤 ∧ 𝑦 = 𝑧 ) → ( ( 𝐹 ‘ 𝑥 ) = ( 𝐹 ‘ 𝑦 ) ↔ ( 𝐹 ‘ 𝑤 ) = ( 𝐹 ‘ 𝑧 ) ) )
25 breq12 ⊢ ( ( 𝑥 = 𝑤 ∧ 𝑦 = 𝑧 ) → ( 𝑥 𝑆 𝑦 ↔ 𝑤 𝑆 𝑧 ) )
26 24 25 anbi12d ⊢ ( ( 𝑥 = 𝑤 ∧ 𝑦 = 𝑧 ) → ( ( ( 𝐹 ‘ 𝑥 ) = ( 𝐹 ‘ 𝑦 ) ∧ 𝑥 𝑆 𝑦 ) ↔ ( ( 𝐹 ‘ 𝑤 ) = ( 𝐹 ‘ 𝑧 ) ∧ 𝑤 𝑆 𝑧 ) ) )
27 23 26 orbi12d ⊢ ( ( 𝑥 = 𝑤 ∧ 𝑦 = 𝑧 ) → ( ( ( 𝐹 ‘ 𝑥 ) 𝑅 ( 𝐹 ‘ 𝑦 ) ∨ ( ( 𝐹 ‘ 𝑥 ) = ( 𝐹 ‘ 𝑦 ) ∧ 𝑥 𝑆 𝑦 ) ) ↔ ( ( 𝐹 ‘ 𝑤 ) 𝑅 ( 𝐹 ‘ 𝑧 ) ∨ ( ( 𝐹 ‘ 𝑤 ) = ( 𝐹 ‘ 𝑧 ) ∧ 𝑤 𝑆 𝑧 ) ) ) )
28 27 1 brab2a ⊢ ( 𝑤 𝑇 𝑧 ↔ ( ( 𝑤 ∈ 𝐴 ∧ 𝑧 ∈ 𝐴 ) ∧ ( ( 𝐹 ‘ 𝑤 ) 𝑅 ( 𝐹 ‘ 𝑧 ) ∨ ( ( 𝐹 ‘ 𝑤 ) = ( 𝐹 ‘ 𝑧 ) ∧ 𝑤 𝑆 𝑧 ) ) ) )
29 2 ffvelcdmda ⊢ ( ( 𝜑 ∧ 𝑤 ∈ 𝐴 ) → ( 𝐹 ‘ 𝑤 ) ∈ 𝐵 )
30 29 adantrr ⊢ ( ( 𝜑 ∧ ( 𝑤 ∈ 𝐴 ∧ 𝑧 ∈ 𝐴 ) ) → ( 𝐹 ‘ 𝑤 ) ∈ 𝐵 )
31 breq1 ⊢ ( 𝑢 = ( 𝐹 ‘ 𝑤 ) → ( 𝑢 𝑅 ( 𝐹 ‘ 𝑧 ) ↔ ( 𝐹 ‘ 𝑤 ) 𝑅 ( 𝐹 ‘ 𝑧 ) ) )
32 31 elrab3 ⊢ ( ( 𝐹 ‘ 𝑤 ) ∈ 𝐵 → ( ( 𝐹 ‘ 𝑤 ) ∈ { 𝑢 ∈ 𝐵 ∣ 𝑢 𝑅 ( 𝐹 ‘ 𝑧 ) } ↔ ( 𝐹 ‘ 𝑤 ) 𝑅 ( 𝐹 ‘ 𝑧 ) ) )
33 30 32 syl ⊢ ( ( 𝜑 ∧ ( 𝑤 ∈ 𝐴 ∧ 𝑧 ∈ 𝐴 ) ) → ( ( 𝐹 ‘ 𝑤 ) ∈ { 𝑢 ∈ 𝐵 ∣ 𝑢 𝑅 ( 𝐹 ‘ 𝑧 ) } ↔ ( 𝐹 ‘ 𝑤 ) 𝑅 ( 𝐹 ‘ 𝑧 ) ) )
34 33 biimprd ⊢ ( ( 𝜑 ∧ ( 𝑤 ∈ 𝐴 ∧ 𝑧 ∈ 𝐴 ) ) → ( ( 𝐹 ‘ 𝑤 ) 𝑅 ( 𝐹 ‘ 𝑧 ) → ( 𝐹 ‘ 𝑤 ) ∈ { 𝑢 ∈ 𝐵 ∣ 𝑢 𝑅 ( 𝐹 ‘ 𝑧 ) } ) )
35 simpl ⊢ ( ( ( 𝐹 ‘ 𝑤 ) = ( 𝐹 ‘ 𝑧 ) ∧ 𝑤 𝑆 𝑧 ) → ( 𝐹 ‘ 𝑤 ) = ( 𝐹 ‘ 𝑧 ) )
36 fvex ⊢ ( 𝐹 ‘ 𝑤 ) ∈ V
37 36 elsn ⊢ ( ( 𝐹 ‘ 𝑤 ) ∈ { ( 𝐹 ‘ 𝑧 ) } ↔ ( 𝐹 ‘ 𝑤 ) = ( 𝐹 ‘ 𝑧 ) )
38 35 37 sylibr ⊢ ( ( ( 𝐹 ‘ 𝑤 ) = ( 𝐹 ‘ 𝑧 ) ∧ 𝑤 𝑆 𝑧 ) → ( 𝐹 ‘ 𝑤 ) ∈ { ( 𝐹 ‘ 𝑧 ) } )
39 38 a1i ⊢ ( ( 𝜑 ∧ ( 𝑤 ∈ 𝐴 ∧ 𝑧 ∈ 𝐴 ) ) → ( ( ( 𝐹 ‘ 𝑤 ) = ( 𝐹 ‘ 𝑧 ) ∧ 𝑤 𝑆 𝑧 ) → ( 𝐹 ‘ 𝑤 ) ∈ { ( 𝐹 ‘ 𝑧 ) } ) )
40 34 39 orim12d ⊢ ( ( 𝜑 ∧ ( 𝑤 ∈ 𝐴 ∧ 𝑧 ∈ 𝐴 ) ) → ( ( ( 𝐹 ‘ 𝑤 ) 𝑅 ( 𝐹 ‘ 𝑧 ) ∨ ( ( 𝐹 ‘ 𝑤 ) = ( 𝐹 ‘ 𝑧 ) ∧ 𝑤 𝑆 𝑧 ) ) → ( ( 𝐹 ‘ 𝑤 ) ∈ { 𝑢 ∈ 𝐵 ∣ 𝑢 𝑅 ( 𝐹 ‘ 𝑧 ) } ∨ ( 𝐹 ‘ 𝑤 ) ∈ { ( 𝐹 ‘ 𝑧 ) } ) ) )
41 elun ⊢ ( ( 𝐹 ‘ 𝑤 ) ∈ ( { 𝑢 ∈ 𝐵 ∣ 𝑢 𝑅 ( 𝐹 ‘ 𝑧 ) } ∪ { ( 𝐹 ‘ 𝑧 ) } ) ↔ ( ( 𝐹 ‘ 𝑤 ) ∈ { 𝑢 ∈ 𝐵 ∣ 𝑢 𝑅 ( 𝐹 ‘ 𝑧 ) } ∨ ( 𝐹 ‘ 𝑤 ) ∈ { ( 𝐹 ‘ 𝑧 ) } ) )
42 40 41 imbitrrdi ⊢ ( ( 𝜑 ∧ ( 𝑤 ∈ 𝐴 ∧ 𝑧 ∈ 𝐴 ) ) → ( ( ( 𝐹 ‘ 𝑤 ) 𝑅 ( 𝐹 ‘ 𝑧 ) ∨ ( ( 𝐹 ‘ 𝑤 ) = ( 𝐹 ‘ 𝑧 ) ∧ 𝑤 𝑆 𝑧 ) ) → ( 𝐹 ‘ 𝑤 ) ∈ ( { 𝑢 ∈ 𝐵 ∣ 𝑢 𝑅 ( 𝐹 ‘ 𝑧 ) } ∪ { ( 𝐹 ‘ 𝑧 ) } ) ) )
43 simprl ⊢ ( ( 𝜑 ∧ ( 𝑤 ∈ 𝐴 ∧ 𝑧 ∈ 𝐴 ) ) → 𝑤 ∈ 𝐴 )
44 42 43 jctild ⊢ ( ( 𝜑 ∧ ( 𝑤 ∈ 𝐴 ∧ 𝑧 ∈ 𝐴 ) ) → ( ( ( 𝐹 ‘ 𝑤 ) 𝑅 ( 𝐹 ‘ 𝑧 ) ∨ ( ( 𝐹 ‘ 𝑤 ) = ( 𝐹 ‘ 𝑧 ) ∧ 𝑤 𝑆 𝑧 ) ) → ( 𝑤 ∈ 𝐴 ∧ ( 𝐹 ‘ 𝑤 ) ∈ ( { 𝑢 ∈ 𝐵 ∣ 𝑢 𝑅 ( 𝐹 ‘ 𝑧 ) } ∪ { ( 𝐹 ‘ 𝑧 ) } ) ) ) )
45 2 ffnd ⊢ ( 𝜑 → 𝐹 Fn 𝐴 )
46 45 adantr ⊢ ( ( 𝜑 ∧ ( 𝑤 ∈ 𝐴 ∧ 𝑧 ∈ 𝐴 ) ) → 𝐹 Fn 𝐴 )
47 elpreima ⊢ ( 𝐹 Fn 𝐴 → ( 𝑤 ∈ ( ◡ 𝐹 “ ( { 𝑢 ∈ 𝐵 ∣ 𝑢 𝑅 ( 𝐹 ‘ 𝑧 ) } ∪ { ( 𝐹 ‘ 𝑧 ) } ) ) ↔ ( 𝑤 ∈ 𝐴 ∧ ( 𝐹 ‘ 𝑤 ) ∈ ( { 𝑢 ∈ 𝐵 ∣ 𝑢 𝑅 ( 𝐹 ‘ 𝑧 ) } ∪ { ( 𝐹 ‘ 𝑧 ) } ) ) ) )
48 46 47 syl ⊢ ( ( 𝜑 ∧ ( 𝑤 ∈ 𝐴 ∧ 𝑧 ∈ 𝐴 ) ) → ( 𝑤 ∈ ( ◡ 𝐹 “ ( { 𝑢 ∈ 𝐵 ∣ 𝑢 𝑅 ( 𝐹 ‘ 𝑧 ) } ∪ { ( 𝐹 ‘ 𝑧 ) } ) ) ↔ ( 𝑤 ∈ 𝐴 ∧ ( 𝐹 ‘ 𝑤 ) ∈ ( { 𝑢 ∈ 𝐵 ∣ 𝑢 𝑅 ( 𝐹 ‘ 𝑧 ) } ∪ { ( 𝐹 ‘ 𝑧 ) } ) ) ) )
49 44 48 sylibrd ⊢ ( ( 𝜑 ∧ ( 𝑤 ∈ 𝐴 ∧ 𝑧 ∈ 𝐴 ) ) → ( ( ( 𝐹 ‘ 𝑤 ) 𝑅 ( 𝐹 ‘ 𝑧 ) ∨ ( ( 𝐹 ‘ 𝑤 ) = ( 𝐹 ‘ 𝑧 ) ∧ 𝑤 𝑆 𝑧 ) ) → 𝑤 ∈ ( ◡ 𝐹 “ ( { 𝑢 ∈ 𝐵 ∣ 𝑢 𝑅 ( 𝐹 ‘ 𝑧 ) } ∪ { ( 𝐹 ‘ 𝑧 ) } ) ) ) )
50 49 expimpd ⊢ ( 𝜑 → ( ( ( 𝑤 ∈ 𝐴 ∧ 𝑧 ∈ 𝐴 ) ∧ ( ( 𝐹 ‘ 𝑤 ) 𝑅 ( 𝐹 ‘ 𝑧 ) ∨ ( ( 𝐹 ‘ 𝑤 ) = ( 𝐹 ‘ 𝑧 ) ∧ 𝑤 𝑆 𝑧 ) ) ) → 𝑤 ∈ ( ◡ 𝐹 “ ( { 𝑢 ∈ 𝐵 ∣ 𝑢 𝑅 ( 𝐹 ‘ 𝑧 ) } ∪ { ( 𝐹 ‘ 𝑧 ) } ) ) ) )
51 28 50 biimtrid ⊢ ( 𝜑 → ( 𝑤 𝑇 𝑧 → 𝑤 ∈ ( ◡ 𝐹 “ ( { 𝑢 ∈ 𝐵 ∣ 𝑢 𝑅 ( 𝐹 ‘ 𝑧 ) } ∪ { ( 𝐹 ‘ 𝑧 ) } ) ) ) )
52 20 51 biimtrid ⊢ ( 𝜑 → ( 𝑤 ∈ ( ◡ 𝑇 “ { 𝑧 } ) → 𝑤 ∈ ( ◡ 𝐹 “ ( { 𝑢 ∈ 𝐵 ∣ 𝑢 𝑅 ( 𝐹 ‘ 𝑧 ) } ∪ { ( 𝐹 ‘ 𝑧 ) } ) ) ) )
53 52 ssrdv ⊢ ( 𝜑 → ( ◡ 𝑇 “ { 𝑧 } ) ⊆ ( ◡ 𝐹 “ ( { 𝑢 ∈ 𝐵 ∣ 𝑢 𝑅 ( 𝐹 ‘ 𝑧 ) } ∪ { ( 𝐹 ‘ 𝑧 ) } ) ) )
54 17 53 sstrid ⊢ ( 𝜑 → ( 𝐴 ∩ ( ◡ 𝑇 “ { 𝑧 } ) ) ⊆ ( ◡ 𝐹 “ ( { 𝑢 ∈ 𝐵 ∣ 𝑢 𝑅 ( 𝐹 ‘ 𝑧 ) } ∪ { ( 𝐹 ‘ 𝑧 ) } ) ) )
55 54 adantr ⊢ ( ( 𝜑 ∧ 𝑧 ∈ 𝐴 ) → ( 𝐴 ∩ ( ◡ 𝑇 “ { 𝑧 } ) ) ⊆ ( ◡ 𝐹 “ ( { 𝑢 ∈ 𝐵 ∣ 𝑢 𝑅 ( 𝐹 ‘ 𝑧 ) } ∪ { ( 𝐹 ‘ 𝑧 ) } ) ) )
56 16 55 ssexd ⊢ ( ( 𝜑 ∧ 𝑧 ∈ 𝐴 ) → ( 𝐴 ∩ ( ◡ 𝑇 “ { 𝑧 } ) ) ∈ V )
57 56 ralrimiva ⊢ ( 𝜑 → ∀ 𝑧 ∈ 𝐴 ( 𝐴 ∩ ( ◡ 𝑇 “ { 𝑧 } ) ) ∈ V )
58 dfse2 ⊢ ( 𝑇 Se 𝐴 ↔ ∀ 𝑧 ∈ 𝐴 ( 𝐴 ∩ ( ◡ 𝑇 “ { 𝑧 } ) ) ∈ V )
59 57 58 sylibr ⊢ ( 𝜑 → 𝑇 Se 𝐴 )