Theorems in the form of “if and only if” such that the proofs of BOTH directions are nontrivial
2
$begingroup$
In Theorems in the form of "if and only if" such that the proof of one direction is extremely EASY to prove and the other one is extremely HARD, bof suggested the question in the title is more interesting, which motivates me to create this list. So my request is:
Theorems in the form of "if and only if" that the proofs of BOTH directions are nontrivial. The 'if and only if' formulation should be as natural as possible.
Thanks in advance.
soft-question big-list
asked Jan 11 at 7:56
YuiTo ChengYuiTo Cheng
1,9732633
$endgroup$
add a comment |
2
$begingroup$
In Theorems in the form of "if and only if" such that the proof of one direction is extremely EASY to prove and the other one is extremely HARD, bof suggested the question in the title is more interesting, which motivates me to create this list. So my request is:
Theorems in the form of "if and only if" that the proofs of BOTH directions are nontrivial. The 'if and only if' formulation should be as natural as possible.
Thanks in advance.
soft-question big-list
asked Jan 11 at 7:56
YuiTo ChengYuiTo Cheng
1,9732633
$endgroup$
1
$begingroup$
I suppose the set theorists can provide some good examples of the form "ZF + X is consistent iff ZF + Y is consistent". For example, ZFC + Souslin's hypothesis is consistent iff ZFC + Borel's conjecture is consistent; but this example is kind of artificial.
$endgroup$
– bof
Jan 11 at 9:05
$begingroup$
A potentially even simpler example is "X is equivalent to Y in this set theory", e.g. all the ZF equivalents of the axiom of choice. But it may be hard to meet the OP's standard for the proof being "nontrivial". For example, the proof AC is equivalent to Zorn's lemma isn't that long. Maybe two equivalents of AC should be compared, e.g. Kőnig's & Zermelo's theorems.
$endgroup$
– J.G.
Jan 13 at 8:30
$begingroup$
@YuiToCheng comment of this form are usually not productive and thus routinely removed. If you want further information on this in general terms please ask in chat (Math Mods' office) or on meta. Preferably the former.
$endgroup$
– quid♦
Jan 13 at 19:21
$begingroup$
@quid Is this moderator's responsibility, or a computer-based process?
$endgroup$
– YuiTo Cheng
Feb 17 at 6:07
$begingroup$
@YuiToCheng mostly the former based on community input. As said earlier if you want to discuss this on more detail, please, use the appropriate venue.
$endgroup$
– quid♦
Feb 17 at 13:22
add a comment |
2
2
2
3
$begingroup$
In Theorems in the form of "if and only if" such that the proof of one direction is extremely EASY to prove and the other one is extremely HARD, bof suggested the question in the title is more interesting, which motivates me to create this list. So my request is:
Theorems in the form of "if and only if" that the proofs of BOTH directions are nontrivial. The 'if and only if' formulation should be as natural as possible.
Thanks in advance.
soft-question big-list
asked Jan 11 at 7:56
YuiTo ChengYuiTo Cheng
1,9732633
$endgroup$
In Theorems in the form of "if and only if" such that the proof of one direction is extremely EASY to prove and the other one is extremely HARD, bof suggested the question in the title is more interesting, which motivates me to create this list. So my request is:
Theorems in the form of "if and only if" that the proofs of BOTH directions are nontrivial. The 'if and only if' formulation should be as natural as possible.
Thanks in advance.
soft-question big-list
soft-question big-list
asked Jan 11 at 7:56
YuiTo ChengYuiTo Cheng
1,9732633
asked Jan 11 at 7:56
YuiTo ChengYuiTo Cheng
1,9732633
edited Jan 11 at 12:55
YuiTo Cheng
asked Jan 11 at 7:56
YuiTo ChengYuiTo Cheng
1,9732633
asked Jan 11 at 7:56
YuiTo ChengYuiTo Cheng
1,9732633
asked Jan 11 at 7:56
YuiTo ChengYuiTo Cheng
1,9732633
1,9732633
1
$begingroup$
I suppose the set theorists can provide some good examples of the form "ZF + X is consistent iff ZF + Y is consistent". For example, ZFC + Souslin's hypothesis is consistent iff ZFC + Borel's conjecture is consistent; but this example is kind of artificial.
$endgroup$
– bof
Jan 11 at 9:05
$begingroup$
A potentially even simpler example is "X is equivalent to Y in this set theory", e.g. all the ZF equivalents of the axiom of choice. But it may be hard to meet the OP's standard for the proof being "nontrivial". For example, the proof AC is equivalent to Zorn's lemma isn't that long. Maybe two equivalents of AC should be compared, e.g. Kőnig's & Zermelo's theorems.
$endgroup$
– J.G.
Jan 13 at 8:30
$begingroup$
@YuiToCheng comment of this form are usually not productive and thus routinely removed. If you want further information on this in general terms please ask in chat (Math Mods' office) or on meta. Preferably the former.
$endgroup$
– quid♦
Jan 13 at 19:21
$begingroup$
@quid Is this moderator's responsibility, or a computer-based process?
$endgroup$
– YuiTo Cheng
Feb 17 at 6:07
$begingroup$
@YuiToCheng mostly the former based on community input. As said earlier if you want to discuss this on more detail, please, use the appropriate venue.
$endgroup$
– quid♦
Feb 17 at 13:22
add a comment |
1
$begingroup$
I suppose the set theorists can provide some good examples of the form "ZF + X is consistent iff ZF + Y is consistent". For example, ZFC + Souslin's hypothesis is consistent iff ZFC + Borel's conjecture is consistent; but this example is kind of artificial.
$endgroup$
– bof
Jan 11 at 9:05
$begingroup$
A potentially even simpler example is "X is equivalent to Y in this set theory", e.g. all the ZF equivalents of the axiom of choice. But it may be hard to meet the OP's standard for the proof being "nontrivial". For example, the proof AC is equivalent to Zorn's lemma isn't that long. Maybe two equivalents of AC should be compared, e.g. Kőnig's & Zermelo's theorems.
$endgroup$
– J.G.
Jan 13 at 8:30
$begingroup$
@YuiToCheng comment of this form are usually not productive and thus routinely removed. If you want further information on this in general terms please ask in chat (Math Mods' office) or on meta. Preferably the former.
$endgroup$
– quid♦
Jan 13 at 19:21
$begingroup$
@quid Is this moderator's responsibility, or a computer-based process?
$endgroup$
– YuiTo Cheng
Feb 17 at 6:07
$begingroup$
@YuiToCheng mostly the former based on community input. As said earlier if you want to discuss this on more detail, please, use the appropriate venue.
$endgroup$
– quid♦
Feb 17 at 13:22
1
1
$begingroup$
I suppose the set theorists can provide some good examples of the form "ZF + X is consistent iff ZF + Y is consistent". For example, ZFC + Souslin's hypothesis is consistent iff ZFC + Borel's conjecture is consistent; but this example is kind of artificial.
$endgroup$
– bof
Jan 11 at 9:05
$begingroup$
I suppose the set theorists can provide some good examples of the form "ZF + X is consistent iff ZF + Y is consistent". For example, ZFC + Souslin's hypothesis is consistent iff ZFC + Borel's conjecture is consistent; but this example is kind of artificial.
$endgroup$
– bof
Jan 11 at 9:05
$begingroup$
A potentially even simpler example is "X is equivalent to Y in this set theory", e.g. all the ZF equivalents of the axiom of choice. But it may be hard to meet the OP's standard for the proof being "nontrivial". For example, the proof AC is equivalent to Zorn's lemma isn't that long. Maybe two equivalents of AC should be compared, e.g. Kőnig's & Zermelo's theorems.
$endgroup$
– J.G.
Jan 13 at 8:30
$begingroup$
A potentially even simpler example is "X is equivalent to Y in this set theory", e.g. all the ZF equivalents of the axiom of choice. But it may be hard to meet the OP's standard for the proof being "nontrivial". For example, the proof AC is equivalent to Zorn's lemma isn't that long. Maybe two equivalents of AC should be compared, e.g. Kőnig's & Zermelo's theorems.
$endgroup$
– J.G.
Jan 13 at 8:30
$begingroup$
@YuiToCheng comment of this form are usually not productive and thus routinely removed. If you want further information on this in general terms please ask in chat (Math Mods' office) or on meta. Preferably the former.
$endgroup$
– quid♦
Jan 13 at 19:21
$begingroup$
@YuiToCheng comment of this form are usually not productive and thus routinely removed. If you want further information on this in general terms please ask in chat (Math Mods' office) or on meta. Preferably the former.
$endgroup$
– quid♦
Jan 13 at 19:21
$begingroup$
@quid Is this moderator's responsibility, or a computer-based process?
$endgroup$
– YuiTo Cheng
Feb 17 at 6:07
$begingroup$
@quid Is this moderator's responsibility, or a computer-based process?
$endgroup$
– YuiTo Cheng
Feb 17 at 6:07
$begingroup$
@YuiToCheng mostly the former based on community input. As said earlier if you want to discuss this on more detail, please, use the appropriate venue.
$endgroup$
– quid♦
Feb 17 at 13:22
$begingroup$
@YuiToCheng mostly the former based on community input. As said earlier if you want to discuss this on more detail, please, use the appropriate venue.
$endgroup$
– quid♦
Feb 17 at 13:22
add a comment |
0
active
oldest
votes
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
});
}
});
draft saved
draft discarded
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%2f3069590%2ftheorems-in-the-form-of-if-and-only-if-such-that-the-proofs-of-both-directions%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
draft saved
draft discarded
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.
draft saved
draft discarded
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%2f3069590%2ftheorems-in-the-form-of-if-and-only-if-such-that-the-proofs-of-both-directions%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
$begingroup$
I suppose the set theorists can provide some good examples of the form "ZF + X is consistent iff ZF + Y is consistent". For example, ZFC + Souslin's hypothesis is consistent iff ZFC + Borel's conjecture is consistent; but this example is kind of artificial.
$endgroup$
– bof
Jan 11 at 9:05
$begingroup$
A potentially even simpler example is "X is equivalent to Y in this set theory", e.g. all the ZF equivalents of the axiom of choice. But it may be hard to meet the OP's standard for the proof being "nontrivial". For example, the proof AC is equivalent to Zorn's lemma isn't that long. Maybe two equivalents of AC should be compared, e.g. Kőnig's & Zermelo's theorems.
$endgroup$
– J.G.
Jan 13 at 8:30
$begingroup$
@YuiToCheng comment of this form are usually not productive and thus routinely removed. If you want further information on this in general terms please ask in chat (Math Mods' office) or on meta. Preferably the former.
$endgroup$
– quid♦
Jan 13 at 19:21
$begingroup$
@quid Is this moderator's responsibility, or a computer-based process?
$endgroup$
– YuiTo Cheng
Feb 17 at 6:07
$begingroup$
@YuiToCheng mostly the former based on community input. As said earlier if you want to discuss this on more detail, please, use the appropriate venue.
$endgroup$
– quid♦
Feb 17 at 13:22