Confused about $x notin x$ example in Axiom of Specification
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
In Halmos's Naive Set Thoery, I'm having a lot of problems in the Axiom of Specification. Halmos takes an example where a set $B$ is obtained from a set $A$ using the following specification:
$$B = x in A : x notin x $$
He then proceeds to prove that $B notin A$.
While I'm still struggling with the proof, I have a more fundamental doubt here. Just a few lines ago he had argued that $A notin A$ is an impossible set (which seems true enough), but doesn't the same reasoning apply to $x notin x$? How can an element ever contain itself? It seems to me that because such a specification is impossible, it is absurd to derive any proof from it.
Please shed some light!
elementary-set-theory
add a comment |Â
up vote
0
down vote
favorite
In Halmos's Naive Set Thoery, I'm having a lot of problems in the Axiom of Specification. Halmos takes an example where a set $B$ is obtained from a set $A$ using the following specification:
$$B = x in A : x notin x $$
He then proceeds to prove that $B notin A$.
While I'm still struggling with the proof, I have a more fundamental doubt here. Just a few lines ago he had argued that $A notin A$ is an impossible set (which seems true enough), but doesn't the same reasoning apply to $x notin x$? How can an element ever contain itself? It seems to me that because such a specification is impossible, it is absurd to derive any proof from it.
Please shed some light!
elementary-set-theory
1
"$A notin A$" is a truth value, not a set.
– Hurkyl
Feb 13 '14 at 19:21
Yes, but $B$ is. And my point is that it seems absurd that $B$ be defined like this. In fact, intuitively, it seems as if $B = A$!
– dotslash
Feb 14 '14 at 16:50
add a comment |Â
up vote
0
down vote
favorite
up vote
0
down vote
favorite
In Halmos's Naive Set Thoery, I'm having a lot of problems in the Axiom of Specification. Halmos takes an example where a set $B$ is obtained from a set $A$ using the following specification:
$$B = x in A : x notin x $$
He then proceeds to prove that $B notin A$.
While I'm still struggling with the proof, I have a more fundamental doubt here. Just a few lines ago he had argued that $A notin A$ is an impossible set (which seems true enough), but doesn't the same reasoning apply to $x notin x$? How can an element ever contain itself? It seems to me that because such a specification is impossible, it is absurd to derive any proof from it.
Please shed some light!
elementary-set-theory
In Halmos's Naive Set Thoery, I'm having a lot of problems in the Axiom of Specification. Halmos takes an example where a set $B$ is obtained from a set $A$ using the following specification:
$$B = x in A : x notin x $$
He then proceeds to prove that $B notin A$.
While I'm still struggling with the proof, I have a more fundamental doubt here. Just a few lines ago he had argued that $A notin A$ is an impossible set (which seems true enough), but doesn't the same reasoning apply to $x notin x$? How can an element ever contain itself? It seems to me that because such a specification is impossible, it is absurd to derive any proof from it.
Please shed some light!
elementary-set-theory
asked Feb 13 '14 at 18:45
dotslash
94721226
94721226
1
"$A notin A$" is a truth value, not a set.
– Hurkyl
Feb 13 '14 at 19:21
Yes, but $B$ is. And my point is that it seems absurd that $B$ be defined like this. In fact, intuitively, it seems as if $B = A$!
– dotslash
Feb 14 '14 at 16:50
add a comment |Â
1
"$A notin A$" is a truth value, not a set.
– Hurkyl
Feb 13 '14 at 19:21
Yes, but $B$ is. And my point is that it seems absurd that $B$ be defined like this. In fact, intuitively, it seems as if $B = A$!
– dotslash
Feb 14 '14 at 16:50
1
1
"$A notin A$" is a truth value, not a set.
– Hurkyl
Feb 13 '14 at 19:21
"$A notin A$" is a truth value, not a set.
– Hurkyl
Feb 13 '14 at 19:21
Yes, but $B$ is. And my point is that it seems absurd that $B$ be defined like this. In fact, intuitively, it seems as if $B = A$!
– dotslash
Feb 14 '14 at 16:50
Yes, but $B$ is. And my point is that it seems absurd that $B$ be defined like this. In fact, intuitively, it seems as if $B = A$!
– dotslash
Feb 14 '14 at 16:50
add a comment |Â
3 Answers
3
active
oldest
votes
up vote
3
down vote
accepted
@gregkow's answer is not incorrect, but I think it doesn't get to the real issue. Namely, his answer uses the axiom of foundation which rules out self-membership outright; but we can ignore that axiom and allow self-membership consistently and find that specification will still prove that $Bnotin A$.
Note that the central issue of Russel's paradox is that the Russel class, $R$, contains (or would contain if it existed) every set that's not a member of itself. We can use specification to show that $A$ must not contain every set of its members that aren't members of themselves, even if some of them are members of themselves.
Specification says that something is a member of $B$ if and only if it is in $A$ and not a member of itself. If $B$ is a member of itself then, by the definition of $B$, it must be in $A$ and not a member of itself; that's obviously contradictory. If $B$ is not a member of itself, then it must either be a member of itself or it's not in $A$; since the former would be paradoxical, it shows that $B$ exists and is not in $A$. One immediate consequence is that $A$ cannot contain its own power set.
And for once I'm not going to launch into an advertisement for NF!
– Malice Vidrine
Feb 13 '14 at 19:23
This seems like a good answer, but damned if I say I can understand Russel's Paradox . . . my head is beginning to hurt!
– dotslash
Feb 14 '14 at 16:58
If you know any proof methods for first order logic, I personally found it easier to wrap my head around a formal proof of contradiction from the single premise $forall x(xin Riff xnotin x)$. It sounds funny in informal English, but a clear proof is like two lines long.
– Malice Vidrine
Feb 14 '14 at 17:24
@MaliceVidrine Thanks. I don't have a huge amount of background in set theory, though I have read into it a fair bit. Nice answer!
– gregkow
Feb 14 '14 at 17:26
@MaliceVidrine I did study some first-order logic some time back, but all this talk of sets within sets that contain or do not contain sets that contain/do not contain themselves, ad infinitum, is something I'm encountering the first time. So I guess it will take some time to break it down and digest.
– dotslash
Feb 14 '14 at 17:30
add a comment |Â
up vote
2
down vote
This is true, an element cannot be an element of itself. Thus, $xin A:xnotin x=A$, since $xnotin x$ is always true. We then conclude $B=A$, so by what we had before, $Bnotin A$. It's not absurd to derive a proof from a true statement such as $xnotin x$.
Yes, this is what also appears to be the case to me, but I think all the rigor in the book has some point to it. Unfortunately, Set Theory is beginning to give me headache. :D
– dotslash
Feb 14 '14 at 16:55
add a comment |Â
up vote
2
down vote
If you know that for every set $x$, $xnotin x$, then you know that for every element $xin A$, $xnotin x$ and therefore $xin B$. It follows immediately, if so, that $A=B$. So indeed $Bnotin A$.
However proving that $Anotin A$ requires the axiom of regularity which is harder to justify naively, whereas proving that $Bnotin A$ does not require that axiom.
What naive set theory usually proves (I am unfamiliar with Halmos' text, so it might not be the case here) is that there is no set "of all the sets which are not members of themselves", that is $xmid xnotin x$ is not a set. But this case $A$ is just any set and it may or may not be a member of itself, so the context differs.
add a comment |Â
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
accepted
@gregkow's answer is not incorrect, but I think it doesn't get to the real issue. Namely, his answer uses the axiom of foundation which rules out self-membership outright; but we can ignore that axiom and allow self-membership consistently and find that specification will still prove that $Bnotin A$.
Note that the central issue of Russel's paradox is that the Russel class, $R$, contains (or would contain if it existed) every set that's not a member of itself. We can use specification to show that $A$ must not contain every set of its members that aren't members of themselves, even if some of them are members of themselves.
Specification says that something is a member of $B$ if and only if it is in $A$ and not a member of itself. If $B$ is a member of itself then, by the definition of $B$, it must be in $A$ and not a member of itself; that's obviously contradictory. If $B$ is not a member of itself, then it must either be a member of itself or it's not in $A$; since the former would be paradoxical, it shows that $B$ exists and is not in $A$. One immediate consequence is that $A$ cannot contain its own power set.
And for once I'm not going to launch into an advertisement for NF!
– Malice Vidrine
Feb 13 '14 at 19:23
This seems like a good answer, but damned if I say I can understand Russel's Paradox . . . my head is beginning to hurt!
– dotslash
Feb 14 '14 at 16:58
If you know any proof methods for first order logic, I personally found it easier to wrap my head around a formal proof of contradiction from the single premise $forall x(xin Riff xnotin x)$. It sounds funny in informal English, but a clear proof is like two lines long.
– Malice Vidrine
Feb 14 '14 at 17:24
@MaliceVidrine Thanks. I don't have a huge amount of background in set theory, though I have read into it a fair bit. Nice answer!
– gregkow
Feb 14 '14 at 17:26
@MaliceVidrine I did study some first-order logic some time back, but all this talk of sets within sets that contain or do not contain sets that contain/do not contain themselves, ad infinitum, is something I'm encountering the first time. So I guess it will take some time to break it down and digest.
– dotslash
Feb 14 '14 at 17:30
add a comment |Â
up vote
3
down vote
accepted
@gregkow's answer is not incorrect, but I think it doesn't get to the real issue. Namely, his answer uses the axiom of foundation which rules out self-membership outright; but we can ignore that axiom and allow self-membership consistently and find that specification will still prove that $Bnotin A$.
Note that the central issue of Russel's paradox is that the Russel class, $R$, contains (or would contain if it existed) every set that's not a member of itself. We can use specification to show that $A$ must not contain every set of its members that aren't members of themselves, even if some of them are members of themselves.
Specification says that something is a member of $B$ if and only if it is in $A$ and not a member of itself. If $B$ is a member of itself then, by the definition of $B$, it must be in $A$ and not a member of itself; that's obviously contradictory. If $B$ is not a member of itself, then it must either be a member of itself or it's not in $A$; since the former would be paradoxical, it shows that $B$ exists and is not in $A$. One immediate consequence is that $A$ cannot contain its own power set.
And for once I'm not going to launch into an advertisement for NF!
– Malice Vidrine
Feb 13 '14 at 19:23
This seems like a good answer, but damned if I say I can understand Russel's Paradox . . . my head is beginning to hurt!
– dotslash
Feb 14 '14 at 16:58
If you know any proof methods for first order logic, I personally found it easier to wrap my head around a formal proof of contradiction from the single premise $forall x(xin Riff xnotin x)$. It sounds funny in informal English, but a clear proof is like two lines long.
– Malice Vidrine
Feb 14 '14 at 17:24
@MaliceVidrine Thanks. I don't have a huge amount of background in set theory, though I have read into it a fair bit. Nice answer!
– gregkow
Feb 14 '14 at 17:26
@MaliceVidrine I did study some first-order logic some time back, but all this talk of sets within sets that contain or do not contain sets that contain/do not contain themselves, ad infinitum, is something I'm encountering the first time. So I guess it will take some time to break it down and digest.
– dotslash
Feb 14 '14 at 17:30
add a comment |Â
up vote
3
down vote
accepted
up vote
3
down vote
accepted
@gregkow's answer is not incorrect, but I think it doesn't get to the real issue. Namely, his answer uses the axiom of foundation which rules out self-membership outright; but we can ignore that axiom and allow self-membership consistently and find that specification will still prove that $Bnotin A$.
Note that the central issue of Russel's paradox is that the Russel class, $R$, contains (or would contain if it existed) every set that's not a member of itself. We can use specification to show that $A$ must not contain every set of its members that aren't members of themselves, even if some of them are members of themselves.
Specification says that something is a member of $B$ if and only if it is in $A$ and not a member of itself. If $B$ is a member of itself then, by the definition of $B$, it must be in $A$ and not a member of itself; that's obviously contradictory. If $B$ is not a member of itself, then it must either be a member of itself or it's not in $A$; since the former would be paradoxical, it shows that $B$ exists and is not in $A$. One immediate consequence is that $A$ cannot contain its own power set.
@gregkow's answer is not incorrect, but I think it doesn't get to the real issue. Namely, his answer uses the axiom of foundation which rules out self-membership outright; but we can ignore that axiom and allow self-membership consistently and find that specification will still prove that $Bnotin A$.
Note that the central issue of Russel's paradox is that the Russel class, $R$, contains (or would contain if it existed) every set that's not a member of itself. We can use specification to show that $A$ must not contain every set of its members that aren't members of themselves, even if some of them are members of themselves.
Specification says that something is a member of $B$ if and only if it is in $A$ and not a member of itself. If $B$ is a member of itself then, by the definition of $B$, it must be in $A$ and not a member of itself; that's obviously contradictory. If $B$ is not a member of itself, then it must either be a member of itself or it's not in $A$; since the former would be paradoxical, it shows that $B$ exists and is not in $A$. One immediate consequence is that $A$ cannot contain its own power set.
answered Feb 13 '14 at 19:20
Malice Vidrine
5,32121019
5,32121019
And for once I'm not going to launch into an advertisement for NF!
– Malice Vidrine
Feb 13 '14 at 19:23
This seems like a good answer, but damned if I say I can understand Russel's Paradox . . . my head is beginning to hurt!
– dotslash
Feb 14 '14 at 16:58
If you know any proof methods for first order logic, I personally found it easier to wrap my head around a formal proof of contradiction from the single premise $forall x(xin Riff xnotin x)$. It sounds funny in informal English, but a clear proof is like two lines long.
– Malice Vidrine
Feb 14 '14 at 17:24
@MaliceVidrine Thanks. I don't have a huge amount of background in set theory, though I have read into it a fair bit. Nice answer!
– gregkow
Feb 14 '14 at 17:26
@MaliceVidrine I did study some first-order logic some time back, but all this talk of sets within sets that contain or do not contain sets that contain/do not contain themselves, ad infinitum, is something I'm encountering the first time. So I guess it will take some time to break it down and digest.
– dotslash
Feb 14 '14 at 17:30
add a comment |Â
And for once I'm not going to launch into an advertisement for NF!
– Malice Vidrine
Feb 13 '14 at 19:23
This seems like a good answer, but damned if I say I can understand Russel's Paradox . . . my head is beginning to hurt!
– dotslash
Feb 14 '14 at 16:58
If you know any proof methods for first order logic, I personally found it easier to wrap my head around a formal proof of contradiction from the single premise $forall x(xin Riff xnotin x)$. It sounds funny in informal English, but a clear proof is like two lines long.
– Malice Vidrine
Feb 14 '14 at 17:24
@MaliceVidrine Thanks. I don't have a huge amount of background in set theory, though I have read into it a fair bit. Nice answer!
– gregkow
Feb 14 '14 at 17:26
@MaliceVidrine I did study some first-order logic some time back, but all this talk of sets within sets that contain or do not contain sets that contain/do not contain themselves, ad infinitum, is something I'm encountering the first time. So I guess it will take some time to break it down and digest.
– dotslash
Feb 14 '14 at 17:30
And for once I'm not going to launch into an advertisement for NF!
– Malice Vidrine
Feb 13 '14 at 19:23
And for once I'm not going to launch into an advertisement for NF!
– Malice Vidrine
Feb 13 '14 at 19:23
This seems like a good answer, but damned if I say I can understand Russel's Paradox . . . my head is beginning to hurt!
– dotslash
Feb 14 '14 at 16:58
This seems like a good answer, but damned if I say I can understand Russel's Paradox . . . my head is beginning to hurt!
– dotslash
Feb 14 '14 at 16:58
If you know any proof methods for first order logic, I personally found it easier to wrap my head around a formal proof of contradiction from the single premise $forall x(xin Riff xnotin x)$. It sounds funny in informal English, but a clear proof is like two lines long.
– Malice Vidrine
Feb 14 '14 at 17:24
If you know any proof methods for first order logic, I personally found it easier to wrap my head around a formal proof of contradiction from the single premise $forall x(xin Riff xnotin x)$. It sounds funny in informal English, but a clear proof is like two lines long.
– Malice Vidrine
Feb 14 '14 at 17:24
@MaliceVidrine Thanks. I don't have a huge amount of background in set theory, though I have read into it a fair bit. Nice answer!
– gregkow
Feb 14 '14 at 17:26
@MaliceVidrine Thanks. I don't have a huge amount of background in set theory, though I have read into it a fair bit. Nice answer!
– gregkow
Feb 14 '14 at 17:26
@MaliceVidrine I did study some first-order logic some time back, but all this talk of sets within sets that contain or do not contain sets that contain/do not contain themselves, ad infinitum, is something I'm encountering the first time. So I guess it will take some time to break it down and digest.
– dotslash
Feb 14 '14 at 17:30
@MaliceVidrine I did study some first-order logic some time back, but all this talk of sets within sets that contain or do not contain sets that contain/do not contain themselves, ad infinitum, is something I'm encountering the first time. So I guess it will take some time to break it down and digest.
– dotslash
Feb 14 '14 at 17:30
add a comment |Â
up vote
2
down vote
This is true, an element cannot be an element of itself. Thus, $xin A:xnotin x=A$, since $xnotin x$ is always true. We then conclude $B=A$, so by what we had before, $Bnotin A$. It's not absurd to derive a proof from a true statement such as $xnotin x$.
Yes, this is what also appears to be the case to me, but I think all the rigor in the book has some point to it. Unfortunately, Set Theory is beginning to give me headache. :D
– dotslash
Feb 14 '14 at 16:55
add a comment |Â
up vote
2
down vote
This is true, an element cannot be an element of itself. Thus, $xin A:xnotin x=A$, since $xnotin x$ is always true. We then conclude $B=A$, so by what we had before, $Bnotin A$. It's not absurd to derive a proof from a true statement such as $xnotin x$.
Yes, this is what also appears to be the case to me, but I think all the rigor in the book has some point to it. Unfortunately, Set Theory is beginning to give me headache. :D
– dotslash
Feb 14 '14 at 16:55
add a comment |Â
up vote
2
down vote
up vote
2
down vote
This is true, an element cannot be an element of itself. Thus, $xin A:xnotin x=A$, since $xnotin x$ is always true. We then conclude $B=A$, so by what we had before, $Bnotin A$. It's not absurd to derive a proof from a true statement such as $xnotin x$.
This is true, an element cannot be an element of itself. Thus, $xin A:xnotin x=A$, since $xnotin x$ is always true. We then conclude $B=A$, so by what we had before, $Bnotin A$. It's not absurd to derive a proof from a true statement such as $xnotin x$.
answered Feb 13 '14 at 18:55
gregkow
54326
54326
Yes, this is what also appears to be the case to me, but I think all the rigor in the book has some point to it. Unfortunately, Set Theory is beginning to give me headache. :D
– dotslash
Feb 14 '14 at 16:55
add a comment |Â
Yes, this is what also appears to be the case to me, but I think all the rigor in the book has some point to it. Unfortunately, Set Theory is beginning to give me headache. :D
– dotslash
Feb 14 '14 at 16:55
Yes, this is what also appears to be the case to me, but I think all the rigor in the book has some point to it. Unfortunately, Set Theory is beginning to give me headache. :D
– dotslash
Feb 14 '14 at 16:55
Yes, this is what also appears to be the case to me, but I think all the rigor in the book has some point to it. Unfortunately, Set Theory is beginning to give me headache. :D
– dotslash
Feb 14 '14 at 16:55
add a comment |Â
up vote
2
down vote
If you know that for every set $x$, $xnotin x$, then you know that for every element $xin A$, $xnotin x$ and therefore $xin B$. It follows immediately, if so, that $A=B$. So indeed $Bnotin A$.
However proving that $Anotin A$ requires the axiom of regularity which is harder to justify naively, whereas proving that $Bnotin A$ does not require that axiom.
What naive set theory usually proves (I am unfamiliar with Halmos' text, so it might not be the case here) is that there is no set "of all the sets which are not members of themselves", that is $xmid xnotin x$ is not a set. But this case $A$ is just any set and it may or may not be a member of itself, so the context differs.
add a comment |Â
up vote
2
down vote
If you know that for every set $x$, $xnotin x$, then you know that for every element $xin A$, $xnotin x$ and therefore $xin B$. It follows immediately, if so, that $A=B$. So indeed $Bnotin A$.
However proving that $Anotin A$ requires the axiom of regularity which is harder to justify naively, whereas proving that $Bnotin A$ does not require that axiom.
What naive set theory usually proves (I am unfamiliar with Halmos' text, so it might not be the case here) is that there is no set "of all the sets which are not members of themselves", that is $xmid xnotin x$ is not a set. But this case $A$ is just any set and it may or may not be a member of itself, so the context differs.
add a comment |Â
up vote
2
down vote
up vote
2
down vote
If you know that for every set $x$, $xnotin x$, then you know that for every element $xin A$, $xnotin x$ and therefore $xin B$. It follows immediately, if so, that $A=B$. So indeed $Bnotin A$.
However proving that $Anotin A$ requires the axiom of regularity which is harder to justify naively, whereas proving that $Bnotin A$ does not require that axiom.
What naive set theory usually proves (I am unfamiliar with Halmos' text, so it might not be the case here) is that there is no set "of all the sets which are not members of themselves", that is $xmid xnotin x$ is not a set. But this case $A$ is just any set and it may or may not be a member of itself, so the context differs.
If you know that for every set $x$, $xnotin x$, then you know that for every element $xin A$, $xnotin x$ and therefore $xin B$. It follows immediately, if so, that $A=B$. So indeed $Bnotin A$.
However proving that $Anotin A$ requires the axiom of regularity which is harder to justify naively, whereas proving that $Bnotin A$ does not require that axiom.
What naive set theory usually proves (I am unfamiliar with Halmos' text, so it might not be the case here) is that there is no set "of all the sets which are not members of themselves", that is $xmid xnotin x$ is not a set. But this case $A$ is just any set and it may or may not be a member of itself, so the context differs.
edited Feb 13 '14 at 19:29
answered Feb 13 '14 at 19:00
Asaf Karagila♦
292k31403733
292k31403733
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f675393%2fconfused-about-x-notin-x-example-in-axiom-of-specification%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
1
"$A notin A$" is a truth value, not a set.
– Hurkyl
Feb 13 '14 at 19:21
Yes, but $B$ is. And my point is that it seems absurd that $B$ be defined like this. In fact, intuitively, it seems as if $B = A$!
– dotslash
Feb 14 '14 at 16:50