Proof: $U$ is an ultrafilter of a Boolean algebra $B$ if and only if for all $x$ in $U$ exactly one of...
$begingroup$
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 Jan 4 at 17:54
Andrés E. Caicedo
65.8k8160252
asked Jan 3 at 20:34
MarmosetMarmoset
506
$endgroup$
add a comment |
$begingroup$
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 Jan 4 at 17:54
Andrés E. Caicedo
65.8k8160252
asked Jan 3 at 20:34
MarmosetMarmoset
506
$endgroup$
$begingroup$
What do you denote by $x^*$? $neg x$?
$endgroup$
– mathcounterexamples.net
Jan 3 at 20:45
$begingroup$
Indeed, my mistake.
$endgroup$
– Marmoset
Jan 3 at 21:50
$begingroup$
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?"
$endgroup$
– Not Mike
Jan 3 at 22:07
1
$begingroup$
In general, such a subst will not even be a filter ...
$endgroup$
– Hagen von Eitzen
Jan 3 at 23:35
add a comment |
$begingroup$
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 Jan 4 at 17:54
Andrés E. Caicedo
65.8k8160252
asked Jan 3 at 20:34
MarmosetMarmoset
506
$endgroup$
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 Jan 4 at 17:54
Andrés E. Caicedo
65.8k8160252
asked Jan 3 at 20:34
MarmosetMarmoset
506
edited Jan 4 at 17:54
Andrés E. Caicedo
65.8k8160252
asked Jan 3 at 20:34
MarmosetMarmoset
506
edited Jan 4 at 17:54
Andrés E. Caicedo
65.8k8160252
edited Jan 4 at 17:54
Andrés E. Caicedo
65.8k8160252
edited Jan 4 at 17:54
Andrés E. Caicedo
65.8k8160252
65.8k8160252
asked Jan 3 at 20:34
MarmosetMarmoset
506
asked Jan 3 at 20:34
MarmosetMarmoset
506
asked Jan 3 at 20:34
MarmosetMarmoset
506
506
$begingroup$
What do you denote by $x^*$? $neg x$?
$endgroup$
– mathcounterexamples.net
Jan 3 at 20:45
$begingroup$
Indeed, my mistake.
$endgroup$
– Marmoset
Jan 3 at 21:50
$begingroup$
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?"
$endgroup$
– Not Mike
Jan 3 at 22:07
1
$begingroup$
In general, such a subst will not even be a filter ...
$endgroup$
– Hagen von Eitzen
Jan 3 at 23:35
add a comment |
$begingroup$
What do you denote by $x^*$? $neg x$?
$endgroup$
– mathcounterexamples.net
Jan 3 at 20:45
$begingroup$
Indeed, my mistake.
$endgroup$
– Marmoset
Jan 3 at 21:50
$begingroup$
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?"
$endgroup$
– Not Mike
Jan 3 at 22:07
1
$begingroup$
In general, such a subst will not even be a filter ...
$endgroup$
– Hagen von Eitzen
Jan 3 at 23:35
$begingroup$
What do you denote by $x^*$? $neg x$?
$endgroup$
– mathcounterexamples.net
Jan 3 at 20:45
$begingroup$
What do you denote by $x^*$? $neg x$?
$endgroup$
– mathcounterexamples.net
Jan 3 at 20:45
$begingroup$
Indeed, my mistake.
$endgroup$
– Marmoset
Jan 3 at 21:50
$begingroup$
Indeed, my mistake.
$endgroup$
– Marmoset
Jan 3 at 21:50
$begingroup$
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?"
$endgroup$
– Not Mike
Jan 3 at 22:07
$begingroup$
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?"
$endgroup$
– Not Mike
Jan 3 at 22:07
1
1
$begingroup$
In general, such a subst will not even be a filter ...
$endgroup$
– Hagen von Eitzen
Jan 3 at 23:35
$begingroup$
In general, such a subst will not even be a filter ...
$endgroup$
– Hagen von Eitzen
Jan 3 at 23:35
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
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 Jan 4 at 1:03
spaceisdarkgreenspaceisdarkgreen
33.8k21753
$endgroup$
2
$begingroup$
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.)
$endgroup$
– Andreas Blass
Jan 4 at 3:25
$begingroup$
@AndreasBlass Yes, I put that incorrectly, thank you for the correction!
$endgroup$
– spaceisdarkgreen
Jan 4 at 3:29
$begingroup$
Thank you very much! This was very helpful
$endgroup$
– Marmoset
Jan 4 at 15:02
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
});
}
});
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
$begingroup$
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 Jan 4 at 1:03
spaceisdarkgreenspaceisdarkgreen
33.8k21753
$endgroup$
2
$begingroup$
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.)
$endgroup$
– Andreas Blass
Jan 4 at 3:25
$begingroup$
@AndreasBlass Yes, I put that incorrectly, thank you for the correction!
$endgroup$
– spaceisdarkgreen
Jan 4 at 3:29
$begingroup$
Thank you very much! This was very helpful
$endgroup$
– Marmoset
Jan 4 at 15:02
add a comment |
$begingroup$
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 Jan 4 at 1:03
spaceisdarkgreenspaceisdarkgreen
33.8k21753
$endgroup$
2
$begingroup$
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.)
$endgroup$
– Andreas Blass
Jan 4 at 3:25
$begingroup$
@AndreasBlass Yes, I put that incorrectly, thank you for the correction!
$endgroup$
– spaceisdarkgreen
Jan 4 at 3:29
$begingroup$
Thank you very much! This was very helpful
$endgroup$
– Marmoset
Jan 4 at 15:02
add a comment |
$begingroup$
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 Jan 4 at 1:03
spaceisdarkgreenspaceisdarkgreen
33.8k21753
$endgroup$
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 Jan 4 at 1:03
spaceisdarkgreenspaceisdarkgreen
33.8k21753
edited Jan 4 at 3:34
answered Jan 4 at 1:03
spaceisdarkgreenspaceisdarkgreen
33.8k21753
answered Jan 4 at 1:03
spaceisdarkgreenspaceisdarkgreen
33.8k21753
answered Jan 4 at 1:03
spaceisdarkgreenspaceisdarkgreen
33.8k21753
33.8k21753
2
$begingroup$
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.)
$endgroup$
– Andreas Blass
Jan 4 at 3:25
$begingroup$
@AndreasBlass Yes, I put that incorrectly, thank you for the correction!
$endgroup$
– spaceisdarkgreen
Jan 4 at 3:29
$begingroup$
Thank you very much! This was very helpful
$endgroup$
– Marmoset
Jan 4 at 15:02
add a comment |
2
$begingroup$
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.)
$endgroup$
– Andreas Blass
Jan 4 at 3:25
$begingroup$
@AndreasBlass Yes, I put that incorrectly, thank you for the correction!
$endgroup$
– spaceisdarkgreen
Jan 4 at 3:29
$begingroup$
Thank you very much! This was very helpful
$endgroup$
– Marmoset
Jan 4 at 15:02
2
2
$begingroup$
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.)
$endgroup$
– Andreas Blass
Jan 4 at 3:25
$begingroup$
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.)
$endgroup$
– Andreas Blass
Jan 4 at 3:25
$begingroup$
@AndreasBlass Yes, I put that incorrectly, thank you for the correction!
$endgroup$
– spaceisdarkgreen
Jan 4 at 3:29
$begingroup$
@AndreasBlass Yes, I put that incorrectly, thank you for the correction!
$endgroup$
– spaceisdarkgreen
Jan 4 at 3:29
$begingroup$
Thank you very much! This was very helpful
$endgroup$
– Marmoset
Jan 4 at 15:02
$begingroup$
Thank you very much! This was very helpful
$endgroup$
– Marmoset
Jan 4 at 15:02
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.
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
$begingroup$
What do you denote by $x^*$? $neg x$?
$endgroup$
– mathcounterexamples.net
Jan 3 at 20:45
$begingroup$
Indeed, my mistake.
$endgroup$
– Marmoset
Jan 3 at 21:50
$begingroup$
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?"
$endgroup$
– Not Mike
Jan 3 at 22:07
1
$begingroup$
In general, such a subst will not even be a filter ...
$endgroup$
– Hagen von Eitzen
Jan 3 at 23:35