What is my mistake in proving that $Asubseteq B$ implies $Bsubseteq A$?
up vote
0
down vote
favorite
It's legitimate to use a tautology in any proof at any time right? Also whenever P and P $implies$ Q appears I Can announce Q, the reason being modes pones rule. So where is the mistake here?
Proof that $A subseteq B implies B subseteq A$:
- Assume $A subseteq B$
- Suppose $x in A$
$A subseteq B implies (x in A implies x in B)$ (Definition of subset)
$x in A implies x in B$ (Modus pones step 1 and 3)
$x in B$ (Modus pones step 2 and 4)
$x in A implies (x in B implies x in A )$ (tautology $q implies (p implies q)$)
$x in B implies x in A$ (Modus pones step 2 and 6)
$x in B implies x in A implies B subseteq A$ (Definition of subset)
$B subseteq A$ (Modus pones step 7 and 8)
$B subseteq A implies (A subseteq B implies B subseteq A)$ (tautology)
$A subseteq B implies B subseteq A$ (Modus pones step 9 and 10).
elementary-set-theory logic
edited Nov 19 at 8:52
Asaf Karagila♦
300k32422752
asked Nov 19 at 7:17
tnstse
111
add a comment |
up vote
0
down vote
favorite
It's legitimate to use a tautology in any proof at any time right? Also whenever P and P $implies$ Q appears I Can announce Q, the reason being modes pones rule. So where is the mistake here?
Proof that $A subseteq B implies B subseteq A$:
- Assume $A subseteq B$
- Suppose $x in A$
$A subseteq B implies (x in A implies x in B)$ (Definition of subset)
$x in A implies x in B$ (Modus pones step 1 and 3)
$x in B$ (Modus pones step 2 and 4)
$x in A implies (x in B implies x in A )$ (tautology $q implies (p implies q)$)
$x in B implies x in A$ (Modus pones step 2 and 6)
$x in B implies x in A implies B subseteq A$ (Definition of subset)
$B subseteq A$ (Modus pones step 7 and 8)
$B subseteq A implies (A subseteq B implies B subseteq A)$ (tautology)
$A subseteq B implies B subseteq A$ (Modus pones step 9 and 10).
elementary-set-theory logic
edited Nov 19 at 8:52
Asaf Karagila♦
300k32422752
asked Nov 19 at 7:17
tnstse
111
1
The definition of subset : $A subseteq B$ is : $forall x (x in A to x in B)$. It is a predicate logic formula and not a priopositional one.
– Mauro ALLEGRANZA
Nov 19 at 7:21
1
$Bsubseteq A$ means $forall x(xin Bimplies xin A)$, but you have only obtained $forall x(xin Aimplies(xin Bimplies xin A))$.
– Lord Shark the Unknown
Nov 19 at 7:28
The set A = {1, 2} is a subset of B = {1, 2, 3}, the expressions A ⊆ B is true but is B ⊆ A? This is probably true only if A=B.
– NoChance
Nov 19 at 7:45
@NoChance thanks for the counter example, but i did point out that the proof is invalid. I wanted to know which step is wrong. frustratingly, none of the comments helped me.
– tnstse
Nov 19 at 7:46
As @LordSharktheUnknown points out, the problem is that in step 8, your definition of subset uses the label $x$ to denote any element. In the previous lines you use the label $x$ to denote any element of $A$. You then conflate the two, essentially applying the subset definition only to those elements that are already in $A$ instead of to all possible elements, and thereby ignoring all elements in $B$ $A$.
– Jaap Scherphuis
Nov 19 at 7:54
add a comment |
up vote
0
down vote
favorite
up vote
0
down vote
favorite
It's legitimate to use a tautology in any proof at any time right? Also whenever P and P $implies$ Q appears I Can announce Q, the reason being modes pones rule. So where is the mistake here?
Proof that $A subseteq B implies B subseteq A$:
- Assume $A subseteq B$
- Suppose $x in A$
$A subseteq B implies (x in A implies x in B)$ (Definition of subset)
$x in A implies x in B$ (Modus pones step 1 and 3)
$x in B$ (Modus pones step 2 and 4)
$x in A implies (x in B implies x in A )$ (tautology $q implies (p implies q)$)
$x in B implies x in A$ (Modus pones step 2 and 6)
$x in B implies x in A implies B subseteq A$ (Definition of subset)
$B subseteq A$ (Modus pones step 7 and 8)
$B subseteq A implies (A subseteq B implies B subseteq A)$ (tautology)
$A subseteq B implies B subseteq A$ (Modus pones step 9 and 10).
elementary-set-theory logic
edited Nov 19 at 8:52
Asaf Karagila♦
300k32422752
asked Nov 19 at 7:17
tnstse
111
It's legitimate to use a tautology in any proof at any time right? Also whenever P and P $implies$ Q appears I Can announce Q, the reason being modes pones rule. So where is the mistake here?
Proof that $A subseteq B implies B subseteq A$:
- Assume $A subseteq B$
- Suppose $x in A$
$A subseteq B implies (x in A implies x in B)$ (Definition of subset)
$x in A implies x in B$ (Modus pones step 1 and 3)
$x in B$ (Modus pones step 2 and 4)
$x in A implies (x in B implies x in A )$ (tautology $q implies (p implies q)$)
$x in B implies x in A$ (Modus pones step 2 and 6)
$x in B implies x in A implies B subseteq A$ (Definition of subset)
$B subseteq A$ (Modus pones step 7 and 8)
$B subseteq A implies (A subseteq B implies B subseteq A)$ (tautology)
$A subseteq B implies B subseteq A$ (Modus pones step 9 and 10).
elementary-set-theory logic
elementary-set-theory logic
edited Nov 19 at 8:52
Asaf Karagila♦
300k32422752
asked Nov 19 at 7:17
tnstse
111
edited Nov 19 at 8:52
Asaf Karagila♦
300k32422752
asked Nov 19 at 7:17
tnstse
111
edited Nov 19 at 8:52
Asaf Karagila♦
300k32422752
edited Nov 19 at 8:52
Asaf Karagila♦
300k32422752
edited Nov 19 at 8:52
Asaf Karagila♦
300k32422752
300k32422752
asked Nov 19 at 7:17
tnstse
111
asked Nov 19 at 7:17
tnstse
111
asked Nov 19 at 7:17
tnstse
111
111
1
The definition of subset : $A subseteq B$ is : $forall x (x in A to x in B)$. It is a predicate logic formula and not a priopositional one.
– Mauro ALLEGRANZA
Nov 19 at 7:21
1
$Bsubseteq A$ means $forall x(xin Bimplies xin A)$, but you have only obtained $forall x(xin Aimplies(xin Bimplies xin A))$.
– Lord Shark the Unknown
Nov 19 at 7:28
The set A = {1, 2} is a subset of B = {1, 2, 3}, the expressions A ⊆ B is true but is B ⊆ A? This is probably true only if A=B.
– NoChance
Nov 19 at 7:45
@NoChance thanks for the counter example, but i did point out that the proof is invalid. I wanted to know which step is wrong. frustratingly, none of the comments helped me.
– tnstse
Nov 19 at 7:46
As @LordSharktheUnknown points out, the problem is that in step 8, your definition of subset uses the label $x$ to denote any element. In the previous lines you use the label $x$ to denote any element of $A$. You then conflate the two, essentially applying the subset definition only to those elements that are already in $A$ instead of to all possible elements, and thereby ignoring all elements in $B$ $A$.
– Jaap Scherphuis
Nov 19 at 7:54
add a comment |
1
The definition of subset : $A subseteq B$ is : $forall x (x in A to x in B)$. It is a predicate logic formula and not a priopositional one.
– Mauro ALLEGRANZA
Nov 19 at 7:21
1
$Bsubseteq A$ means $forall x(xin Bimplies xin A)$, but you have only obtained $forall x(xin Aimplies(xin Bimplies xin A))$.
– Lord Shark the Unknown
Nov 19 at 7:28
The set A = {1, 2} is a subset of B = {1, 2, 3}, the expressions A ⊆ B is true but is B ⊆ A? This is probably true only if A=B.
– NoChance
Nov 19 at 7:45
@NoChance thanks for the counter example, but i did point out that the proof is invalid. I wanted to know which step is wrong. frustratingly, none of the comments helped me.
– tnstse
Nov 19 at 7:46
As @LordSharktheUnknown points out, the problem is that in step 8, your definition of subset uses the label $x$ to denote any element. In the previous lines you use the label $x$ to denote any element of $A$. You then conflate the two, essentially applying the subset definition only to those elements that are already in $A$ instead of to all possible elements, and thereby ignoring all elements in $B$ $A$.
– Jaap Scherphuis
Nov 19 at 7:54
1
1
The definition of subset : $A subseteq B$ is : $forall x (x in A to x in B)$. It is a predicate logic formula and not a priopositional one.
– Mauro ALLEGRANZA
Nov 19 at 7:21
The definition of subset : $A subseteq B$ is : $forall x (x in A to x in B)$. It is a predicate logic formula and not a priopositional one.
– Mauro ALLEGRANZA
Nov 19 at 7:21
1
1
$Bsubseteq A$ means $forall x(xin Bimplies xin A)$, but you have only obtained $forall x(xin Aimplies(xin Bimplies xin A))$.
– Lord Shark the Unknown
Nov 19 at 7:28
$Bsubseteq A$ means $forall x(xin Bimplies xin A)$, but you have only obtained $forall x(xin Aimplies(xin Bimplies xin A))$.
– Lord Shark the Unknown
Nov 19 at 7:28
The set A = {1, 2} is a subset of B = {1, 2, 3}, the expressions A ⊆ B is true but is B ⊆ A? This is probably true only if A=B.
– NoChance
Nov 19 at 7:45
The set A = {1, 2} is a subset of B = {1, 2, 3}, the expressions A ⊆ B is true but is B ⊆ A? This is probably true only if A=B.
– NoChance
Nov 19 at 7:45
@NoChance thanks for the counter example, but i did point out that the proof is invalid. I wanted to know which step is wrong. frustratingly, none of the comments helped me.
– tnstse
Nov 19 at 7:46
@NoChance thanks for the counter example, but i did point out that the proof is invalid. I wanted to know which step is wrong. frustratingly, none of the comments helped me.
– tnstse
Nov 19 at 7:46
As @LordSharktheUnknown points out, the problem is that in step 8, your definition of subset uses the label $x$ to denote any element. In the previous lines you use the label $x$ to denote any element of $A$. You then conflate the two, essentially applying the subset definition only to those elements that are already in $A$ instead of to all possible elements, and thereby ignoring all elements in $B$ $A$.
– Jaap Scherphuis
Nov 19 at 7:54
As @LordSharktheUnknown points out, the problem is that in step 8, your definition of subset uses the label $x$ to denote any element. In the previous lines you use the label $x$ to denote any element of $A$. You then conflate the two, essentially applying the subset definition only to those elements that are already in $A$ instead of to all possible elements, and thereby ignoring all elements in $B$ $A$.
– Jaap Scherphuis
Nov 19 at 7:54
add a comment |
2 Answers
2
active
oldest
votes
up vote
5
down vote
Long comment
The wrong proof is :
1) Assume : $A ⊆ B$
2) Suppose : $x ∈ A$
3) $forall x (x∈A⟹x∈B)$ --- definition of subset [not used]
4) $x ∈ A ⟹ x∈B$ --- by Universal instantiation [not used]
5) $x∈B$ --- from 2) and 4) by Modus pones [not used]
6) $x∈A ⟹ (x∈B ⟹ x∈A)$ --- from tautology : $q⟹(p⟹q)$
7) $x∈B ⟹ x∈A$ --- by Modus pones from 2) and 6)
But we cannot apply the definition of subset to 7) in order to conclude with $B⊆A$ because we have not yet proved : $forall x (x∈B ⟹ x∈A)$.
The "obvious" step is to apply Universal generalization to 7), but this move is invalid, because $x$ is free in assumption 2).
Intuitively, we have chosen an $x$ such that $x$ belongs to $A$ and we have derived, with this assumption, that $x∈B ⟹ x∈A$; but this does not mean that the formula that we have derived holds for $x$ whatever.
answered Nov 19 at 8:12
Mauro ALLEGRANZA
63.8k448110
add a comment |
up vote
1
down vote
Your definition of subset is incorrect, as it should be a universal quantified statement.
Certainly should we suppose that for any $x$ which satisfies $xin A$, we may derive $xin Bto xin A$. However, this is not the same as deriving $forall x~(xin Bto xin A)$ , which is the actual definition for $Bsubseteq A$. All you can prove from this line of reasoning is that $Acap Bsubseteq A$.
$$forall x~(xin Ato(xin Bto xin A))\forall x~((xin Awedge xin B)to xin A)\forall x~(xin Acap Bto xin A)\Acap Bsubseteq A$$
answered Nov 19 at 13:35
Graham Kemp
84.6k43378
add a comment |
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
5
down vote
Long comment
The wrong proof is :
1) Assume : $A ⊆ B$
2) Suppose : $x ∈ A$
3) $forall x (x∈A⟹x∈B)$ --- definition of subset [not used]
4) $x ∈ A ⟹ x∈B$ --- by Universal instantiation [not used]
5) $x∈B$ --- from 2) and 4) by Modus pones [not used]
6) $x∈A ⟹ (x∈B ⟹ x∈A)$ --- from tautology : $q⟹(p⟹q)$
7) $x∈B ⟹ x∈A$ --- by Modus pones from 2) and 6)
But we cannot apply the definition of subset to 7) in order to conclude with $B⊆A$ because we have not yet proved : $forall x (x∈B ⟹ x∈A)$.
The "obvious" step is to apply Universal generalization to 7), but this move is invalid, because $x$ is free in assumption 2).
Intuitively, we have chosen an $x$ such that $x$ belongs to $A$ and we have derived, with this assumption, that $x∈B ⟹ x∈A$; but this does not mean that the formula that we have derived holds for $x$ whatever.
answered Nov 19 at 8:12
Mauro ALLEGRANZA
63.8k448110
add a comment |
up vote
5
down vote
Long comment
The wrong proof is :
1) Assume : $A ⊆ B$
2) Suppose : $x ∈ A$
3) $forall x (x∈A⟹x∈B)$ --- definition of subset [not used]
4) $x ∈ A ⟹ x∈B$ --- by Universal instantiation [not used]
5) $x∈B$ --- from 2) and 4) by Modus pones [not used]
6) $x∈A ⟹ (x∈B ⟹ x∈A)$ --- from tautology : $q⟹(p⟹q)$
7) $x∈B ⟹ x∈A$ --- by Modus pones from 2) and 6)
But we cannot apply the definition of subset to 7) in order to conclude with $B⊆A$ because we have not yet proved : $forall x (x∈B ⟹ x∈A)$.
The "obvious" step is to apply Universal generalization to 7), but this move is invalid, because $x$ is free in assumption 2).
Intuitively, we have chosen an $x$ such that $x$ belongs to $A$ and we have derived, with this assumption, that $x∈B ⟹ x∈A$; but this does not mean that the formula that we have derived holds for $x$ whatever.
answered Nov 19 at 8:12
Mauro ALLEGRANZA
63.8k448110
add a comment |
up vote
5
down vote
up vote
5
down vote
Long comment
The wrong proof is :
1) Assume : $A ⊆ B$
2) Suppose : $x ∈ A$
3) $forall x (x∈A⟹x∈B)$ --- definition of subset [not used]
4) $x ∈ A ⟹ x∈B$ --- by Universal instantiation [not used]
5) $x∈B$ --- from 2) and 4) by Modus pones [not used]
6) $x∈A ⟹ (x∈B ⟹ x∈A)$ --- from tautology : $q⟹(p⟹q)$
7) $x∈B ⟹ x∈A$ --- by Modus pones from 2) and 6)
But we cannot apply the definition of subset to 7) in order to conclude with $B⊆A$ because we have not yet proved : $forall x (x∈B ⟹ x∈A)$.
The "obvious" step is to apply Universal generalization to 7), but this move is invalid, because $x$ is free in assumption 2).
Intuitively, we have chosen an $x$ such that $x$ belongs to $A$ and we have derived, with this assumption, that $x∈B ⟹ x∈A$; but this does not mean that the formula that we have derived holds for $x$ whatever.
answered Nov 19 at 8:12
Mauro ALLEGRANZA
63.8k448110
Long comment
The wrong proof is :
1) Assume : $A ⊆ B$
2) Suppose : $x ∈ A$
3) $forall x (x∈A⟹x∈B)$ --- definition of subset [not used]
4) $x ∈ A ⟹ x∈B$ --- by Universal instantiation [not used]
5) $x∈B$ --- from 2) and 4) by Modus pones [not used]
6) $x∈A ⟹ (x∈B ⟹ x∈A)$ --- from tautology : $q⟹(p⟹q)$
7) $x∈B ⟹ x∈A$ --- by Modus pones from 2) and 6)
But we cannot apply the definition of subset to 7) in order to conclude with $B⊆A$ because we have not yet proved : $forall x (x∈B ⟹ x∈A)$.
The "obvious" step is to apply Universal generalization to 7), but this move is invalid, because $x$ is free in assumption 2).
Intuitively, we have chosen an $x$ such that $x$ belongs to $A$ and we have derived, with this assumption, that $x∈B ⟹ x∈A$; but this does not mean that the formula that we have derived holds for $x$ whatever.
answered Nov 19 at 8:12
Mauro ALLEGRANZA
63.8k448110
edited Nov 19 at 10:47
answered Nov 19 at 8:12
Mauro ALLEGRANZA
63.8k448110
answered Nov 19 at 8:12
Mauro ALLEGRANZA
63.8k448110
answered Nov 19 at 8:12
Mauro ALLEGRANZA
63.8k448110
63.8k448110
add a comment |
add a comment |
up vote
1
down vote
Your definition of subset is incorrect, as it should be a universal quantified statement.
Certainly should we suppose that for any $x$ which satisfies $xin A$, we may derive $xin Bto xin A$. However, this is not the same as deriving $forall x~(xin Bto xin A)$ , which is the actual definition for $Bsubseteq A$. All you can prove from this line of reasoning is that $Acap Bsubseteq A$.
$$forall x~(xin Ato(xin Bto xin A))\forall x~((xin Awedge xin B)to xin A)\forall x~(xin Acap Bto xin A)\Acap Bsubseteq A$$
answered Nov 19 at 13:35
Graham Kemp
84.6k43378
add a comment |
up vote
1
down vote
Your definition of subset is incorrect, as it should be a universal quantified statement.
Certainly should we suppose that for any $x$ which satisfies $xin A$, we may derive $xin Bto xin A$. However, this is not the same as deriving $forall x~(xin Bto xin A)$ , which is the actual definition for $Bsubseteq A$. All you can prove from this line of reasoning is that $Acap Bsubseteq A$.
$$forall x~(xin Ato(xin Bto xin A))\forall x~((xin Awedge xin B)to xin A)\forall x~(xin Acap Bto xin A)\Acap Bsubseteq A$$
answered Nov 19 at 13:35
Graham Kemp
84.6k43378
add a comment |
up vote
1
down vote
up vote
1
down vote
Your definition of subset is incorrect, as it should be a universal quantified statement.
Certainly should we suppose that for any $x$ which satisfies $xin A$, we may derive $xin Bto xin A$. However, this is not the same as deriving $forall x~(xin Bto xin A)$ , which is the actual definition for $Bsubseteq A$. All you can prove from this line of reasoning is that $Acap Bsubseteq A$.
$$forall x~(xin Ato(xin Bto xin A))\forall x~((xin Awedge xin B)to xin A)\forall x~(xin Acap Bto xin A)\Acap Bsubseteq A$$
answered Nov 19 at 13:35
Graham Kemp
84.6k43378
Your definition of subset is incorrect, as it should be a universal quantified statement.
Certainly should we suppose that for any $x$ which satisfies $xin A$, we may derive $xin Bto xin A$. However, this is not the same as deriving $forall x~(xin Bto xin A)$ , which is the actual definition for $Bsubseteq A$. All you can prove from this line of reasoning is that $Acap Bsubseteq A$.
$$forall x~(xin Ato(xin Bto xin A))\forall x~((xin Awedge xin B)to xin A)\forall x~(xin Acap Bto xin A)\Acap Bsubseteq A$$
answered Nov 19 at 13:35
Graham Kemp
84.6k43378
answered Nov 19 at 13:35
Graham Kemp
84.6k43378
answered Nov 19 at 13:35
Graham Kemp
84.6k43378
answered Nov 19 at 13:35
Graham Kemp
84.6k43378
84.6k43378
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3004613%2fwhat-is-my-mistake-in-proving-that-a-subseteq-b-implies-b-subseteq-a%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
The definition of subset : $A subseteq B$ is : $forall x (x in A to x in B)$. It is a predicate logic formula and not a priopositional one.
– Mauro ALLEGRANZA
Nov 19 at 7:21
1
$Bsubseteq A$ means $forall x(xin Bimplies xin A)$, but you have only obtained $forall x(xin Aimplies(xin Bimplies xin A))$.
– Lord Shark the Unknown
Nov 19 at 7:28
The set A = {1, 2} is a subset of B = {1, 2, 3}, the expressions A ⊆ B is true but is B ⊆ A? This is probably true only if A=B.
– NoChance
Nov 19 at 7:45
@NoChance thanks for the counter example, but i did point out that the proof is invalid. I wanted to know which step is wrong. frustratingly, none of the comments helped me.
– tnstse
Nov 19 at 7:46
As @LordSharktheUnknown points out, the problem is that in step 8, your definition of subset uses the label $x$ to denote any element. In the previous lines you use the label $x$ to denote any element of $A$. You then conflate the two, essentially applying the subset definition only to those elements that are already in $A$ instead of to all possible elements, and thereby ignoring all elements in $B$ $A$.
– Jaap Scherphuis
Nov 19 at 7:54