Re:Believe It, Then Don’t: Toward a Pedagogy of Discomfort
by dullcrisp on Sunday March 20, 2016 @10:26PM
(#11325818)
Induction, I would suppose.
Base case: There is no injection from a non-empty set to the empty set.
Inductive case: Let A be a set of size (m+1) and B be a set of size (n+1), and let f be an injection from A to B. Pick x in A.
Since f(y) is not equal to f(x) for any y not equal to x in A, the restriction of f to A\{x} is an injection into B\{f(x)}; and presumably you believe that A\{x} has size m and B\{f(x)} has size n. Then we've produced an injection from a set of size m to a set of size n.
Thus if there is no injection from a set of size m to a set of size n, then there isn't one from a set of size (m+1) to one of size (n+1).
Base case: There is no injection from a non-empty set to the empty set.
Inductive case: Let A be a set of size (m+1) and B be a set of size (n+1), and let f be an injection from A to B. Pick x in A.
Since f(y) is not equal to f(x) for any y not equal to x in A, the restriction of f to A\{x} is an injection into B\{f(x)}; and presumably you believe that A\{x} has size m and B\{f(x)} has size n. Then we've produced an injection from a set of size m to a set of size n.
Thus if there is no injection from a set of size m to a set of size n, then there isn't one from a set of size (m+1) to one of size (n+1).