We know an example iff any exist
$begingroup$
Consider a statement of this form:
We don't know whether or not there exist any [X] with property [Y], but we do know that [some concrete instance/example of an X] has property [Y] iff any [X] has property [Y].
Is there a name for this sort of statement? When is it possible to (truthfully) make such a statement? Where have such statements appeared in math?
(The one statement I've heard that inspired this question is that we have a (completely impractical) algorithm that will solve any problem in NP, and we know that it will run in polynomial time iff P=NP.)
logic examples-counterexamples predicate-logic quantifiers
asked Dec 20 '18 at 17:20
Joseph SibleJoseph Sible
1495
$endgroup$
|
show 1 more comment
$begingroup$
Consider a statement of this form:
We don't know whether or not there exist any [X] with property [Y], but we do know that [some concrete instance/example of an X] has property [Y] iff any [X] has property [Y].
Is there a name for this sort of statement? When is it possible to (truthfully) make such a statement? Where have such statements appeared in math?
(The one statement I've heard that inspired this question is that we have a (completely impractical) algorithm that will solve any problem in NP, and we know that it will run in polynomial time iff P=NP.)
logic examples-counterexamples predicate-logic quantifiers
asked Dec 20 '18 at 17:20
Joseph SibleJoseph Sible
1495
$endgroup$
$begingroup$
Something like this might be called a "universal object" for property $Y$ in category theory. I don't believe the statement that inspired your question: can you give a reference for it, please.
$endgroup$
– Rob Arthan
Dec 21 '18 at 23:26
$begingroup$
@RobArthan I don't remember where I saw it in the first place, but here it is on Wikipedia.
$endgroup$
– Joseph Sible
Dec 22 '18 at 2:53
$begingroup$
Thanks for the link. You haven't stated it quite right: those algorithms solve particular NP-complete problems in a certain sense (and so they can be used to solve any other given NP-complete problem in that sense when composed with an appropriate reduction). Sorry if I sound a bit pedantic - I was just interested in the actual statement.
$endgroup$
– Rob Arthan
Dec 22 '18 at 18:23
$begingroup$
I'm a bit confused. Can you formally express the above statement using the language of predicate logic, e.g $exists x: Y(x)$, etc.
$endgroup$
– Dan Christensen
Dec 23 '18 at 15:50
$begingroup$
@DanChristensen I think $(exists x : Y(x)) implies Y(a)$ (where $a$ is some constant) is how I'd express that like that.
$endgroup$
– Joseph Sible
Dec 25 '18 at 0:55
|
show 1 more comment
$begingroup$
Consider a statement of this form:
We don't know whether or not there exist any [X] with property [Y], but we do know that [some concrete instance/example of an X] has property [Y] iff any [X] has property [Y].
Is there a name for this sort of statement? When is it possible to (truthfully) make such a statement? Where have such statements appeared in math?
(The one statement I've heard that inspired this question is that we have a (completely impractical) algorithm that will solve any problem in NP, and we know that it will run in polynomial time iff P=NP.)
logic examples-counterexamples predicate-logic quantifiers
asked Dec 20 '18 at 17:20
Joseph SibleJoseph Sible
1495
$endgroup$
Consider a statement of this form:
We don't know whether or not there exist any [X] with property [Y], but we do know that [some concrete instance/example of an X] has property [Y] iff any [X] has property [Y].
Is there a name for this sort of statement? When is it possible to (truthfully) make such a statement? Where have such statements appeared in math?
(The one statement I've heard that inspired this question is that we have a (completely impractical) algorithm that will solve any problem in NP, and we know that it will run in polynomial time iff P=NP.)
logic examples-counterexamples predicate-logic quantifiers
logic examples-counterexamples predicate-logic quantifiers
asked Dec 20 '18 at 17:20
Joseph SibleJoseph Sible
1495
asked Dec 20 '18 at 17:20
Joseph SibleJoseph Sible
1495
asked Dec 20 '18 at 17:20
Joseph SibleJoseph Sible
1495
asked Dec 20 '18 at 17:20
Joseph SibleJoseph Sible
1495
asked Dec 20 '18 at 17:20
Joseph SibleJoseph Sible
1495
1495
$begingroup$
Something like this might be called a "universal object" for property $Y$ in category theory. I don't believe the statement that inspired your question: can you give a reference for it, please.
$endgroup$
– Rob Arthan
Dec 21 '18 at 23:26
$begingroup$
@RobArthan I don't remember where I saw it in the first place, but here it is on Wikipedia.
$endgroup$
– Joseph Sible
Dec 22 '18 at 2:53
$begingroup$
Thanks for the link. You haven't stated it quite right: those algorithms solve particular NP-complete problems in a certain sense (and so they can be used to solve any other given NP-complete problem in that sense when composed with an appropriate reduction). Sorry if I sound a bit pedantic - I was just interested in the actual statement.
$endgroup$
– Rob Arthan
Dec 22 '18 at 18:23
$begingroup$
I'm a bit confused. Can you formally express the above statement using the language of predicate logic, e.g $exists x: Y(x)$, etc.
$endgroup$
– Dan Christensen
Dec 23 '18 at 15:50
$begingroup$
@DanChristensen I think $(exists x : Y(x)) implies Y(a)$ (where $a$ is some constant) is how I'd express that like that.
$endgroup$
– Joseph Sible
Dec 25 '18 at 0:55
|
show 1 more comment
$begingroup$
Something like this might be called a "universal object" for property $Y$ in category theory. I don't believe the statement that inspired your question: can you give a reference for it, please.
$endgroup$
– Rob Arthan
Dec 21 '18 at 23:26
$begingroup$
@RobArthan I don't remember where I saw it in the first place, but here it is on Wikipedia.
$endgroup$
– Joseph Sible
Dec 22 '18 at 2:53
$begingroup$
Thanks for the link. You haven't stated it quite right: those algorithms solve particular NP-complete problems in a certain sense (and so they can be used to solve any other given NP-complete problem in that sense when composed with an appropriate reduction). Sorry if I sound a bit pedantic - I was just interested in the actual statement.
$endgroup$
– Rob Arthan
Dec 22 '18 at 18:23
$begingroup$
I'm a bit confused. Can you formally express the above statement using the language of predicate logic, e.g $exists x: Y(x)$, etc.
$endgroup$
– Dan Christensen
Dec 23 '18 at 15:50
$begingroup$
@DanChristensen I think $(exists x : Y(x)) implies Y(a)$ (where $a$ is some constant) is how I'd express that like that.
$endgroup$
– Joseph Sible
Dec 25 '18 at 0:55
$begingroup$
Something like this might be called a "universal object" for property $Y$ in category theory. I don't believe the statement that inspired your question: can you give a reference for it, please.
$endgroup$
– Rob Arthan
Dec 21 '18 at 23:26
$begingroup$
Something like this might be called a "universal object" for property $Y$ in category theory. I don't believe the statement that inspired your question: can you give a reference for it, please.
$endgroup$
– Rob Arthan
Dec 21 '18 at 23:26
$begingroup$
@RobArthan I don't remember where I saw it in the first place, but here it is on Wikipedia.
$endgroup$
– Joseph Sible
Dec 22 '18 at 2:53
$begingroup$
@RobArthan I don't remember where I saw it in the first place, but here it is on Wikipedia.
$endgroup$
– Joseph Sible
Dec 22 '18 at 2:53
$begingroup$
Thanks for the link. You haven't stated it quite right: those algorithms solve particular NP-complete problems in a certain sense (and so they can be used to solve any other given NP-complete problem in that sense when composed with an appropriate reduction). Sorry if I sound a bit pedantic - I was just interested in the actual statement.
$endgroup$
– Rob Arthan
Dec 22 '18 at 18:23
$begingroup$
Thanks for the link. You haven't stated it quite right: those algorithms solve particular NP-complete problems in a certain sense (and so they can be used to solve any other given NP-complete problem in that sense when composed with an appropriate reduction). Sorry if I sound a bit pedantic - I was just interested in the actual statement.
$endgroup$
– Rob Arthan
Dec 22 '18 at 18:23
$begingroup$
I'm a bit confused. Can you formally express the above statement using the language of predicate logic, e.g $exists x: Y(x)$, etc.
$endgroup$
– Dan Christensen
Dec 23 '18 at 15:50
$begingroup$
I'm a bit confused. Can you formally express the above statement using the language of predicate logic, e.g $exists x: Y(x)$, etc.
$endgroup$
– Dan Christensen
Dec 23 '18 at 15:50
$begingroup$
@DanChristensen I think $(exists x : Y(x)) implies Y(a)$ (where $a$ is some constant) is how I'd express that like that.
$endgroup$
– Joseph Sible
Dec 25 '18 at 0:55
$begingroup$
@DanChristensen I think $(exists x : Y(x)) implies Y(a)$ (where $a$ is some constant) is how I'd express that like that.
$endgroup$
– Joseph Sible
Dec 25 '18 at 0:55
|
show 1 more 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
});
}
});
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%2f3047775%2fwe-know-an-example-iff-any-exist%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
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%2f3047775%2fwe-know-an-example-iff-any-exist%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$
Something like this might be called a "universal object" for property $Y$ in category theory. I don't believe the statement that inspired your question: can you give a reference for it, please.
$endgroup$
– Rob Arthan
Dec 21 '18 at 23:26
$begingroup$
@RobArthan I don't remember where I saw it in the first place, but here it is on Wikipedia.
$endgroup$
– Joseph Sible
Dec 22 '18 at 2:53
$begingroup$
Thanks for the link. You haven't stated it quite right: those algorithms solve particular NP-complete problems in a certain sense (and so they can be used to solve any other given NP-complete problem in that sense when composed with an appropriate reduction). Sorry if I sound a bit pedantic - I was just interested in the actual statement.
$endgroup$
– Rob Arthan
Dec 22 '18 at 18:23
$begingroup$
I'm a bit confused. Can you formally express the above statement using the language of predicate logic, e.g $exists x: Y(x)$, etc.
$endgroup$
– Dan Christensen
Dec 23 '18 at 15:50
$begingroup$
@DanChristensen I think $(exists x : Y(x)) implies Y(a)$ (where $a$ is some constant) is how I'd express that like that.
$endgroup$
– Joseph Sible
Dec 25 '18 at 0:55