Mixing
How can I prove that set membership is irreflexive?
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
Essentially, I want to prove that $forall x(x notin x)$. I'm not sure where to begin with this. I have tried manipulating the axiom of specification to achieve this, as my guess is this is the axiom that enforces this (given it's purpose of eliminating Russell's paradox and the set of all sets, etc.).
In fact, I am trying to prove this statement as part of proving that the set of all sets doesn't exist. Here's my planned method:
- Assume that the set of all sets exist. From this I can derive $exists x(x in x)$
- Prove $forall x(x notin x)$, from which it follows that $neg exists x(x in x)$
- A contradiction arises, disproving the assumption in 1.
I am working through a set theory book, and trying to write proofs to satisfy myself that various statements in the book are true. For all I know, this might be proven further in the book, and may require further axioms that I have not yet encountered. At this point the only axioms I have are extensionality and the axiom schema of specification. Perhaps I need other axioms not yet encountered?
set-theory
asked Jul 17 at 4:52
esotechnica
358214
add a comment |Â
up vote
0
down vote
favorite
Essentially, I want to prove that $forall x(x notin x)$. I'm not sure where to begin with this. I have tried manipulating the axiom of specification to achieve this, as my guess is this is the axiom that enforces this (given it's purpose of eliminating Russell's paradox and the set of all sets, etc.).
In fact, I am trying to prove this statement as part of proving that the set of all sets doesn't exist. Here's my planned method:
- Assume that the set of all sets exist. From this I can derive $exists x(x in x)$
- Prove $forall x(x notin x)$, from which it follows that $neg exists x(x in x)$
- A contradiction arises, disproving the assumption in 1.
I am working through a set theory book, and trying to write proofs to satisfy myself that various statements in the book are true. For all I know, this might be proven further in the book, and may require further axioms that I have not yet encountered. At this point the only axioms I have are extensionality and the axiom schema of specification. Perhaps I need other axioms not yet encountered?
set-theory
asked Jul 17 at 4:52
esotechnica
358214
2
The axiom of regularity is necessarily needed to prove it.
– Hanul Jeon
Jul 17 at 4:59
2
Perhaps surprisingly, separation is not what enforces $forall x(xnotin x)$. It is foundation (and it is not provable without foundation). An easier way to show that a set of all sets doesn't exist is just from Russell's paradox alone. If it did, we could use separation to show the existence of Russell's paradoxical set. (Note that foundation is not necessary here.)
– spaceisdarkgreen
Jul 17 at 4:59
1
Also, on a side note, it's probably a bad habit to think of specification/separation as 'eliminating Russell's paradox' because adding axioms can never do anything but increase your chances of being inconsistent (the upside of course is that you can prove more things). What avoids Russell is that specification is a weakened form of the unrestricted comprehension axiom that was part of naive set theory.
– spaceisdarkgreen
Jul 17 at 5:42
Some authors use the word Regularity; others say Foundation.
– DanielWainfleet
Jul 24 at 18:41
add a comment |Â
up vote
0
down vote
favorite
up vote
0
down vote
favorite
Essentially, I want to prove that $forall x(x notin x)$. I'm not sure where to begin with this. I have tried manipulating the axiom of specification to achieve this, as my guess is this is the axiom that enforces this (given it's purpose of eliminating Russell's paradox and the set of all sets, etc.).
In fact, I am trying to prove this statement as part of proving that the set of all sets doesn't exist. Here's my planned method:
- Assume that the set of all sets exist. From this I can derive $exists x(x in x)$
- Prove $forall x(x notin x)$, from which it follows that $neg exists x(x in x)$
- A contradiction arises, disproving the assumption in 1.
I am working through a set theory book, and trying to write proofs to satisfy myself that various statements in the book are true. For all I know, this might be proven further in the book, and may require further axioms that I have not yet encountered. At this point the only axioms I have are extensionality and the axiom schema of specification. Perhaps I need other axioms not yet encountered?
set-theory
asked Jul 17 at 4:52
esotechnica
358214
Essentially, I want to prove that $forall x(x notin x)$. I'm not sure where to begin with this. I have tried manipulating the axiom of specification to achieve this, as my guess is this is the axiom that enforces this (given it's purpose of eliminating Russell's paradox and the set of all sets, etc.).
In fact, I am trying to prove this statement as part of proving that the set of all sets doesn't exist. Here's my planned method:
- Assume that the set of all sets exist. From this I can derive $exists x(x in x)$
- Prove $forall x(x notin x)$, from which it follows that $neg exists x(x in x)$
- A contradiction arises, disproving the assumption in 1.
I am working through a set theory book, and trying to write proofs to satisfy myself that various statements in the book are true. For all I know, this might be proven further in the book, and may require further axioms that I have not yet encountered. At this point the only axioms I have are extensionality and the axiom schema of specification. Perhaps I need other axioms not yet encountered?
set-theory
asked Jul 17 at 4:52
esotechnica
358214
asked Jul 17 at 4:52
esotechnica
358214
asked Jul 17 at 4:52
esotechnica
358214
asked Jul 17 at 4:52
esotechnica
358214
358214
2
The axiom of regularity is necessarily needed to prove it.
– Hanul Jeon
Jul 17 at 4:59
2
Perhaps surprisingly, separation is not what enforces $forall x(xnotin x)$. It is foundation (and it is not provable without foundation). An easier way to show that a set of all sets doesn't exist is just from Russell's paradox alone. If it did, we could use separation to show the existence of Russell's paradoxical set. (Note that foundation is not necessary here.)
– spaceisdarkgreen
Jul 17 at 4:59
1
Also, on a side note, it's probably a bad habit to think of specification/separation as 'eliminating Russell's paradox' because adding axioms can never do anything but increase your chances of being inconsistent (the upside of course is that you can prove more things). What avoids Russell is that specification is a weakened form of the unrestricted comprehension axiom that was part of naive set theory.
– spaceisdarkgreen
Jul 17 at 5:42
Some authors use the word Regularity; others say Foundation.
– DanielWainfleet
Jul 24 at 18:41
add a comment |Â
2
The axiom of regularity is necessarily needed to prove it.
– Hanul Jeon
Jul 17 at 4:59
2
Perhaps surprisingly, separation is not what enforces $forall x(xnotin x)$. It is foundation (and it is not provable without foundation). An easier way to show that a set of all sets doesn't exist is just from Russell's paradox alone. If it did, we could use separation to show the existence of Russell's paradoxical set. (Note that foundation is not necessary here.)
– spaceisdarkgreen
Jul 17 at 4:59
1
Also, on a side note, it's probably a bad habit to think of specification/separation as 'eliminating Russell's paradox' because adding axioms can never do anything but increase your chances of being inconsistent (the upside of course is that you can prove more things). What avoids Russell is that specification is a weakened form of the unrestricted comprehension axiom that was part of naive set theory.
– spaceisdarkgreen
Jul 17 at 5:42
Some authors use the word Regularity; others say Foundation.
– DanielWainfleet
Jul 24 at 18:41
2
2
The axiom of regularity is necessarily needed to prove it.
– Hanul Jeon
Jul 17 at 4:59
The axiom of regularity is necessarily needed to prove it.
– Hanul Jeon
Jul 17 at 4:59
2
2
Perhaps surprisingly, separation is not what enforces $forall x(xnotin x)$. It is foundation (and it is not provable without foundation). An easier way to show that a set of all sets doesn't exist is just from Russell's paradox alone. If it did, we could use separation to show the existence of Russell's paradoxical set. (Note that foundation is not necessary here.)
– spaceisdarkgreen
Jul 17 at 4:59
Perhaps surprisingly, separation is not what enforces $forall x(xnotin x)$. It is foundation (and it is not provable without foundation). An easier way to show that a set of all sets doesn't exist is just from Russell's paradox alone. If it did, we could use separation to show the existence of Russell's paradoxical set. (Note that foundation is not necessary here.)
– spaceisdarkgreen
Jul 17 at 4:59
1
1
Also, on a side note, it's probably a bad habit to think of specification/separation as 'eliminating Russell's paradox' because adding axioms can never do anything but increase your chances of being inconsistent (the upside of course is that you can prove more things). What avoids Russell is that specification is a weakened form of the unrestricted comprehension axiom that was part of naive set theory.
– spaceisdarkgreen
Jul 17 at 5:42
Also, on a side note, it's probably a bad habit to think of specification/separation as 'eliminating Russell's paradox' because adding axioms can never do anything but increase your chances of being inconsistent (the upside of course is that you can prove more things). What avoids Russell is that specification is a weakened form of the unrestricted comprehension axiom that was part of naive set theory.
– spaceisdarkgreen
Jul 17 at 5:42
Some authors use the word Regularity; others say Foundation.
– DanielWainfleet
Jul 24 at 18:41
Some authors use the word Regularity; others say Foundation.
– DanielWainfleet
Jul 24 at 18:41
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
3
down vote
accepted
You need the axiom of regularity to prove your statement. The axiom of regularity states every non-empty set has a $in$-minimal element in the following sense: if $xin A$ is a $in$-minimal element of $A$ then no $yin x$ satisfy $yin A$.
Now you can prove your statement as follows: assume that there is $x$ such that $xin x$. Take $A=x$, then $A$ must have a $in$-minimal element. As $A$ is singleton, such $in$-minimal element must be $x$. However it is impossible, since $xin x$ satisfies $xin A$.
(In fact, you can prove stronger theorem: the axiom of regularity proves there is no $in$-descending chain. That is, there is no sequence $langle x_n mid n=0,1,2cdotsrangle$ such that $x_0ni x_1ni x_2nicdots$.)
Axiom of regulariry is necessary to prove the statement. Assuming there is a set $q$ such that $q=q$ does not derive any contradiction under ZFC without regularity. (A set $q$ such that $q=q$ is known as Quine atom.)
answered Jul 17 at 5:03
Hanul Jeon
17.2k42579
1
Kunen's textbook (Chapter IV, Exercises 18 & 19) shows how to obtain, from ZFC, a class model $Bbb M=(M,E)$ that satisfies all the axioms of ZFC except Regularity (Foundation) but $Bbb M$ satisfies $ exists x; (x=x).$ So if the rest of the axioms are consistent then they cannot disprove the existence of a Quine atom.
– DanielWainfleet
Jul 24 at 19:00
@DanielWainfleet Thank you for your informative comment.
– Hanul Jeon
Jul 25 at 10:12
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
accepted
You need the axiom of regularity to prove your statement. The axiom of regularity states every non-empty set has a $in$-minimal element in the following sense: if $xin A$ is a $in$-minimal element of $A$ then no $yin x$ satisfy $yin A$.
Now you can prove your statement as follows: assume that there is $x$ such that $xin x$. Take $A=x$, then $A$ must have a $in$-minimal element. As $A$ is singleton, such $in$-minimal element must be $x$. However it is impossible, since $xin x$ satisfies $xin A$.
(In fact, you can prove stronger theorem: the axiom of regularity proves there is no $in$-descending chain. That is, there is no sequence $langle x_n mid n=0,1,2cdotsrangle$ such that $x_0ni x_1ni x_2nicdots$.)
Axiom of regulariry is necessary to prove the statement. Assuming there is a set $q$ such that $q=q$ does not derive any contradiction under ZFC without regularity. (A set $q$ such that $q=q$ is known as Quine atom.)
answered Jul 17 at 5:03
Hanul Jeon
17.2k42579
1
Kunen's textbook (Chapter IV, Exercises 18 & 19) shows how to obtain, from ZFC, a class model $Bbb M=(M,E)$ that satisfies all the axioms of ZFC except Regularity (Foundation) but $Bbb M$ satisfies $ exists x; (x=x).$ So if the rest of the axioms are consistent then they cannot disprove the existence of a Quine atom.
– DanielWainfleet
Jul 24 at 19:00
@DanielWainfleet Thank you for your informative comment.
– Hanul Jeon
Jul 25 at 10:12
add a comment |Â
up vote
3
down vote
accepted
You need the axiom of regularity to prove your statement. The axiom of regularity states every non-empty set has a $in$-minimal element in the following sense: if $xin A$ is a $in$-minimal element of $A$ then no $yin x$ satisfy $yin A$.
Now you can prove your statement as follows: assume that there is $x$ such that $xin x$. Take $A=x$, then $A$ must have a $in$-minimal element. As $A$ is singleton, such $in$-minimal element must be $x$. However it is impossible, since $xin x$ satisfies $xin A$.
(In fact, you can prove stronger theorem: the axiom of regularity proves there is no $in$-descending chain. That is, there is no sequence $langle x_n mid n=0,1,2cdotsrangle$ such that $x_0ni x_1ni x_2nicdots$.)
Axiom of regulariry is necessary to prove the statement. Assuming there is a set $q$ such that $q=q$ does not derive any contradiction under ZFC without regularity. (A set $q$ such that $q=q$ is known as Quine atom.)
answered Jul 17 at 5:03
Hanul Jeon
17.2k42579
1
Kunen's textbook (Chapter IV, Exercises 18 & 19) shows how to obtain, from ZFC, a class model $Bbb M=(M,E)$ that satisfies all the axioms of ZFC except Regularity (Foundation) but $Bbb M$ satisfies $ exists x; (x=x).$ So if the rest of the axioms are consistent then they cannot disprove the existence of a Quine atom.
– DanielWainfleet
Jul 24 at 19:00
@DanielWainfleet Thank you for your informative comment.
– Hanul Jeon
Jul 25 at 10:12
add a comment |Â
up vote
3
down vote
accepted
up vote
3
down vote
accepted
You need the axiom of regularity to prove your statement. The axiom of regularity states every non-empty set has a $in$-minimal element in the following sense: if $xin A$ is a $in$-minimal element of $A$ then no $yin x$ satisfy $yin A$.
Now you can prove your statement as follows: assume that there is $x$ such that $xin x$. Take $A=x$, then $A$ must have a $in$-minimal element. As $A$ is singleton, such $in$-minimal element must be $x$. However it is impossible, since $xin x$ satisfies $xin A$.
(In fact, you can prove stronger theorem: the axiom of regularity proves there is no $in$-descending chain. That is, there is no sequence $langle x_n mid n=0,1,2cdotsrangle$ such that $x_0ni x_1ni x_2nicdots$.)
Axiom of regulariry is necessary to prove the statement. Assuming there is a set $q$ such that $q=q$ does not derive any contradiction under ZFC without regularity. (A set $q$ such that $q=q$ is known as Quine atom.)
answered Jul 17 at 5:03
Hanul Jeon
17.2k42579
You need the axiom of regularity to prove your statement. The axiom of regularity states every non-empty set has a $in$-minimal element in the following sense: if $xin A$ is a $in$-minimal element of $A$ then no $yin x$ satisfy $yin A$.
Now you can prove your statement as follows: assume that there is $x$ such that $xin x$. Take $A=x$, then $A$ must have a $in$-minimal element. As $A$ is singleton, such $in$-minimal element must be $x$. However it is impossible, since $xin x$ satisfies $xin A$.
(In fact, you can prove stronger theorem: the axiom of regularity proves there is no $in$-descending chain. That is, there is no sequence $langle x_n mid n=0,1,2cdotsrangle$ such that $x_0ni x_1ni x_2nicdots$.)
Axiom of regulariry is necessary to prove the statement. Assuming there is a set $q$ such that $q=q$ does not derive any contradiction under ZFC without regularity. (A set $q$ such that $q=q$ is known as Quine atom.)
answered Jul 17 at 5:03
Hanul Jeon
17.2k42579
answered Jul 17 at 5:03
Hanul Jeon
17.2k42579
answered Jul 17 at 5:03
Hanul Jeon
17.2k42579
answered Jul 17 at 5:03
Hanul Jeon
17.2k42579
17.2k42579
1
Kunen's textbook (Chapter IV, Exercises 18 & 19) shows how to obtain, from ZFC, a class model $Bbb M=(M,E)$ that satisfies all the axioms of ZFC except Regularity (Foundation) but $Bbb M$ satisfies $ exists x; (x=x).$ So if the rest of the axioms are consistent then they cannot disprove the existence of a Quine atom.
– DanielWainfleet
Jul 24 at 19:00
@DanielWainfleet Thank you for your informative comment.
– Hanul Jeon
Jul 25 at 10:12
add a comment |Â
1
Kunen's textbook (Chapter IV, Exercises 18 & 19) shows how to obtain, from ZFC, a class model $Bbb M=(M,E)$ that satisfies all the axioms of ZFC except Regularity (Foundation) but $Bbb M$ satisfies $ exists x; (x=x).$ So if the rest of the axioms are consistent then they cannot disprove the existence of a Quine atom.
– DanielWainfleet
Jul 24 at 19:00
@DanielWainfleet Thank you for your informative comment.
– Hanul Jeon
Jul 25 at 10:12
1
1
Kunen's textbook (Chapter IV, Exercises 18 & 19) shows how to obtain, from ZFC, a class model $Bbb M=(M,E)$ that satisfies all the axioms of ZFC except Regularity (Foundation) but $Bbb M$ satisfies $ exists x; (x=x).$ So if the rest of the axioms are consistent then they cannot disprove the existence of a Quine atom.
– DanielWainfleet
Jul 24 at 19:00
Kunen's textbook (Chapter IV, Exercises 18 & 19) shows how to obtain, from ZFC, a class model $Bbb M=(M,E)$ that satisfies all the axioms of ZFC except Regularity (Foundation) but $Bbb M$ satisfies $ exists x; (x=x).$ So if the rest of the axioms are consistent then they cannot disprove the existence of a Quine atom.
– DanielWainfleet
Jul 24 at 19:00
@DanielWainfleet Thank you for your informative comment.
– Hanul Jeon
Jul 25 at 10:12
@DanielWainfleet Thank you for your informative comment.
– Hanul Jeon
Jul 25 at 10:12
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%2f2854142%2fhow-can-i-prove-that-set-membership-is-irreflexive%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
2
The axiom of regularity is necessarily needed to prove it.
– Hanul Jeon
Jul 17 at 4:59
2
Perhaps surprisingly, separation is not what enforces $forall x(xnotin x)$. It is foundation (and it is not provable without foundation). An easier way to show that a set of all sets doesn't exist is just from Russell's paradox alone. If it did, we could use separation to show the existence of Russell's paradoxical set. (Note that foundation is not necessary here.)
– spaceisdarkgreen
Jul 17 at 4:59
1
Also, on a side note, it's probably a bad habit to think of specification/separation as 'eliminating Russell's paradox' because adding axioms can never do anything but increase your chances of being inconsistent (the upside of course is that you can prove more things). What avoids Russell is that specification is a weakened form of the unrestricted comprehension axiom that was part of naive set theory.
– spaceisdarkgreen
Jul 17 at 5:42
Some authors use the word Regularity; others say Foundation.
– DanielWainfleet
Jul 24 at 18:41