bonanova 83 Report post Posted November 21, 2014 Two sets have the same size (cardinality) if their elements can be placed in a 1-1 correspondence. (A bijection exists.) For finite sets this is a simple concept. The sets {a b c d e f g} and {days of the week} are the same size; they both have a 1-1 correspondence with the first 7 counting numbers. For infinite sets things get dicey. The counting numbers, the even counting numbers (seemingly half as many) and the rational numbers (seemingly infinitely more numerous) have equal cardinality. Bijections among these sets can be easily described in words (or with a simple picture.) Can you verbally describe a bijection of the counting numbers with all of their subsets (their superset power set)? Or, remembering that neither set is finite, verbally prove no such bijection exists? Quote Share this post Link to post Share on other sites
0 bonanova 83 Report post Posted November 28, 2014 I decided to post a separate thread to show how Russell's paradox relates to the powerset proof. Quote Share this post Link to post Share on other sites
0 karthickgururaj 4 Report post Posted November 22, 2014 I think I got this.. pleased as punch Let, N be the set of counting numbers, {1, 2, 3, ..}. Let S(N) be its super set. The one-to-one mapping from N -> S(N) is easy, for each 'x' in N, we map it to {x} in S(N). For the mapping S(N) -> N, take any element {x_{0}, x_{1}, .., x_{n}} in set S(N). Map it to: p(x_{0})*p(x_{1})*..*p(x_{n}), where p(m) denotes the m^{th} prime number (p(1) = 2, p(2) = 3, etc). This maps each element in S(N) to a unique element in N. Quote Share this post Link to post Share on other sites
0 phil1882 13 Report post Posted November 24, 2014 (edited) no you can't if you could, you could map the counting numbers to the reals, which are uncountably infinite. to prove this, simply let each subset represent a decimal number, with the decimal point after the first number in the set, and the rest of the number in the set of the remaining numbers. for example the subset {1, 3, 5, 7, 11, 13...} would be represented as 1.3571113... to prove that the real numbers are uncountably infinite, imagine you try to construct a countably infinite number of real numbers. say the following list. 1 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.9 1.01 ... now i will construct a number not on the list. take the digit in each decimal place, add 1 unless 9, then go back to 0. so for the above sequence, the number 2.21111... will never appear. Edited November 24, 2014 by phil1882 Quote Share this post Link to post Share on other sites
0 bonanova 83 Report post Posted November 24, 2014 I think I got this.. pleased as punch Let, N be the set of counting numbers, {1, 2, 3, ..}. Let S(N) be its super set. The one-to-one mapping from N -> S(N) is easy, for each 'x' in N, we map it to {x} in S(N). For the mapping S(N) -> N, take any element {x_{0}, x_{1}, .., x_{n}} in set S(N). Map it to: p(x_{0})*p(x_{1})*..*p(x_{n}), where p(m) denotes the m^{th} prime number (p(1) = 2, p(2) = 3, etc). This maps each element in S(N) to a unique element in N. karthikgururaj proposes two injections (both of which are far from being surjections also) rather than a single bijection. So the question is, are two (one each direction) injections equivalent to a bijection? Quote Share this post Link to post Share on other sites
0 karthickgururaj 4 Report post Posted November 24, 2014 no you can't if you could, you could map the counting numbers to the reals, which are uncountably infinite. to prove this, simply let each subset represent a decimal number, with the decimal point after the first number in the set, and the rest of the number in the set of the remaining numbers. for example the subset {1, 3, 5, 7, 11, 13...} would be represented as 1.3571113... to prove that the real numbers are uncountably infinite, imagine you try to construct a countably infinite number of real numbers. say the following list. 1 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.9 1.01 ... now i will construct a number not on the list. take the digit in each decimal place, add 1 unless 9, then go back to 0. so for the above sequence, the number 2.21111... will never appear. Since the subset is unordered, a single subset can map to more than one decimal number. For example, {1, 3, 5, 7, 11, 13} can map to either 1.3571113 or 3.5171113 or 7.1113531 or.. etc. So it is one-to-many mapping, not one-to-one. Further, a given subset will represent only a rational number. Irrationals will require mapping of subset with infinite number of elements - which is not legal. Quote Share this post Link to post Share on other sites
0 karthickgururaj 4 Report post Posted November 24, 2014 I think I got this.. pleased as punch Let, N be the set of counting numbers, {1, 2, 3, ..}. Let S(N) be its super set. The one-to-one mapping from N -> S(N) is easy, for each 'x' in N, we map it to {x} in S(N). For the mapping S(N) -> N, take any element {x_{0}, x_{1}, .., x_{n}} in set S(N). Map it to: p(x_{0})*p(x_{1})*..*p(x_{n}), where p(m) denotes the m^{th} prime number (p(1) = 2, p(2) = 3, etc). This maps each element in S(N) to a unique element in N. karthikgururaj proposes two injections (both of which are far from being surjections also) rather than a single bijection. So the question is, are two (one each direction) injections equivalent to a bijection? I thought about this when posting the solution.. In truth, it doesn't appear to be an equivalent to bijection If an injection can be defined from set A to B, then it implies cardinality of B must be greater than or equal to A. If an injection can be defined both ways, it implies the cardinality of both must be same.. This is trivial for finite sets, I'm not sure for infinite sets. Quote Share this post Link to post Share on other sites
0 bonanova 83 Report post Posted November 24, 2014 See if there's a similar case (of oppositely directed injections) that applies to finite sets. Quote Share this post Link to post Share on other sites
0 karthickgururaj 4 Report post Posted November 26, 2014 See if there's a similar case (of oppositely directed injections) that applies to finite sets. For finite sets it is easy to see that a bijection exists, if there are two injections, one from A to B, and other from B to A. If f: A -> B is an injection from A to B and g: B -> A is an other injection from B to A, then the number of elements in A and B are both same. So, a bijection can be defined from A to B. I googled a bit on this and read about Schröder–Bernstein theorem, which essentially asserts that if there are two injections in reverse directions, then a bijection exists. Quote Share this post Link to post Share on other sites
0 bonanova 83 Report post Posted November 26, 2014 @karthickgururaj, S-B theorem seems to be exactly what we're looking for. The part that seems difficult, but I can't yet say it's impossible, is the injection from the superset into the original set. In your solution, can you identify (or give examples of) sets A and B? That would complete the proof. Or, apply it to say A = {1, 2, 3}. Quote Share this post Link to post Share on other sites
0 witzar 18 Report post Posted November 26, 2014 The set of all subsets of a set S is called a power set (powerset) of S. According to Cantor's theorem, cardinality of the power set of any set S is strictly greater then cardinality of S. PS The Schröder–Bernstein theorem was called Cantor–Bernstein theorem at my set theory classes. Quote Share this post Link to post Share on other sites
0 karthickgururaj 4 Report post Posted November 27, 2014 The set of all subsets of a set S is called a power set (powerset) of S. According to Cantor's theorem, cardinality of the power set of any set S is strictly greater then cardinality of S. PS The Schröder–Bernstein theorem was called Cantor–Bernstein theorem at my set theory classes. Interesting! Thanks for the link. Reading the wiki article exposes one assumption in my solution. I assumed that, while the super set has infinite number of elements, each individual element of the super set has a finite number of elements. In other words, I assumed that (for example), "the set of all even numbers" is NOT a member of super set. If that assumption is removed, my solution won't work. Quote Share this post Link to post Share on other sites
0 karthickgururaj 4 Report post Posted November 27, 2014 @karthickgururaj, S-B theorem seems to be exactly what we're looking for. The part that seems difficult, but I can't yet say it's impossible, is the injection from the superset into the original set. In your solution, can you identify (or give examples of) sets A and B? That would complete the proof. Or, apply it to say A = {1, 2, 3}.For a finite set, like A = {1, 2, 3}, clearly the super set has higher number of elements (in this case 8), so we can't define an injection from the superset to the original set. For an infinite set, like N = {1, 2, 3, .. }, it is not immediately clear whether we can (or not) define the injection from the superset of N (lets call it S(N)) to N. (So, I have just restated part of the OP!) S(N) will be like, { {1}, {2}, {1, 2, 3, 100}, {4, 5, 6}, {10^9, 10^8, 10^7}, ... }. Specifically, the assumption here is that the super set does NOT have an element like: {2, 4, 6, 8, ...}. Then, any specific element of S(N) will have a finite set of elements: {x_{0}, x_{1}, .., x_{n}}. This can be mapped to a unique number in N: : p(x_{0})*p(x_{1})*..*p(x_{n}), where p(m) denotes the m^{th} prime number (p(1) = 2, p(2) = 3, etc). However, I do not know if the assumption is valid. After reading about Cantor's theorem, it appears not. Quote Share this post Link to post Share on other sites
0 bonanova 83 Report post Posted November 27, 2014 Post 12 clears up the suggested injection from a powerset to its set. Which leaves us just with the need for a simple word proof. The one I have in mind refers closely to Russell's paradox. I used the wrong term (superset) for powerset in my above posts. Brain fart. Quote Share this post Link to post Share on other sites
0 gavinksong 11 Report post Posted December 4, 2014 Well, what are the chances: I just wrote about this in my blog. http://en.m.wikipedia.org/wiki/Cantor%27s_theorem Quote Share this post Link to post Share on other sites
0 gavinksong 11 Report post Posted December 4, 2014 Sorry for spoiling the fun, but here's a modified excerpt that explains the theorem for the case of natural numbers: A mapping between the set of all natural numbers and its power set might look something like this: | 1 2 3 4 5 ... 1 | O X X X O ... 2 | X X X X X ... 3 | X O O O O ... 4 | O X O X O ... 5 | X O O X X ... ... ...... To the left are the natural numbers, and to the right are sets of natural numbers. In each row, a column is marked with an O if the corresponding set contains the corresponding natural number or an X if it doesn't. For example, the number 1 is mapped to a set containing 1 and 5 but not 2, 3, or 4. If we take the diagonal and switch all the O's to X's and vice versa, we will end up with a set that is different from all the sets in the list, which proves that any given mapping is non-surjective. Quote Share this post Link to post Share on other sites
0 bonanova 83 Report post Posted December 4, 2014 What fun? The succinct proof says is a subset of A that does not map to an element. It uses symbols, and the diagonal proof uses symbols. The narrative is words-only: B comprises A's red elements. I'm given to understand there are serious mathematicians who reject these proofs, and reject Cantor's orders of infinity. Quote Share this post Link to post Share on other sites
Two sets have the same size (cardinality) if their elements can be placed
in a 1-1 correspondence. (A bijection exists.)
For finite sets this is a simple concept.
The sets {a b c d e f g} and {days of the week} are the same size;
they both have a 1-1 correspondence with the first 7 counting numbers.
For infinite sets things get dicey.
The counting numbers, the even counting numbers (seemingly half as many)
and the rational numbers (seemingly infinitely more numerous) have equal cardinality.
Bijections among these sets can be easily described in words (or with a simple picture.)
Can you verbally describe a bijection of the counting numbers with all of their subsets (their
supersetpower set)?Or, remembering that neither set is finite, verbally prove no such bijection exists?
Share this post
Link to post
Share on other sites