Proof: $U$ is an ultrafilter of a Boolean algebra $B$ if and only if for all $x$ in $U$ exactly one of...
I have been stuck with this problem for a while now. I have a proof that letting $U$ be an ultrafilter, exactly one of $x,x^*$ belongs to $U$ for all $x$ in $B$, I did this by showing that both belong to $U$ implies that $U=B$ which cannot be the case, and if neither long to $U$ then a contradiction can be derived by de-Morgan's laws. However, I'm stuck with the reverse implication, I need to prove that:
"If $U$ is a subset of a Boolean algebra $B$ such that $forall x in B$, exactly one of $x in U$ and $x^* in U$ is true, U is an ultrafilter.".
Is this even the case? Any help would be greatly appreciated, thanks in advance.
elementary-set-theory boolean-algebra filters
edited 2 days ago
Andrés E. Caicedo
64.8k8158246
asked 2 days ago
Marmoset
62
New contributor
Marmoset is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
I have been stuck with this problem for a while now. I have a proof that letting $U$ be an ultrafilter, exactly one of $x,x^*$ belongs to $U$ for all $x$ in $B$, I did this by showing that both belong to $U$ implies that $U=B$ which cannot be the case, and if neither long to $U$ then a contradiction can be derived by de-Morgan's laws. However, I'm stuck with the reverse implication, I need to prove that:
"If $U$ is a subset of a Boolean algebra $B$ such that $forall x in B$, exactly one of $x in U$ and $x^* in U$ is true, U is an ultrafilter.".
Is this even the case? Any help would be greatly appreciated, thanks in advance.
elementary-set-theory boolean-algebra filters
edited 2 days ago
Andrés E. Caicedo
64.8k8158246
asked 2 days ago
Marmoset
62
New contributor
Marmoset is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
What do you denote by $x^*$? $neg x$?
– mathcounterexamples.net
2 days ago
Indeed, my mistake.
– Marmoset
2 days ago
For a given ultrafilter $usubset B$, define the set $u^ast = { 1-a: a in u}$ and consider the two questions: "Does this set meet the required hypothesis?" and "Is u^ast a filter?"
– Not Mike
2 days ago
1
In general, such a subst will not even be a filter ...
– Hagen von Eitzen
2 days ago
add a comment |
I have been stuck with this problem for a while now. I have a proof that letting $U$ be an ultrafilter, exactly one of $x,x^*$ belongs to $U$ for all $x$ in $B$, I did this by showing that both belong to $U$ implies that $U=B$ which cannot be the case, and if neither long to $U$ then a contradiction can be derived by de-Morgan's laws. However, I'm stuck with the reverse implication, I need to prove that:
"If $U$ is a subset of a Boolean algebra $B$ such that $forall x in B$, exactly one of $x in U$ and $x^* in U$ is true, U is an ultrafilter.".
Is this even the case? Any help would be greatly appreciated, thanks in advance.
elementary-set-theory boolean-algebra filters
edited 2 days ago
Andrés E. Caicedo
64.8k8158246
asked 2 days ago
Marmoset
62
New contributor
Marmoset is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
I have been stuck with this problem for a while now. I have a proof that letting $U$ be an ultrafilter, exactly one of $x,x^*$ belongs to $U$ for all $x$ in $B$, I did this by showing that both belong to $U$ implies that $U=B$ which cannot be the case, and if neither long to $U$ then a contradiction can be derived by de-Morgan's laws. However, I'm stuck with the reverse implication, I need to prove that:
"If $U$ is a subset of a Boolean algebra $B$ such that $forall x in B$, exactly one of $x in U$ and $x^* in U$ is true, U is an ultrafilter.".
Is this even the case? Any help would be greatly appreciated, thanks in advance.
elementary-set-theory boolean-algebra filters
elementary-set-theory boolean-algebra filters
edited 2 days ago
Andrés E. Caicedo
64.8k8158246
asked 2 days ago
Marmoset
62
New contributor
Marmoset is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 2 days ago
Andrés E. Caicedo
64.8k8158246
asked 2 days ago
Marmoset
62
New contributor
Marmoset is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 2 days ago
Andrés E. Caicedo
64.8k8158246
edited 2 days ago
Andrés E. Caicedo
64.8k8158246
edited 2 days ago
Andrés E. Caicedo
64.8k8158246
64.8k8158246
asked 2 days ago
Marmoset
62
New contributor
Marmoset is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 2 days ago
Marmoset
62
asked 2 days ago
Marmoset
62
62
New contributor
Marmoset is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Marmoset is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Marmoset is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
What do you denote by $x^*$? $neg x$?
– mathcounterexamples.net
2 days ago
Indeed, my mistake.
– Marmoset
2 days ago
For a given ultrafilter $usubset B$, define the set $u^ast = { 1-a: a in u}$ and consider the two questions: "Does this set meet the required hypothesis?" and "Is u^ast a filter?"
– Not Mike
2 days ago
1
In general, such a subst will not even be a filter ...
– Hagen von Eitzen
2 days ago
add a comment |
What do you denote by $x^*$? $neg x$?
– mathcounterexamples.net
2 days ago
Indeed, my mistake.
– Marmoset
2 days ago
For a given ultrafilter $usubset B$, define the set $u^ast = { 1-a: a in u}$ and consider the two questions: "Does this set meet the required hypothesis?" and "Is u^ast a filter?"
– Not Mike
2 days ago
1
In general, such a subst will not even be a filter ...
– Hagen von Eitzen
2 days ago
What do you denote by $x^*$? $neg x$?
– mathcounterexamples.net
2 days ago
What do you denote by $x^*$? $neg x$?
– mathcounterexamples.net
2 days ago
Indeed, my mistake.
– Marmoset
2 days ago
Indeed, my mistake.
– Marmoset
2 days ago
For a given ultrafilter $usubset B$, define the set $u^ast = { 1-a: a in u}$ and consider the two questions: "Does this set meet the required hypothesis?" and "Is u^ast a filter?"
– Not Mike
2 days ago
For a given ultrafilter $usubset B$, define the set $u^ast = { 1-a: a in u}$ and consider the two questions: "Does this set meet the required hypothesis?" and "Is u^ast a filter?"
– Not Mike
2 days ago
1
1
In general, such a subst will not even be a filter ...
– Hagen von Eitzen
2 days ago
In general, such a subst will not even be a filter ...
– Hagen von Eitzen
2 days ago
add a comment |
1 Answer
1
active
oldest
votes
A correct statement would be
If $Usubseteq B$ is a filter and for all $xin B$ exactly one of $xin U$ or $x^*in U$ is true, then $U$ is an ultrafilter.
The converse holds as well, and this is sometimes taken as the definition of an ultrafilter. I presume the one you've been given is that an ultrafilter is a maximal (proper) filter.
To see that the statement holds, note first that the fact that both $x$ and $x^*$ aren't in $U$ implies $U$ is a proper filter. Assume that $F$ is a filter extending $U$ and let $xin Fsetminus U.$ Then $x^*in U,$ so $x^*in F$ and since both $x$ and $x^*$ are in $F,$ $F$ is improper.
Without the provision that $U$ is a filter, the statement becomes very badly false. Just randomly choose elements of a Boolean algebra, randomly label with zero or one (indicators as to whether the element is inside or outside $U$), and assign the complement the opposite label. Odds are you hit a counterexample. (To guarantee you do so, just make sure you start out labeling the $0$ element with a one and the $1$ element with a zero).
answered 2 days ago
spaceisdarkgreen
32.4k21753
2
Although it's easy to get counterexamples, it's not quite as easy as you made it sound. You need to arrange for each complementary pair $x$ and $neg x$ to get opposite values. So randomly pick one element from each complementary pair, label the chosen elements $1$ and the unchosen ones $0$. As you said, you have a good chance of getting a counterexample, and you can guarantee a counterexample by choosing $0$ from the pair ${0,1}$. (Also, if you have bad luck and get an ultrafilter, just take its complement to get a counterexample.)
– Andreas Blass
2 days ago
@AndreasBlass Yes, I put that incorrectly, thank you for the correction!
– spaceisdarkgreen
2 days ago
Thank you very much! This was very helpful
– Marmoset
2 days ago
add a comment |
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
});
}
});
Marmoset is a new contributor. Be nice, and check out our Code of Conduct.
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%2f3060976%2fproof-u-is-an-ultrafilter-of-a-boolean-algebra-b-if-and-only-if-for-all-x%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
A correct statement would be
If $Usubseteq B$ is a filter and for all $xin B$ exactly one of $xin U$ or $x^*in U$ is true, then $U$ is an ultrafilter.
The converse holds as well, and this is sometimes taken as the definition of an ultrafilter. I presume the one you've been given is that an ultrafilter is a maximal (proper) filter.
To see that the statement holds, note first that the fact that both $x$ and $x^*$ aren't in $U$ implies $U$ is a proper filter. Assume that $F$ is a filter extending $U$ and let $xin Fsetminus U.$ Then $x^*in U,$ so $x^*in F$ and since both $x$ and $x^*$ are in $F,$ $F$ is improper.
Without the provision that $U$ is a filter, the statement becomes very badly false. Just randomly choose elements of a Boolean algebra, randomly label with zero or one (indicators as to whether the element is inside or outside $U$), and assign the complement the opposite label. Odds are you hit a counterexample. (To guarantee you do so, just make sure you start out labeling the $0$ element with a one and the $1$ element with a zero).
answered 2 days ago
spaceisdarkgreen
32.4k21753
2
Although it's easy to get counterexamples, it's not quite as easy as you made it sound. You need to arrange for each complementary pair $x$ and $neg x$ to get opposite values. So randomly pick one element from each complementary pair, label the chosen elements $1$ and the unchosen ones $0$. As you said, you have a good chance of getting a counterexample, and you can guarantee a counterexample by choosing $0$ from the pair ${0,1}$. (Also, if you have bad luck and get an ultrafilter, just take its complement to get a counterexample.)
– Andreas Blass
2 days ago
@AndreasBlass Yes, I put that incorrectly, thank you for the correction!
– spaceisdarkgreen
2 days ago
Thank you very much! This was very helpful
– Marmoset
2 days ago
add a comment |
A correct statement would be
If $Usubseteq B$ is a filter and for all $xin B$ exactly one of $xin U$ or $x^*in U$ is true, then $U$ is an ultrafilter.
The converse holds as well, and this is sometimes taken as the definition of an ultrafilter. I presume the one you've been given is that an ultrafilter is a maximal (proper) filter.
To see that the statement holds, note first that the fact that both $x$ and $x^*$ aren't in $U$ implies $U$ is a proper filter. Assume that $F$ is a filter extending $U$ and let $xin Fsetminus U.$ Then $x^*in U,$ so $x^*in F$ and since both $x$ and $x^*$ are in $F,$ $F$ is improper.
Without the provision that $U$ is a filter, the statement becomes very badly false. Just randomly choose elements of a Boolean algebra, randomly label with zero or one (indicators as to whether the element is inside or outside $U$), and assign the complement the opposite label. Odds are you hit a counterexample. (To guarantee you do so, just make sure you start out labeling the $0$ element with a one and the $1$ element with a zero).
answered 2 days ago
spaceisdarkgreen
32.4k21753
2
Although it's easy to get counterexamples, it's not quite as easy as you made it sound. You need to arrange for each complementary pair $x$ and $neg x$ to get opposite values. So randomly pick one element from each complementary pair, label the chosen elements $1$ and the unchosen ones $0$. As you said, you have a good chance of getting a counterexample, and you can guarantee a counterexample by choosing $0$ from the pair ${0,1}$. (Also, if you have bad luck and get an ultrafilter, just take its complement to get a counterexample.)
– Andreas Blass
2 days ago
@AndreasBlass Yes, I put that incorrectly, thank you for the correction!
– spaceisdarkgreen
2 days ago
Thank you very much! This was very helpful
– Marmoset
2 days ago
add a comment |
A correct statement would be
If $Usubseteq B$ is a filter and for all $xin B$ exactly one of $xin U$ or $x^*in U$ is true, then $U$ is an ultrafilter.
The converse holds as well, and this is sometimes taken as the definition of an ultrafilter. I presume the one you've been given is that an ultrafilter is a maximal (proper) filter.
To see that the statement holds, note first that the fact that both $x$ and $x^*$ aren't in $U$ implies $U$ is a proper filter. Assume that $F$ is a filter extending $U$ and let $xin Fsetminus U.$ Then $x^*in U,$ so $x^*in F$ and since both $x$ and $x^*$ are in $F,$ $F$ is improper.
Without the provision that $U$ is a filter, the statement becomes very badly false. Just randomly choose elements of a Boolean algebra, randomly label with zero or one (indicators as to whether the element is inside or outside $U$), and assign the complement the opposite label. Odds are you hit a counterexample. (To guarantee you do so, just make sure you start out labeling the $0$ element with a one and the $1$ element with a zero).
answered 2 days ago
spaceisdarkgreen
32.4k21753
A correct statement would be
If $Usubseteq B$ is a filter and for all $xin B$ exactly one of $xin U$ or $x^*in U$ is true, then $U$ is an ultrafilter.
The converse holds as well, and this is sometimes taken as the definition of an ultrafilter. I presume the one you've been given is that an ultrafilter is a maximal (proper) filter.
To see that the statement holds, note first that the fact that both $x$ and $x^*$ aren't in $U$ implies $U$ is a proper filter. Assume that $F$ is a filter extending $U$ and let $xin Fsetminus U.$ Then $x^*in U,$ so $x^*in F$ and since both $x$ and $x^*$ are in $F,$ $F$ is improper.
Without the provision that $U$ is a filter, the statement becomes very badly false. Just randomly choose elements of a Boolean algebra, randomly label with zero or one (indicators as to whether the element is inside or outside $U$), and assign the complement the opposite label. Odds are you hit a counterexample. (To guarantee you do so, just make sure you start out labeling the $0$ element with a one and the $1$ element with a zero).
answered 2 days ago
spaceisdarkgreen
32.4k21753
edited 2 days ago
answered 2 days ago
spaceisdarkgreen
32.4k21753
answered 2 days ago
spaceisdarkgreen
32.4k21753
answered 2 days ago
spaceisdarkgreen
32.4k21753
32.4k21753
2
Although it's easy to get counterexamples, it's not quite as easy as you made it sound. You need to arrange for each complementary pair $x$ and $neg x$ to get opposite values. So randomly pick one element from each complementary pair, label the chosen elements $1$ and the unchosen ones $0$. As you said, you have a good chance of getting a counterexample, and you can guarantee a counterexample by choosing $0$ from the pair ${0,1}$. (Also, if you have bad luck and get an ultrafilter, just take its complement to get a counterexample.)
– Andreas Blass
2 days ago
@AndreasBlass Yes, I put that incorrectly, thank you for the correction!
– spaceisdarkgreen
2 days ago
Thank you very much! This was very helpful
– Marmoset
2 days ago
add a comment |
2
Although it's easy to get counterexamples, it's not quite as easy as you made it sound. You need to arrange for each complementary pair $x$ and $neg x$ to get opposite values. So randomly pick one element from each complementary pair, label the chosen elements $1$ and the unchosen ones $0$. As you said, you have a good chance of getting a counterexample, and you can guarantee a counterexample by choosing $0$ from the pair ${0,1}$. (Also, if you have bad luck and get an ultrafilter, just take its complement to get a counterexample.)
– Andreas Blass
2 days ago
@AndreasBlass Yes, I put that incorrectly, thank you for the correction!
– spaceisdarkgreen
2 days ago
Thank you very much! This was very helpful
– Marmoset
2 days ago
2
2
Although it's easy to get counterexamples, it's not quite as easy as you made it sound. You need to arrange for each complementary pair $x$ and $neg x$ to get opposite values. So randomly pick one element from each complementary pair, label the chosen elements $1$ and the unchosen ones $0$. As you said, you have a good chance of getting a counterexample, and you can guarantee a counterexample by choosing $0$ from the pair ${0,1}$. (Also, if you have bad luck and get an ultrafilter, just take its complement to get a counterexample.)
– Andreas Blass
2 days ago
Although it's easy to get counterexamples, it's not quite as easy as you made it sound. You need to arrange for each complementary pair $x$ and $neg x$ to get opposite values. So randomly pick one element from each complementary pair, label the chosen elements $1$ and the unchosen ones $0$. As you said, you have a good chance of getting a counterexample, and you can guarantee a counterexample by choosing $0$ from the pair ${0,1}$. (Also, if you have bad luck and get an ultrafilter, just take its complement to get a counterexample.)
– Andreas Blass
2 days ago
@AndreasBlass Yes, I put that incorrectly, thank you for the correction!
– spaceisdarkgreen
2 days ago
@AndreasBlass Yes, I put that incorrectly, thank you for the correction!
– spaceisdarkgreen
2 days ago
Thank you very much! This was very helpful
– Marmoset
2 days ago
Thank you very much! This was very helpful
– Marmoset
2 days ago
add a comment |
Marmoset is a new contributor. Be nice, and check out our Code of Conduct.
Marmoset is a new contributor. Be nice, and check out our Code of Conduct.
Marmoset is a new contributor. Be nice, and check out our Code of Conduct.
Marmoset is a new contributor. Be nice, and check out our Code of Conduct.
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%2f3060976%2fproof-u-is-an-ultrafilter-of-a-boolean-algebra-b-if-and-only-if-for-all-x%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
What do you denote by $x^*$? $neg x$?
– mathcounterexamples.net
2 days ago
Indeed, my mistake.
– Marmoset
2 days ago
For a given ultrafilter $usubset B$, define the set $u^ast = { 1-a: a in u}$ and consider the two questions: "Does this set meet the required hypothesis?" and "Is u^ast a filter?"
– Not Mike
2 days ago
1
In general, such a subst will not even be a filter ...
– Hagen von Eitzen
2 days ago