Is it possible to constructively prove that every quaternion has a square root?Did Gödel prove that the Ramified Theory of Types collapses at $omega_1$?Bishop quote stating that axiom of choice is constructively validIn what ways is ZF (without Choice) “somewhat constructive”Is every set smaller than a regular cardinal, constructively?
Is it possible to constructively prove that every quaternion has a square root?
Did Gödel prove that the Ramified Theory of Types collapses at $omega_1$?Bishop quote stating that axiom of choice is constructively validIn what ways is ZF (without Choice) “somewhat constructive”Is every set smaller than a regular cardinal, constructively?
$begingroup$
Is it possible to constructively prove that every $q in mathbb H$ has some $r$ such that $r^2 = q$? The difficulty here is that $q$ might be negative, in which case there might be "too many" values of $r$. Namely, $r$ could then equal any vector quaternion of magnitude $sqrtq$. The presence of this seemingly severe discontinuity suggests that there can't be a way to constructively prove that every quaternion has a square root.
The variety of constructivism can be as strong as possible. So any Choice principle, or Markov's Principle, or Bar Induction, is allowed.
My thoughts were to do some kind of reduction to $LPO$ or $LLPO$ or $LEM$. But I don't see how.
The way to find a square-root classically is as follows: If $q = w + xi + yj + zk$ is not a scalar quaternion, then it lies on a unique "complex plane". This is due to the fact that a vector quaternion (of the form $xi + yj + zk$) always squares to $-(x^2 + y^2 + z^2)$, which is a negative scalar. The problem then reduces to finding the square root of a complex number. The difficulty is exactly in the case when $x=y=z=0$.
constructive-mathematics reverse-math computable-analysis
asked 8 hours ago
jkabrgjkabrg
2141 silver badge9 bronze badges
$endgroup$
|
show 13 more comments
$begingroup$
Is it possible to constructively prove that every $q in mathbb H$ has some $r$ such that $r^2 = q$? The difficulty here is that $q$ might be negative, in which case there might be "too many" values of $r$. Namely, $r$ could then equal any vector quaternion of magnitude $sqrtq$. The presence of this seemingly severe discontinuity suggests that there can't be a way to constructively prove that every quaternion has a square root.
The variety of constructivism can be as strong as possible. So any Choice principle, or Markov's Principle, or Bar Induction, is allowed.
My thoughts were to do some kind of reduction to $LPO$ or $LLPO$ or $LEM$. But I don't see how.
The way to find a square-root classically is as follows: If $q = w + xi + yj + zk$ is not a scalar quaternion, then it lies on a unique "complex plane". This is due to the fact that a vector quaternion (of the form $xi + yj + zk$) always squares to $-(x^2 + y^2 + z^2)$, which is a negative scalar. The problem then reduces to finding the square root of a complex number. The difficulty is exactly in the case when $x=y=z=0$.
constructive-mathematics reverse-math computable-analysis
asked 8 hours ago
jkabrgjkabrg
2141 silver badge9 bronze badges
$endgroup$
1
$begingroup$
@WillSawin That isn't enough. It is possible to prove that every complex number has a square root in spite of the fact that there is no continuous function that gives the square root
$endgroup$
– jkabrg
7 hours ago
1
$begingroup$
Proving that "every quaternion has a square root" is not the same as "having the square root function".
$endgroup$
– Andrej Bauer
7 hours ago
2
$begingroup$
Showing that every complex number has a square root is already non-constructive, so in particular it is non-constructive for quaternion as well. This is due to the fact that it is not possible to chose the square root of $z in mathbbC$ continuously near every point (it do not work around $0$). One can show constructively that every Quaternion $q$ such that $N(q)>0$ has a square root though.
$endgroup$
– Simon Henry
7 hours ago
1
$begingroup$
@SimonHenry: the fundamental theorem of algebra holds constructively, dx.doi.org/10.2140/pjm.2000.196.213 In particular, the polynomial $z^2 - c = 0$ has a root, for all $c in mathbbC$.
$endgroup$
– Andrej Bauer
7 hours ago
1
$begingroup$
@CarloBeenakker asked whether the proof he linked to was constructive. My point was that already the first step, namely assuming every quaternion has the form $a + b u$ for unit $u$ is problematics, constructively. That's why we're discussing constructive math.
$endgroup$
– Andrej Bauer
6 hours ago
|
show 13 more comments
$begingroup$
Is it possible to constructively prove that every $q in mathbb H$ has some $r$ such that $r^2 = q$? The difficulty here is that $q$ might be negative, in which case there might be "too many" values of $r$. Namely, $r$ could then equal any vector quaternion of magnitude $sqrtq$. The presence of this seemingly severe discontinuity suggests that there can't be a way to constructively prove that every quaternion has a square root.
The variety of constructivism can be as strong as possible. So any Choice principle, or Markov's Principle, or Bar Induction, is allowed.
My thoughts were to do some kind of reduction to $LPO$ or $LLPO$ or $LEM$. But I don't see how.
The way to find a square-root classically is as follows: If $q = w + xi + yj + zk$ is not a scalar quaternion, then it lies on a unique "complex plane". This is due to the fact that a vector quaternion (of the form $xi + yj + zk$) always squares to $-(x^2 + y^2 + z^2)$, which is a negative scalar. The problem then reduces to finding the square root of a complex number. The difficulty is exactly in the case when $x=y=z=0$.
constructive-mathematics reverse-math computable-analysis
asked 8 hours ago
jkabrgjkabrg
2141 silver badge9 bronze badges
$endgroup$
Is it possible to constructively prove that every $q in mathbb H$ has some $r$ such that $r^2 = q$? The difficulty here is that $q$ might be negative, in which case there might be "too many" values of $r$. Namely, $r$ could then equal any vector quaternion of magnitude $sqrtq$. The presence of this seemingly severe discontinuity suggests that there can't be a way to constructively prove that every quaternion has a square root.
The variety of constructivism can be as strong as possible. So any Choice principle, or Markov's Principle, or Bar Induction, is allowed.
My thoughts were to do some kind of reduction to $LPO$ or $LLPO$ or $LEM$. But I don't see how.
The way to find a square-root classically is as follows: If $q = w + xi + yj + zk$ is not a scalar quaternion, then it lies on a unique "complex plane". This is due to the fact that a vector quaternion (of the form $xi + yj + zk$) always squares to $-(x^2 + y^2 + z^2)$, which is a negative scalar. The problem then reduces to finding the square root of a complex number. The difficulty is exactly in the case when $x=y=z=0$.
constructive-mathematics reverse-math computable-analysis
constructive-mathematics reverse-math computable-analysis
asked 8 hours ago
jkabrgjkabrg
2141 silver badge9 bronze badges
asked 8 hours ago
jkabrgjkabrg
2141 silver badge9 bronze badges
edited 6 hours ago
jkabrg
asked 8 hours ago
jkabrgjkabrg
2141 silver badge9 bronze badges
asked 8 hours ago
jkabrgjkabrg
2141 silver badge9 bronze badges
asked 8 hours ago
jkabrgjkabrg
2141 silver badge9 bronze badges
2141 silver badge9 bronze badges
1
$begingroup$
@WillSawin That isn't enough. It is possible to prove that every complex number has a square root in spite of the fact that there is no continuous function that gives the square root
$endgroup$
– jkabrg
7 hours ago
1
$begingroup$
Proving that "every quaternion has a square root" is not the same as "having the square root function".
$endgroup$
– Andrej Bauer
7 hours ago
2
$begingroup$
Showing that every complex number has a square root is already non-constructive, so in particular it is non-constructive for quaternion as well. This is due to the fact that it is not possible to chose the square root of $z in mathbbC$ continuously near every point (it do not work around $0$). One can show constructively that every Quaternion $q$ such that $N(q)>0$ has a square root though.
$endgroup$
– Simon Henry
7 hours ago
1
$begingroup$
@SimonHenry: the fundamental theorem of algebra holds constructively, dx.doi.org/10.2140/pjm.2000.196.213 In particular, the polynomial $z^2 - c = 0$ has a root, for all $c in mathbbC$.
$endgroup$
– Andrej Bauer
7 hours ago
1
$begingroup$
@CarloBeenakker asked whether the proof he linked to was constructive. My point was that already the first step, namely assuming every quaternion has the form $a + b u$ for unit $u$ is problematics, constructively. That's why we're discussing constructive math.
$endgroup$
– Andrej Bauer
6 hours ago
|
show 13 more comments
1
$begingroup$
@WillSawin That isn't enough. It is possible to prove that every complex number has a square root in spite of the fact that there is no continuous function that gives the square root
$endgroup$
– jkabrg
7 hours ago
1
$begingroup$
Proving that "every quaternion has a square root" is not the same as "having the square root function".
$endgroup$
– Andrej Bauer
7 hours ago
2
$begingroup$
Showing that every complex number has a square root is already non-constructive, so in particular it is non-constructive for quaternion as well. This is due to the fact that it is not possible to chose the square root of $z in mathbbC$ continuously near every point (it do not work around $0$). One can show constructively that every Quaternion $q$ such that $N(q)>0$ has a square root though.
$endgroup$
– Simon Henry
7 hours ago
1
$begingroup$
@SimonHenry: the fundamental theorem of algebra holds constructively, dx.doi.org/10.2140/pjm.2000.196.213 In particular, the polynomial $z^2 - c = 0$ has a root, for all $c in mathbbC$.
$endgroup$
– Andrej Bauer
7 hours ago
1
$begingroup$
@CarloBeenakker asked whether the proof he linked to was constructive. My point was that already the first step, namely assuming every quaternion has the form $a + b u$ for unit $u$ is problematics, constructively. That's why we're discussing constructive math.
$endgroup$
– Andrej Bauer
6 hours ago
1
1
$begingroup$
@WillSawin That isn't enough. It is possible to prove that every complex number has a square root in spite of the fact that there is no continuous function that gives the square root
$endgroup$
– jkabrg
7 hours ago
$begingroup$
@WillSawin That isn't enough. It is possible to prove that every complex number has a square root in spite of the fact that there is no continuous function that gives the square root
$endgroup$
– jkabrg
7 hours ago
1
1
$begingroup$
Proving that "every quaternion has a square root" is not the same as "having the square root function".
$endgroup$
– Andrej Bauer
7 hours ago
$begingroup$
Proving that "every quaternion has a square root" is not the same as "having the square root function".
$endgroup$
– Andrej Bauer
7 hours ago
2
2
$begingroup$
Showing that every complex number has a square root is already non-constructive, so in particular it is non-constructive for quaternion as well. This is due to the fact that it is not possible to chose the square root of $z in mathbbC$ continuously near every point (it do not work around $0$). One can show constructively that every Quaternion $q$ such that $N(q)>0$ has a square root though.
$endgroup$
– Simon Henry
7 hours ago
$begingroup$
Showing that every complex number has a square root is already non-constructive, so in particular it is non-constructive for quaternion as well. This is due to the fact that it is not possible to chose the square root of $z in mathbbC$ continuously near every point (it do not work around $0$). One can show constructively that every Quaternion $q$ such that $N(q)>0$ has a square root though.
$endgroup$
– Simon Henry
7 hours ago
1
1
$begingroup$
@SimonHenry: the fundamental theorem of algebra holds constructively, dx.doi.org/10.2140/pjm.2000.196.213 In particular, the polynomial $z^2 - c = 0$ has a root, for all $c in mathbbC$.
$endgroup$
– Andrej Bauer
7 hours ago
$begingroup$
@SimonHenry: the fundamental theorem of algebra holds constructively, dx.doi.org/10.2140/pjm.2000.196.213 In particular, the polynomial $z^2 - c = 0$ has a root, for all $c in mathbbC$.
$endgroup$
– Andrej Bauer
7 hours ago
1
1
$begingroup$
@CarloBeenakker asked whether the proof he linked to was constructive. My point was that already the first step, namely assuming every quaternion has the form $a + b u$ for unit $u$ is problematics, constructively. That's why we're discussing constructive math.
$endgroup$
– Andrej Bauer
6 hours ago
$begingroup$
@CarloBeenakker asked whether the proof he linked to was constructive. My point was that already the first step, namely assuming every quaternion has the form $a + b u$ for unit $u$ is problematics, constructively. That's why we're discussing constructive math.
$endgroup$
– Andrej Bauer
6 hours ago
|
show 13 more comments
2 Answers
2
active
oldest
votes
$begingroup$
The operation is not Type 2 computable. The argument is similar to how the set $mathbb R$ is not computably equivalent to its decimal representation. This latter statement is called the tablemaker's dilemma. Constructivists and Type 2 computability theorists make use of a redundant "nega-binary" representation of real numbers instead.
Let $q=-1 + 0i + 0j + 0k$. Assume the T2TM (Type 2 Turing Machine) outputs a quaternion $r$. This $r$ is a vector. Now observe that the machine must have read only finitely many digits of the nega-binary representation of $q$. Displace $q$ by some vector $v$ which is not parallel to $r$, where the vector $v$ has magnitude smaller than $2^-n$, where $n$ is the number of nega-binary digits the machine has read. The machine must give the same output because the prefix of the new input is the same, but this output is wrong.
To demonstrate that two quaternions very close to $-1$ may have very different square roots: Consider $-1 + epsilon i$: Its square roots are $pm (i + fracepsilon2)+ o(epsilon)$. Now consider $-1 + delta j$: Its square roots are $pm (j + fracdelta2)+ o(delta)$. Now the distance between each of each of these sets is at least $sqrt2$, which is much greater than zero. If after reading $n$ digits of $q = -1.0 + 0i + 0j + 0k$, the machine decides to output the first digits of $0 + 1i + 0j + 0k$, then one can play a trick on it by changing $q$ to $q' = -1 + 0i + 10^-2nj + 0k$. Those first digits of the output will then be completely wrong.
This T2TM argument is probably a valid Type 1 argument. In which case, it provides a convincing proof that quaternion square-root is uncomputable, and therefore can not be proved constructively.
It would be nice to see a "purer" proof that reduces to LPO or some other such principle, but I can't think of one. [edit] See below.
answered 7 hours ago
jkabrgjkabrg
2141 silver badge9 bronze badges
$endgroup$
$begingroup$
Presumably you want T2TM to output an approximation to a quaternion $r$, and to take $v$ to be not parallel to any quaternion approximated by this approximation, which is easy to do? Or is this implicit in what you do?
$endgroup$
– Will Sawin
7 hours ago
$begingroup$
@WillSawin Taking a vector not parallel to $r$ is easy, in the sense that it's computable. That is indeed what I meant
$endgroup$
– jkabrg
7 hours ago
$begingroup$
@WillSawin Constructively, the existence of non-parallel vector can be proved using just Weak Countable Choice. That's the formal logic angle
$endgroup$
– jkabrg
7 hours ago
$begingroup$
I'll improve the write-up later
$endgroup$
– jkabrg
7 hours ago
1
$begingroup$
Here's a simpler example: for each real we can compute an integer larger than it (but depending on the representations), even though we cannot compute an integer larger than the real in a way that respects equality of reals.
$endgroup$
– Andrej Bauer
7 hours ago
|
show 10 more comments
$begingroup$
Reduction to LLPO (Lesser Limited Principle of Omniscience).
The statement LLPO is the following (from Wikipedia): For any sequence a0, a1, ... such that each ai is either 0 or 1, and such that at most one ai is nonzero, the following holds: either a2i = 0 for all i, or a2i+1 = 0 for all i, where a2i and a2i+1 are entries with even and odd index respectively.
This is considered a quintessentially non-constructive claim.
The claim that every quaternion has a square root implies LLPO.
Consider a sequence $(p_n)_n geq 1 in 0,1$, with the property that at most one element of the sequence is equal to $1$. Construct a sequence of quaternions $q_n = -1 + ileft(1 - sum_1^inftyfrac1 - p_2n2^nright) + jleft(1 - sum_1^inftyfrac1 - p_2n+12^nright)$. The sequence clearly converges to some $q_infty$. Now we assume that we can get an $r$ such that $r^2 = q_infty$. Consider the angle $theta$ between $r$ and $i$ (considered as 4d vectors with the standard inner product), and likewise consider the angle $phi$ between $r$ and $j$. Either $theta > arctan(1/2)$ or $phi > arctan(1/2)$, as these two open regions cover all the non-zero quaternions. If $theta > arctan(1/2)$ then we conclude that all $a_2n=0$. If $phi > arctan(1/2)$ then we conclude that all $a_2n+1=0$. This is exactly LLPO.
answered 1 hour ago
jkabrgjkabrg
2141 silver badge9 bronze badges
$endgroup$
add a comment
|
Your Answer
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "504"
;
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/4.0/"u003ecc by-sa 4.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%2fmathoverflow.net%2fquestions%2f342041%2fis-it-possible-to-constructively-prove-that-every-quaternion-has-a-square-root%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The operation is not Type 2 computable. The argument is similar to how the set $mathbb R$ is not computably equivalent to its decimal representation. This latter statement is called the tablemaker's dilemma. Constructivists and Type 2 computability theorists make use of a redundant "nega-binary" representation of real numbers instead.
Let $q=-1 + 0i + 0j + 0k$. Assume the T2TM (Type 2 Turing Machine) outputs a quaternion $r$. This $r$ is a vector. Now observe that the machine must have read only finitely many digits of the nega-binary representation of $q$. Displace $q$ by some vector $v$ which is not parallel to $r$, where the vector $v$ has magnitude smaller than $2^-n$, where $n$ is the number of nega-binary digits the machine has read. The machine must give the same output because the prefix of the new input is the same, but this output is wrong.
To demonstrate that two quaternions very close to $-1$ may have very different square roots: Consider $-1 + epsilon i$: Its square roots are $pm (i + fracepsilon2)+ o(epsilon)$. Now consider $-1 + delta j$: Its square roots are $pm (j + fracdelta2)+ o(delta)$. Now the distance between each of each of these sets is at least $sqrt2$, which is much greater than zero. If after reading $n$ digits of $q = -1.0 + 0i + 0j + 0k$, the machine decides to output the first digits of $0 + 1i + 0j + 0k$, then one can play a trick on it by changing $q$ to $q' = -1 + 0i + 10^-2nj + 0k$. Those first digits of the output will then be completely wrong.
This T2TM argument is probably a valid Type 1 argument. In which case, it provides a convincing proof that quaternion square-root is uncomputable, and therefore can not be proved constructively.
It would be nice to see a "purer" proof that reduces to LPO or some other such principle, but I can't think of one. [edit] See below.
answered 7 hours ago
jkabrgjkabrg
2141 silver badge9 bronze badges
$endgroup$
$begingroup$
Presumably you want T2TM to output an approximation to a quaternion $r$, and to take $v$ to be not parallel to any quaternion approximated by this approximation, which is easy to do? Or is this implicit in what you do?
$endgroup$
– Will Sawin
7 hours ago
$begingroup$
@WillSawin Taking a vector not parallel to $r$ is easy, in the sense that it's computable. That is indeed what I meant
$endgroup$
– jkabrg
7 hours ago
$begingroup$
@WillSawin Constructively, the existence of non-parallel vector can be proved using just Weak Countable Choice. That's the formal logic angle
$endgroup$
– jkabrg
7 hours ago
$begingroup$
I'll improve the write-up later
$endgroup$
– jkabrg
7 hours ago
1
$begingroup$
Here's a simpler example: for each real we can compute an integer larger than it (but depending on the representations), even though we cannot compute an integer larger than the real in a way that respects equality of reals.
$endgroup$
– Andrej Bauer
7 hours ago
|
show 10 more comments
$begingroup$
The operation is not Type 2 computable. The argument is similar to how the set $mathbb R$ is not computably equivalent to its decimal representation. This latter statement is called the tablemaker's dilemma. Constructivists and Type 2 computability theorists make use of a redundant "nega-binary" representation of real numbers instead.
Let $q=-1 + 0i + 0j + 0k$. Assume the T2TM (Type 2 Turing Machine) outputs a quaternion $r$. This $r$ is a vector. Now observe that the machine must have read only finitely many digits of the nega-binary representation of $q$. Displace $q$ by some vector $v$ which is not parallel to $r$, where the vector $v$ has magnitude smaller than $2^-n$, where $n$ is the number of nega-binary digits the machine has read. The machine must give the same output because the prefix of the new input is the same, but this output is wrong.
To demonstrate that two quaternions very close to $-1$ may have very different square roots: Consider $-1 + epsilon i$: Its square roots are $pm (i + fracepsilon2)+ o(epsilon)$. Now consider $-1 + delta j$: Its square roots are $pm (j + fracdelta2)+ o(delta)$. Now the distance between each of each of these sets is at least $sqrt2$, which is much greater than zero. If after reading $n$ digits of $q = -1.0 + 0i + 0j + 0k$, the machine decides to output the first digits of $0 + 1i + 0j + 0k$, then one can play a trick on it by changing $q$ to $q' = -1 + 0i + 10^-2nj + 0k$. Those first digits of the output will then be completely wrong.
This T2TM argument is probably a valid Type 1 argument. In which case, it provides a convincing proof that quaternion square-root is uncomputable, and therefore can not be proved constructively.
It would be nice to see a "purer" proof that reduces to LPO or some other such principle, but I can't think of one. [edit] See below.
answered 7 hours ago
jkabrgjkabrg
2141 silver badge9 bronze badges
$endgroup$
$begingroup$
Presumably you want T2TM to output an approximation to a quaternion $r$, and to take $v$ to be not parallel to any quaternion approximated by this approximation, which is easy to do? Or is this implicit in what you do?
$endgroup$
– Will Sawin
7 hours ago
$begingroup$
@WillSawin Taking a vector not parallel to $r$ is easy, in the sense that it's computable. That is indeed what I meant
$endgroup$
– jkabrg
7 hours ago
$begingroup$
@WillSawin Constructively, the existence of non-parallel vector can be proved using just Weak Countable Choice. That's the formal logic angle
$endgroup$
– jkabrg
7 hours ago
$begingroup$
I'll improve the write-up later
$endgroup$
– jkabrg
7 hours ago
1
$begingroup$
Here's a simpler example: for each real we can compute an integer larger than it (but depending on the representations), even though we cannot compute an integer larger than the real in a way that respects equality of reals.
$endgroup$
– Andrej Bauer
7 hours ago
|
show 10 more comments
$begingroup$
The operation is not Type 2 computable. The argument is similar to how the set $mathbb R$ is not computably equivalent to its decimal representation. This latter statement is called the tablemaker's dilemma. Constructivists and Type 2 computability theorists make use of a redundant "nega-binary" representation of real numbers instead.
Let $q=-1 + 0i + 0j + 0k$. Assume the T2TM (Type 2 Turing Machine) outputs a quaternion $r$. This $r$ is a vector. Now observe that the machine must have read only finitely many digits of the nega-binary representation of $q$. Displace $q$ by some vector $v$ which is not parallel to $r$, where the vector $v$ has magnitude smaller than $2^-n$, where $n$ is the number of nega-binary digits the machine has read. The machine must give the same output because the prefix of the new input is the same, but this output is wrong.
To demonstrate that two quaternions very close to $-1$ may have very different square roots: Consider $-1 + epsilon i$: Its square roots are $pm (i + fracepsilon2)+ o(epsilon)$. Now consider $-1 + delta j$: Its square roots are $pm (j + fracdelta2)+ o(delta)$. Now the distance between each of each of these sets is at least $sqrt2$, which is much greater than zero. If after reading $n$ digits of $q = -1.0 + 0i + 0j + 0k$, the machine decides to output the first digits of $0 + 1i + 0j + 0k$, then one can play a trick on it by changing $q$ to $q' = -1 + 0i + 10^-2nj + 0k$. Those first digits of the output will then be completely wrong.
This T2TM argument is probably a valid Type 1 argument. In which case, it provides a convincing proof that quaternion square-root is uncomputable, and therefore can not be proved constructively.
It would be nice to see a "purer" proof that reduces to LPO or some other such principle, but I can't think of one. [edit] See below.
answered 7 hours ago
jkabrgjkabrg
2141 silver badge9 bronze badges
$endgroup$
The operation is not Type 2 computable. The argument is similar to how the set $mathbb R$ is not computably equivalent to its decimal representation. This latter statement is called the tablemaker's dilemma. Constructivists and Type 2 computability theorists make use of a redundant "nega-binary" representation of real numbers instead.
Let $q=-1 + 0i + 0j + 0k$. Assume the T2TM (Type 2 Turing Machine) outputs a quaternion $r$. This $r$ is a vector. Now observe that the machine must have read only finitely many digits of the nega-binary representation of $q$. Displace $q$ by some vector $v$ which is not parallel to $r$, where the vector $v$ has magnitude smaller than $2^-n$, where $n$ is the number of nega-binary digits the machine has read. The machine must give the same output because the prefix of the new input is the same, but this output is wrong.
To demonstrate that two quaternions very close to $-1$ may have very different square roots: Consider $-1 + epsilon i$: Its square roots are $pm (i + fracepsilon2)+ o(epsilon)$. Now consider $-1 + delta j$: Its square roots are $pm (j + fracdelta2)+ o(delta)$. Now the distance between each of each of these sets is at least $sqrt2$, which is much greater than zero. If after reading $n$ digits of $q = -1.0 + 0i + 0j + 0k$, the machine decides to output the first digits of $0 + 1i + 0j + 0k$, then one can play a trick on it by changing $q$ to $q' = -1 + 0i + 10^-2nj + 0k$. Those first digits of the output will then be completely wrong.
This T2TM argument is probably a valid Type 1 argument. In which case, it provides a convincing proof that quaternion square-root is uncomputable, and therefore can not be proved constructively.
It would be nice to see a "purer" proof that reduces to LPO or some other such principle, but I can't think of one. [edit] See below.
answered 7 hours ago
jkabrgjkabrg
2141 silver badge9 bronze badges
edited 1 hour ago
answered 7 hours ago
jkabrgjkabrg
2141 silver badge9 bronze badges
answered 7 hours ago
jkabrgjkabrg
2141 silver badge9 bronze badges
answered 7 hours ago
jkabrgjkabrg
2141 silver badge9 bronze badges
2141 silver badge9 bronze badges
$begingroup$
Presumably you want T2TM to output an approximation to a quaternion $r$, and to take $v$ to be not parallel to any quaternion approximated by this approximation, which is easy to do? Or is this implicit in what you do?
$endgroup$
– Will Sawin
7 hours ago
$begingroup$
@WillSawin Taking a vector not parallel to $r$ is easy, in the sense that it's computable. That is indeed what I meant
$endgroup$
– jkabrg
7 hours ago
$begingroup$
@WillSawin Constructively, the existence of non-parallel vector can be proved using just Weak Countable Choice. That's the formal logic angle
$endgroup$
– jkabrg
7 hours ago
$begingroup$
I'll improve the write-up later
$endgroup$
– jkabrg
7 hours ago
1
$begingroup$
Here's a simpler example: for each real we can compute an integer larger than it (but depending on the representations), even though we cannot compute an integer larger than the real in a way that respects equality of reals.
$endgroup$
– Andrej Bauer
7 hours ago
|
show 10 more comments
$begingroup$
Presumably you want T2TM to output an approximation to a quaternion $r$, and to take $v$ to be not parallel to any quaternion approximated by this approximation, which is easy to do? Or is this implicit in what you do?
$endgroup$
– Will Sawin
7 hours ago
$begingroup$
@WillSawin Taking a vector not parallel to $r$ is easy, in the sense that it's computable. That is indeed what I meant
$endgroup$
– jkabrg
7 hours ago
$begingroup$
@WillSawin Constructively, the existence of non-parallel vector can be proved using just Weak Countable Choice. That's the formal logic angle
$endgroup$
– jkabrg
7 hours ago
$begingroup$
I'll improve the write-up later
$endgroup$
– jkabrg
7 hours ago
1
$begingroup$
Here's a simpler example: for each real we can compute an integer larger than it (but depending on the representations), even though we cannot compute an integer larger than the real in a way that respects equality of reals.
$endgroup$
– Andrej Bauer
7 hours ago
$begingroup$
Presumably you want T2TM to output an approximation to a quaternion $r$, and to take $v$ to be not parallel to any quaternion approximated by this approximation, which is easy to do? Or is this implicit in what you do?
$endgroup$
– Will Sawin
7 hours ago
$begingroup$
Presumably you want T2TM to output an approximation to a quaternion $r$, and to take $v$ to be not parallel to any quaternion approximated by this approximation, which is easy to do? Or is this implicit in what you do?
$endgroup$
– Will Sawin
7 hours ago
$begingroup$
@WillSawin Taking a vector not parallel to $r$ is easy, in the sense that it's computable. That is indeed what I meant
$endgroup$
– jkabrg
7 hours ago
$begingroup$
@WillSawin Taking a vector not parallel to $r$ is easy, in the sense that it's computable. That is indeed what I meant
$endgroup$
– jkabrg
7 hours ago
$begingroup$
@WillSawin Constructively, the existence of non-parallel vector can be proved using just Weak Countable Choice. That's the formal logic angle
$endgroup$
– jkabrg
7 hours ago
$begingroup$
@WillSawin Constructively, the existence of non-parallel vector can be proved using just Weak Countable Choice. That's the formal logic angle
$endgroup$
– jkabrg
7 hours ago
$begingroup$
I'll improve the write-up later
$endgroup$
– jkabrg
7 hours ago
$begingroup$
I'll improve the write-up later
$endgroup$
– jkabrg
7 hours ago
1
1
$begingroup$
Here's a simpler example: for each real we can compute an integer larger than it (but depending on the representations), even though we cannot compute an integer larger than the real in a way that respects equality of reals.
$endgroup$
– Andrej Bauer
7 hours ago
$begingroup$
Here's a simpler example: for each real we can compute an integer larger than it (but depending on the representations), even though we cannot compute an integer larger than the real in a way that respects equality of reals.
$endgroup$
– Andrej Bauer
7 hours ago
|
show 10 more comments
$begingroup$
Reduction to LLPO (Lesser Limited Principle of Omniscience).
The statement LLPO is the following (from Wikipedia): For any sequence a0, a1, ... such that each ai is either 0 or 1, and such that at most one ai is nonzero, the following holds: either a2i = 0 for all i, or a2i+1 = 0 for all i, where a2i and a2i+1 are entries with even and odd index respectively.
This is considered a quintessentially non-constructive claim.
The claim that every quaternion has a square root implies LLPO.
Consider a sequence $(p_n)_n geq 1 in 0,1$, with the property that at most one element of the sequence is equal to $1$. Construct a sequence of quaternions $q_n = -1 + ileft(1 - sum_1^inftyfrac1 - p_2n2^nright) + jleft(1 - sum_1^inftyfrac1 - p_2n+12^nright)$. The sequence clearly converges to some $q_infty$. Now we assume that we can get an $r$ such that $r^2 = q_infty$. Consider the angle $theta$ between $r$ and $i$ (considered as 4d vectors with the standard inner product), and likewise consider the angle $phi$ between $r$ and $j$. Either $theta > arctan(1/2)$ or $phi > arctan(1/2)$, as these two open regions cover all the non-zero quaternions. If $theta > arctan(1/2)$ then we conclude that all $a_2n=0$. If $phi > arctan(1/2)$ then we conclude that all $a_2n+1=0$. This is exactly LLPO.
answered 1 hour ago
jkabrgjkabrg
2141 silver badge9 bronze badges
$endgroup$
add a comment
|
$begingroup$
Reduction to LLPO (Lesser Limited Principle of Omniscience).
The statement LLPO is the following (from Wikipedia): For any sequence a0, a1, ... such that each ai is either 0 or 1, and such that at most one ai is nonzero, the following holds: either a2i = 0 for all i, or a2i+1 = 0 for all i, where a2i and a2i+1 are entries with even and odd index respectively.
This is considered a quintessentially non-constructive claim.
The claim that every quaternion has a square root implies LLPO.
Consider a sequence $(p_n)_n geq 1 in 0,1$, with the property that at most one element of the sequence is equal to $1$. Construct a sequence of quaternions $q_n = -1 + ileft(1 - sum_1^inftyfrac1 - p_2n2^nright) + jleft(1 - sum_1^inftyfrac1 - p_2n+12^nright)$. The sequence clearly converges to some $q_infty$. Now we assume that we can get an $r$ such that $r^2 = q_infty$. Consider the angle $theta$ between $r$ and $i$ (considered as 4d vectors with the standard inner product), and likewise consider the angle $phi$ between $r$ and $j$. Either $theta > arctan(1/2)$ or $phi > arctan(1/2)$, as these two open regions cover all the non-zero quaternions. If $theta > arctan(1/2)$ then we conclude that all $a_2n=0$. If $phi > arctan(1/2)$ then we conclude that all $a_2n+1=0$. This is exactly LLPO.
answered 1 hour ago
jkabrgjkabrg
2141 silver badge9 bronze badges
$endgroup$
add a comment
|
$begingroup$
Reduction to LLPO (Lesser Limited Principle of Omniscience).
The statement LLPO is the following (from Wikipedia): For any sequence a0, a1, ... such that each ai is either 0 or 1, and such that at most one ai is nonzero, the following holds: either a2i = 0 for all i, or a2i+1 = 0 for all i, where a2i and a2i+1 are entries with even and odd index respectively.
This is considered a quintessentially non-constructive claim.
The claim that every quaternion has a square root implies LLPO.
Consider a sequence $(p_n)_n geq 1 in 0,1$, with the property that at most one element of the sequence is equal to $1$. Construct a sequence of quaternions $q_n = -1 + ileft(1 - sum_1^inftyfrac1 - p_2n2^nright) + jleft(1 - sum_1^inftyfrac1 - p_2n+12^nright)$. The sequence clearly converges to some $q_infty$. Now we assume that we can get an $r$ such that $r^2 = q_infty$. Consider the angle $theta$ between $r$ and $i$ (considered as 4d vectors with the standard inner product), and likewise consider the angle $phi$ between $r$ and $j$. Either $theta > arctan(1/2)$ or $phi > arctan(1/2)$, as these two open regions cover all the non-zero quaternions. If $theta > arctan(1/2)$ then we conclude that all $a_2n=0$. If $phi > arctan(1/2)$ then we conclude that all $a_2n+1=0$. This is exactly LLPO.
answered 1 hour ago
jkabrgjkabrg
2141 silver badge9 bronze badges
$endgroup$
Reduction to LLPO (Lesser Limited Principle of Omniscience).
The statement LLPO is the following (from Wikipedia): For any sequence a0, a1, ... such that each ai is either 0 or 1, and such that at most one ai is nonzero, the following holds: either a2i = 0 for all i, or a2i+1 = 0 for all i, where a2i and a2i+1 are entries with even and odd index respectively.
This is considered a quintessentially non-constructive claim.
The claim that every quaternion has a square root implies LLPO.
Consider a sequence $(p_n)_n geq 1 in 0,1$, with the property that at most one element of the sequence is equal to $1$. Construct a sequence of quaternions $q_n = -1 + ileft(1 - sum_1^inftyfrac1 - p_2n2^nright) + jleft(1 - sum_1^inftyfrac1 - p_2n+12^nright)$. The sequence clearly converges to some $q_infty$. Now we assume that we can get an $r$ such that $r^2 = q_infty$. Consider the angle $theta$ between $r$ and $i$ (considered as 4d vectors with the standard inner product), and likewise consider the angle $phi$ between $r$ and $j$. Either $theta > arctan(1/2)$ or $phi > arctan(1/2)$, as these two open regions cover all the non-zero quaternions. If $theta > arctan(1/2)$ then we conclude that all $a_2n=0$. If $phi > arctan(1/2)$ then we conclude that all $a_2n+1=0$. This is exactly LLPO.
answered 1 hour ago
jkabrgjkabrg
2141 silver badge9 bronze badges
edited 33 mins ago
answered 1 hour ago
jkabrgjkabrg
2141 silver badge9 bronze badges
answered 1 hour ago
jkabrgjkabrg
2141 silver badge9 bronze badges
answered 1 hour ago
jkabrgjkabrg
2141 silver badge9 bronze badges
2141 silver badge9 bronze badges
add a comment
|
add a comment
|
Thanks for contributing an answer to MathOverflow!
- 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%2fmathoverflow.net%2fquestions%2f342041%2fis-it-possible-to-constructively-prove-that-every-quaternion-has-a-square-root%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$
@WillSawin That isn't enough. It is possible to prove that every complex number has a square root in spite of the fact that there is no continuous function that gives the square root
$endgroup$
– jkabrg
7 hours ago
1
$begingroup$
Proving that "every quaternion has a square root" is not the same as "having the square root function".
$endgroup$
– Andrej Bauer
7 hours ago
2
$begingroup$
Showing that every complex number has a square root is already non-constructive, so in particular it is non-constructive for quaternion as well. This is due to the fact that it is not possible to chose the square root of $z in mathbbC$ continuously near every point (it do not work around $0$). One can show constructively that every Quaternion $q$ such that $N(q)>0$ has a square root though.
$endgroup$
– Simon Henry
7 hours ago
1
$begingroup$
@SimonHenry: the fundamental theorem of algebra holds constructively, dx.doi.org/10.2140/pjm.2000.196.213 In particular, the polynomial $z^2 - c = 0$ has a root, for all $c in mathbbC$.
$endgroup$
– Andrej Bauer
7 hours ago
1
$begingroup$
@CarloBeenakker asked whether the proof he linked to was constructive. My point was that already the first step, namely assuming every quaternion has the form $a + b u$ for unit $u$ is problematics, constructively. That's why we're discussing constructive math.
$endgroup$
– Andrej Bauer
6 hours ago