Mixing
How to apply the axioms in set theory?
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
Consider these axioms, from my book:
Axiom of equality $∀x ∀y [x = y → ∀z (x ∈ z ↔ y ∈ z)]$
Axiom of extensionality $∀x ∀y [x = y ↔ ∀u (u ∈ x ↔ u ∈ y)]$
The Axiom of Existence $∃z z = ∅$
The Axiom of Pairing $∀x ∀y ∃z z = x, y$
I understand these axioms, and I am given a theorem and the exercise of solving the $4,5$ parts(not homework, really, I'm self studying this), but I don't get how to apply them. The book says that the first 3 are immediate consequences of the Axiom of Extensionality, but is that all? I don't see how they are immdeiate consequences.
I am used to applying simple properties like,
$forall a forall b forall c(a=b implies a+c = b+c)$, but These axioms are hard to work with.
Theorem 1:
$qquad1) (forall x) x=x$
$qquad2) ∀x ∀y x = y → y = x$
$qquad3) ∀x ∀y ∀z [(x = y ∧ y = z) → x = z$
$qquad4) ∀x ∀y ∃z z = <x, y>$
$qquad5) ∀u ∀v ∀x ∀y [<u, v> = <x, y> ↔ (u = x ∧ v = y)].$
How do you correctly apply the axioms?
Edit: Book Title
An Introduction To Set Theory
by Professor William A. R. Weiss
http://www.math.toronto.edu/weiss/set_theory.pdf
elementary-set-theory proof-writing proof-explanation
asked Jul 15 at 9:54
JavaLearner
13211
 |Â
show 2 more comments
up vote
1
down vote
favorite
Consider these axioms, from my book:
Axiom of equality $∀x ∀y [x = y → ∀z (x ∈ z ↔ y ∈ z)]$
Axiom of extensionality $∀x ∀y [x = y ↔ ∀u (u ∈ x ↔ u ∈ y)]$
The Axiom of Existence $∃z z = ∅$
The Axiom of Pairing $∀x ∀y ∃z z = x, y$
I understand these axioms, and I am given a theorem and the exercise of solving the $4,5$ parts(not homework, really, I'm self studying this), but I don't get how to apply them. The book says that the first 3 are immediate consequences of the Axiom of Extensionality, but is that all? I don't see how they are immdeiate consequences.
I am used to applying simple properties like,
$forall a forall b forall c(a=b implies a+c = b+c)$, but These axioms are hard to work with.
Theorem 1:
$qquad1) (forall x) x=x$
$qquad2) ∀x ∀y x = y → y = x$
$qquad3) ∀x ∀y ∀z [(x = y ∧ y = z) → x = z$
$qquad4) ∀x ∀y ∃z z = <x, y>$
$qquad5) ∀u ∀v ∀x ∀y [<u, v> = <x, y> ↔ (u = x ∧ v = y)].$
How do you correctly apply the axioms?
Edit: Book Title
An Introduction To Set Theory
by Professor William A. R. Weiss
http://www.math.toronto.edu/weiss/set_theory.pdf
elementary-set-theory proof-writing proof-explanation
asked Jul 15 at 9:54
JavaLearner
13211
2) is straightforward using the answer below: from $x=y$ we have $∀u(u∈x↔u∈y)$; but by logic we have $∀u(u∈y↔u∈x)$ and thus...
– Mauro ALLEGRANZA
Jul 15 at 10:47
The same for 3): use transitivity of $↔$.
– Mauro ALLEGRANZA
Jul 15 at 10:47
For 4) you need the definition of ordered pair (usually based on the pair $ x,y $.
– Mauro ALLEGRANZA
Jul 15 at 10:48
@MauroALLEGRANZA so for the transitivity,$x=y∧y=z implies∀u(u∈x↔u∈y) ∧ ∀u(u∈y↔u∈z) implies ∀u(u∈x↔u∈z) implies x =z$
– JavaLearner
Jul 15 at 22:38
As for the pairing, $forall xforall yexists z (z=x,y) implies forall x forall y exists u(u=x,x,y) implies forall x forall y exists u(u=⟨x,y⟩)$
– JavaLearner
Jul 15 at 22:47
 |Â
show 2 more comments
up vote
1
down vote
favorite
up vote
1
down vote
favorite
Consider these axioms, from my book:
Axiom of equality $∀x ∀y [x = y → ∀z (x ∈ z ↔ y ∈ z)]$
Axiom of extensionality $∀x ∀y [x = y ↔ ∀u (u ∈ x ↔ u ∈ y)]$
The Axiom of Existence $∃z z = ∅$
The Axiom of Pairing $∀x ∀y ∃z z = x, y$
I understand these axioms, and I am given a theorem and the exercise of solving the $4,5$ parts(not homework, really, I'm self studying this), but I don't get how to apply them. The book says that the first 3 are immediate consequences of the Axiom of Extensionality, but is that all? I don't see how they are immdeiate consequences.
I am used to applying simple properties like,
$forall a forall b forall c(a=b implies a+c = b+c)$, but These axioms are hard to work with.
Theorem 1:
$qquad1) (forall x) x=x$
$qquad2) ∀x ∀y x = y → y = x$
$qquad3) ∀x ∀y ∀z [(x = y ∧ y = z) → x = z$
$qquad4) ∀x ∀y ∃z z = <x, y>$
$qquad5) ∀u ∀v ∀x ∀y [<u, v> = <x, y> ↔ (u = x ∧ v = y)].$
How do you correctly apply the axioms?
Edit: Book Title
An Introduction To Set Theory
by Professor William A. R. Weiss
http://www.math.toronto.edu/weiss/set_theory.pdf
elementary-set-theory proof-writing proof-explanation
asked Jul 15 at 9:54
JavaLearner
13211
Consider these axioms, from my book:
Axiom of equality $∀x ∀y [x = y → ∀z (x ∈ z ↔ y ∈ z)]$
Axiom of extensionality $∀x ∀y [x = y ↔ ∀u (u ∈ x ↔ u ∈ y)]$
The Axiom of Existence $∃z z = ∅$
The Axiom of Pairing $∀x ∀y ∃z z = x, y$
I understand these axioms, and I am given a theorem and the exercise of solving the $4,5$ parts(not homework, really, I'm self studying this), but I don't get how to apply them. The book says that the first 3 are immediate consequences of the Axiom of Extensionality, but is that all? I don't see how they are immdeiate consequences.
I am used to applying simple properties like,
$forall a forall b forall c(a=b implies a+c = b+c)$, but These axioms are hard to work with.
Theorem 1:
$qquad1) (forall x) x=x$
$qquad2) ∀x ∀y x = y → y = x$
$qquad3) ∀x ∀y ∀z [(x = y ∧ y = z) → x = z$
$qquad4) ∀x ∀y ∃z z = <x, y>$
$qquad5) ∀u ∀v ∀x ∀y [<u, v> = <x, y> ↔ (u = x ∧ v = y)].$
How do you correctly apply the axioms?
Edit: Book Title
An Introduction To Set Theory
by Professor William A. R. Weiss
http://www.math.toronto.edu/weiss/set_theory.pdf
elementary-set-theory proof-writing proof-explanation
asked Jul 15 at 9:54
JavaLearner
13211
edited Jul 17 at 9:04
asked Jul 15 at 9:54
JavaLearner
13211
asked Jul 15 at 9:54
JavaLearner
13211
asked Jul 15 at 9:54
JavaLearner
13211
13211
2) is straightforward using the answer below: from $x=y$ we have $∀u(u∈x↔u∈y)$; but by logic we have $∀u(u∈y↔u∈x)$ and thus...
– Mauro ALLEGRANZA
Jul 15 at 10:47
The same for 3): use transitivity of $↔$.
– Mauro ALLEGRANZA
Jul 15 at 10:47
For 4) you need the definition of ordered pair (usually based on the pair $ x,y $.
– Mauro ALLEGRANZA
Jul 15 at 10:48
@MauroALLEGRANZA so for the transitivity,$x=y∧y=z implies∀u(u∈x↔u∈y) ∧ ∀u(u∈y↔u∈z) implies ∀u(u∈x↔u∈z) implies x =z$
– JavaLearner
Jul 15 at 22:38
As for the pairing, $forall xforall yexists z (z=x,y) implies forall x forall y exists u(u=x,x,y) implies forall x forall y exists u(u=⟨x,y⟩)$
– JavaLearner
Jul 15 at 22:47
 |Â
show 2 more comments
2) is straightforward using the answer below: from $x=y$ we have $∀u(u∈x↔u∈y)$; but by logic we have $∀u(u∈y↔u∈x)$ and thus...
– Mauro ALLEGRANZA
Jul 15 at 10:47
The same for 3): use transitivity of $↔$.
– Mauro ALLEGRANZA
Jul 15 at 10:47
For 4) you need the definition of ordered pair (usually based on the pair $ x,y $.
– Mauro ALLEGRANZA
Jul 15 at 10:48
@MauroALLEGRANZA so for the transitivity,$x=y∧y=z implies∀u(u∈x↔u∈y) ∧ ∀u(u∈y↔u∈z) implies ∀u(u∈x↔u∈z) implies x =z$
– JavaLearner
Jul 15 at 22:38
As for the pairing, $forall xforall yexists z (z=x,y) implies forall x forall y exists u(u=x,x,y) implies forall x forall y exists u(u=⟨x,y⟩)$
– JavaLearner
Jul 15 at 22:47
2) is straightforward using the answer below: from $x=y$ we have $∀u(u∈x↔u∈y)$; but by logic we have $∀u(u∈y↔u∈x)$ and thus...
– Mauro ALLEGRANZA
Jul 15 at 10:47
2) is straightforward using the answer below: from $x=y$ we have $∀u(u∈x↔u∈y)$; but by logic we have $∀u(u∈y↔u∈x)$ and thus...
– Mauro ALLEGRANZA
Jul 15 at 10:47
The same for 3): use transitivity of $↔$.
– Mauro ALLEGRANZA
Jul 15 at 10:47
The same for 3): use transitivity of $↔$.
– Mauro ALLEGRANZA
Jul 15 at 10:47
For 4) you need the definition of ordered pair (usually based on the pair $ x,y $.
– Mauro ALLEGRANZA
Jul 15 at 10:48
For 4) you need the definition of ordered pair (usually based on the pair $ x,y $.
– Mauro ALLEGRANZA
Jul 15 at 10:48
@MauroALLEGRANZA so for the transitivity,$x=y∧y=z implies∀u(u∈x↔u∈y) ∧ ∀u(u∈y↔u∈z) implies ∀u(u∈x↔u∈z) implies x =z$
– JavaLearner
Jul 15 at 22:38
@MauroALLEGRANZA so for the transitivity,$x=y∧y=z implies∀u(u∈x↔u∈y) ∧ ∀u(u∈y↔u∈z) implies ∀u(u∈x↔u∈z) implies x =z$
– JavaLearner
Jul 15 at 22:38
As for the pairing, $forall xforall yexists z (z=x,y) implies forall x forall y exists u(u=x,x,y) implies forall x forall y exists u(u=⟨x,y⟩)$
– JavaLearner
Jul 15 at 22:47
As for the pairing, $forall xforall yexists z (z=x,y) implies forall x forall y exists u(u=x,x,y) implies forall x forall y exists u(u=⟨x,y⟩)$
– JavaLearner
Jul 15 at 22:47
 |Â
show 2 more comments
3 Answers
3
active
oldest
votes
up vote
4
down vote
accepted
TL;DR The book you're using does things in an unnecessarily confusing way, and you should consider finding another book to self-learn from.
The first two axioms and first three parts of your theorem do make some sense together. The axioms apparently define how the $=$ symbol behaves in the theory, and parts (1), (2), (3) then tell you that those axioms force $=$ to be an equivalence relation. So far so good, and it is indeed an immediate consequence of the second of the axioms. (Mason's answer sketches the beginning of how that works).
However, choosing to have those two axioms in the first place is a rather iffy decision by the book. Generally there are two ways to approach equality in axiomatic set theory:
The most common these days is to consider $=$ and its properties to built into the logic you reason about sets with. This way, you would develop ways to work with $=$ before you even start speaking about the axioms of set theory specifically. Doing things this way, the (1), (2), (3) you quote, as well as the book's "Axiom of Equality" and the "$to$" direction of its "Axiom of Extensionality" would be axioms of logic, not about set theory in particular.
Alternatively, for those who want to build set theory with an absolutely minimal logical footprint, declare that your language does not contain an $=$ symbol at all, but when you write $x=y$ it is really an abbreviation for some more complex formula -- which could be either $forall u(uin x leftrightarrow uin y)$ or $forall z(xin zleftrightarrow yin z)$. Depending on the choice, either your book's "Axiom of Equality" or its "Axiom of Extensionality" would become vacuous, and the other would be a real axiom that tells you something about sets. Your (1), (2), (3) would then be something you need to prove by unfolding the abbreviation, but the remaining axiom would not be necessary for that.
What the book does seems to be a mixture of the two strategies which gives you the worst of both worlds and the benefit of neither. Apparently it does consider $=$ to be an actual symbol in its language (or it wouldn't need both axioms), but it doesn't assume that logic tells you how it works, so you still need to derive the properties of equality by hand.
The axioms of "Existence" and "Pairing" are phrased very mysteriously. It looks like the book considers $emptyset$ and $,$ to be something that is already part of the language -- but if so it ought to present axioms that tell you how they behave. That's not what the two axioms it does give you do. They just assert that the symbols can be used -- and that is certainly something that pure logic itself already ought to give you, at least once you have proved $forall x(x=x)$.
The only way I can imagine those two axioms to have any real meaning is if the book has secretly defined the combination "$x = emptyset$" to be an abbreviation of something like $forall z(znotin x)$. And the combination "$z=x,y$" would be an abbreviation of $forall u(uin z leftrightarrow u=x lor u=y)$.
But if so, the real meat is still in those abbreviations. And it's rather confusing that in some contexts you would need $=$ to be a symbol in its own right (otherwise the two first axioms would not both be meaningful), and in other contexts it's part of a notation that's an abbreviation.
In parts (4) and (5) of the theorem, things get even more confusing, because the notation $langle x,yrangle$ suddenly pops out of nowhere. Unless you have axioms for it, it too must be an abbreviation.
It's usual, following Kuratowski, to define $langle x,yrangle$ to mean $x,x,y$. But this definition will not work "out of the box" unless $,$ is a function symbol, which we have just argued it can't really be.
So perhaps the entire combo $z=langle x,yrangle$ is an abbreviation, for something like $exists sexists t(z=s,tland s=x,xland t=x,y)$. That would at least work. But then the notation $langle u,vrangle=langle x,yrangle$ is still not defined, and you need to appeal to some kind of "of course you can figure out what this actually means".
Commonly, presenting general rules for treating notations as function symbols when they're really defined as abbreviated relations would be part of the book's development of logic that comes before set theory. But I'm getting the impression that such a development has not actually taken place in your book. An author careful enough to do that would certainly have steered clear of the problems with the axioms already presented.
answered Jul 15 at 13:03
Henning Makholm
226k16291520
Maybe it would be valuable for OP to include the title and author?
– Mason
Jul 17 at 8:05
add a comment |Â
up vote
1
down vote
Just something that may help you get started. Not a complete answer.
Axiom of extensionality $forall x forall y [x = y ↔ forall u (u ∈ x ↔ u ∈ y)]$
What happens if we let $x=y$?
Well then $forall u (u ∈ x ↔ u ∈ y)]$ becomes $forall u (u ∈ x ↔ u ∈ x)]$ but this must evaluate to true. Because it is saying that a statement implies itself. Something like $S↔S$, But then this implies that $x=x$ as this is the left hand side of this axiom.
answered Jul 15 at 10:22
Mason
1,2401224
add a comment |Â
up vote
1
down vote
For $3$,
$x=y∧y=z implies $ (By extensionality )
$∀u(u∈x↔u∈y)∧∀u(u∈y↔u∈z) implies $ (By the transitivity of $↔$)
$∀u(u∈x↔u∈z) implies $ (By extensionality)
$x=z$
For 4,
$∀x∀y∃z(z=x,y)$ by the pairing axiom. Now by applying the pairing axiom again we find
$∃u(u=x,x,y)$. Note that the pairing axiom can be written $∀a∀b∃c(c=a,b)$. We get the desired result by taking $a=x$, $b=z= x,y$ and $c=u$.
$∀x∀y∃u(u=⟨x,y⟩)$
edited Jul 17 at 8:49
Mason
1,2401224
answered Jul 16 at 3:41
JavaLearner
13211
1
I am not sure how to prove the last one.
– JavaLearner
Jul 16 at 3:50
1
I think we will need your texts definition of $⟨x,y⟩$ to make progress.
– Mason
Jul 17 at 8:07
1
It is $x,x,y$
– JavaLearner
Jul 17 at 8:09
1
I think 3 looks fine + I am not sure if we are allowed to use transitivity in middle implication. I worry that we are begging the question but someone who knows more than me will let us know. I am sorry to put your words in your mouth if you wanted to justify the implication in some other way. How would you justify the steps for $4$? These (How?)s are for you to change as you see fit.
– Mason
Jul 17 at 8:24
1
@Mason, just making sure you recieve a notification.
– JavaLearner
Jul 17 at 8:32
 |Â
show 3 more comments
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
4
down vote
accepted
TL;DR The book you're using does things in an unnecessarily confusing way, and you should consider finding another book to self-learn from.
The first two axioms and first three parts of your theorem do make some sense together. The axioms apparently define how the $=$ symbol behaves in the theory, and parts (1), (2), (3) then tell you that those axioms force $=$ to be an equivalence relation. So far so good, and it is indeed an immediate consequence of the second of the axioms. (Mason's answer sketches the beginning of how that works).
However, choosing to have those two axioms in the first place is a rather iffy decision by the book. Generally there are two ways to approach equality in axiomatic set theory:
The most common these days is to consider $=$ and its properties to built into the logic you reason about sets with. This way, you would develop ways to work with $=$ before you even start speaking about the axioms of set theory specifically. Doing things this way, the (1), (2), (3) you quote, as well as the book's "Axiom of Equality" and the "$to$" direction of its "Axiom of Extensionality" would be axioms of logic, not about set theory in particular.
Alternatively, for those who want to build set theory with an absolutely minimal logical footprint, declare that your language does not contain an $=$ symbol at all, but when you write $x=y$ it is really an abbreviation for some more complex formula -- which could be either $forall u(uin x leftrightarrow uin y)$ or $forall z(xin zleftrightarrow yin z)$. Depending on the choice, either your book's "Axiom of Equality" or its "Axiom of Extensionality" would become vacuous, and the other would be a real axiom that tells you something about sets. Your (1), (2), (3) would then be something you need to prove by unfolding the abbreviation, but the remaining axiom would not be necessary for that.
What the book does seems to be a mixture of the two strategies which gives you the worst of both worlds and the benefit of neither. Apparently it does consider $=$ to be an actual symbol in its language (or it wouldn't need both axioms), but it doesn't assume that logic tells you how it works, so you still need to derive the properties of equality by hand.
The axioms of "Existence" and "Pairing" are phrased very mysteriously. It looks like the book considers $emptyset$ and $,$ to be something that is already part of the language -- but if so it ought to present axioms that tell you how they behave. That's not what the two axioms it does give you do. They just assert that the symbols can be used -- and that is certainly something that pure logic itself already ought to give you, at least once you have proved $forall x(x=x)$.
The only way I can imagine those two axioms to have any real meaning is if the book has secretly defined the combination "$x = emptyset$" to be an abbreviation of something like $forall z(znotin x)$. And the combination "$z=x,y$" would be an abbreviation of $forall u(uin z leftrightarrow u=x lor u=y)$.
But if so, the real meat is still in those abbreviations. And it's rather confusing that in some contexts you would need $=$ to be a symbol in its own right (otherwise the two first axioms would not both be meaningful), and in other contexts it's part of a notation that's an abbreviation.
In parts (4) and (5) of the theorem, things get even more confusing, because the notation $langle x,yrangle$ suddenly pops out of nowhere. Unless you have axioms for it, it too must be an abbreviation.
It's usual, following Kuratowski, to define $langle x,yrangle$ to mean $x,x,y$. But this definition will not work "out of the box" unless $,$ is a function symbol, which we have just argued it can't really be.
So perhaps the entire combo $z=langle x,yrangle$ is an abbreviation, for something like $exists sexists t(z=s,tland s=x,xland t=x,y)$. That would at least work. But then the notation $langle u,vrangle=langle x,yrangle$ is still not defined, and you need to appeal to some kind of "of course you can figure out what this actually means".
Commonly, presenting general rules for treating notations as function symbols when they're really defined as abbreviated relations would be part of the book's development of logic that comes before set theory. But I'm getting the impression that such a development has not actually taken place in your book. An author careful enough to do that would certainly have steered clear of the problems with the axioms already presented.
answered Jul 15 at 13:03
Henning Makholm
226k16291520
Maybe it would be valuable for OP to include the title and author?
– Mason
Jul 17 at 8:05
add a comment |Â
up vote
4
down vote
accepted
TL;DR The book you're using does things in an unnecessarily confusing way, and you should consider finding another book to self-learn from.
The first two axioms and first three parts of your theorem do make some sense together. The axioms apparently define how the $=$ symbol behaves in the theory, and parts (1), (2), (3) then tell you that those axioms force $=$ to be an equivalence relation. So far so good, and it is indeed an immediate consequence of the second of the axioms. (Mason's answer sketches the beginning of how that works).
However, choosing to have those two axioms in the first place is a rather iffy decision by the book. Generally there are two ways to approach equality in axiomatic set theory:
The most common these days is to consider $=$ and its properties to built into the logic you reason about sets with. This way, you would develop ways to work with $=$ before you even start speaking about the axioms of set theory specifically. Doing things this way, the (1), (2), (3) you quote, as well as the book's "Axiom of Equality" and the "$to$" direction of its "Axiom of Extensionality" would be axioms of logic, not about set theory in particular.
Alternatively, for those who want to build set theory with an absolutely minimal logical footprint, declare that your language does not contain an $=$ symbol at all, but when you write $x=y$ it is really an abbreviation for some more complex formula -- which could be either $forall u(uin x leftrightarrow uin y)$ or $forall z(xin zleftrightarrow yin z)$. Depending on the choice, either your book's "Axiom of Equality" or its "Axiom of Extensionality" would become vacuous, and the other would be a real axiom that tells you something about sets. Your (1), (2), (3) would then be something you need to prove by unfolding the abbreviation, but the remaining axiom would not be necessary for that.
What the book does seems to be a mixture of the two strategies which gives you the worst of both worlds and the benefit of neither. Apparently it does consider $=$ to be an actual symbol in its language (or it wouldn't need both axioms), but it doesn't assume that logic tells you how it works, so you still need to derive the properties of equality by hand.
The axioms of "Existence" and "Pairing" are phrased very mysteriously. It looks like the book considers $emptyset$ and $,$ to be something that is already part of the language -- but if so it ought to present axioms that tell you how they behave. That's not what the two axioms it does give you do. They just assert that the symbols can be used -- and that is certainly something that pure logic itself already ought to give you, at least once you have proved $forall x(x=x)$.
The only way I can imagine those two axioms to have any real meaning is if the book has secretly defined the combination "$x = emptyset$" to be an abbreviation of something like $forall z(znotin x)$. And the combination "$z=x,y$" would be an abbreviation of $forall u(uin z leftrightarrow u=x lor u=y)$.
But if so, the real meat is still in those abbreviations. And it's rather confusing that in some contexts you would need $=$ to be a symbol in its own right (otherwise the two first axioms would not both be meaningful), and in other contexts it's part of a notation that's an abbreviation.
In parts (4) and (5) of the theorem, things get even more confusing, because the notation $langle x,yrangle$ suddenly pops out of nowhere. Unless you have axioms for it, it too must be an abbreviation.
It's usual, following Kuratowski, to define $langle x,yrangle$ to mean $x,x,y$. But this definition will not work "out of the box" unless $,$ is a function symbol, which we have just argued it can't really be.
So perhaps the entire combo $z=langle x,yrangle$ is an abbreviation, for something like $exists sexists t(z=s,tland s=x,xland t=x,y)$. That would at least work. But then the notation $langle u,vrangle=langle x,yrangle$ is still not defined, and you need to appeal to some kind of "of course you can figure out what this actually means".
Commonly, presenting general rules for treating notations as function symbols when they're really defined as abbreviated relations would be part of the book's development of logic that comes before set theory. But I'm getting the impression that such a development has not actually taken place in your book. An author careful enough to do that would certainly have steered clear of the problems with the axioms already presented.
answered Jul 15 at 13:03
Henning Makholm
226k16291520
Maybe it would be valuable for OP to include the title and author?
– Mason
Jul 17 at 8:05
add a comment |Â
up vote
4
down vote
accepted
up vote
4
down vote
accepted
TL;DR The book you're using does things in an unnecessarily confusing way, and you should consider finding another book to self-learn from.
The first two axioms and first three parts of your theorem do make some sense together. The axioms apparently define how the $=$ symbol behaves in the theory, and parts (1), (2), (3) then tell you that those axioms force $=$ to be an equivalence relation. So far so good, and it is indeed an immediate consequence of the second of the axioms. (Mason's answer sketches the beginning of how that works).
However, choosing to have those two axioms in the first place is a rather iffy decision by the book. Generally there are two ways to approach equality in axiomatic set theory:
The most common these days is to consider $=$ and its properties to built into the logic you reason about sets with. This way, you would develop ways to work with $=$ before you even start speaking about the axioms of set theory specifically. Doing things this way, the (1), (2), (3) you quote, as well as the book's "Axiom of Equality" and the "$to$" direction of its "Axiom of Extensionality" would be axioms of logic, not about set theory in particular.
Alternatively, for those who want to build set theory with an absolutely minimal logical footprint, declare that your language does not contain an $=$ symbol at all, but when you write $x=y$ it is really an abbreviation for some more complex formula -- which could be either $forall u(uin x leftrightarrow uin y)$ or $forall z(xin zleftrightarrow yin z)$. Depending on the choice, either your book's "Axiom of Equality" or its "Axiom of Extensionality" would become vacuous, and the other would be a real axiom that tells you something about sets. Your (1), (2), (3) would then be something you need to prove by unfolding the abbreviation, but the remaining axiom would not be necessary for that.
What the book does seems to be a mixture of the two strategies which gives you the worst of both worlds and the benefit of neither. Apparently it does consider $=$ to be an actual symbol in its language (or it wouldn't need both axioms), but it doesn't assume that logic tells you how it works, so you still need to derive the properties of equality by hand.
The axioms of "Existence" and "Pairing" are phrased very mysteriously. It looks like the book considers $emptyset$ and $,$ to be something that is already part of the language -- but if so it ought to present axioms that tell you how they behave. That's not what the two axioms it does give you do. They just assert that the symbols can be used -- and that is certainly something that pure logic itself already ought to give you, at least once you have proved $forall x(x=x)$.
The only way I can imagine those two axioms to have any real meaning is if the book has secretly defined the combination "$x = emptyset$" to be an abbreviation of something like $forall z(znotin x)$. And the combination "$z=x,y$" would be an abbreviation of $forall u(uin z leftrightarrow u=x lor u=y)$.
But if so, the real meat is still in those abbreviations. And it's rather confusing that in some contexts you would need $=$ to be a symbol in its own right (otherwise the two first axioms would not both be meaningful), and in other contexts it's part of a notation that's an abbreviation.
In parts (4) and (5) of the theorem, things get even more confusing, because the notation $langle x,yrangle$ suddenly pops out of nowhere. Unless you have axioms for it, it too must be an abbreviation.
It's usual, following Kuratowski, to define $langle x,yrangle$ to mean $x,x,y$. But this definition will not work "out of the box" unless $,$ is a function symbol, which we have just argued it can't really be.
So perhaps the entire combo $z=langle x,yrangle$ is an abbreviation, for something like $exists sexists t(z=s,tland s=x,xland t=x,y)$. That would at least work. But then the notation $langle u,vrangle=langle x,yrangle$ is still not defined, and you need to appeal to some kind of "of course you can figure out what this actually means".
Commonly, presenting general rules for treating notations as function symbols when they're really defined as abbreviated relations would be part of the book's development of logic that comes before set theory. But I'm getting the impression that such a development has not actually taken place in your book. An author careful enough to do that would certainly have steered clear of the problems with the axioms already presented.
answered Jul 15 at 13:03
Henning Makholm
226k16291520
TL;DR The book you're using does things in an unnecessarily confusing way, and you should consider finding another book to self-learn from.
The first two axioms and first three parts of your theorem do make some sense together. The axioms apparently define how the $=$ symbol behaves in the theory, and parts (1), (2), (3) then tell you that those axioms force $=$ to be an equivalence relation. So far so good, and it is indeed an immediate consequence of the second of the axioms. (Mason's answer sketches the beginning of how that works).
However, choosing to have those two axioms in the first place is a rather iffy decision by the book. Generally there are two ways to approach equality in axiomatic set theory:
The most common these days is to consider $=$ and its properties to built into the logic you reason about sets with. This way, you would develop ways to work with $=$ before you even start speaking about the axioms of set theory specifically. Doing things this way, the (1), (2), (3) you quote, as well as the book's "Axiom of Equality" and the "$to$" direction of its "Axiom of Extensionality" would be axioms of logic, not about set theory in particular.
Alternatively, for those who want to build set theory with an absolutely minimal logical footprint, declare that your language does not contain an $=$ symbol at all, but when you write $x=y$ it is really an abbreviation for some more complex formula -- which could be either $forall u(uin x leftrightarrow uin y)$ or $forall z(xin zleftrightarrow yin z)$. Depending on the choice, either your book's "Axiom of Equality" or its "Axiom of Extensionality" would become vacuous, and the other would be a real axiom that tells you something about sets. Your (1), (2), (3) would then be something you need to prove by unfolding the abbreviation, but the remaining axiom would not be necessary for that.
What the book does seems to be a mixture of the two strategies which gives you the worst of both worlds and the benefit of neither. Apparently it does consider $=$ to be an actual symbol in its language (or it wouldn't need both axioms), but it doesn't assume that logic tells you how it works, so you still need to derive the properties of equality by hand.
The axioms of "Existence" and "Pairing" are phrased very mysteriously. It looks like the book considers $emptyset$ and $,$ to be something that is already part of the language -- but if so it ought to present axioms that tell you how they behave. That's not what the two axioms it does give you do. They just assert that the symbols can be used -- and that is certainly something that pure logic itself already ought to give you, at least once you have proved $forall x(x=x)$.
The only way I can imagine those two axioms to have any real meaning is if the book has secretly defined the combination "$x = emptyset$" to be an abbreviation of something like $forall z(znotin x)$. And the combination "$z=x,y$" would be an abbreviation of $forall u(uin z leftrightarrow u=x lor u=y)$.
But if so, the real meat is still in those abbreviations. And it's rather confusing that in some contexts you would need $=$ to be a symbol in its own right (otherwise the two first axioms would not both be meaningful), and in other contexts it's part of a notation that's an abbreviation.
In parts (4) and (5) of the theorem, things get even more confusing, because the notation $langle x,yrangle$ suddenly pops out of nowhere. Unless you have axioms for it, it too must be an abbreviation.
It's usual, following Kuratowski, to define $langle x,yrangle$ to mean $x,x,y$. But this definition will not work "out of the box" unless $,$ is a function symbol, which we have just argued it can't really be.
So perhaps the entire combo $z=langle x,yrangle$ is an abbreviation, for something like $exists sexists t(z=s,tland s=x,xland t=x,y)$. That would at least work. But then the notation $langle u,vrangle=langle x,yrangle$ is still not defined, and you need to appeal to some kind of "of course you can figure out what this actually means".
Commonly, presenting general rules for treating notations as function symbols when they're really defined as abbreviated relations would be part of the book's development of logic that comes before set theory. But I'm getting the impression that such a development has not actually taken place in your book. An author careful enough to do that would certainly have steered clear of the problems with the axioms already presented.
answered Jul 15 at 13:03
Henning Makholm
226k16291520
edited Jul 16 at 17:40
answered Jul 15 at 13:03
Henning Makholm
226k16291520
answered Jul 15 at 13:03
Henning Makholm
226k16291520
answered Jul 15 at 13:03
Henning Makholm
226k16291520
226k16291520
Maybe it would be valuable for OP to include the title and author?
– Mason
Jul 17 at 8:05
add a comment |Â
Maybe it would be valuable for OP to include the title and author?
– Mason
Jul 17 at 8:05
Maybe it would be valuable for OP to include the title and author?
– Mason
Jul 17 at 8:05
Maybe it would be valuable for OP to include the title and author?
– Mason
Jul 17 at 8:05
add a comment |Â
up vote
1
down vote
Just something that may help you get started. Not a complete answer.
Axiom of extensionality $forall x forall y [x = y ↔ forall u (u ∈ x ↔ u ∈ y)]$
What happens if we let $x=y$?
Well then $forall u (u ∈ x ↔ u ∈ y)]$ becomes $forall u (u ∈ x ↔ u ∈ x)]$ but this must evaluate to true. Because it is saying that a statement implies itself. Something like $S↔S$, But then this implies that $x=x$ as this is the left hand side of this axiom.
answered Jul 15 at 10:22
Mason
1,2401224
add a comment |Â
up vote
1
down vote
Just something that may help you get started. Not a complete answer.
Axiom of extensionality $forall x forall y [x = y ↔ forall u (u ∈ x ↔ u ∈ y)]$
What happens if we let $x=y$?
Well then $forall u (u ∈ x ↔ u ∈ y)]$ becomes $forall u (u ∈ x ↔ u ∈ x)]$ but this must evaluate to true. Because it is saying that a statement implies itself. Something like $S↔S$, But then this implies that $x=x$ as this is the left hand side of this axiom.
answered Jul 15 at 10:22
Mason
1,2401224
add a comment |Â
up vote
1
down vote
up vote
1
down vote
Just something that may help you get started. Not a complete answer.
Axiom of extensionality $forall x forall y [x = y ↔ forall u (u ∈ x ↔ u ∈ y)]$
What happens if we let $x=y$?
Well then $forall u (u ∈ x ↔ u ∈ y)]$ becomes $forall u (u ∈ x ↔ u ∈ x)]$ but this must evaluate to true. Because it is saying that a statement implies itself. Something like $S↔S$, But then this implies that $x=x$ as this is the left hand side of this axiom.
answered Jul 15 at 10:22
Mason
1,2401224
Just something that may help you get started. Not a complete answer.
Axiom of extensionality $forall x forall y [x = y ↔ forall u (u ∈ x ↔ u ∈ y)]$
What happens if we let $x=y$?
Well then $forall u (u ∈ x ↔ u ∈ y)]$ becomes $forall u (u ∈ x ↔ u ∈ x)]$ but this must evaluate to true. Because it is saying that a statement implies itself. Something like $S↔S$, But then this implies that $x=x$ as this is the left hand side of this axiom.
answered Jul 15 at 10:22
Mason
1,2401224
answered Jul 15 at 10:22
Mason
1,2401224
answered Jul 15 at 10:22
Mason
1,2401224
answered Jul 15 at 10:22
Mason
1,2401224
1,2401224
add a comment |Â
add a comment |Â
up vote
1
down vote
For $3$,
$x=y∧y=z implies $ (By extensionality )
$∀u(u∈x↔u∈y)∧∀u(u∈y↔u∈z) implies $ (By the transitivity of $↔$)
$∀u(u∈x↔u∈z) implies $ (By extensionality)
$x=z$
For 4,
$∀x∀y∃z(z=x,y)$ by the pairing axiom. Now by applying the pairing axiom again we find
$∃u(u=x,x,y)$. Note that the pairing axiom can be written $∀a∀b∃c(c=a,b)$. We get the desired result by taking $a=x$, $b=z= x,y$ and $c=u$.
$∀x∀y∃u(u=⟨x,y⟩)$
edited Jul 17 at 8:49
Mason
1,2401224
answered Jul 16 at 3:41
JavaLearner
13211
1
I am not sure how to prove the last one.
– JavaLearner
Jul 16 at 3:50
1
I think we will need your texts definition of $⟨x,y⟩$ to make progress.
– Mason
Jul 17 at 8:07
1
It is $x,x,y$
– JavaLearner
Jul 17 at 8:09
1
I think 3 looks fine + I am not sure if we are allowed to use transitivity in middle implication. I worry that we are begging the question but someone who knows more than me will let us know. I am sorry to put your words in your mouth if you wanted to justify the implication in some other way. How would you justify the steps for $4$? These (How?)s are for you to change as you see fit.
– Mason
Jul 17 at 8:24
1
@Mason, just making sure you recieve a notification.
– JavaLearner
Jul 17 at 8:32
 |Â
show 3 more comments
up vote
1
down vote
For $3$,
$x=y∧y=z implies $ (By extensionality )
$∀u(u∈x↔u∈y)∧∀u(u∈y↔u∈z) implies $ (By the transitivity of $↔$)
$∀u(u∈x↔u∈z) implies $ (By extensionality)
$x=z$
For 4,
$∀x∀y∃z(z=x,y)$ by the pairing axiom. Now by applying the pairing axiom again we find
$∃u(u=x,x,y)$. Note that the pairing axiom can be written $∀a∀b∃c(c=a,b)$. We get the desired result by taking $a=x$, $b=z= x,y$ and $c=u$.
$∀x∀y∃u(u=⟨x,y⟩)$
edited Jul 17 at 8:49
Mason
1,2401224
answered Jul 16 at 3:41
JavaLearner
13211
1
I am not sure how to prove the last one.
– JavaLearner
Jul 16 at 3:50
1
I think we will need your texts definition of $⟨x,y⟩$ to make progress.
– Mason
Jul 17 at 8:07
1
It is $x,x,y$
– JavaLearner
Jul 17 at 8:09
1
I think 3 looks fine + I am not sure if we are allowed to use transitivity in middle implication. I worry that we are begging the question but someone who knows more than me will let us know. I am sorry to put your words in your mouth if you wanted to justify the implication in some other way. How would you justify the steps for $4$? These (How?)s are for you to change as you see fit.
– Mason
Jul 17 at 8:24
1
@Mason, just making sure you recieve a notification.
– JavaLearner
Jul 17 at 8:32
 |Â
show 3 more comments
up vote
1
down vote
up vote
1
down vote
For $3$,
$x=y∧y=z implies $ (By extensionality )
$∀u(u∈x↔u∈y)∧∀u(u∈y↔u∈z) implies $ (By the transitivity of $↔$)
$∀u(u∈x↔u∈z) implies $ (By extensionality)
$x=z$
For 4,
$∀x∀y∃z(z=x,y)$ by the pairing axiom. Now by applying the pairing axiom again we find
$∃u(u=x,x,y)$. Note that the pairing axiom can be written $∀a∀b∃c(c=a,b)$. We get the desired result by taking $a=x$, $b=z= x,y$ and $c=u$.
$∀x∀y∃u(u=⟨x,y⟩)$
edited Jul 17 at 8:49
Mason
1,2401224
answered Jul 16 at 3:41
JavaLearner
13211
For $3$,
$x=y∧y=z implies $ (By extensionality )
$∀u(u∈x↔u∈y)∧∀u(u∈y↔u∈z) implies $ (By the transitivity of $↔$)
$∀u(u∈x↔u∈z) implies $ (By extensionality)
$x=z$
For 4,
$∀x∀y∃z(z=x,y)$ by the pairing axiom. Now by applying the pairing axiom again we find
$∃u(u=x,x,y)$. Note that the pairing axiom can be written $∀a∀b∃c(c=a,b)$. We get the desired result by taking $a=x$, $b=z= x,y$ and $c=u$.
$∀x∀y∃u(u=⟨x,y⟩)$
edited Jul 17 at 8:49
Mason
1,2401224
answered Jul 16 at 3:41
JavaLearner
13211
edited Jul 17 at 8:49
Mason
1,2401224
edited Jul 17 at 8:49
Mason
1,2401224
edited Jul 17 at 8:49
Mason
1,2401224
1,2401224
answered Jul 16 at 3:41
JavaLearner
13211
answered Jul 16 at 3:41
JavaLearner
13211
answered Jul 16 at 3:41
JavaLearner
13211
13211
1
I am not sure how to prove the last one.
– JavaLearner
Jul 16 at 3:50
1
I think we will need your texts definition of $⟨x,y⟩$ to make progress.
– Mason
Jul 17 at 8:07
1
It is $x,x,y$
– JavaLearner
Jul 17 at 8:09
1
I think 3 looks fine + I am not sure if we are allowed to use transitivity in middle implication. I worry that we are begging the question but someone who knows more than me will let us know. I am sorry to put your words in your mouth if you wanted to justify the implication in some other way. How would you justify the steps for $4$? These (How?)s are for you to change as you see fit.
– Mason
Jul 17 at 8:24
1
@Mason, just making sure you recieve a notification.
– JavaLearner
Jul 17 at 8:32
 |Â
show 3 more comments
1
I am not sure how to prove the last one.
– JavaLearner
Jul 16 at 3:50
1
I think we will need your texts definition of $⟨x,y⟩$ to make progress.
– Mason
Jul 17 at 8:07
1
It is $x,x,y$
– JavaLearner
Jul 17 at 8:09
1
I think 3 looks fine + I am not sure if we are allowed to use transitivity in middle implication. I worry that we are begging the question but someone who knows more than me will let us know. I am sorry to put your words in your mouth if you wanted to justify the implication in some other way. How would you justify the steps for $4$? These (How?)s are for you to change as you see fit.
– Mason
Jul 17 at 8:24
1
@Mason, just making sure you recieve a notification.
– JavaLearner
Jul 17 at 8:32
1
1
I am not sure how to prove the last one.
– JavaLearner
Jul 16 at 3:50
I am not sure how to prove the last one.
– JavaLearner
Jul 16 at 3:50
1
1
I think we will need your texts definition of $⟨x,y⟩$ to make progress.
– Mason
Jul 17 at 8:07
I think we will need your texts definition of $⟨x,y⟩$ to make progress.
– Mason
Jul 17 at 8:07
1
1
It is $x,x,y$
– JavaLearner
Jul 17 at 8:09
It is $x,x,y$
– JavaLearner
Jul 17 at 8:09
1
1
I think 3 looks fine + I am not sure if we are allowed to use transitivity in middle implication. I worry that we are begging the question but someone who knows more than me will let us know. I am sorry to put your words in your mouth if you wanted to justify the implication in some other way. How would you justify the steps for $4$? These (How?)s are for you to change as you see fit.
– Mason
Jul 17 at 8:24
I think 3 looks fine + I am not sure if we are allowed to use transitivity in middle implication. I worry that we are begging the question but someone who knows more than me will let us know. I am sorry to put your words in your mouth if you wanted to justify the implication in some other way. How would you justify the steps for $4$? These (How?)s are for you to change as you see fit.
– Mason
Jul 17 at 8:24
1
1
@Mason, just making sure you recieve a notification.
– JavaLearner
Jul 17 at 8:32
@Mason, just making sure you recieve a notification.
– JavaLearner
Jul 17 at 8:32
 |Â
show 3 more comments
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%2f2852343%2fhow-to-apply-the-axioms-in-set-theory%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) is straightforward using the answer below: from $x=y$ we have $∀u(u∈x↔u∈y)$; but by logic we have $∀u(u∈y↔u∈x)$ and thus...
– Mauro ALLEGRANZA
Jul 15 at 10:47
The same for 3): use transitivity of $↔$.
– Mauro ALLEGRANZA
Jul 15 at 10:47
For 4) you need the definition of ordered pair (usually based on the pair $ x,y $.
– Mauro ALLEGRANZA
Jul 15 at 10:48
@MauroALLEGRANZA so for the transitivity,$x=y∧y=z implies∀u(u∈x↔u∈y) ∧ ∀u(u∈y↔u∈z) implies ∀u(u∈x↔u∈z) implies x =z$
– JavaLearner
Jul 15 at 22:38
As for the pairing, $forall xforall yexists z (z=x,y) implies forall x forall y exists u(u=x,x,y) implies forall x forall y exists u(u=⟨x,y⟩)$
– JavaLearner
Jul 15 at 22:47