Consider the set N of all natural numbers; we can assign each natural number a...
Ayanna Trujillo
Answered question
2022-06-20
Consider the set N of all natural numbers; we can assign each natural number a point on a single axis. Let A be the set of all of these points; A is a countable set (we can assign each point to the natural number it represents and vice versa). Therefore, the cardinality of the power set of A is equal to the cardinality of the continuum.
If we look at these points, we can create connections between them where each connection connects two points. Let B be the set of all of those connections. A connection of two points is a subset of A containing exactly 2 objects that belong to A, and so B is the set of all subsets of A which contain exactly 2 objects that belong to A.
The question is: what is the cardinality of B?
We came up with a few options, not sure whether they cover all cases, but these are the ones we thought about:
1. B is a countable set, which means its cardinality is the same as that of A (This seems possible; however, we couldn't find an injective & surjective function that matches objects from A to B)
2. B's cardinality is the cardinality of the continuum
3. B's cardinality is in between the cardinality of A and the cardinality of the continuum and therefore denies the continuum hypothesis (This seems like a problematic possibility since it has been proved that the continuum hypothesis is independent of the axioms of set theory)
4. B's cardinality is smaller than that of A (seems very unlikely, since A's cardinality is the smallest infinite cardinal, and B is clearly an infinite set).
If we look at these points, we can create connections between them where each connection connects two points. Let B be the set of all of those connections. A connection of two points is a subset of A containing exactly 2 objects that belong to A, and so B is the set of all subsets of A which contain exactly 2 objects that belong to A.
The question is: what is the cardinality of B?
We came up with a few options, not sure whether they cover all cases, but these are the ones we thought about:
1. B is a countable set, which means its cardinality is the same as that of A (This seems possible; however, we couldn't find an injective & surjective function that matches objects from A to B)
2. B's cardinality is the cardinality of the continuum
3. B's cardinality is in between the cardinality of A and the cardinality of the continuum and therefore denies the continuum hypothesis (This seems like a problematic possibility since it has been proved that the continuum hypothesis is independent of the axioms of set theory)
4. B's cardinality is smaller than that of A (seems very unlikely, since A's cardinality is the smallest infinite cardinal, and B is clearly an infinite set).
Answer & Explanation
boomzwamhc
Beginner2022-06-21Added 17 answers
The set you are talking about is sometimes written as in combinatorics: the set of all 2-element subsets of N. It has the same cardinality as N. An explicit bijection is given by the combinatorial number system system for k=2: map the subset with .
A similar bijection holds for k-element subsets for any fixed finite k (see the linked page). Even the union of all those sets is in bijection with N; in this case a slightly different bijection works: interpret the subset as a binary number, with the bit in position i indicating whether i is present in the subset (value 1) or not (value 0).
In order to get an uncountable collection of subsets of N, your collection must contain some subsets that are infinite, and moreover need infinite information to describe (a necessary but not sufficient condition). As long as each element can be specified, using some fixed and definite encoding, by a finite amount of data, one can order the elements by size of those data first, and then for a fixed size by some total ordering of the encoding data (lexicographically for instance); this produces a well-ordering in which each element occurs in a position corresponding to a natural number. The above bijections are in fact inspired by fairly simple such ordering schemes, but using "largest element" in the place of "data size" (but that would no longer work for collections containing infinite subsets with finite descriptions).
A similar bijection holds for k-element subsets for any fixed finite k (see the linked page). Even the union of all those sets is in bijection with N; in this case a slightly different bijection works: interpret the subset as a binary number, with the bit in position i indicating whether i is present in the subset (value 1) or not (value 0).
In order to get an uncountable collection of subsets of N, your collection must contain some subsets that are infinite, and moreover need infinite information to describe (a necessary but not sufficient condition). As long as each element can be specified, using some fixed and definite encoding, by a finite amount of data, one can order the elements by size of those data first, and then for a fixed size by some total ordering of the encoding data (lexicographically for instance); this produces a well-ordering in which each element occurs in a position corresponding to a natural number. The above bijections are in fact inspired by fairly simple such ordering schemes, but using "largest element" in the place of "data size" (but that would no longer work for collections containing infinite subsets with finite descriptions).
