Proving associativity of a certain binary aperation in any complemented distributive lattice
$begingroup$
If, in a Boolean lattice $(X,vee,wedge,0,1,')$ (i.e. a complemented distributive lattice), we define $x+y=(x'wedge y)vee(xwedge y')$, is there an elegant way to prove that $(x+y)+z=x+(y+z)$ rather than just opening everything?
For example, in a ring with identity $(X,+,0,-,cdot,1)$, if we define $xvee y=x+y-xy$, we easily get the associativity of $vee$ by opening everything, but we can also do this: notice that $1-(xvee y)=1-x-y+xy=(1-x)(1-y)$, therefore:
$1-(xvee(yvee z))=(1-x)(1-(yvee z))=(1-x)((1-y)(1-z))=((1-x)(1-y))(1-z)=(1-(xvee y))(1-z)=1-((xvee y)vee z)$
ring-theory boolean-algebra lattice-orders boolean-ring
asked Dec 11 '18 at 17:39
Daniel KawaiDaniel Kawai
13013
$endgroup$
add a comment |
$begingroup$
If, in a Boolean lattice $(X,vee,wedge,0,1,')$ (i.e. a complemented distributive lattice), we define $x+y=(x'wedge y)vee(xwedge y')$, is there an elegant way to prove that $(x+y)+z=x+(y+z)$ rather than just opening everything?
For example, in a ring with identity $(X,+,0,-,cdot,1)$, if we define $xvee y=x+y-xy$, we easily get the associativity of $vee$ by opening everything, but we can also do this: notice that $1-(xvee y)=1-x-y+xy=(1-x)(1-y)$, therefore:
$1-(xvee(yvee z))=(1-x)(1-(yvee z))=(1-x)((1-y)(1-z))=((1-x)(1-y))(1-z)=(1-(xvee y))(1-z)=1-((xvee y)vee z)$
ring-theory boolean-algebra lattice-orders boolean-ring
asked Dec 11 '18 at 17:39
Daniel KawaiDaniel Kawai
13013
$endgroup$
$begingroup$
Some people misunderstood my question, they think I am referring only to the two-element boolean algebra, and I already know a simpler method for it. The problem is that it only worked for this specific example, while my question is about any complemented distributive lattice, such as the powerset os a set, the set of regular open sets of a topological space, and so on.
$endgroup$
– Daniel Kawai
Dec 21 '18 at 5:14
add a comment |
$begingroup$
If, in a Boolean lattice $(X,vee,wedge,0,1,')$ (i.e. a complemented distributive lattice), we define $x+y=(x'wedge y)vee(xwedge y')$, is there an elegant way to prove that $(x+y)+z=x+(y+z)$ rather than just opening everything?
For example, in a ring with identity $(X,+,0,-,cdot,1)$, if we define $xvee y=x+y-xy$, we easily get the associativity of $vee$ by opening everything, but we can also do this: notice that $1-(xvee y)=1-x-y+xy=(1-x)(1-y)$, therefore:
$1-(xvee(yvee z))=(1-x)(1-(yvee z))=(1-x)((1-y)(1-z))=((1-x)(1-y))(1-z)=(1-(xvee y))(1-z)=1-((xvee y)vee z)$
ring-theory boolean-algebra lattice-orders boolean-ring
asked Dec 11 '18 at 17:39
Daniel KawaiDaniel Kawai
13013
$endgroup$
If, in a Boolean lattice $(X,vee,wedge,0,1,')$ (i.e. a complemented distributive lattice), we define $x+y=(x'wedge y)vee(xwedge y')$, is there an elegant way to prove that $(x+y)+z=x+(y+z)$ rather than just opening everything?
For example, in a ring with identity $(X,+,0,-,cdot,1)$, if we define $xvee y=x+y-xy$, we easily get the associativity of $vee$ by opening everything, but we can also do this: notice that $1-(xvee y)=1-x-y+xy=(1-x)(1-y)$, therefore:
$1-(xvee(yvee z))=(1-x)(1-(yvee z))=(1-x)((1-y)(1-z))=((1-x)(1-y))(1-z)=(1-(xvee y))(1-z)=1-((xvee y)vee z)$
ring-theory boolean-algebra lattice-orders boolean-ring
ring-theory boolean-algebra lattice-orders boolean-ring
asked Dec 11 '18 at 17:39
Daniel KawaiDaniel Kawai
13013
asked Dec 11 '18 at 17:39
Daniel KawaiDaniel Kawai
13013
edited Dec 13 '18 at 2:29
Daniel Kawai
asked Dec 11 '18 at 17:39
Daniel KawaiDaniel Kawai
13013
asked Dec 11 '18 at 17:39
Daniel KawaiDaniel Kawai
13013
asked Dec 11 '18 at 17:39
Daniel KawaiDaniel Kawai
13013
13013
$begingroup$
Some people misunderstood my question, they think I am referring only to the two-element boolean algebra, and I already know a simpler method for it. The problem is that it only worked for this specific example, while my question is about any complemented distributive lattice, such as the powerset os a set, the set of regular open sets of a topological space, and so on.
$endgroup$
– Daniel Kawai
Dec 21 '18 at 5:14
add a comment |
$begingroup$
Some people misunderstood my question, they think I am referring only to the two-element boolean algebra, and I already know a simpler method for it. The problem is that it only worked for this specific example, while my question is about any complemented distributive lattice, such as the powerset os a set, the set of regular open sets of a topological space, and so on.
$endgroup$
– Daniel Kawai
Dec 21 '18 at 5:14
$begingroup$
Some people misunderstood my question, they think I am referring only to the two-element boolean algebra, and I already know a simpler method for it. The problem is that it only worked for this specific example, while my question is about any complemented distributive lattice, such as the powerset os a set, the set of regular open sets of a topological space, and so on.
$endgroup$
– Daniel Kawai
Dec 21 '18 at 5:14
$begingroup$
Some people misunderstood my question, they think I am referring only to the two-element boolean algebra, and I already know a simpler method for it. The problem is that it only worked for this specific example, while my question is about any complemented distributive lattice, such as the powerset os a set, the set of regular open sets of a topological space, and so on.
$endgroup$
– Daniel Kawai
Dec 21 '18 at 5:14
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Treating true as $1$ and false as $0$, the xor of $x,,y$ has the same parity as their sum. (If you want to work in algebra, it's modulo $2$ arithmetic.) Since addition associates, xor associates up to parity. But no distinct truth values are of the same parity, so xor associates.
answered Dec 11 '18 at 17:56
J.G.J.G.
27.6k22843
$endgroup$
$begingroup$
Sorry, but by "Boolean algebra" I wanted to mean "Boolean lattice", i.e., any complemented distributive lattice. How can you use the parity method in any Boolean lattice? I only know how to do it in the Boolean algebra ${0,1}$.
$endgroup$
– Daniel Kawai
Dec 11 '18 at 18:59
$begingroup$
@DanielKawai In that case isomorphism to ring addition proves the result.
$endgroup$
– J.G.
Dec 11 '18 at 19:32
$begingroup$
In the general case, what ring and what isomorphism are you referring to? If you wanted to mean the induced boolean ring in that $x+y=(x' wedge y)vee(xwedge y')$ and $xy=xwedge y$, this argument looks like circular, because to prove it is indeed a ring, you have to prove, in particular, that $+$ is associative.
$endgroup$
– Daniel Kawai
Dec 11 '18 at 19:45
$begingroup$
@DanielKawai How do you define xor on the lattice?
$endgroup$
– J.G.
Dec 11 '18 at 19:50
$begingroup$
I'll denote xor with $oplus$ so $+$ can be ordinary addition. If $y=0$, $xoplus y=x$; if $y=1$, $xoplus y=1-x$. Thus $xoplus y=x+y(1-2x)=x+y-2xy$ and $1-2(xoplus y)=(1-2x)(1-2y)$. This makes associativity immediate.
$endgroup$
– J.G.
Dec 11 '18 at 20:17
|
show 3 more comments
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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%2f3035547%2fproving-associativity-of-a-certain-binary-aperation-in-any-complemented-distribu%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Treating true as $1$ and false as $0$, the xor of $x,,y$ has the same parity as their sum. (If you want to work in algebra, it's modulo $2$ arithmetic.) Since addition associates, xor associates up to parity. But no distinct truth values are of the same parity, so xor associates.
answered Dec 11 '18 at 17:56
J.G.J.G.
27.6k22843
$endgroup$
$begingroup$
Sorry, but by "Boolean algebra" I wanted to mean "Boolean lattice", i.e., any complemented distributive lattice. How can you use the parity method in any Boolean lattice? I only know how to do it in the Boolean algebra ${0,1}$.
$endgroup$
– Daniel Kawai
Dec 11 '18 at 18:59
$begingroup$
@DanielKawai In that case isomorphism to ring addition proves the result.
$endgroup$
– J.G.
Dec 11 '18 at 19:32
$begingroup$
In the general case, what ring and what isomorphism are you referring to? If you wanted to mean the induced boolean ring in that $x+y=(x' wedge y)vee(xwedge y')$ and $xy=xwedge y$, this argument looks like circular, because to prove it is indeed a ring, you have to prove, in particular, that $+$ is associative.
$endgroup$
– Daniel Kawai
Dec 11 '18 at 19:45
$begingroup$
@DanielKawai How do you define xor on the lattice?
$endgroup$
– J.G.
Dec 11 '18 at 19:50
$begingroup$
I'll denote xor with $oplus$ so $+$ can be ordinary addition. If $y=0$, $xoplus y=x$; if $y=1$, $xoplus y=1-x$. Thus $xoplus y=x+y(1-2x)=x+y-2xy$ and $1-2(xoplus y)=(1-2x)(1-2y)$. This makes associativity immediate.
$endgroup$
– J.G.
Dec 11 '18 at 20:17
|
show 3 more comments
$begingroup$
Treating true as $1$ and false as $0$, the xor of $x,,y$ has the same parity as their sum. (If you want to work in algebra, it's modulo $2$ arithmetic.) Since addition associates, xor associates up to parity. But no distinct truth values are of the same parity, so xor associates.
answered Dec 11 '18 at 17:56
J.G.J.G.
27.6k22843
$endgroup$
$begingroup$
Sorry, but by "Boolean algebra" I wanted to mean "Boolean lattice", i.e., any complemented distributive lattice. How can you use the parity method in any Boolean lattice? I only know how to do it in the Boolean algebra ${0,1}$.
$endgroup$
– Daniel Kawai
Dec 11 '18 at 18:59
$begingroup$
@DanielKawai In that case isomorphism to ring addition proves the result.
$endgroup$
– J.G.
Dec 11 '18 at 19:32
$begingroup$
In the general case, what ring and what isomorphism are you referring to? If you wanted to mean the induced boolean ring in that $x+y=(x' wedge y)vee(xwedge y')$ and $xy=xwedge y$, this argument looks like circular, because to prove it is indeed a ring, you have to prove, in particular, that $+$ is associative.
$endgroup$
– Daniel Kawai
Dec 11 '18 at 19:45
$begingroup$
@DanielKawai How do you define xor on the lattice?
$endgroup$
– J.G.
Dec 11 '18 at 19:50
$begingroup$
I'll denote xor with $oplus$ so $+$ can be ordinary addition. If $y=0$, $xoplus y=x$; if $y=1$, $xoplus y=1-x$. Thus $xoplus y=x+y(1-2x)=x+y-2xy$ and $1-2(xoplus y)=(1-2x)(1-2y)$. This makes associativity immediate.
$endgroup$
– J.G.
Dec 11 '18 at 20:17
|
show 3 more comments
$begingroup$
Treating true as $1$ and false as $0$, the xor of $x,,y$ has the same parity as their sum. (If you want to work in algebra, it's modulo $2$ arithmetic.) Since addition associates, xor associates up to parity. But no distinct truth values are of the same parity, so xor associates.
answered Dec 11 '18 at 17:56
J.G.J.G.
27.6k22843
$endgroup$
Treating true as $1$ and false as $0$, the xor of $x,,y$ has the same parity as their sum. (If you want to work in algebra, it's modulo $2$ arithmetic.) Since addition associates, xor associates up to parity. But no distinct truth values are of the same parity, so xor associates.
answered Dec 11 '18 at 17:56
J.G.J.G.
27.6k22843
answered Dec 11 '18 at 17:56
J.G.J.G.
27.6k22843
answered Dec 11 '18 at 17:56
J.G.J.G.
27.6k22843
answered Dec 11 '18 at 17:56
J.G.J.G.
27.6k22843
27.6k22843
$begingroup$
Sorry, but by "Boolean algebra" I wanted to mean "Boolean lattice", i.e., any complemented distributive lattice. How can you use the parity method in any Boolean lattice? I only know how to do it in the Boolean algebra ${0,1}$.
$endgroup$
– Daniel Kawai
Dec 11 '18 at 18:59
$begingroup$
@DanielKawai In that case isomorphism to ring addition proves the result.
$endgroup$
– J.G.
Dec 11 '18 at 19:32
$begingroup$
In the general case, what ring and what isomorphism are you referring to? If you wanted to mean the induced boolean ring in that $x+y=(x' wedge y)vee(xwedge y')$ and $xy=xwedge y$, this argument looks like circular, because to prove it is indeed a ring, you have to prove, in particular, that $+$ is associative.
$endgroup$
– Daniel Kawai
Dec 11 '18 at 19:45
$begingroup$
@DanielKawai How do you define xor on the lattice?
$endgroup$
– J.G.
Dec 11 '18 at 19:50
$begingroup$
I'll denote xor with $oplus$ so $+$ can be ordinary addition. If $y=0$, $xoplus y=x$; if $y=1$, $xoplus y=1-x$. Thus $xoplus y=x+y(1-2x)=x+y-2xy$ and $1-2(xoplus y)=(1-2x)(1-2y)$. This makes associativity immediate.
$endgroup$
– J.G.
Dec 11 '18 at 20:17
|
show 3 more comments
$begingroup$
Sorry, but by "Boolean algebra" I wanted to mean "Boolean lattice", i.e., any complemented distributive lattice. How can you use the parity method in any Boolean lattice? I only know how to do it in the Boolean algebra ${0,1}$.
$endgroup$
– Daniel Kawai
Dec 11 '18 at 18:59
$begingroup$
@DanielKawai In that case isomorphism to ring addition proves the result.
$endgroup$
– J.G.
Dec 11 '18 at 19:32
$begingroup$
In the general case, what ring and what isomorphism are you referring to? If you wanted to mean the induced boolean ring in that $x+y=(x' wedge y)vee(xwedge y')$ and $xy=xwedge y$, this argument looks like circular, because to prove it is indeed a ring, you have to prove, in particular, that $+$ is associative.
$endgroup$
– Daniel Kawai
Dec 11 '18 at 19:45
$begingroup$
@DanielKawai How do you define xor on the lattice?
$endgroup$
– J.G.
Dec 11 '18 at 19:50
$begingroup$
I'll denote xor with $oplus$ so $+$ can be ordinary addition. If $y=0$, $xoplus y=x$; if $y=1$, $xoplus y=1-x$. Thus $xoplus y=x+y(1-2x)=x+y-2xy$ and $1-2(xoplus y)=(1-2x)(1-2y)$. This makes associativity immediate.
$endgroup$
– J.G.
Dec 11 '18 at 20:17
$begingroup$
Sorry, but by "Boolean algebra" I wanted to mean "Boolean lattice", i.e., any complemented distributive lattice. How can you use the parity method in any Boolean lattice? I only know how to do it in the Boolean algebra ${0,1}$.
$endgroup$
– Daniel Kawai
Dec 11 '18 at 18:59
$begingroup$
Sorry, but by "Boolean algebra" I wanted to mean "Boolean lattice", i.e., any complemented distributive lattice. How can you use the parity method in any Boolean lattice? I only know how to do it in the Boolean algebra ${0,1}$.
$endgroup$
– Daniel Kawai
Dec 11 '18 at 18:59
$begingroup$
@DanielKawai In that case isomorphism to ring addition proves the result.
$endgroup$
– J.G.
Dec 11 '18 at 19:32
$begingroup$
@DanielKawai In that case isomorphism to ring addition proves the result.
$endgroup$
– J.G.
Dec 11 '18 at 19:32
$begingroup$
In the general case, what ring and what isomorphism are you referring to? If you wanted to mean the induced boolean ring in that $x+y=(x' wedge y)vee(xwedge y')$ and $xy=xwedge y$, this argument looks like circular, because to prove it is indeed a ring, you have to prove, in particular, that $+$ is associative.
$endgroup$
– Daniel Kawai
Dec 11 '18 at 19:45
$begingroup$
In the general case, what ring and what isomorphism are you referring to? If you wanted to mean the induced boolean ring in that $x+y=(x' wedge y)vee(xwedge y')$ and $xy=xwedge y$, this argument looks like circular, because to prove it is indeed a ring, you have to prove, in particular, that $+$ is associative.
$endgroup$
– Daniel Kawai
Dec 11 '18 at 19:45
$begingroup$
@DanielKawai How do you define xor on the lattice?
$endgroup$
– J.G.
Dec 11 '18 at 19:50
$begingroup$
@DanielKawai How do you define xor on the lattice?
$endgroup$
– J.G.
Dec 11 '18 at 19:50
$begingroup$
I'll denote xor with $oplus$ so $+$ can be ordinary addition. If $y=0$, $xoplus y=x$; if $y=1$, $xoplus y=1-x$. Thus $xoplus y=x+y(1-2x)=x+y-2xy$ and $1-2(xoplus y)=(1-2x)(1-2y)$. This makes associativity immediate.
$endgroup$
– J.G.
Dec 11 '18 at 20:17
$begingroup$
I'll denote xor with $oplus$ so $+$ can be ordinary addition. If $y=0$, $xoplus y=x$; if $y=1$, $xoplus y=1-x$. Thus $xoplus y=x+y(1-2x)=x+y-2xy$ and $1-2(xoplus y)=(1-2x)(1-2y)$. This makes associativity immediate.
$endgroup$
– J.G.
Dec 11 '18 at 20:17
|
show 3 more comments
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.
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%2f3035547%2fproving-associativity-of-a-certain-binary-aperation-in-any-complemented-distribu%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
$begingroup$
Some people misunderstood my question, they think I am referring only to the two-element boolean algebra, and I already know a simpler method for it. The problem is that it only worked for this specific example, while my question is about any complemented distributive lattice, such as the powerset os a set, the set of regular open sets of a topological space, and so on.
$endgroup$
– Daniel Kawai
Dec 21 '18 at 5:14