Question

Let \(f\) be a mapping, and \(A \subseteq D_{f} .\) Prove that (i) if \(A\) is countable, so is \(f[A]\); (ii) if \(f\) is one to one and \(A\) is uncountable, so is \(f[A]\).

Short answer

(i) If \(A\) is countable, \(f[A]\) is countable; (ii) if \(f\) is one-to-one and \(A\) is uncountable, so is \(f[A]\).

Step-by-step solution

Define Countability

A set is countable if it is either finite or has the same cardinality as the set of natural numbers, i.e., it can be put in a one-to-one correspondence with \(\mathbb{N}\). An uncountable set is one that is not countable.

Demonstrate (i) If \(A\) is countable, \(f[A]\) is countable

Given a countable set \(A\), every element in \(f[A]\) is equal to \(f(a)\) for some \(a \in A\). Define a function \(g: A \rightarrow f[A]\), where \(g(a) = f(a)\). Thus, each element of \(f[A]\) corresponds to an element in \(A\), meaning \(f[A]\) can be put in a one-to-one correspondence with a subset of \(A\). Since \(A\) is countable, \(f[A]\) must be countable as well. Hence, \(f[A]\) is either finite or countable.

Demonstrate (ii) If \(f\) is one-to-one and \(A\) is uncountable, so is \(f[A]\)

Assume \(f\) is one-to-one (injective) and \(A\) is uncountable. For each different element \(a_1 eq a_2 \in A\), the one-to-one property ensures that \(f(a_1) eq f(a_2)\). This means \(f\) creates no duplicates in \(f[A]\). Consequently, \(f[A]\) must also be uncountable as there exists a bijection between \(A\) and \(f[A]\) since \(f\) is injective. Therefore, the cardinality of \(f[A]\) is equal to the cardinality of \(A\), confirming \(f[A]\) is uncountable.

Key concepts

one-to-one mapping

A one-to-one mapping, often called an "injective function," is a type of mathematical function where each element in the domain maps to a unique element in the codomain. This means that if you have two different elements in the domain, their images cannot be the same in the codomain. In mathematical terms, for a function \( f: A \rightarrow B \), if \( f(a_1) = f(a_2) \) implies \( a_1 = a_2 \), then \( f \) is injective.
The importance of injective functions lies in their ability to maintain distinctness of elements when mapping them from one set to another. This property is crucial when determining countability, especially when exploring how elements of one set correspond to another set without creating duplicates.

• Ensures no two different elements in the domain map to the same element in the codomain.
• Important for demonstrating the relationship between uncountable sets.

finite set

A finite set is a collection of distinct elements that has a specific number of members, which we can count entirely. This means the set ends after a certain number of elements, unlike infinite sets that continue indefinitely. Examples of finite sets include the set of letters in the Word "Apple", {A, p, l, e}, or the set of numbers {1, 2, 3, 4}. Finite sets play a significant role in discussing countability because every finite set is countable by definition.

• Contains a fixed, countable number of elements.
• Contrast with infinite sets, which cannot be completely counted.

natural numbers

Natural numbers are the set of positive integers starting from 1 and going onwards, i.e., \( \mathbb{N} = \{1, 2, 3, 4, \ldots\} \). They form the basis of counting and order in mathematics. In discussions of countability, natural numbers are the standard measure of a set's size, notably if comparing to other infinite sets.
When a set is said to be countably infinite, it implies there's a one-to-one correspondence with the set of natural numbers. If you can list the elements of a set just like natural numbers (even if it goes on forever), it's countably infinite.

• Commonly used to demonstrate the concept of countability.
• The smallest infinite set.
• Helps to understand other concepts like integers or rational numbers when discussing countability.

bijection

A bijection, or bijective function, is a type of function where every element from one set corresponds to exactly one element in another set, and vice versa. This kind of function combines properties of both injective and surjective functions, meaning it's both one-to-one and onto.
To have a bijection between two sets implies that they have the same cardinality or size, which is crucial for talking about countability. If there's a bijection from set \(A\) to set \(B\), we say \(A\) and \(B\) are of the same size—even if they're infinite.

• Ensures a perfect pair-up of elements between two sets.
• Crucial for demonstrating that two sets have the same cardinality.
• Used in algebraic structures and many branches of mathematics to establish isomorphisms.