On Wednesday, September 7, 2022 at 10:22:19 PM UTC-4, Dan Christensen wrote:
> On Wednesday, September 7, 2022 at 8:00:09 PM UTC-4, Mostowski Collapse wrote:
> > Pitty DC Proof cannot prove:
> >
> > Proposition: 4.2.5 If A is a set and F : A -> B then F is a set.
> No need to. It is easy, however, to reconstruct graph g of function f in DC Proof (only 60 lines):
>
> ALL(a):ALL(b):ALL(f):[Set(a) & Set(b) & ALL(c):[c in a => f(c) in b]
> => EXIST(g):[Set'(g)
> & ALL(c):ALL(d):[(c,d) in g => c in a & d in b]
> & ALL(c):ALL(d):[c in a & d in b => [(c,d) in g <=> f(c)=d]]]]
PROOF
Suppose...
1 Set(x) & Set(y) & ALL(c):[c in x => f(c) in y]
Premise
2 Set(x)
Split, 1
3 Set(y)
Split, 1
4 ALL(c):[c in x => f(c) in y]
Split, 1
Apply Cartesian Product Axiom
5 ALL(a1):ALL(a2):[Set(a1) & Set(a2) => EXIST(b):[Set'(b) & ALL(c1):ALL(c2):[(c1,c2) in b <=> c1 in a1 & c2 in a2]]]
Cart Prod
6 ALL(a2):[Set(x) & Set(a2) => EXIST(b):[Set'(b) & ALL(c1):ALL(c2):[(c1,c2) in b <=> c1 in x & c2 in a2]]]
U Spec, 5
7 Set(x) & Set(y) => EXIST(b):[Set'(b) & ALL(c1):ALL(c2):[(c1,c2) in b <=> c1 in x & c2 in y]]
U Spec, 6
8 Set(x) & Set(y)
Join, 2, 3
9 EXIST(b):[Set'(b) & ALL(c1):ALL(c2):[(c1,c2) in b <=> c1 in x & c2 in y]]
Detach, 7, 8
10 Set'(xy) & ALL(c1):ALL(c2):[(c1,c2) in xy <=> c1 in x & c2 in y]
E Spec, 9
Define: xy (Cartesian product x*y)
11 Set'(xy)
Split, 10
12 ALL(c1):ALL(c2):[(c1,c2) in xy <=> c1 in x & c2 in y]
Split, 10
Apply Subset Axiom
13 EXIST(sub):[Set'(sub) & ALL(a):ALL(b):[(a,b) in sub <=> (a,b) in xy & f(a)=b]]
Subset, 11
14 Set'(g) & ALL(a):ALL(b):[(a,b) in g <=> (a,b) in xy & f(a)=b]
E Spec, 13
Define: g (graph set for function f)
15 Set'(g)
Split, 14
16 ALL(a):ALL(b):[(a,b) in g <=> (a,b) in xy & f(a)=b]
Split, 14
Prove: ALL(c):ALL(d):[c in x & d in y => [(c,d) in g <=> f(c)=d]]
Suppose...
17 t in x & u in y
Premise
18 t in x
Split, 17
19 u in y
Split, 17
Suppose...
20 (t,u) in g
Premise
21 ALL(b):[(t,b) in g <=> (t,b) in xy & f(t)=b]
U Spec, 16
22 (t,u) in g <=> (t,u) in xy & f(t)=u
U Spec, 21
23 [(t,u) in g => (t,u) in xy & f(t)=u]
& [(t,u) in xy & f(t)=u => (t,u) in g]
Iff-And, 22
24 (t,u) in g => (t,u) in xy & f(t)=u
Split, 23
25 (t,u) in xy & f(t)=u
Detach, 24, 20
26 (t,u) in xy
Split, 25
27 f(t)=u
Split, 25
As Required:
28 (t,u) in g => f(t)=u
Conclusion, 20
Prove: f(t)=u => (t,u) in g
Suppose...
29 f(t)=u
Premise
30 ALL(b):[(t,b) in g <=> (t,b) in xy & f(t)=b]
U Spec, 16
31 (t,u) in g <=> (t,u) in xy & f(t)=u
U Spec, 30
32 [(t,u) in g => (t,u) in xy & f(t)=u]
& [(t,u) in xy & f(t)=u => (t,u) in g]
Iff-And, 31
33 (t,u) in xy & f(t)=u => (t,u) in g
Split, 32
34 ALL(c2):[(t,c2) in xy <=> t in x & c2 in y]
U Spec, 12
35 (t,u) in xy <=> t in x & u in y
U Spec, 34
36 [(t,u) in xy => t in x & u in y]
& [t in x & u in y => (t,u) in xy]
Iff-And, 35
37 t in x & u in y => (t,u) in xy
Split, 36
38 (t,u) in xy
Detach, 37, 17
39 (t,u) in xy & f(t)=u
Join, 38, 29
40 (t,u) in g
Detach, 33, 39
As Required:
41 f(t)=u => (t,u) in g
Conclusion, 29
42 [(t,u) in g => f(t)=u] & [f(t)=u => (t,u) in g]
Join, 28, 41
43 (t,u) in g <=> f(t)=u
Iff-And, 42
As Required:
44 ALL(c):ALL(d):[c in x & d in y => [(c,d) in g <=> f(c)=d]]
Conclusion, 17
Prove: ALL(c):ALL(d):[(c,d) in g => c in x & d in y]
Suppose...
45 (t,u) in g
Premise
46 ALL(b):[(t,b) in g <=> (t,b) in xy & f(t)=b]
U Spec, 16
47 (t,u) in g <=> (t,u) in xy & f(t)=u
U Spec, 46
48 [(t,u) in g => (t,u) in xy & f(t)=u]
& [(t,u) in xy & f(t)=u => (t,u) in g]
Iff-And, 47
49 (t,u) in g => (t,u) in xy & f(t)=u
Split, 48
50 (t,u) in xy & f(t)=u
Detach, 49, 45
51 (t,u) in xy
Split, 50
52 ALL(c2):[(t,c2) in xy <=> t in x & c2 in y]
U Spec, 12
53 (t,u) in xy <=> t in x & u in y
U Spec, 52
54 [(t,u) in xy => t in x & u in y]
& [t in x & u in y => (t,u) in xy]
Iff-And, 53
55 (t,u) in xy => t in x & u in y
Split, 54
56 t in x & u in y
Detach, 55, 51
As Required:
57 ALL(c):ALL(d):[(c,d) in g => c in x & d in y]
Conclusion, 45
58 Set'(g)
& ALL(c):ALL(d):[(c,d) in g => c in x & d in y]
Join, 15, 57
59 Set'(g)
& ALL(c):ALL(d):[(c,d) in g => c in x & d in y]
& ALL(c):ALL(d):[c in x & d in y => [(c,d) in g <=> f(c)=d]]
Join, 58, 44
As Required:
60 ALL(a):ALL(b):ALL(f):[Set(a) & Set(b) & ALL(c):[c in a => f(c) in b]
=> EXIST(g):[Set'(g)
& ALL(c):ALL(d):[(c,d) in g => c in a & d in b]
& ALL(c):ALL(d):[c in a & d in b => [(c,d) in g <=> f(c)=d]]]]
Conclusion, 1