|
Which did come first... (pg. 4)
|
View this Thread in Original format
| Flyboy217 |
| quote: | Originally posted by Noisician
you don't think russell's paradox is interesting enough? hmm... i think it's amazing how one little antinomy followed from apparently sound assumptions was able to plunge the entire set theory into a crisis at the time it was devised. the paradox destroyed one of the most plausible postulates that cantor and his adherents piously believed in. what russell did was checkmate cantor's comprehension principle in two simple moves. unlike previous antinomies that had arisen before, russel's one did not require lengthy expositions and seemed very sound even to persons completely unfamiliar with set theory. he actually showed that some classes could not be regarded as sets. sure cantor had already been partially aware of this contradiction (he knew of the burali-forti paradox) but he didn't devote attention to this discovery at all, nor was he any disturbed by it. and boy, was he wrong. this clever trick of russel's persuaded zermelo into developing what later became known as zermelo-fraenkel set theory, the one we still use nowadays. hell, it still remains the best we have. though i should also add that the axiomatic approach it's based on is not ideal, either. while it helps with blocking the logical antinomies, it does not guard against various semantic antinomies, such as berry's paradox for example.
oh and btw, a chicken is just the means by which one egg produces another egg. |
No no sorry, you misunderstand. I said the question "does the set of all sets contain itself" is not interesting in the way that Russell's Paradox is. Clearly Russell's Paradox is *very* interesting. Godel perhaps wouldn't have been motivated to produce On Principia Mathematica if not for this. And then where would we be... |
|
|
| DJ Rat 187 |
stupidest I've ever heard
P.S. God doesn't exist ;) |
|
|
| Noisician |
| quote: | Originally posted by Flyboy217
No no sorry, you misunderstand. I said the question "does the set of all sets contain itself" is not interesting in the way that Russell's Paradox is. |
all right, then :)
but i still think the issue he brought up is engaging AND important. the thing is, the deeper you look into it, the less basic it appears to be. admittedly, one tends to intuitively assume that the set of all sets would surely contain itself (after all, it includes ALL sets, right?), but it actually turns out that such a structure cannot possibly exist in the universe of discourse. it's not a valid object in the sense that it is not subject to the fundamental axioms of modern set theory. as a result, it cannot be a member of a class - and this restriction includes itself too. as i said this follows from zermelo's axioms. the axiom of separation (AS) states that
if A is a set then A' = {x∈A:P(x)} is a set as well.
less formally this means that
if B⊆A and A is a set then so is B
taking the contraposition of this implication, we get an equivalent statement:
(given that B is a subclass of A) if B is not a set then neither is A.
now, if the set of all sets existed, it would have an extension of the form
{x:x is a set}
applying the axiom of separation, we can single out some members and still get a subclass that is a subset. namely, take A' such that
A' = {x∈A:x∉x}
by AS, the subclass above is a set. but we've just written an extension of the russell class, which is clearly not a set. a contradiction. or you can look at it differently and note that since russell's class is included in A, by the contraposition of the AS, A is not a set. either way, A is not a valid object in the universe.
now, you might argue that russell's class doesn't really count due to its bizzare and somewhat artificial nature. amazingly enough we can show that the class is, in fact, perfectly legal. its existence follows from cantor's theorem:
if A is a set and P(A) is its power set, then |A| < |P(A)|
among other things, it implies that there does not exist a mapping from A into P(A) that is a bijection (ie, it's never surjective).
now, if A is the class of all sets, then P(A)⊆A. let us introduce an equivalence relation on A as follows: {(x,x):x∈A}. this diagonal relation (call it _R_) is clearly a bijection from A to itself. but look, we just showed that there is a map from A to a class that includes P(A) (namely A itself) that is one-to-one AND onto. and since |A| ≠ |P(A)|, the class
C = {x∈A:x∉_R_(x)}
becomes russell's paradoxical class.
|
|
|
| UWM |
Not to sound cocky, I'm fairly intelligent, but you Noisician make me feel like I know absolutely nothing.
:p |
|
|
| smokeape |
[edit]Dang, a revolting devlopment from another thread...
Beer came first!
But...
AC/DC - Who Made Who
:D
[[[smoke]]] |
|
|
| Flyboy217 |
| quote: | Originally posted by Noisician
its existence follows from cantor's theorem:
if A is a set and P(A) is its power set, then |A| < |P(A)|
among other things, it implies that there does not exist a mapping from A into P(A) that is a bijection (ie, it's never surjective).
|
Cantor's theorem is nice. A similar application of his famous diagonal slash proves it too:
Suppose you have a set S, and a function f(x):S→P(S).
Define the set T = {x∈S | x∉f(x)}.
Now, since T ⊆ S, clearly T ∈ P(S). Now suppose f(x) is surjective. Then we can denote the pre-image of T as t∈S.
But then we have:
t∉f(t)=T→t∈T and
t∈T→t∉f(t)=T
A contradiction! Hence, T is not surjective, and f(x) cannot be a bijection from the a set to its power set.
I had never seen that use of Russell's paradox to invalidate the concept of a set of all sets, however. Maybe I'll go learn a bit of set theory ;)
BTW, I've never seen the notation x∉_R_(x), where R is a binary relation. I understand it to mean ¬_R_(x,x) or something? Without understanding that, the final step in your explanation is hard to follow:
| quote: | Originally posted by Noisician
and since |A| ≠ |P(A)|, the class
C = {x∈A:x∉_R_(x)}
|
I take this to mean the following: since |A| < |P(A)|, and since _R_:A→P(A) and exhibits a bijection by construction, there exists x∈A that does not meet the trivial equivalence relation? I'd love it if you clarified here.
P.S. I think we're boring everyone. |
|
|
| Cloudburst |
| fcuk, I barely passed that mathematics course and you bring up the memories yet again.. gah.. :p |
|
|
| Algenis |
| I would have to say the chicken came first. |
|
|
| Noisician |
| quote: | Originally posted by Flyboy217
BTW, I've never seen the notation x∉_R_(x), where R is a binary relation. I understand it to mean ¬_R_(x,x) or something? Without understanding that, the final step in your explanation is hard to follow: |
in addition to being an equivalence relation, _R_ is also a function. hence, _R_(x) is the same as _R_x, whichever notation you are more familiar with. it's called the identity relation on a class. look at the following definition of a function - it should then become clear what i meant in my previous post:
ƒ = {(x,ƒx):x∈dom ƒ}
| quote: | Originally posted by Flyboy217
I take this to mean the following: since |A| < |P(A)|, and since _R_:A→P(A) and exhibits a bijection by construction, there exists x∈A that does not meet the trivial equivalence relation? I'd love it if you clarified here. |
you almost answered your own question with the "diagonal slash" you provided :)
let me restate it a little bit.
in order to show that |A| < |P(A)| we need show a) |A| ≤ |P(A)| and b) |A| ≠ |P(A)|
a) we define a map h from A into P(A) as follows: ha = {a} ∀a∈A. clearly, h is an injection from A to its power set.
b) we let m be a map from A to P(A). then for every x∈A, mx is a member of P(A) - that is, a subset of A. take
C = {x∈A:x∉mx}
then C is a subset of A - that is, a member of P(A). if m were surjective, there would be some c∈A for which mc = C. therefore c∈mc if and only if c∈C.
but from the definition of C above, c∈C if and only if c∉mc. a contradiction.
now, returning to my previous post, just take the identity relation on the class of all sets i described above as the m in the proof, and the C of the proof becomes russell's class of all sets that do not belong to themselves. |
|
|
| Flyboy217 |
| quote: | Originally posted by Noisician
in addition to being an equivalence relation, _R_ is also a function. hence, _R_(x) is the same as _R_x, whichever notation you are more familiar with. it's called the identity relation on a class. look at the following definition of a function - it should then become clear what i meant in my previous post:
ƒ = {(x,ƒx):x∈dom ƒ}
|
A ha! And it all becomes clear. I had never seen a function being used as both a function and a relation. So, in your relation _R_(x,x), _R_(x) simply denotes the image of x. Makes sense.
I suppose the reason I was confused was because of the specific case. For general A, if _R_:A→A, then it doesn't make sense to say, for x∈A, that x∈_R_(x) (since it doesn't mean anything for an element to contain other elements). Since we're talking about the purported set of all sets, such a map indeed makes sense.
| quote: | Originally posted by Noisician
you almost answered your own question with the "diagonal slash" you provided :)
let me restate it a little bit.
in order to show that |A| < |P(A)| we need show a) |A| ≤ |P(A)| and b) |A| ≠ |P(A)|
a) we define a map h from A into P(A) as follows: ha = {a} ∀a∈A. clearly, h is an injection from A to its power set.
b) we let m be a map from A to P(A). then for every x∈A, mx is a member of P(A) - that is, a subset of A. take
C = {x∈A:x∉mx}
then C is a subset of A - that is, a member of P(A). if m were surjective, there would be some c∈A for which mc = C. therefore c∈mc if and only if c∈C.
but from the definition of C above, c∈C if and only if c∉mc. a contradiction.
now, returning to my previous post, just take the identity relation on the class of all sets i described above as the m in the proof, and the C of the proof becomes russell's class of all sets that do not belong to themselves. |
Yep, no problems here. Your relation m is my function f, and your set C is my set T. The only difference is that, by the nature of your set A, it makes sense for elements to contain each other.
I guess the key point here is this: m needs only be a surjection. Since, by construction, _R_ is a bijection from A to A, and as you said, P(A)⊆A, _R_ is also a surjective map from A to P(A), and can thus stand in for m.
So Russell's set IS indeed valid (and of course contradictory), and by the Axiom of Separation, A is invalid. Nice trick; I'll buy it for now :). There still seems to me to be something fishy about the validity of the construction of Russell's set, but that's perhaps only because it's counterintuitive.
In any case, I hope our discourse has clarified a few matters for anyone else listening in. Russell and Cantor were apparently pretty clever ;) |
|
|
| MaRt |
| The question is not whether the chicken or egg came first, but rather at which point in evolution a chicken became a chicken. Oh wait, I've gone cross-eyed...:crazy: |
|
|
| Noisician |
| quote: | Originally posted by Flyboy217
A ha! And it all becomes clear. I had never seen a function being used as both a function and a relation. So, in your relation _R_(x,x), _R_(x) simply denotes the image of x. Makes sense. |
let me tell you something. modern set theory is well-known for its dogma of reductionism that aims to reduce all mathematical concepts to the notion of class and the relation 'being a member of'. as a result, in set theory a function is considered to be a special case of a relation, which itself happens to be a subclass of the cartesian product of a number of (not necessarily distinct) classes. to be precise,
a function ƒ is a class of ordered pairs that meets the functionality criterion: whenever both (x,y)∈ƒ and (x,z)∈ƒ then y=z.
there used to be a slight problem with the definition above in the sense that it alludes to the notion of an ordered pair, and ordered pairs themselves were yet to be reduced to basic set-theoretical structures. fortunately, the resolution came in the early 1920s, when k.kuratowski conjectured that an ordered pair was just a special case of a set and proposed the following definition that is still widely used today:
(a,b) = {a,{a,b}}
btw, by the axiom of pairing {a,b} is always a set for all objects a and b in the universe of discourse.
a similar story happened to cardinals. when cantor first introduced cardinals, he regarded them as special abstract entities of a brand new kind. obviously, this was a big no-no for all advocates of the reductionist program. so there were a few attempts made to redefine cardinals in terms of hitherto posited objects of set theory. though some restrictions applied in that all such definitions had to be coordinated with cantor's basic concepts of cardinality: if class A is assigned an object |A| and class B is assigned an object |B| and if these classes are known to be equipollent, we say |A| = |B| and call these objects cardinals. thus,
|A|=|B| iff A≈B
in the late 1800s frege (a reductionist) hit upon a very elegant idea concering these new abstract objects. he conjectured that |A| was nothing more than [A]≈ - that is, the equivalence class of A modulo ≈. it would've worked perfectly fine if [A]≈ were always a set (read, object). unfortunately, it's not. for if A happened to be a singleton then [A]≈ would be the class of all singletons. and then ∪[A]≈ would be the class of all objects - in other words, the universe of discourse itself, which is a proper class. so then |A|, too, would be a proper class by the axiom of union. and hence we wouldn't be able to form classes of cardinals, which is very inconvenient.
i should also add that it is possible to simulate the behavior that characterizes the system of natural numbers through ordinals and cardinals alone. this means that natural numbers really are reducable after all. in addition, bolzano and hamilton showed in the 19th century that it is possible to reduce all the concepts of the mathematical analysis to those of natural number, function, set and relation.
| quote: | Originally posted by Flyboy217
So Russell's set IS indeed valid (and of course contradictory), and by the Axiom of Separation, A is invalid. Nice trick; I'll buy it for now :).
|
well, using pradoxes to distinguish proper classes is not a rare phenomenon in set theory. another famous example of this is the burali-forti paradox, which was originally used to prove that the class of all ordinals was a proper class. |
|
|
|
|
