proposition: Theorem split_interval : { g : nat -> nat & { h | (forall j, j <= n -> g j <= n) /\ (forall j, j <= n -> h j <= n) /\ (forall j, g (h j) = j) /\ (forall j, h (g j) = j) /\ g i = n } }.
proof: Proof. Proof using Hi. exists g, h. split; [ | split; [ | split; [ | split ] ] ]; auto. + intros j; unfold h. destruct (le_lt_dec (S n) j) as [ | H1 ]; auto. destruct (le_lt_dec n j) as [ H2 | H2 ]. { unfold g. destruct (le_lt_dec (S n) i); try lia. destruct (le_lt_dec i i); lia. } destruct (le_lt_dec i j) as [ H3 | H3 ]. { unfold g. destruct (le_lt_dec (S n) (j+1)); try lia. destruct (le_lt_dec i (j+1)); try lia. destruct (le_lt_dec (j+1) i); lia. } { unfold g. destruct (le_lt_dec (S n) j); try lia. destruct (le_lt_dec i j); try lia. } + intros j; unfold g. destruct (le_lt_dec (S n) j) as [ | H1 ]; auto. destruct (le_lt_dec i j) as [ H2 | H2 ]. destruct (le_lt_dec j i) as [ H3 | H3 ]. { unfold h. destruct (le_lt_dec (S n) n); try lia. destruct (le_lt_dec n n); lia. } { unfold h. destruct (le_lt_dec (S n) (j-1)); try lia. destruct (le_lt_dec n (j-1)); try lia. destruct (le_lt_dec i (j-1)); lia. } { unfold h. destruct (le_lt_dec (S n) j); try lia. destruct (le_lt_dec n j); try lia. destruct (le_lt_dec i j); lia. } + unfold g. destruct (le_lt_dec (S n) i); try lia. destruct (le_lt_dec i i); lia. Qed.
imports: List Arith Lia Undecidability.Shared.Libs.DLW.Utils(utils_tac utils_list sums php)