Prove that a function f : A -> B is one to one if and only if any non-empty subset S ⊆ A, f^-1 (f(S)) = S. DO NOT assume a priori that the inverse function f^-1 exists; in this question f^-1 (S) denotes the pre-image of S.
To prove that a function f: A -> B is one-to-one if and only if for any non-empty subset S ⊆ A, f^(-1)(f(S)) = S, we need to prove both directions of the statement.
First, let's assume that f is one-to-one.
To prove: For any non-empty subset S ⊆ A, f^(-1)(f(S)) = S.
1. Let's take an arbitrary non-empty subset S ⊆ A.
2. We need to show that f^(-1)(f(S)) = S.
3. Consider an arbitrary element x ∈ S.
4. Since f is one-to-one, each element in S will correspond to a unique element in f(S).
5. So, for each x ∈ S, there exists a unique element y ∈ f(S) such that f(x) = y.
6. Now, let's consider an arbitrary element y ∈ f(S).
7. Since y ∈ f(S), there exists an element x' ∈ S such that f(x') = y.
8. Since f(x) = y and f(x') = y, it implies x = x'.
9. Therefore, for each y ∈ f(S), there exists a unique element x ∈ S such that f(x) = y.
10. This means that f^(-1)(f(S)) consists of all the elements in S.
11. Also, since each element in S has a unique pre-image in f^(-1)(f(S)), it implies that f^(-1)(f(S)) does not contain any elements outside of S.
12. Hence, f^(-1)(f(S)) = S.
Now, let's prove the other direction, assuming that for any non-empty subset S ⊆ A, f^(-1)(f(S)) = S.
To prove: f is one-to-one.
1. Let's assume that f is not one-to-one.
2. This means there exist two distinct elements x1, x2 ∈ A such that f(x1) = f(x2).
3. Let's consider the subset S = {x1} ⊆ A.
4. Since x1 ∈ S, we have f^(-1)(f(S)) = S (from the given assumption).
5. Therefore, x1 ∈ f^(-1)(f(S)).
6. Since f(x1) = f(x2), it implies that x2 ∈ f^(-1)(f(S)).
7. But x1 and x2 are distinct, which contradicts the assumption that f^(-1)(f(S)) = S.
8. Hence, our assumption that f is not one-to-one must be false.
9. Therefore, f is one-to-one.
By proving both directions, we have established that a function f: A -> B is one-to-one if and only if for any non-empty subset S ⊆ A, f^(-1)(f(S)) = S.