Question

Show that if \(A \subseteq B\) and there is an injection \(g: B \rightarrow A,\) then \(|A|=|B|\)

Short answer

By forming a bijective function from A to B, it has been shown that the cardinalities of set A and set B are equal, i.e., |A| = |B|.

Step-by-step solution

Analyze the given

We are given a set A is a subset of B. This means that every element in set A is also in set B. We are also given a function g that is an injection or one-to-one from B to A. A one-to-one function from set B to A indicates that each element of set B maps to a unique element in set A.

Define a function

Now, let's define a function f: A ⟶ B as follows: For an element a in A, if there exists an element b in B such that g(b) = a, then f(a) = b; otherwise, f(a) = a.

Establish that f is a bijection

Next, we establish that function f is a bijection. \n\nInjectivity: f is an injection - assume f(a1) = f(a2) for some a1, a2 in A. If there are elements b1, b2 in B such that g(b1) = a1 and g(b2) = a2, then b1 = f(a1) = f(a2) = b2. But, as given, g is an injection so b1=b2 implies a1=a2. If there is no such b in B for any of the a in A, then a1 = f(a1) = f(a2) = a2. So f(a1) = f(a2) implies a1 = a2, hence f is an injection. \n\nSurjectivity: f is a surjection - for each b in B, if there is an a in A such that g(b) = a, then f(a) = b; otherwise, there exists b in A (since A is a subset of B), such that f(b) = b. Therefore, f covers all elements of B and hence, f is a surjection.\n\nSince f is both an injection and surjection, f is a bijection which means that |A| = |B|.

Conclusion

Since we have established that there is a bijection from set A to set B, it implies that the cardinalities of the two sets are equal, i.e., |A| = |B|, thus proving the statement.