A De Morgan law application in set theory
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
The application of De Morgan law in the field of set theory generate this equality, but i'm not able to understand it. Can you help me ? Thanks for your time
$bigcup A_n=bigcup (A_1^ccap ...cap A_n-1^c cap A_n)$
elementary-set-theory
add a comment |Â
up vote
0
down vote
favorite
The application of De Morgan law in the field of set theory generate this equality, but i'm not able to understand it. Can you help me ? Thanks for your time
$bigcup A_n=bigcup (A_1^ccap ...cap A_n-1^c cap A_n)$
elementary-set-theory
1
DeMorgan's Laws. After Augustus DeMorgan
â DanielWainfleet
Sep 2 at 9:18
add a comment |Â
up vote
0
down vote
favorite
up vote
0
down vote
favorite
The application of De Morgan law in the field of set theory generate this equality, but i'm not able to understand it. Can you help me ? Thanks for your time
$bigcup A_n=bigcup (A_1^ccap ...cap A_n-1^c cap A_n)$
elementary-set-theory
The application of De Morgan law in the field of set theory generate this equality, but i'm not able to understand it. Can you help me ? Thanks for your time
$bigcup A_n=bigcup (A_1^ccap ...cap A_n-1^c cap A_n)$
elementary-set-theory
elementary-set-theory
edited Sep 2 at 12:33
Andrés E. Caicedo
63.4k7154238
63.4k7154238
asked Sep 2 at 8:12
Koinos
757
757
1
DeMorgan's Laws. After Augustus DeMorgan
â DanielWainfleet
Sep 2 at 9:18
add a comment |Â
1
DeMorgan's Laws. After Augustus DeMorgan
â DanielWainfleet
Sep 2 at 9:18
1
1
DeMorgan's Laws. After Augustus DeMorgan
â DanielWainfleet
Sep 2 at 9:18
DeMorgan's Laws. After Augustus DeMorgan
â DanielWainfleet
Sep 2 at 9:18
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
1
down vote
I think you may actually be thinking of $cup A_n=(A_1^c cap ... cap A_n^c)^c$.
An element is in the left hand side if and only if it is in one of the $A_i$. Now let us look at $A_1^c cap ... cap A_n^c$. An element is in this if and only if it is not in $A_1$ and not in $A_2$ and not in any of the $A_i$. So the element is in $(A_1^c cap ... cap A_n^c)^c$ if and only if it is in one of the $A_i$ and that is exactly the same as the condition of being in the left hand side. This shows that the two sets have the same elements and so they are equal.
Looking at your comment, you are right, this does work. Let us imagine that all of the $A_i$ are empty except the first three. Then your expression gives $A_1 cup A_2 cup A_3 = A_1 cup (A_1^c cap A_2) cup (A_1^c cap A_2^c cap A_3)$. What this does is write the union on the LHS as a disjoint union. An element in the LHS is in $A_1$, $A_2$ or $A_3$. If it was in $A_1$ then it will be captured in the first term of the union on the RHS. If it is in $A_2$ but not $A_1$, it will be captured in the second term of the RHS. If it had been in $A_1$ then it would have been captured in the first term (of the RHS). If it is in $A_3$ but was not in $A_1$ or $A_2$ then it will be captured in the third term of the union on the RHS. So we have shown that the LHS is a subset of the RHS (every element of the LHS is in the RHS). It is easy to see that the RHS is a subset of the LHS (everything in the LHS must be in the RHS because each term in the LHS union is a superset of the corresponding term in the union on the RHS). So the two sets are equal. This method clearly generalises to situations when more (or all) of the $A_i$ are non-empty.
This explains why the identity works. There will be a mechanical proof from the De Morgan laws. I'll keep thinking about that but it may just mirror this reasoning.
No, i found precisely this
â Koinos
Sep 2 at 9:12
1
You're right; this does work, I've amended my answer to reflect that.
â Simon Terrington
Sep 2 at 10:37
Hi @SimonTerrington, maybe have misread the notation but what happens in the (albeit rather trivial) case where for example $forall n,A_n=A_1â â $ then $LHS=A_1$ but $RHS=â $ ? just wondering if any conditions on the sets or it's claimed in full generality. On the face of it strikes me cannot be true if all are equal but might be barking up wrong tree!
â Mehness
Sep 2 at 10:51
1
OK so this is a good point, but if you look at this last term within the intersection on the RHS, it is not complemented so for the term in which $n=1$ (on the RHS counter) then we would have $A_1$. So the LHS and RHS would both be equal to $A_1$ in this case.
â Simon Terrington
Sep 2 at 10:56
yep fair enough! :)
â Mehness
Sep 2 at 11:00
 |Â
show 1 more comment
up vote
0
down vote
So we want to see $$bigcup_n in mathbbN A_n = bigcup_n in mathbbN left(A_1^c cap A_2^c ldots A_n-1^c cap A_nright)$$
where $mathbbN$ starts at $n=1$. The first term on the right is just $A_1$, the second $A_1^c cup A_2$ etc.
If $x$ is in the right hand side it is in some set of the form $A_1^c cap A_2^c ldots A_n-1^c cap A_n subseteq A_n$ so then it's certainly in the left hand side.
If $x$ is in the left hand side, then $x in A_n$ for some $n in mathbbN$, and let $n_0 =min n: x in A_n$ which is well-defined as $mathbbN$ has a well-ordering.
Then for all $i=1, ldots, n_0 - 1$ we know that $x notin A_i$ (or we would contradict the minimality of $n_0$; the statement is voidly true if $n_0$ happens to be $1$) Hence
$ x in A_1^c cap A_2^c ldots A_n_0 - 1^c cap A_n_0$ and so $x$ is in the right hand side.
This is not an application of DeMorgan, the well-orderedness of the index set is crucial.
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
I think you may actually be thinking of $cup A_n=(A_1^c cap ... cap A_n^c)^c$.
An element is in the left hand side if and only if it is in one of the $A_i$. Now let us look at $A_1^c cap ... cap A_n^c$. An element is in this if and only if it is not in $A_1$ and not in $A_2$ and not in any of the $A_i$. So the element is in $(A_1^c cap ... cap A_n^c)^c$ if and only if it is in one of the $A_i$ and that is exactly the same as the condition of being in the left hand side. This shows that the two sets have the same elements and so they are equal.
Looking at your comment, you are right, this does work. Let us imagine that all of the $A_i$ are empty except the first three. Then your expression gives $A_1 cup A_2 cup A_3 = A_1 cup (A_1^c cap A_2) cup (A_1^c cap A_2^c cap A_3)$. What this does is write the union on the LHS as a disjoint union. An element in the LHS is in $A_1$, $A_2$ or $A_3$. If it was in $A_1$ then it will be captured in the first term of the union on the RHS. If it is in $A_2$ but not $A_1$, it will be captured in the second term of the RHS. If it had been in $A_1$ then it would have been captured in the first term (of the RHS). If it is in $A_3$ but was not in $A_1$ or $A_2$ then it will be captured in the third term of the union on the RHS. So we have shown that the LHS is a subset of the RHS (every element of the LHS is in the RHS). It is easy to see that the RHS is a subset of the LHS (everything in the LHS must be in the RHS because each term in the LHS union is a superset of the corresponding term in the union on the RHS). So the two sets are equal. This method clearly generalises to situations when more (or all) of the $A_i$ are non-empty.
This explains why the identity works. There will be a mechanical proof from the De Morgan laws. I'll keep thinking about that but it may just mirror this reasoning.
No, i found precisely this
â Koinos
Sep 2 at 9:12
1
You're right; this does work, I've amended my answer to reflect that.
â Simon Terrington
Sep 2 at 10:37
Hi @SimonTerrington, maybe have misread the notation but what happens in the (albeit rather trivial) case where for example $forall n,A_n=A_1â â $ then $LHS=A_1$ but $RHS=â $ ? just wondering if any conditions on the sets or it's claimed in full generality. On the face of it strikes me cannot be true if all are equal but might be barking up wrong tree!
â Mehness
Sep 2 at 10:51
1
OK so this is a good point, but if you look at this last term within the intersection on the RHS, it is not complemented so for the term in which $n=1$ (on the RHS counter) then we would have $A_1$. So the LHS and RHS would both be equal to $A_1$ in this case.
â Simon Terrington
Sep 2 at 10:56
yep fair enough! :)
â Mehness
Sep 2 at 11:00
 |Â
show 1 more comment
up vote
1
down vote
I think you may actually be thinking of $cup A_n=(A_1^c cap ... cap A_n^c)^c$.
An element is in the left hand side if and only if it is in one of the $A_i$. Now let us look at $A_1^c cap ... cap A_n^c$. An element is in this if and only if it is not in $A_1$ and not in $A_2$ and not in any of the $A_i$. So the element is in $(A_1^c cap ... cap A_n^c)^c$ if and only if it is in one of the $A_i$ and that is exactly the same as the condition of being in the left hand side. This shows that the two sets have the same elements and so they are equal.
Looking at your comment, you are right, this does work. Let us imagine that all of the $A_i$ are empty except the first three. Then your expression gives $A_1 cup A_2 cup A_3 = A_1 cup (A_1^c cap A_2) cup (A_1^c cap A_2^c cap A_3)$. What this does is write the union on the LHS as a disjoint union. An element in the LHS is in $A_1$, $A_2$ or $A_3$. If it was in $A_1$ then it will be captured in the first term of the union on the RHS. If it is in $A_2$ but not $A_1$, it will be captured in the second term of the RHS. If it had been in $A_1$ then it would have been captured in the first term (of the RHS). If it is in $A_3$ but was not in $A_1$ or $A_2$ then it will be captured in the third term of the union on the RHS. So we have shown that the LHS is a subset of the RHS (every element of the LHS is in the RHS). It is easy to see that the RHS is a subset of the LHS (everything in the LHS must be in the RHS because each term in the LHS union is a superset of the corresponding term in the union on the RHS). So the two sets are equal. This method clearly generalises to situations when more (or all) of the $A_i$ are non-empty.
This explains why the identity works. There will be a mechanical proof from the De Morgan laws. I'll keep thinking about that but it may just mirror this reasoning.
No, i found precisely this
â Koinos
Sep 2 at 9:12
1
You're right; this does work, I've amended my answer to reflect that.
â Simon Terrington
Sep 2 at 10:37
Hi @SimonTerrington, maybe have misread the notation but what happens in the (albeit rather trivial) case where for example $forall n,A_n=A_1â â $ then $LHS=A_1$ but $RHS=â $ ? just wondering if any conditions on the sets or it's claimed in full generality. On the face of it strikes me cannot be true if all are equal but might be barking up wrong tree!
â Mehness
Sep 2 at 10:51
1
OK so this is a good point, but if you look at this last term within the intersection on the RHS, it is not complemented so for the term in which $n=1$ (on the RHS counter) then we would have $A_1$. So the LHS and RHS would both be equal to $A_1$ in this case.
â Simon Terrington
Sep 2 at 10:56
yep fair enough! :)
â Mehness
Sep 2 at 11:00
 |Â
show 1 more comment
up vote
1
down vote
up vote
1
down vote
I think you may actually be thinking of $cup A_n=(A_1^c cap ... cap A_n^c)^c$.
An element is in the left hand side if and only if it is in one of the $A_i$. Now let us look at $A_1^c cap ... cap A_n^c$. An element is in this if and only if it is not in $A_1$ and not in $A_2$ and not in any of the $A_i$. So the element is in $(A_1^c cap ... cap A_n^c)^c$ if and only if it is in one of the $A_i$ and that is exactly the same as the condition of being in the left hand side. This shows that the two sets have the same elements and so they are equal.
Looking at your comment, you are right, this does work. Let us imagine that all of the $A_i$ are empty except the first three. Then your expression gives $A_1 cup A_2 cup A_3 = A_1 cup (A_1^c cap A_2) cup (A_1^c cap A_2^c cap A_3)$. What this does is write the union on the LHS as a disjoint union. An element in the LHS is in $A_1$, $A_2$ or $A_3$. If it was in $A_1$ then it will be captured in the first term of the union on the RHS. If it is in $A_2$ but not $A_1$, it will be captured in the second term of the RHS. If it had been in $A_1$ then it would have been captured in the first term (of the RHS). If it is in $A_3$ but was not in $A_1$ or $A_2$ then it will be captured in the third term of the union on the RHS. So we have shown that the LHS is a subset of the RHS (every element of the LHS is in the RHS). It is easy to see that the RHS is a subset of the LHS (everything in the LHS must be in the RHS because each term in the LHS union is a superset of the corresponding term in the union on the RHS). So the two sets are equal. This method clearly generalises to situations when more (or all) of the $A_i$ are non-empty.
This explains why the identity works. There will be a mechanical proof from the De Morgan laws. I'll keep thinking about that but it may just mirror this reasoning.
I think you may actually be thinking of $cup A_n=(A_1^c cap ... cap A_n^c)^c$.
An element is in the left hand side if and only if it is in one of the $A_i$. Now let us look at $A_1^c cap ... cap A_n^c$. An element is in this if and only if it is not in $A_1$ and not in $A_2$ and not in any of the $A_i$. So the element is in $(A_1^c cap ... cap A_n^c)^c$ if and only if it is in one of the $A_i$ and that is exactly the same as the condition of being in the left hand side. This shows that the two sets have the same elements and so they are equal.
Looking at your comment, you are right, this does work. Let us imagine that all of the $A_i$ are empty except the first three. Then your expression gives $A_1 cup A_2 cup A_3 = A_1 cup (A_1^c cap A_2) cup (A_1^c cap A_2^c cap A_3)$. What this does is write the union on the LHS as a disjoint union. An element in the LHS is in $A_1$, $A_2$ or $A_3$. If it was in $A_1$ then it will be captured in the first term of the union on the RHS. If it is in $A_2$ but not $A_1$, it will be captured in the second term of the RHS. If it had been in $A_1$ then it would have been captured in the first term (of the RHS). If it is in $A_3$ but was not in $A_1$ or $A_2$ then it will be captured in the third term of the union on the RHS. So we have shown that the LHS is a subset of the RHS (every element of the LHS is in the RHS). It is easy to see that the RHS is a subset of the LHS (everything in the LHS must be in the RHS because each term in the LHS union is a superset of the corresponding term in the union on the RHS). So the two sets are equal. This method clearly generalises to situations when more (or all) of the $A_i$ are non-empty.
This explains why the identity works. There will be a mechanical proof from the De Morgan laws. I'll keep thinking about that but it may just mirror this reasoning.
edited Sep 2 at 10:50
answered Sep 2 at 8:39
Simon Terrington
41526
41526
No, i found precisely this
â Koinos
Sep 2 at 9:12
1
You're right; this does work, I've amended my answer to reflect that.
â Simon Terrington
Sep 2 at 10:37
Hi @SimonTerrington, maybe have misread the notation but what happens in the (albeit rather trivial) case where for example $forall n,A_n=A_1â â $ then $LHS=A_1$ but $RHS=â $ ? just wondering if any conditions on the sets or it's claimed in full generality. On the face of it strikes me cannot be true if all are equal but might be barking up wrong tree!
â Mehness
Sep 2 at 10:51
1
OK so this is a good point, but if you look at this last term within the intersection on the RHS, it is not complemented so for the term in which $n=1$ (on the RHS counter) then we would have $A_1$. So the LHS and RHS would both be equal to $A_1$ in this case.
â Simon Terrington
Sep 2 at 10:56
yep fair enough! :)
â Mehness
Sep 2 at 11:00
 |Â
show 1 more comment
No, i found precisely this
â Koinos
Sep 2 at 9:12
1
You're right; this does work, I've amended my answer to reflect that.
â Simon Terrington
Sep 2 at 10:37
Hi @SimonTerrington, maybe have misread the notation but what happens in the (albeit rather trivial) case where for example $forall n,A_n=A_1â â $ then $LHS=A_1$ but $RHS=â $ ? just wondering if any conditions on the sets or it's claimed in full generality. On the face of it strikes me cannot be true if all are equal but might be barking up wrong tree!
â Mehness
Sep 2 at 10:51
1
OK so this is a good point, but if you look at this last term within the intersection on the RHS, it is not complemented so for the term in which $n=1$ (on the RHS counter) then we would have $A_1$. So the LHS and RHS would both be equal to $A_1$ in this case.
â Simon Terrington
Sep 2 at 10:56
yep fair enough! :)
â Mehness
Sep 2 at 11:00
No, i found precisely this
â Koinos
Sep 2 at 9:12
No, i found precisely this
â Koinos
Sep 2 at 9:12
1
1
You're right; this does work, I've amended my answer to reflect that.
â Simon Terrington
Sep 2 at 10:37
You're right; this does work, I've amended my answer to reflect that.
â Simon Terrington
Sep 2 at 10:37
Hi @SimonTerrington, maybe have misread the notation but what happens in the (albeit rather trivial) case where for example $forall n,A_n=A_1â â $ then $LHS=A_1$ but $RHS=â $ ? just wondering if any conditions on the sets or it's claimed in full generality. On the face of it strikes me cannot be true if all are equal but might be barking up wrong tree!
â Mehness
Sep 2 at 10:51
Hi @SimonTerrington, maybe have misread the notation but what happens in the (albeit rather trivial) case where for example $forall n,A_n=A_1â â $ then $LHS=A_1$ but $RHS=â $ ? just wondering if any conditions on the sets or it's claimed in full generality. On the face of it strikes me cannot be true if all are equal but might be barking up wrong tree!
â Mehness
Sep 2 at 10:51
1
1
OK so this is a good point, but if you look at this last term within the intersection on the RHS, it is not complemented so for the term in which $n=1$ (on the RHS counter) then we would have $A_1$. So the LHS and RHS would both be equal to $A_1$ in this case.
â Simon Terrington
Sep 2 at 10:56
OK so this is a good point, but if you look at this last term within the intersection on the RHS, it is not complemented so for the term in which $n=1$ (on the RHS counter) then we would have $A_1$. So the LHS and RHS would both be equal to $A_1$ in this case.
â Simon Terrington
Sep 2 at 10:56
yep fair enough! :)
â Mehness
Sep 2 at 11:00
yep fair enough! :)
â Mehness
Sep 2 at 11:00
 |Â
show 1 more comment
up vote
0
down vote
So we want to see $$bigcup_n in mathbbN A_n = bigcup_n in mathbbN left(A_1^c cap A_2^c ldots A_n-1^c cap A_nright)$$
where $mathbbN$ starts at $n=1$. The first term on the right is just $A_1$, the second $A_1^c cup A_2$ etc.
If $x$ is in the right hand side it is in some set of the form $A_1^c cap A_2^c ldots A_n-1^c cap A_n subseteq A_n$ so then it's certainly in the left hand side.
If $x$ is in the left hand side, then $x in A_n$ for some $n in mathbbN$, and let $n_0 =min n: x in A_n$ which is well-defined as $mathbbN$ has a well-ordering.
Then for all $i=1, ldots, n_0 - 1$ we know that $x notin A_i$ (or we would contradict the minimality of $n_0$; the statement is voidly true if $n_0$ happens to be $1$) Hence
$ x in A_1^c cap A_2^c ldots A_n_0 - 1^c cap A_n_0$ and so $x$ is in the right hand side.
This is not an application of DeMorgan, the well-orderedness of the index set is crucial.
add a comment |Â
up vote
0
down vote
So we want to see $$bigcup_n in mathbbN A_n = bigcup_n in mathbbN left(A_1^c cap A_2^c ldots A_n-1^c cap A_nright)$$
where $mathbbN$ starts at $n=1$. The first term on the right is just $A_1$, the second $A_1^c cup A_2$ etc.
If $x$ is in the right hand side it is in some set of the form $A_1^c cap A_2^c ldots A_n-1^c cap A_n subseteq A_n$ so then it's certainly in the left hand side.
If $x$ is in the left hand side, then $x in A_n$ for some $n in mathbbN$, and let $n_0 =min n: x in A_n$ which is well-defined as $mathbbN$ has a well-ordering.
Then for all $i=1, ldots, n_0 - 1$ we know that $x notin A_i$ (or we would contradict the minimality of $n_0$; the statement is voidly true if $n_0$ happens to be $1$) Hence
$ x in A_1^c cap A_2^c ldots A_n_0 - 1^c cap A_n_0$ and so $x$ is in the right hand side.
This is not an application of DeMorgan, the well-orderedness of the index set is crucial.
add a comment |Â
up vote
0
down vote
up vote
0
down vote
So we want to see $$bigcup_n in mathbbN A_n = bigcup_n in mathbbN left(A_1^c cap A_2^c ldots A_n-1^c cap A_nright)$$
where $mathbbN$ starts at $n=1$. The first term on the right is just $A_1$, the second $A_1^c cup A_2$ etc.
If $x$ is in the right hand side it is in some set of the form $A_1^c cap A_2^c ldots A_n-1^c cap A_n subseteq A_n$ so then it's certainly in the left hand side.
If $x$ is in the left hand side, then $x in A_n$ for some $n in mathbbN$, and let $n_0 =min n: x in A_n$ which is well-defined as $mathbbN$ has a well-ordering.
Then for all $i=1, ldots, n_0 - 1$ we know that $x notin A_i$ (or we would contradict the minimality of $n_0$; the statement is voidly true if $n_0$ happens to be $1$) Hence
$ x in A_1^c cap A_2^c ldots A_n_0 - 1^c cap A_n_0$ and so $x$ is in the right hand side.
This is not an application of DeMorgan, the well-orderedness of the index set is crucial.
So we want to see $$bigcup_n in mathbbN A_n = bigcup_n in mathbbN left(A_1^c cap A_2^c ldots A_n-1^c cap A_nright)$$
where $mathbbN$ starts at $n=1$. The first term on the right is just $A_1$, the second $A_1^c cup A_2$ etc.
If $x$ is in the right hand side it is in some set of the form $A_1^c cap A_2^c ldots A_n-1^c cap A_n subseteq A_n$ so then it's certainly in the left hand side.
If $x$ is in the left hand side, then $x in A_n$ for some $n in mathbbN$, and let $n_0 =min n: x in A_n$ which is well-defined as $mathbbN$ has a well-ordering.
Then for all $i=1, ldots, n_0 - 1$ we know that $x notin A_i$ (or we would contradict the minimality of $n_0$; the statement is voidly true if $n_0$ happens to be $1$) Hence
$ x in A_1^c cap A_2^c ldots A_n_0 - 1^c cap A_n_0$ and so $x$ is in the right hand side.
This is not an application of DeMorgan, the well-orderedness of the index set is crucial.
answered Sep 2 at 19:10
Henno Brandsma
93.3k342101
93.3k342101
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%2f2902474%2fa-de-morgan-law-application-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
1
DeMorgan's Laws. After Augustus DeMorgan
â DanielWainfleet
Sep 2 at 9:18