advancedresearch / prop

Propositional logic with types in Rust
MIT License
59 stars 2 forks source link

Proper handling of monic and epic functions in `id` and `comp` module #1734

Closed bvssvni closed 1 year ago

bvssvni commented 1 year ago

Currently, it is possible to prove that every function is both monic and epic, due to the axioms:

(f : a -> b) ⋀ (f . inv(f))  =>  id{b}
(f : a -> b) ⋀ id{b}  =>  (f . inv(f))
(f : a -> b) ⋀ (inv(f) . f)  =>  id{a}
(f : a -> b) ⋀ id{a}  =>  (inv(f). f)

This should be changed to:

~(f . inv(f)) ⋀ (f : a -> b) ⋀ (f . inv(f))  =>  id{b}
~((f . inv(f))) ⋀ (f : a -> b) ⋀ id{b}  =>  (f . inv(f))
~(inv(f) . f) ⋀ (f : a -> b) ⋀ (inv(f) . f)  =>  id{a}
~(inv(f). f) ⋀ (f : a -> b) ⋀ id{a}  =>  (inv(f). f)

Here: