Metamath Proof Explorer


Theorem reclem2pr

Description: Lemma for Proposition 9-3.7 of Gleason p. 124. (Contributed by NM, 30-Apr-1996) (Revised by Mario Carneiro, 12-Jun-2013) (New usage is discouraged.)

Ref Expression
Hypothesis reclempr.1 𝐵 = { 𝑥 ∣ ∃ 𝑦 ( 𝑥 <Q 𝑦 ∧ ¬ ( *Q𝑦 ) ∈ 𝐴 ) }
Assertion reclem2pr ( 𝐴P𝐵P )

Proof

Step Hyp Ref Expression
1 reclempr.1 𝐵 = { 𝑥 ∣ ∃ 𝑦 ( 𝑥 <Q 𝑦 ∧ ¬ ( *Q𝑦 ) ∈ 𝐴 ) }
2 prpssnq ( 𝐴P𝐴Q )
3 pssnel ( 𝐴Q → ∃ 𝑥 ( 𝑥Q ∧ ¬ 𝑥𝐴 ) )
4 recclnq ( 𝑥Q → ( *Q𝑥 ) ∈ Q )
5 nsmallnq ( ( *Q𝑥 ) ∈ Q → ∃ 𝑧 𝑧 <Q ( *Q𝑥 ) )
6 4 5 syl ( 𝑥Q → ∃ 𝑧 𝑧 <Q ( *Q𝑥 ) )
7 6 adantr ( ( 𝑥Q ∧ ¬ 𝑥𝐴 ) → ∃ 𝑧 𝑧 <Q ( *Q𝑥 ) )
8 recrecnq ( 𝑥Q → ( *Q ‘ ( *Q𝑥 ) ) = 𝑥 )
9 8 eleq1d ( 𝑥Q → ( ( *Q ‘ ( *Q𝑥 ) ) ∈ 𝐴𝑥𝐴 ) )
10 9 notbid ( 𝑥Q → ( ¬ ( *Q ‘ ( *Q𝑥 ) ) ∈ 𝐴 ↔ ¬ 𝑥𝐴 ) )
11 10 anbi2d ( 𝑥Q → ( ( 𝑧 <Q ( *Q𝑥 ) ∧ ¬ ( *Q ‘ ( *Q𝑥 ) ) ∈ 𝐴 ) ↔ ( 𝑧 <Q ( *Q𝑥 ) ∧ ¬ 𝑥𝐴 ) ) )
12 fvex ( *Q𝑥 ) ∈ V
13 breq2 ( 𝑦 = ( *Q𝑥 ) → ( 𝑧 <Q 𝑦𝑧 <Q ( *Q𝑥 ) ) )
14 fveq2 ( 𝑦 = ( *Q𝑥 ) → ( *Q𝑦 ) = ( *Q ‘ ( *Q𝑥 ) ) )
15 14 eleq1d ( 𝑦 = ( *Q𝑥 ) → ( ( *Q𝑦 ) ∈ 𝐴 ↔ ( *Q ‘ ( *Q𝑥 ) ) ∈ 𝐴 ) )
16 15 notbid ( 𝑦 = ( *Q𝑥 ) → ( ¬ ( *Q𝑦 ) ∈ 𝐴 ↔ ¬ ( *Q ‘ ( *Q𝑥 ) ) ∈ 𝐴 ) )
17 13 16 anbi12d ( 𝑦 = ( *Q𝑥 ) → ( ( 𝑧 <Q 𝑦 ∧ ¬ ( *Q𝑦 ) ∈ 𝐴 ) ↔ ( 𝑧 <Q ( *Q𝑥 ) ∧ ¬ ( *Q ‘ ( *Q𝑥 ) ) ∈ 𝐴 ) ) )
18 12 17 spcev ( ( 𝑧 <Q ( *Q𝑥 ) ∧ ¬ ( *Q ‘ ( *Q𝑥 ) ) ∈ 𝐴 ) → ∃ 𝑦 ( 𝑧 <Q 𝑦 ∧ ¬ ( *Q𝑦 ) ∈ 𝐴 ) )
19 11 18 syl6bir ( 𝑥Q → ( ( 𝑧 <Q ( *Q𝑥 ) ∧ ¬ 𝑥𝐴 ) → ∃ 𝑦 ( 𝑧 <Q 𝑦 ∧ ¬ ( *Q𝑦 ) ∈ 𝐴 ) ) )
20 vex 𝑧 ∈ V
21 breq1 ( 𝑥 = 𝑧 → ( 𝑥 <Q 𝑦𝑧 <Q 𝑦 ) )
22 21 anbi1d ( 𝑥 = 𝑧 → ( ( 𝑥 <Q 𝑦 ∧ ¬ ( *Q𝑦 ) ∈ 𝐴 ) ↔ ( 𝑧 <Q 𝑦 ∧ ¬ ( *Q𝑦 ) ∈ 𝐴 ) ) )
23 22 exbidv ( 𝑥 = 𝑧 → ( ∃ 𝑦 ( 𝑥 <Q 𝑦 ∧ ¬ ( *Q𝑦 ) ∈ 𝐴 ) ↔ ∃ 𝑦 ( 𝑧 <Q 𝑦 ∧ ¬ ( *Q𝑦 ) ∈ 𝐴 ) ) )
24 20 23 1 elab2 ( 𝑧𝐵 ↔ ∃ 𝑦 ( 𝑧 <Q 𝑦 ∧ ¬ ( *Q𝑦 ) ∈ 𝐴 ) )
25 19 24 syl6ibr ( 𝑥Q → ( ( 𝑧 <Q ( *Q𝑥 ) ∧ ¬ 𝑥𝐴 ) → 𝑧𝐵 ) )
26 25 expcomd ( 𝑥Q → ( ¬ 𝑥𝐴 → ( 𝑧 <Q ( *Q𝑥 ) → 𝑧𝐵 ) ) )
27 26 imp ( ( 𝑥Q ∧ ¬ 𝑥𝐴 ) → ( 𝑧 <Q ( *Q𝑥 ) → 𝑧𝐵 ) )
28 27 eximdv ( ( 𝑥Q ∧ ¬ 𝑥𝐴 ) → ( ∃ 𝑧 𝑧 <Q ( *Q𝑥 ) → ∃ 𝑧 𝑧𝐵 ) )
29 7 28 mpd ( ( 𝑥Q ∧ ¬ 𝑥𝐴 ) → ∃ 𝑧 𝑧𝐵 )
30 n0 ( 𝐵 ≠ ∅ ↔ ∃ 𝑧 𝑧𝐵 )
31 29 30 sylibr ( ( 𝑥Q ∧ ¬ 𝑥𝐴 ) → 𝐵 ≠ ∅ )
32 31 exlimiv ( ∃ 𝑥 ( 𝑥Q ∧ ¬ 𝑥𝐴 ) → 𝐵 ≠ ∅ )
33 2 3 32 3syl ( 𝐴P𝐵 ≠ ∅ )
34 0pss ( ∅ ⊊ 𝐵𝐵 ≠ ∅ )
35 33 34 sylibr ( 𝐴P → ∅ ⊊ 𝐵 )
36 prn0 ( 𝐴P𝐴 ≠ ∅ )
37 elprnq ( ( 𝐴P𝑧𝐴 ) → 𝑧Q )
38 recrecnq ( 𝑧Q → ( *Q ‘ ( *Q𝑧 ) ) = 𝑧 )
39 38 eleq1d ( 𝑧Q → ( ( *Q ‘ ( *Q𝑧 ) ) ∈ 𝐴𝑧𝐴 ) )
40 39 anbi2d ( 𝑧Q → ( ( 𝐴P ∧ ( *Q ‘ ( *Q𝑧 ) ) ∈ 𝐴 ) ↔ ( 𝐴P𝑧𝐴 ) ) )
41 37 40 syl ( ( 𝐴P𝑧𝐴 ) → ( ( 𝐴P ∧ ( *Q ‘ ( *Q𝑧 ) ) ∈ 𝐴 ) ↔ ( 𝐴P𝑧𝐴 ) ) )
42 fvex ( *Q𝑧 ) ∈ V
43 fveq2 ( 𝑥 = ( *Q𝑧 ) → ( *Q𝑥 ) = ( *Q ‘ ( *Q𝑧 ) ) )
44 43 eleq1d ( 𝑥 = ( *Q𝑧 ) → ( ( *Q𝑥 ) ∈ 𝐴 ↔ ( *Q ‘ ( *Q𝑧 ) ) ∈ 𝐴 ) )
45 44 anbi2d ( 𝑥 = ( *Q𝑧 ) → ( ( 𝐴P ∧ ( *Q𝑥 ) ∈ 𝐴 ) ↔ ( 𝐴P ∧ ( *Q ‘ ( *Q𝑧 ) ) ∈ 𝐴 ) ) )
46 42 45 spcev ( ( 𝐴P ∧ ( *Q ‘ ( *Q𝑧 ) ) ∈ 𝐴 ) → ∃ 𝑥 ( 𝐴P ∧ ( *Q𝑥 ) ∈ 𝐴 ) )
47 41 46 syl6bir ( ( 𝐴P𝑧𝐴 ) → ( ( 𝐴P𝑧𝐴 ) → ∃ 𝑥 ( 𝐴P ∧ ( *Q𝑥 ) ∈ 𝐴 ) ) )
48 47 pm2.43i ( ( 𝐴P𝑧𝐴 ) → ∃ 𝑥 ( 𝐴P ∧ ( *Q𝑥 ) ∈ 𝐴 ) )
49 elprnq ( ( 𝐴P ∧ ( *Q𝑥 ) ∈ 𝐴 ) → ( *Q𝑥 ) ∈ Q )
50 dmrecnq dom *Q = Q
51 0nnq ¬ ∅ ∈ Q
52 50 51 ndmfvrcl ( ( *Q𝑥 ) ∈ Q𝑥Q )
53 49 52 syl ( ( 𝐴P ∧ ( *Q𝑥 ) ∈ 𝐴 ) → 𝑥Q )
54 ltrnq ( 𝑥 <Q 𝑦 ↔ ( *Q𝑦 ) <Q ( *Q𝑥 ) )
55 prcdnq ( ( 𝐴P ∧ ( *Q𝑥 ) ∈ 𝐴 ) → ( ( *Q𝑦 ) <Q ( *Q𝑥 ) → ( *Q𝑦 ) ∈ 𝐴 ) )
56 54 55 syl5bi ( ( 𝐴P ∧ ( *Q𝑥 ) ∈ 𝐴 ) → ( 𝑥 <Q 𝑦 → ( *Q𝑦 ) ∈ 𝐴 ) )
57 56 alrimiv ( ( 𝐴P ∧ ( *Q𝑥 ) ∈ 𝐴 ) → ∀ 𝑦 ( 𝑥 <Q 𝑦 → ( *Q𝑦 ) ∈ 𝐴 ) )
58 1 abeq2i ( 𝑥𝐵 ↔ ∃ 𝑦 ( 𝑥 <Q 𝑦 ∧ ¬ ( *Q𝑦 ) ∈ 𝐴 ) )
59 exanali ( ∃ 𝑦 ( 𝑥 <Q 𝑦 ∧ ¬ ( *Q𝑦 ) ∈ 𝐴 ) ↔ ¬ ∀ 𝑦 ( 𝑥 <Q 𝑦 → ( *Q𝑦 ) ∈ 𝐴 ) )
60 58 59 bitri ( 𝑥𝐵 ↔ ¬ ∀ 𝑦 ( 𝑥 <Q 𝑦 → ( *Q𝑦 ) ∈ 𝐴 ) )
61 60 con2bii ( ∀ 𝑦 ( 𝑥 <Q 𝑦 → ( *Q𝑦 ) ∈ 𝐴 ) ↔ ¬ 𝑥𝐵 )
62 57 61 sylib ( ( 𝐴P ∧ ( *Q𝑥 ) ∈ 𝐴 ) → ¬ 𝑥𝐵 )
63 53 62 jca ( ( 𝐴P ∧ ( *Q𝑥 ) ∈ 𝐴 ) → ( 𝑥Q ∧ ¬ 𝑥𝐵 ) )
64 63 eximi ( ∃ 𝑥 ( 𝐴P ∧ ( *Q𝑥 ) ∈ 𝐴 ) → ∃ 𝑥 ( 𝑥Q ∧ ¬ 𝑥𝐵 ) )
65 48 64 syl ( ( 𝐴P𝑧𝐴 ) → ∃ 𝑥 ( 𝑥Q ∧ ¬ 𝑥𝐵 ) )
66 65 ex ( 𝐴P → ( 𝑧𝐴 → ∃ 𝑥 ( 𝑥Q ∧ ¬ 𝑥𝐵 ) ) )
67 66 exlimdv ( 𝐴P → ( ∃ 𝑧 𝑧𝐴 → ∃ 𝑥 ( 𝑥Q ∧ ¬ 𝑥𝐵 ) ) )
68 n0 ( 𝐴 ≠ ∅ ↔ ∃ 𝑧 𝑧𝐴 )
69 nss ( ¬ Q𝐵 ↔ ∃ 𝑥 ( 𝑥Q ∧ ¬ 𝑥𝐵 ) )
70 67 68 69 3imtr4g ( 𝐴P → ( 𝐴 ≠ ∅ → ¬ Q𝐵 ) )
71 36 70 mpd ( 𝐴P → ¬ Q𝐵 )
72 ltrelnq <Q ⊆ ( Q × Q )
73 72 brel ( 𝑥 <Q 𝑦 → ( 𝑥Q𝑦Q ) )
74 73 simpld ( 𝑥 <Q 𝑦𝑥Q )
75 74 adantr ( ( 𝑥 <Q 𝑦 ∧ ¬ ( *Q𝑦 ) ∈ 𝐴 ) → 𝑥Q )
76 75 exlimiv ( ∃ 𝑦 ( 𝑥 <Q 𝑦 ∧ ¬ ( *Q𝑦 ) ∈ 𝐴 ) → 𝑥Q )
77 58 76 sylbi ( 𝑥𝐵𝑥Q )
78 77 ssriv 𝐵Q
79 71 78 jctil ( 𝐴P → ( 𝐵Q ∧ ¬ Q𝐵 ) )
80 dfpss3 ( 𝐵Q ↔ ( 𝐵Q ∧ ¬ Q𝐵 ) )
81 79 80 sylibr ( 𝐴P𝐵Q )
82 35 81 jca ( 𝐴P → ( ∅ ⊊ 𝐵𝐵Q ) )
83 ltsonq <Q Or Q
84 83 72 sotri ( ( 𝑧 <Q 𝑥𝑥 <Q 𝑦 ) → 𝑧 <Q 𝑦 )
85 84 ex ( 𝑧 <Q 𝑥 → ( 𝑥 <Q 𝑦𝑧 <Q 𝑦 ) )
86 85 anim1d ( 𝑧 <Q 𝑥 → ( ( 𝑥 <Q 𝑦 ∧ ¬ ( *Q𝑦 ) ∈ 𝐴 ) → ( 𝑧 <Q 𝑦 ∧ ¬ ( *Q𝑦 ) ∈ 𝐴 ) ) )
87 86 eximdv ( 𝑧 <Q 𝑥 → ( ∃ 𝑦 ( 𝑥 <Q 𝑦 ∧ ¬ ( *Q𝑦 ) ∈ 𝐴 ) → ∃ 𝑦 ( 𝑧 <Q 𝑦 ∧ ¬ ( *Q𝑦 ) ∈ 𝐴 ) ) )
88 87 58 24 3imtr4g ( 𝑧 <Q 𝑥 → ( 𝑥𝐵𝑧𝐵 ) )
89 88 com12 ( 𝑥𝐵 → ( 𝑧 <Q 𝑥𝑧𝐵 ) )
90 89 alrimiv ( 𝑥𝐵 → ∀ 𝑧 ( 𝑧 <Q 𝑥𝑧𝐵 ) )
91 nfe1 𝑦𝑦 ( 𝑥 <Q 𝑦 ∧ ¬ ( *Q𝑦 ) ∈ 𝐴 )
92 91 nfab 𝑦 { 𝑥 ∣ ∃ 𝑦 ( 𝑥 <Q 𝑦 ∧ ¬ ( *Q𝑦 ) ∈ 𝐴 ) }
93 1 92 nfcxfr 𝑦 𝐵
94 nfv 𝑦 𝑥 <Q 𝑧
95 93 94 nfrex 𝑦𝑧𝐵 𝑥 <Q 𝑧
96 19.8a ( ( 𝑧 <Q 𝑦 ∧ ¬ ( *Q𝑦 ) ∈ 𝐴 ) → ∃ 𝑦 ( 𝑧 <Q 𝑦 ∧ ¬ ( *Q𝑦 ) ∈ 𝐴 ) )
97 96 24 sylibr ( ( 𝑧 <Q 𝑦 ∧ ¬ ( *Q𝑦 ) ∈ 𝐴 ) → 𝑧𝐵 )
98 97 adantll ( ( ( 𝑥 <Q 𝑧𝑧 <Q 𝑦 ) ∧ ¬ ( *Q𝑦 ) ∈ 𝐴 ) → 𝑧𝐵 )
99 simpll ( ( ( 𝑥 <Q 𝑧𝑧 <Q 𝑦 ) ∧ ¬ ( *Q𝑦 ) ∈ 𝐴 ) → 𝑥 <Q 𝑧 )
100 98 99 jca ( ( ( 𝑥 <Q 𝑧𝑧 <Q 𝑦 ) ∧ ¬ ( *Q𝑦 ) ∈ 𝐴 ) → ( 𝑧𝐵𝑥 <Q 𝑧 ) )
101 100 expcom ( ¬ ( *Q𝑦 ) ∈ 𝐴 → ( ( 𝑥 <Q 𝑧𝑧 <Q 𝑦 ) → ( 𝑧𝐵𝑥 <Q 𝑧 ) ) )
102 101 eximdv ( ¬ ( *Q𝑦 ) ∈ 𝐴 → ( ∃ 𝑧 ( 𝑥 <Q 𝑧𝑧 <Q 𝑦 ) → ∃ 𝑧 ( 𝑧𝐵𝑥 <Q 𝑧 ) ) )
103 ltbtwnnq ( 𝑥 <Q 𝑦 ↔ ∃ 𝑧 ( 𝑥 <Q 𝑧𝑧 <Q 𝑦 ) )
104 df-rex ( ∃ 𝑧𝐵 𝑥 <Q 𝑧 ↔ ∃ 𝑧 ( 𝑧𝐵𝑥 <Q 𝑧 ) )
105 102 103 104 3imtr4g ( ¬ ( *Q𝑦 ) ∈ 𝐴 → ( 𝑥 <Q 𝑦 → ∃ 𝑧𝐵 𝑥 <Q 𝑧 ) )
106 105 impcom ( ( 𝑥 <Q 𝑦 ∧ ¬ ( *Q𝑦 ) ∈ 𝐴 ) → ∃ 𝑧𝐵 𝑥 <Q 𝑧 )
107 95 106 exlimi ( ∃ 𝑦 ( 𝑥 <Q 𝑦 ∧ ¬ ( *Q𝑦 ) ∈ 𝐴 ) → ∃ 𝑧𝐵 𝑥 <Q 𝑧 )
108 58 107 sylbi ( 𝑥𝐵 → ∃ 𝑧𝐵 𝑥 <Q 𝑧 )
109 90 108 jca ( 𝑥𝐵 → ( ∀ 𝑧 ( 𝑧 <Q 𝑥𝑧𝐵 ) ∧ ∃ 𝑧𝐵 𝑥 <Q 𝑧 ) )
110 109 rgen 𝑥𝐵 ( ∀ 𝑧 ( 𝑧 <Q 𝑥𝑧𝐵 ) ∧ ∃ 𝑧𝐵 𝑥 <Q 𝑧 )
111 elnp ( 𝐵P ↔ ( ( ∅ ⊊ 𝐵𝐵Q ) ∧ ∀ 𝑥𝐵 ( ∀ 𝑧 ( 𝑧 <Q 𝑥𝑧𝐵 ) ∧ ∃ 𝑧𝐵 𝑥 <Q 𝑧 ) ) )
112 82 110 111 sylanblrc ( 𝐴P𝐵P )