Wikipedia:Reference desk/Archives/Mathematics/2009 October 10

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

October 10

Number Theory

What is the maximum integer that divides all numbers of the form p^4 - 1 where p can be any prime greater than 5? In how many ways can you solve this question?

Can we have evidence of you trying to solve this question please? Have you tried particular examples to limit the number and thern tried using modular arithmetic? Dmcq (talk) 12:09, 10 October 2009 (UTC)

This is not homework. Still I can solve it though through factorisation. Then I find prime factors of p - 1, p + 1 and find the answer. I still want to know whether there are other ways to do it, please. —Preceding unsigned comment added by 58.161.138.117 (talk) 12:22, 10 October 2009 (UTC)

So you mean this: "For any prime p>5, 2⁴ divides the number p⁴-1 = (p - 1)(p + 1)(p²+1), for all the three factors are even, and either the first or the second is divisible by 4. Either p - 1 or p + 1 is divisible by 3, since p is not. Finally, if neither p - 1 nor p + 1 is divisible by 5, then p is either 2 or 3 (mod 5), so p² + 1 is divisible by 5, and in any case 5 enters in the factorization too. Thus 240 divides all p⁴ - 1, and it is the maximum for (7⁴ - 1) /240 and (11⁴-1 )/240 are relatively prime". --84.221.80.207 (talk) 13:42, 10 October 2009 (UTC)

Yes. —Preceding unsigned comment added by 58.161.138.117 (talk) 14:30, 10 October 2009 (UTC)

Do the intuitionists agree that an equation of the form (x − a)(x − b) = 0 has two solutions only?

HOOTmag (talk) 18:32, 10 October 2009 (UTC)

They certainly would agree that it does not have a set of three different roots. The harder thing is to show that every solution is either equal to a, or is equal to b. I fear that would come down to how the real numbers themselves are treated. If a and b are not equal but also not separated, then it does not seem possible to prove intuitionistically that every root of the quadratic is equal to one of them or the other. But I could be wrong about that last point. — Carl (CBM · talk) 18:48, 10 October 2009 (UTC)

Since they certainly agree that every number not equal to zero has an inverse number, so they must agree that the product of two given numbers which are not equal to zero is not equal to zero, so they must agree that for every x not equal to a nor to b, (x-a)(x-b) is not equal to zero, hence Q.E.D, right? HOOTmag (talk) 19:39, 10 October 2009 (UTC)

In symbolic terms, you are arguing that from the assumption (x-a)(x-b)=0, you can prove

$\lnot (a\not =x\land b\not =x)$ (*)

I agree that seems fine intuitionistically. But $\lnot (a\not =x)$ does not imply that a=x intuitionistically (when a and x are real numbers), so (*) will not suffice for the thing we are trying to prove, namely that x=a or x=b. I am not a true expert in intuitionism, so there may be some alternative method of proof, but I don't see it myself.

Heuristically, if you could prove intuitionistically that (x-a)(x-b)=0 implies "x=a or x=b", this would mean that from the knowledge that x satisfies (x-a)(x-b)=0, you could effectively determine which one of a or b the number x is equal to. But if a and b are distinct real numbers that are not separated, I cannot see how such a decision could be possible. But this is just a heuristic argument. And, by changing what one means by "x=a", one might be able to work around this. — Carl (CBM · talk) 21:29, 10 October 2009 (UTC)

P.S. Note that if you add an apartness condition on a and b, then everything is fine. If a is apart from b, and (x-a)(x-b)=0, then (by the key "comparison property" of apartness), either x is apart from a or x is apart from b. If x is apart from a then (x-a) is apart from zero, so not equal to zero, in which case we get x-b = 0. Similarly if x is apart from b then x-a = 0. But when a is not apart from b, I do not see how to start the proof. When I say "separated" above it is a synonym for "apart". — Carl (CBM · talk) 21:35, 10 October 2009 (UTC)

Look, when I say that every equation of the form (x − a)(x − b) = 0 has two solutions only, I simply mean:

(1) For every x equal to a or to b: (x − a)(x − b) is equal to zero.

(2) For every x other than a,b: (x − a)(x − b) is not equal to zero.

The intuitionists surely accept (1). My question is about whether they accept (2). Apparently, they do, because they surely agree that the product of two given numbers which are not equal to zero is not equal to zero. Why? because they surely agree that the set of numbers we're talking about (e.g. the rational numbers, or the real numbers, etc.) constitutes a field (hence constitutes an Integral domain, which consequently has no Zero divisor), Right?

HOOTmag (talk) 23:09, 10 October 2009 (UTC)

Yes, they would accept that "if $c\not =a$ and $c\not =b$ then $(c-a)(c-b)\not =0$". But when you say "(x-a)(x-b) = 0 has only two solutions", I hear the stronger statement "if (c-a)(c-b) = 0 then c = a or c = b". So I am thinking of the contrapositive of the statement you seem to be thinking of. The statement I am thinking of, as far as I can tell, is not intuitionistically provable. — Carl (CBM · talk) 23:43, 10 October 2009 (UTC)

PS I think the reason I instantly headed for the contrapositive is that the thing you just said doesn't really make sense from an intuitionistic perspective. You said:

(1) For every x equal to a or to b: (x − a)(x − b) is equal to zero.

(2) For every x other than a,b: (x − a)(x − b) is not equal to zero.

But from an intuitionistic perspective there is no reason that every x must fall into one of these two categories. There are some x for which we cannot assert x = a, and simultaneously cannot assert $x\not =a$. So an intuitionist would not think that the thing you said actually means that there are only two solutions; it only means that there are only two solutions among those values of x the either equal one of a,b or else are not equal to a and not equal to b. — Carl (CBM · talk) 23:48, 10 October 2009 (UTC)

As to your first comment: Apparently, for every statements A,B,C which don't include any sign of negation nor of other connectors, if the statement: "If A then (B or C)" is regularly provable, then it is also intuitionistically provable, because the word "or" is interpreted by the intuitionists in a way "weaker" than how the other mathematicians interpret it (i.e. the intuitionistic "or" is the intuitionistic negation of the "and", which is a "weaker" negation).

As to your second comment, it's a matter of definition: What do I mean by "Only"? when I say to the intuitionists: "A if and only if B", I want them to interpret this: "(1) A if B; (2) not-A if not-B". Similary, when I say to them: "a and b are the only solutions", I want them to interpret this: "(1) a and b are solutions. (2) any number other than a,b is not a solution". Note that the way I define the word "Only" doesn't influence the way they define the word "Not".

HOOTmag (talk) 00:57, 11 October 2009 (UTC)

Even in classical mathematics, when I say, "1 and 2 are the only elements of the set A", I mean "1 ∈ A and 2 ∈ A and, for every c, if c ∈ A then c = 1 or c = 2". As I was saying, this simply involves a contrapositive compared to the statement you seem to think of. But the sentence you are now asking about is not what an intuitionist would mean by "an equation of the form (x − a)(x − b) = 0 has two solutions only", which was the question you originally asked. I do not believe an intuitionist would agree with that quoted sentence, nor would they agree that your later clarification is actually equivalent to it, because your later clarification does not rule out other solutions that are neither equal nor not-equal to a or to b, and so does not actually prove to an intuitionist that there are only two solutions. You are free to change your question, of course, but I was answering the original one.

The underlying point of asking whether intuitionists agree with a sentence is that you have to let them interpret that sentence the way that they usually would. For example, no intuitionist would agree that $\phi \leftrightarrow \lnot \lnot \phi$ is true in general, but they would always agree that $\phi \to \lnot \lnot \phi$ and $\lnot \phi \to \lnot \lnot \lnot \phi$. So the way you want them to interpet ↔ is simply not the way that they would interpret it.

As a side note, the intuitionistic negation of a sentence φ is the sentence $\phi \to \bot$, and $\phi \lor \psi$ is not intuitionistically equivalent to $((\phi \land \psi )\to \bot )\to \bot$ nor to $((\phi \to \bot )\land (\psi \to \bot ))\to \bot$. The intuitionistic "or" is usually considered stronger than the classical one, because an intuitionistic proof of an "or" statement must explicitly prove one of the two sides, unlike a classical proof, which does not need to show which of the two disjuncts is true. So the intuitionistic "or" is true in fewer cases. Of course I guess you could call this "weaker" but that is the opposite of the terminology in the literature. — Carl (CBM · talk) 01:29, 11 October 2009 (UTC)

No, I agree with you that any "Or" which is true in fewer cases is a "stronger" Or. I just define the "Or" as a negation of "And", the intuitionists being free to define the negation as they like. Similarly, I don't define: "A is equivalent to B" as I define: "A if and only if B", because when I say: "A is equivalent to B", I mean: "(1) A if B; (2) B if A", whereas when I say: "A if and only if B", I mean: (1) A if B; (2) Not-A if Not-B". Here again, the intuitionists are free to define the negation as they like.

Back to my original question: when I say: "a and b are the only solutions of the equation", I simply mean: "(1) a and b solve the equation"; (2) any number other than a,b does not solve the equation". I'm sure that every intuitionist would accept both (1) and (2), with respect to my original equation.

Back to the way you had understood my question: To sum up your opinion, the statement "if (c − a)(c − b) = 0 then c = a or c = b", is not intuitionistically provable. Here I let you interpret (intuitionistically) the "Or" - as you wish, and now let me "sharpen" your opinion summed up above: Assume we have a set such that: (1) a and b belong to the set; (2) any element other than a,b doesn't belong to the set (note that in "my" language I would say that the set contains a and b "only"). Now, your opinion would be as follows: the intuitionists are not convinced (i.e. can't prove) that any element belonging to the set is a or b. Right?

HOOTmag (talk) 19:19, 11 October 2009 (UTC)

Yes. — Carl (CBM · talk) 19:30, 11 October 2009 (UTC)

I guess your opinion will not change if I ask you again about any finite set (and not only about a "pair"-set). According to that, the Axiom of Choice wouldn't have been ituitionistically-provable from ZF, even if this axiom had been limited to finite sets only; Right? HOOTmag (talk) 20:08, 11 October 2009 (UTC)

The same problem happens for any finite set. Given that $A=\{a_{1},\ldots ,a_{k}\}$ is a set of real numbers and that $c\in A$, one cannot prove that, in general, $(c=a_{1})\lor \cdots \lor (c=a_{k})$. Further, one cannot prove that there is any natural number r such that there is a bijection from A to {1,2,3,...,r}. — Carl (CBM · talk) 20:47, 11 October 2009 (UTC)

Again, how about intuitionistically-proving the Axiom of Chioce from ZF, had this axiom been limited to finite sets only? HOOTmag (talk) 21:12, 11 October 2009 (UTC)

The axiom of choice has a complex relationship with intuitionistic logic. In intuitionistic type theory, the full axiom of choice is intuitionistically valid. In some intuitionistic systems of set theory, however, the axiom of choice implies the law of the excluded middle, and the proof only uses the axiom of choice for a two element set each of whose elements has (in the classical sense) at most two elements. See Diaconescu's_theorem and the much more thorough SEP entry.

So I don't want to make any general claims about the axiom of choice or variants thereof without first establishing exactly what underlying axioms are in play. I was hoping that my comment about bijections went far enough in the spirit of AC. — Carl (CBM · talk) 22:32, 11 October 2009 (UTC)

You most definitely can prove intuitionistically that $A=\{a_{1},\ldots ,a_{k}\}$ and $c\in A$ implies $(c=a_{1})\lor \cdots \lor (c=a_{k})$, in fact, this is pretty much the definition of $\{a_{1},\ldots ,a_{k}\}$. — Emil J. 11:08, 12 October 2009 (UTC)

Sure, if $x\in \{a_{1},\ldots ,a_{k}\}$ is an abbreviation for $(c=a_{1})\lor \cdots \lor (c=a_{k})$ then you can prove the latter from the former. I was using e.g. the notation {a,b} to stand for $\{c\in \mathbb {R} \mid (c-a)(c-b)=0\}$. In any case I was talking about generalizations of sets of the latter form. I'll watch my notation in the future. The second claim, about the lack of a bijection, applies to both the case I was thinking of and the one you were thinking of. — Carl (CBM · talk) 11:36, 12 October 2009 (UTC)

So, in your opinion, it's not intuitionistically-provable that $\{c\in \mathbb {R} \mid (c-a)(c-b)=0\}$ is: $\{\ a,b\}\$, Right?

P.S. this has been my original question, or - at least - what I've meant. HOOTmag (talk) 17:13, 12 October 2009 (UTC)

Yes. — Carl (CBM · talk) 17:47, 12 October 2009 (UTC)

Can the intuitionists ever prove the equality of any two sets, one of which is defined by the "{}" with the "|", the other one being defined by the "{}" without the "|"? HOOTmag (talk) 19:25, 12 October 2009 (UTC)

Of course. $\{a,b\}=\{x\mid x=a\lor x=b\}$, or for less trivial example, $\{x\in \mathbb {N} \mid x<3\}=\{0,1,2\}$. — Emil J. 09:01, 13 October 2009 (UTC)

Generally, the zero is not considered as belonging to N. Anyways, in Carl's opinion, it's not intuitionistically-provable that $\{c\in \mathbb {N} \mid (c-1)(c-2)=0\}$ is: $\{c\in \mathbb {N} \mid c<3\}\$, Right? HOOTmag (talk) 10:43, 13 October 2009 (UTC)

(outdent) Zero is a natural number, under any non-obfuscated definition of natural number.

Anyway, I can't speak for Carl, but it is intuitionistically provable that $\{c\in \mathbb {N} \mid (c-1)(c-2)=0\}=\{1,2\}=\{c\in \mathbb {N} \mid 0<c<3\}$, and even $\{c\in {\overline {\mathbb {Q} }}\mid (c-1)(c-2)=0\}=\{1,2\}$, while it apparently is not provable that $\{c\in \mathbb {R} \mid (c-1)(c-2)\}=\{1,2\}$. The difference stems from the fact that reals do not have decidable equality. — Emil J. 11:31, 13 October 2009 (UTC)

Hang on. It is actually provable that $\{c\in \mathbb {R} \mid (c-1)(c-2)\}=\{1,2\}$, and more generally, it is provable that a < b implies $\{c\in \mathbb {R} \mid (c-a)(c-b)\}=\{a,b\}$ (due to the intuitionistically provable fact that $a<b\to a<c\lor c<b$). What is apparently not provable is the statement $\forall a,b\in \mathbb {R} \,\{c\in \mathbb {R} \mid (c-a)(c-b)\}=\{a,b\}$, since we do not know that a and b are apart or equal. — Emil J. 11:37, 13 October 2009 (UTC)

Yes. This is what I was trying to say in my posts dated 21:29, 10 October 2009 and 21:35, 10 October 2009. I need to be more clear somehow. — Carl (CBM · talk) 13:46, 13 October 2009 (UTC)

Your posts were perfectly clear, this was just me not paying enough attention. — Emil J. 13:55, 13 October 2009 (UTC)

There is a distinction between $\mathbb {N}$ and $\mathbb {R}$ in intuitionistic mathematics that is not present in classical mathematics. In classical mathematics, one freely identifies the set of natural numbers with its image inside the real numbers. In intuitionistic mathematics, the types matter. The natural numbers are usually treated as a decidable set: for any two natural numbers a,b, either a=b or $a\not =b$. This is not true for real numbers; it is possible for two real numbers to be neither equal not not-equal, and moreover it is possible for them to be not-equal but have no positive distance between them. Only when a and b are real numbers with that latter property do I see any difficulty in proving that $\{c\in \mathbb {R} \mid (c-a)(c-b)=0\}$ is the same set of real numbers as $\{a,b\}$. — Carl (CBM · talk) 11:43, 13 October 2009 (UTC)

Here's a sort of counterexample to the original statement $\forall a,b,c\in \mathbb {R} \,((c-a)(c-b)=0\to c=a\lor c=b)$. First, observe that it is equivalent to $\forall a,b\in \mathbb {R} \,(ab=0\to a=0\lor b=0)$. For definiteness, I'll assume a definition of reals as sequences {a_n}_n∈N of rationals such that |a_n − a_m| ≤ 2⁻ⁿ + 2^−m, with a = b iff |a_n − b_n| ≤ 2¹⁻ⁿ. Let P be a decidable predicate on natural numbers (meaning $\forall n\in \mathbb {N} \,(P(n)\lor \neg P(n))$), and define by induction

$a_{0}=0,\qquad a_{n+1}={\begin{cases}2^{-n},&a_{n}=0{\text{ and }}\neg P(n),\\a_{n},&{\text{otherwise.}}\end{cases}}$

It is easy to see that a = {a_n} is a real number, and a = 0 implies $\forall n\in \mathbb {N} \,P(n)$. Likewise, let Q be another decidable predicate on natural numbers, and define

$b_{0}=0,\qquad b_{n+1}={\begin{cases}2^{-n},&b_{n}=0{\text{ and }}\neg Q(n),\\b_{n},&{\text{otherwise.}}\end{cases}}$

Again, b = {b_n} is a real, and b = 0 implies $\forall n\,Q(n)$. On the other hand, $\forall n,m\,(P(n)\lor Q(m))$ implies $\forall n\,(\forall k\leq n\,P(k)\lor \forall k\leq n\,Q(k))$, which easily gives ab = 0. All in all, if we could intuitionistically prove $\forall a,b\in \mathbb {R} \,(ab=0\to a=0\lor b=0)$, then we could also intuitionistically prove

${\forall n\,(P(n)\lor \neg P(n))\land \forall n\,(Q(n)\lor \neg Q(n))\land \forall n,m\,(P(n)\lor Q(m))\to \forall n\,P(n)\lor \forall n\,Q(n),}$

and we can't do that. — Emil J. 12:34, 13 October 2009 (UTC)

And to make it even more concrete: let T be whatever formal theory we want the statement to be formalized in. Assume that T is recursively axiomatizable, has the disjunction property, proves $\forall a,b\in \mathbb {R} \,(ab=0\to a=0\lor b=0)$, and supports the argument above as well as a modicum of arithmetic, we will show that T is inconsistent.

By Gödel's diagonal lemma, we can find two arithmetical formulas P(x), Q(x) such that P(n) is equivalent to the negation of

"n is a code of a T-proof of $\forall n\in \mathbb {N} \,P(n)$ and there is no m < n which is a code of a T-proof of $\forall n\in \mathbb {N} \,Q(n)$",

and Q(n) is equivalent to the same thing with P and Q reversed. Clearly P and Q are decidable (in both the recursion-theoretic and intuitionistic meanings). Since no number can code proofs of two distinct formulas, we can prove $\forall n,m\in \mathbb {N} \,(P(n)\lor Q(m))$. By the reasoning above, T can also prove $\forall n\in \mathbb {N} \,P(n)\lor \forall n\in \mathbb {N} \,Q(n)$, and since it has the disjunction property, it proves $\forall n\in \mathbb {N} \,P(n)$ or $\forall n\in \mathbb {N} \,Q(n)$. In metatheory, we can find the smallest m which is a T-proof of either of these two sentences. If m is a proof of $\forall n\in \mathbb {N} \,P(n)$, then ¬P(m) is true. Since ¬P(m) is a decidable (in the recursion-theoretic sense) property, it is also provable, hence T is inconsistent. The other case is symmetric. — Emil J. 13:52, 13 October 2009 (UTC)