|
|
|
|
|
|
|
|
|
 Posted: Tue Aug 29, 2006 12:54 am
VorpalNeko No, between A and P(A). A stronger statement is actually proved--there is no surjection f:A→P(A); the fact that there is no bijection follows immediately, of course, since every bijection is surjective by definition. The role of B is that it is constructed so as to not be in the range of f. So wait...you're proving that there exists no surjection between A and P(A), basing it off a function which seems to be, by definition, not a surjection? Quote: Identify each real number in x in [0,1] with the sequence of digits in its base-two representation, i.e., with a function x:N→{0,1} such that x = Sum_k[ x(k)/2^{k+1} ], where N is the set of natural numbers. Suppose you have a given function f:N→[0,1]. Construct a funtion y:N→{0,1} as follows: y(n) = 1 - [f(n)](n), where [f(n)] is the function identified with the real number f(n) in the above manner. The real number corresponding to y is not equal to f(n) for any n because it differs on the nth digit. Thus, f is not a surjection. Confusion, on a few points. In the function x:N-->{0,1}, the set {0,1} is lit. that set, or is it the set of binary representations of N? Also then, is [f(n)] the actual number associated with f(n), or do you mean it to be the nth digit in the binary representation of f(n)? Quote: Replacing N with an arbitrary set A and forgetting all talk of real numbers altogether, what the above argument shows is that there is no surjection f from A to the set of functions {x:A→{0,1}}, by the same construction of y(a) = 1 - [f(a)](a). The only remaining step is to identify each x:A→{0,1} with a subset of A, which is done in the natural way by interpreting it as a characteristic function. Again, I am confused on these points. Are the functions x:A-->{0,1} representations of the elements of A, or a binary partition? I am also confused (and it seems, always have been) on the same definition of the characteristic function. I believe you said that the definition is chi_B(x) = 1 if x is in B. But you said that B was a subset of P(A), but that chi_B has domain A.
|
 |
|
|
|
|
|
|
|
|
|
|
|
|
|
Posted: Tue Aug 29, 2006 1:46 am
Every binary string can be considered a function f from N to the set containing just the element 0 and the element 1.
In other words, every natural number can be considered a position along the binary string, and then the function f applied to that number is the value of that position on the string.
f(n) is thus the nth string, and [f(n)] is the function that takes the position along the string as input and returns the value of that position along the string.
So if you have f(n) giving
f(1)=.1001011....
f(2)=.0110101....
f(3)=.1000100...
f(4)=.0100111...
...
You have [f(1)](1) = 1, [f(1)](2) = 0, [f(2)](2) = 1, and so on.
Thus we get
y(1) = 1-[f(1)](1) = 1-1 = 0
y(2) = 1-[f(2)](2) = 1-1 = 0
y(3) = 1-[f(3)](3) = 1-0 = 1
y(4) = 1-[f(4)](4) = 1-0 = 1
and so on.
Similarly, x:A->{0,1} means assign either 0 or 1 to each element of A, and therefore {x:A->{0,1}} is the set of all functions that assign either 0 or 1 to each element of A. Denote the ath element of that set by x_a. In his notation we get [f(a)](b) = x_a(b), where b is an element of A.
In particular, it assigns either 0 or 1 to a.
Thus we can form the function y:A->{0, 1}, where y(a) = 1 - [f(a)](a) = 1-x_a(a)
As for the last bit, B is not a subset of P(A); B is a subset of A, making it an element of P(A). So chi_B makes perfect sense.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Posted: Tue Aug 29, 2006 12:34 pm
Swordmaster Dragon So wait...you're proving that there exists no surjection between A and P(A), basing it off a function which seems to be, by definition, not a surjection? The function f:A→P(A) is arbitrary. It is proven to not be a surjection, ergo, all functions f:A→P(A) are not surjective. As for the rest, I hope Layra-chan's explication makes it clear.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Posted: Tue Aug 29, 2006 12:40 pm
Okay...so f(n) is a real number, whereas the function [f(n)] places elements from the binary string f(n) to {0,1}. The confusion I had was whether {0,1} in f:N-->{0,1} mapped to a binary string or, as it does in chi_B:A-->{0,1}, to the actual set {0,1}. Thanks for clearing that up.
So, to be clear, we actually have f:N-->R and [f(n)]: R-->{0,1}. But then we also have y: N-->{0,1}...how does this function correlate to a real number, and why does it prove that f can't be a surjection?
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Posted: Tue Aug 29, 2006 12:44 pm
Swordmaster Dragon So, to be clear, we actually have f:N-->R and [f(n)]: R-->{0,1}. But then we also have y: N-->{0,1}...how does this function correlate to a real number, and why does it prove that f can't be a surjection? No, each [f(n)] is a function from N to {0,1} and f is from N to [0,1]. The function y:N→{0,1} is constructed so as to not be equal to [f(n)] for any n. This proves that f is not surjective because the number corresponding to y, Sum_k[ y(k)/2^{k+1} ], is not in the range of f, i.e., it is not f(n) for any n. (Yet again, assume that the countable set of numbers with non-unique representation has already been covered, and therefore not an issue.)
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Posted: Wed Aug 30, 2006 5:08 pm
I believe I understand now. The proof I had seen (before Rudin) was logistically the same, but very different in method...I wish I could find it again. Thank you both so much...I still feel extraordinarily unprepared to be a math major, though.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
