902 apply fast |
902 apply fast |
903 apply (rule LeastI2) |
903 apply (rule LeastI2) |
904 apply (auto elim: monoD intro!: order_antisym) |
904 apply (auto elim: monoD intro!: order_antisym) |
905 done |
905 done |
906 |
906 |
|
907 |
|
908 section {* Transitivity rules for calculational reasoning *} |
|
909 |
|
910 lemma forw_subst: "a = b ==> P b ==> P a" |
|
911 by (rule ssubst) |
|
912 |
|
913 lemma back_subst: "P a ==> a = b ==> P b" |
|
914 by (rule subst) |
|
915 |
|
916 lemma set_rev_mp: "x:A ==> A <= B ==> x:B" |
|
917 by (rule subsetD) |
|
918 |
|
919 lemma set_mp: "A <= B ==> x:A ==> x:B" |
|
920 by (rule subsetD) |
|
921 |
|
922 lemma order_neq_le_trans: "a ~= b ==> (a::'a::order) <= b ==> a < b" |
|
923 by (simp add: order_less_le) |
|
924 |
|
925 lemma order_le_neq_trans: "(a::'a::order) <= b ==> a ~= b ==> a < b" |
|
926 by (simp add: order_less_le) |
|
927 |
|
928 lemma order_less_asym': "(a::'a::order) < b ==> b < a ==> P" |
|
929 by (rule order_less_asym) |
|
930 |
|
931 lemma ord_le_eq_trans: "a <= b ==> b = c ==> a <= c" |
|
932 by (rule subst) |
|
933 |
|
934 lemma ord_eq_le_trans: "a = b ==> b <= c ==> a <= c" |
|
935 by (rule ssubst) |
|
936 |
|
937 lemma ord_less_eq_trans: "a < b ==> b = c ==> a < c" |
|
938 by (rule subst) |
|
939 |
|
940 lemma ord_eq_less_trans: "a = b ==> b < c ==> a < c" |
|
941 by (rule ssubst) |
|
942 |
|
943 lemma order_less_subst2: "(a::'a::order) < b ==> f b < (c::'c::order) ==> |
|
944 (!!x y. x < y ==> f x < f y) ==> f a < c" |
|
945 proof - |
|
946 assume r: "!!x y. x < y ==> f x < f y" |
|
947 assume "a < b" hence "f a < f b" by (rule r) |
|
948 also assume "f b < c" |
|
949 finally (order_less_trans) show ?thesis . |
|
950 qed |
|
951 |
|
952 lemma order_less_subst1: "(a::'a::order) < f b ==> (b::'b::order) < c ==> |
|
953 (!!x y. x < y ==> f x < f y) ==> a < f c" |
|
954 proof - |
|
955 assume r: "!!x y. x < y ==> f x < f y" |
|
956 assume "a < f b" |
|
957 also assume "b < c" hence "f b < f c" by (rule r) |
|
958 finally (order_less_trans) show ?thesis . |
|
959 qed |
|
960 |
|
961 lemma order_le_less_subst2: "(a::'a::order) <= b ==> f b < (c::'c::order) ==> |
|
962 (!!x y. x <= y ==> f x <= f y) ==> f a < c" |
|
963 proof - |
|
964 assume r: "!!x y. x <= y ==> f x <= f y" |
|
965 assume "a <= b" hence "f a <= f b" by (rule r) |
|
966 also assume "f b < c" |
|
967 finally (order_le_less_trans) show ?thesis . |
|
968 qed |
|
969 |
|
970 lemma order_le_less_subst1: "(a::'a::order) <= f b ==> (b::'b::order) < c ==> |
|
971 (!!x y. x < y ==> f x < f y) ==> a < f c" |
|
972 proof - |
|
973 assume r: "!!x y. x < y ==> f x < f y" |
|
974 assume "a <= f b" |
|
975 also assume "b < c" hence "f b < f c" by (rule r) |
|
976 finally (order_le_less_trans) show ?thesis . |
|
977 qed |
|
978 |
|
979 lemma order_less_le_subst2: "(a::'a::order) < b ==> f b <= (c::'c::order) ==> |
|
980 (!!x y. x < y ==> f x < f y) ==> f a < c" |
|
981 proof - |
|
982 assume r: "!!x y. x < y ==> f x < f y" |
|
983 assume "a < b" hence "f a < f b" by (rule r) |
|
984 also assume "f b <= c" |
|
985 finally (order_less_le_trans) show ?thesis . |
|
986 qed |
|
987 |
|
988 lemma order_less_le_subst1: "(a::'a::order) < f b ==> (b::'b::order) <= c ==> |
|
989 (!!x y. x <= y ==> f x <= f y) ==> a < f c" |
|
990 proof - |
|
991 assume r: "!!x y. x <= y ==> f x <= f y" |
|
992 assume "a < f b" |
|
993 also assume "b <= c" hence "f b <= f c" by (rule r) |
|
994 finally (order_less_le_trans) show ?thesis . |
|
995 qed |
|
996 |
|
997 lemma order_subst1: "(a::'a::order) <= f b ==> (b::'b::order) <= c ==> |
|
998 (!!x y. x <= y ==> f x <= f y) ==> a <= f c" |
|
999 proof - |
|
1000 assume r: "!!x y. x <= y ==> f x <= f y" |
|
1001 assume "a <= f b" |
|
1002 also assume "b <= c" hence "f b <= f c" by (rule r) |
|
1003 finally (order_trans) show ?thesis . |
|
1004 qed |
|
1005 |
|
1006 lemma order_subst2: "(a::'a::order) <= b ==> f b <= (c::'c::order) ==> |
|
1007 (!!x y. x <= y ==> f x <= f y) ==> f a <= c" |
|
1008 proof - |
|
1009 assume r: "!!x y. x <= y ==> f x <= f y" |
|
1010 assume "a <= b" hence "f a <= f b" by (rule r) |
|
1011 also assume "f b <= c" |
|
1012 finally (order_trans) show ?thesis . |
|
1013 qed |
|
1014 |
|
1015 lemma ord_le_eq_subst: "a <= b ==> f b = c ==> |
|
1016 (!!x y. x <= y ==> f x <= f y) ==> f a <= c" |
|
1017 proof - |
|
1018 assume r: "!!x y. x <= y ==> f x <= f y" |
|
1019 assume "a <= b" hence "f a <= f b" by (rule r) |
|
1020 also assume "f b = c" |
|
1021 finally (ord_le_eq_trans) show ?thesis . |
|
1022 qed |
|
1023 |
|
1024 lemma ord_eq_le_subst: "a = f b ==> b <= c ==> |
|
1025 (!!x y. x <= y ==> f x <= f y) ==> a <= f c" |
|
1026 proof - |
|
1027 assume r: "!!x y. x <= y ==> f x <= f y" |
|
1028 assume "a = f b" |
|
1029 also assume "b <= c" hence "f b <= f c" by (rule r) |
|
1030 finally (ord_eq_le_trans) show ?thesis . |
|
1031 qed |
|
1032 |
|
1033 lemma ord_less_eq_subst: "a < b ==> f b = c ==> |
|
1034 (!!x y. x < y ==> f x < f y) ==> f a < c" |
|
1035 proof - |
|
1036 assume r: "!!x y. x < y ==> f x < f y" |
|
1037 assume "a < b" hence "f a < f b" by (rule r) |
|
1038 also assume "f b = c" |
|
1039 finally (ord_less_eq_trans) show ?thesis . |
|
1040 qed |
|
1041 |
|
1042 lemma ord_eq_less_subst: "a = f b ==> b < c ==> |
|
1043 (!!x y. x < y ==> f x < f y) ==> a < f c" |
|
1044 proof - |
|
1045 assume r: "!!x y. x < y ==> f x < f y" |
|
1046 assume "a = f b" |
|
1047 also assume "b < c" hence "f b < f c" by (rule r) |
|
1048 finally (ord_eq_less_trans) show ?thesis . |
|
1049 qed |
|
1050 |
|
1051 text {* |
|
1052 Note that this list of rules is in reverse order of priorities. |
|
1053 *} |
|
1054 |
|
1055 lemmas basic_trans_rules [trans] = |
|
1056 order_less_subst2 |
|
1057 order_less_subst1 |
|
1058 order_le_less_subst2 |
|
1059 order_le_less_subst1 |
|
1060 order_less_le_subst2 |
|
1061 order_less_le_subst1 |
|
1062 order_subst2 |
|
1063 order_subst1 |
|
1064 ord_le_eq_subst |
|
1065 ord_eq_le_subst |
|
1066 ord_less_eq_subst |
|
1067 ord_eq_less_subst |
|
1068 forw_subst |
|
1069 back_subst |
|
1070 rev_mp |
|
1071 mp |
|
1072 set_rev_mp |
|
1073 set_mp |
|
1074 order_neq_le_trans |
|
1075 order_le_neq_trans |
|
1076 order_less_trans |
|
1077 order_less_asym' |
|
1078 order_le_less_trans |
|
1079 order_less_le_trans |
|
1080 order_trans |
|
1081 order_antisym |
|
1082 ord_le_eq_trans |
|
1083 ord_eq_le_trans |
|
1084 ord_less_eq_trans |
|
1085 ord_eq_less_trans |
|
1086 trans |
|
1087 |
907 end |
1088 end |