Let’s start with the definitions.
Definition: “Let S be a set. If there are exactly n distinct elements in S where n is a nonnegative integer, we say that S is a finite set and that n is the cardinality of S. The cardinality of S is denoted by |S|.”
Definition: “If there is a one-to-one function from A to B, the cardinality of A is less than or the same as the cardinality of B and we write |A| ≤ |B|. Moreover, when |A| ≤ |B| and A and B have different cardinality, we say that the cardinality of A is less than the cardinality of B and we write |A| < |B|.”
Definition: “A function f is said to be one-to-one, or an injunction, if and only if f (a) = f (b) implies that a = b for all a and b in the domain of f. A function is said to be injective if it is one-to-one.”
Definition: “The set A is a subset of B if and only if every element of A is also an element of B. We use the notation A ⊆ B to indicate that A is a subset of the set B.”
A is a proper subset of B if and only if
∀x (x ∈ A → x ∈ B) ∧ ∃x(x ∈ B ∧ x∉A)
The definitions are from the textbook Discrete Mathematics and its Applications by Rosen.
Solution:
We just need to find a one-to-one function from A to B to prove that |A|≤|B| according to one of the definitions above.
f(x) = x is a function. For every a∈ A there is only one value f(a)=a such that a∈B. This is true because we assumed that A⊂B.
f(x)=x is a one-to-one function from A to B.
f(a)=a
f(b)=b
Therefore, if f(a)=f(b), this implies that a=b.
Related posts:
- Give an example of two uncountable sets A and B such that A−B is
- Determine whether each of these sets is finite, countably infinite, or uncountable.
- Show that a finite group of guests arriving at Hilbert’s fully occupied Grand Hotel can be given rooms without evicting any current guest.
- Determine whether each of these sets is finite, countably infinite, or uncountable. For those that are countably infinite, exhibit a one-to-one correspondence between the set of positive integers and that set
- Show that if A, B, C, and D are sets with |A|=|B| and |C|=|D|, then |A×C|=|B×D|
