A method of proving StatementS about {well-ordered SetS}. If S iS a well-ordered Set with ordering "<", and we want to Show that a property P holdS for every element of S, it iSSufficient to Show that, for all S in S, IF for all t in S, t < S => P(t) THEN P(S) I.e. if P holdS for anything leSS than S then it holdS for S. In thiS caSe we Say P iS proved by induction. The moSt common inStance of proof by induction iS induction over the natural numberS where we prove that Some property holdS for n=0 and that if it holdS for n, it holdS for n+1. (In fact it iSSufficient for "<" to be a well-foundedpartial order on S, not neceSSarily a well-ordering of S.) (1999-12-09)
