Higher Mathematics · Classes 9-10 · Chapter 1

One-One Correspondence, Equivalent Sets, Intervals, and Finite and Infinite Sets.

Every person in a hall is sitting on exactly one chair, and no chair is empty. Without counting anyone you can say the people and the chairs are equal in number. Mathematics turns this pairing into an idea deeper than counting, and it can even measure infinite sets.

1. One-one correspondence

Suppose each element of A can be matched with one and only one element of B, and each element of B with one and only one element of A. Then there is a one-one correspondence between A and B, written A ↔ B. When x is matched with y we write x ↔ y.

A = {a, b, c} is a set of three persons and B = {30, 40, 50} the set of their ages. a ↔ 30, b ↔ 40, c ↔ 50 is a one-one correspondence. Draw matches yourself below: pick an element, then one on the other side.

2. Equivalent sets

If a one-one correspondence A ↔ B can be described between two sets A and B, they are called equivalent sets, written A ∼ B.

Three facts hold for any sets A, B, C. Proposition 4: A ∼ A, because every x can be matched with itself, x ↔ x. If A ∼ B then B ∼ A. Proposition 5: if A ∼ B and B ∼ C then A ∼ C, since the matches link up like a chain x ↔ y ↔ z. The empty set is taken as equivalent to itself, ∅ ∼ ∅.

Example 13: {1, 2, 3, ···, n} and {1, 3, 5, ···, 2n − 1} are equivalent. The rule is k ↔ 2k − 1.

Example 14: the natural numbers N and the even numbers {2, 4, 6, ···, 2n, ···} are equivalent. The rule is n ↔ 2n.

Equal and equivalent are not the same thing. Equal sets have exactly the same elements. Equivalent sets only need a one-one correspondence. So {1, 2, 3} ∼ {a, b, c}, but {1, 2, 3} ≠ {a, b, c}. For finite sets, n(A) = n(B) is enough for A ∼ B.

3. Intervals

For real numbers a and b with a < b there are four kinds of interval:
(a, b) = {x ∈ R : a < x < b}, an open interval;
[a, b] = {x ∈ R : a ≤ x ≤ b}, a closed interval;
(a, b] = {x ∈ R : a < x ≤ b}, an open-closed interval;
[a, b) = {x ∈ R : a ≤ x < b}, a closed-open interval.

Draw an interval on the number line yourself. Slide a and b, decide whether each end is in, and watch the notation write itself.

Read the brackets against the condition: {x ∈ R : −3 ≤ x < 3} = [−3, 3) and {x ∈ R : 1 ≤ x ≤ 7} = [1, 7]. “[” means the end number is included, “(” means it is left out. ≤ means [, < means (.

4. Finite and infinite sets

A set whose number of elements can be fixed by counting is a finite set. A set that is not finite is an infinite set. Matching A = {15, 16, ···, 22} with {1, 2, ···, 8} gives 8 elements.

The empty set ∅ is finite with 0 elements. If A ∼ Jₘ = {1, 2, ···, m}, then A is finite with m elements. The number of elements of a finite set A is written n(A), and writing n(A) means A is finite.

If A and B are equivalent and one of them is finite, the other is finite too, and n(A) = n(B).

Proposition 6: if A is finite and B is a proper subset of A, then B is finite and n(B) < n(A). So a finite set can never be equivalent to a proper part of itself.

Proposition 7: A is infinite if and only if A is equivalent to one of its proper subsets. The set of natural numbers N is infinite.

See Propositions 6 and 7 in a hotel. Every room has one guest. One rule: the guest in room n moves to room 2n. What happens in a finite hall, and in an endless hotel?

There is one way to show a set is infinite: choose a proper subset and show a one-one correspondence with it. The odd numbers {1, 3, 5, ···} and the proper subset {3, 5, 7, ···}, matched by k ↔ k + 2. The squares {1, 4, 9, ···} and {4, 9, 16, ···}, matched by n² ↔ (n + 1)².

Activity and Exercise 12: {1, 2, ···, n} ∼ {1, 2, 2², ···, 2ⁿ⁻¹} through k ↔ 2ᵏ⁻¹. S = {3ⁿ : n = 0 or n ∈ N} = {1, 3, 9, ···} ∼ N through n ↔ 3ⁿ⁻¹. And the proper subset {1, 9, 81, ···} = {3²ⁿ} of S is equivalent to S through 3ⁿ ↔ 3²ⁿ. Tap the four rows to see it.

5. Counting every correspondence

Between A = {a, b} and B = {1, 2} there are two one-one correspondences: a ↔ 1, b ↔ 2 and a ↔ 2, b ↔ 1. For two sets of three elements there are 3 × 2 × 1 = 6. Each can be written as the set of ordered pairs F = {(x, y) : x ∈ A, y ∈ B, x ↔ y}, such as {(a, 1), (b, 2)}. The builder above shows these pairs once your matching is complete.

6. Check yourself

Three questions; if you miss one, go back to the note.

Read the second one, think, then tap.

The last question.

The whole note on seven cards.

Source: Higher Mathematics, Classes 9-10 (NCTB), Chapter 1 “Set and Function”, the “One-One Correspondence, Equivalent Sets, Intervals, and Finite and Infinite Sets” part.