Wikipedia:Reference desk/Archives/Mathematics/2016 August 1

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.

August 1

Homomorphism

A (right R-)module homomorphism is a map f : M → N that is additive (f(x + y) = f(x) + f(y)) and preserves scalar multiplication (f(xr) = f(x)r).

Consider a more general case where the base rings are not identified, that is to say, given a ring homomorphism θ : R → S and a homomorphism f : M → N that is additive and preserves scalar multiplication in a semilinear sense: f(xr) = f(x)θ(r), where, M is a right R-module and N is a right S-module. Is there a name for this beast? I see that on vector spaces it is called a semilinear map (though that article specifies an anti-automorphism, I've seen several references that generalize it to a field homomorphism). —Quondum 00:57, 1 August 2016 (UTC)

See Change of rings. These are R-module morphisms between R-modules M ... and ... S-modules N with "restriction of scalars"/ "scalars restricted to" R, or alternatively, by the adjunction described in that article, S-module morphisms between a beefed up R-module obtained through "extension of scalars" (= "tensoring the R-module M by S") .. and ... an S-module N.

[1] & [2] are similar questions. Someone answers there "So, in my opinion, there is no point in introducing that notion of homomorphism because it can be reduced to the usual one using modules over the same ring." - following those refs, people would surely understand if you used words like "pullback" or probably "module morphism over a ring homomorphism." But was thinking I had seen a name for these guys & according to Synopsis of material from EGA Chapter 0 (Vol. I) §1–4 it was where I suspected- naming them "di-homomorphisms from (R, M) to (S, N)".John Z (talk) 04:43, 1 August 2016 (UTC)

Thanks – that really helps me think about it. I had not understood the point about an S-module inherently having an R-module structure if there exists a homomorphism R → S; N simply becomes a right R-S-bimodule. Some of the terminology is Greek to me, but it does allow one to use the existing concept of module homomorphism, which is a big win. One just has to remember that a bimodule has two different scalar multiplications. The di-homomorphism idea is neat, but I can see it not being popular if there is an alternative.

This presumably applies to semilinear maps with different base rings too. That is to say, we would define a semilinear map M → N by defining a new scalar multiplication for N by R, and the "twist" (the homomorphism R → S) is then built into the definition of this multiplication. It kind of suggests the question: Is a semilinear map between R-modules R-linear or not? This approach says that it is; we just need to remember that we need to specify which of the scalar multiplications we are using with N. —Quondum 06:15, 1 August 2016 (UTC)

Squares cross-number

I'm unsure if this would be better in Maths or in Computing, I chose Maths.

Imagine a cross-word grid filled with numbers (here-in-after cross-number), where the constraints on filling the grid in are (a) All numbers are integer squares (b) No leading zeros (c) all numbers unique (but not all digits unique).

I have two questions and would be happy with either an answer to the question or a suggestion as to how to find out the answer.

(1) What is the smallest grid that has a unique solution. Obviously can't be symmetric about the NW/SE axis.

  3     1
1 6   3 6 fails because of the reflection.

8 1     1 6
  6 4     4 9 has at least two solutions and so is not unique.

(2) What is the smallest grid that has a solution using all 10 digits? (I have no examples.)

-- SGBailey (talk) 11:28, 1 August 2016 (UTC)

Not sure if you will accept this but if your grid looks like this

+--+--+
|  |  |
+==+--+
|  |  |
+--+--+

Then there is only one solution. This is probably not what you were thinking of but some styles of crossword/cross number use a similar technique, usually by making the border bolder.--JohnBlackburne^words_deeds 12:25, 1 August 2016 (UTC)

In other words 81 top across, 16 right down, 36 bottom across and the bold border prevents 83 from being an entry. I was not thinking of explicit barricades like that, whilst they may be useful, I'd still like an answer to the original question as I meant it (whether expressed clearly or not.) -- SGBailey (talk) 13:09, 1 August 2016 (UTC)

• (edit conflict) Just asking for clarification: are single-digit fillings allowed to not be squared (i.e. other than 0, 1, 4, 9) ? If not, the second grid is "single-solution" 16/49 as the "8" in the 81/64 is not a square (and I think no other solution can be found); and the first one has no solution (since 49/49 and 16/16 are forbidden by the rules). Tigraan^{Click here to contact me} 12:32, 1 August 2016 (UTC)

Single digit numbers don't matter - too restricting. In the same way single letter words don't matter/count in a cross-word. -- SGBailey (talk) 13:09, 1 August 2016 (UTC)

I'm guessing the smallest unique is both of

8 1      8
  6 4    1 6
    9      4 9 

in which the two grids are different shapes. There may be other 5 cell grids with a 3 digit across and a couple of 2 digit downs or something. -- SGBailey (talk) 13:13, 1 August 2016 (UTC)

Using 3 digit squares, you can get:

8 4 1
1 9 6

Which is not minimal, but is rather pleasing MChesterMC (talk) 08:47, 2 August 2016 (UTC)

A trivial answer for (2), there are several pandigital square numbers. This OEIS sequence contains all 87. I suspect it would also be easy to find 10-cell grids using 7+ digit squares with no repeating digits (hanging 2 or 3 digit squares off them to complete the set). You can also see that no 10-cell grid is possible without at least one 4 digit square (since leading zeros are forbidden, and 3 digit squares with a zero all contain 2 zeroes). MChesterMC (talk) 15:50, 2 August 2016 (UTC)

Slow day at work - here's a non-trivial one which uses all 10 digits:

      5 4 7 6
      3
      2
1 0 8 9

MChesterMC (talk) 13:34, 3 August 2016 (UTC)

Thanks all -- SGBailey (talk) 14:46, 5 August 2016 (UTC)

Semilinear is not linear?

Following on from my question #Homomorphism above, could I have an opinion on the statement from the article Semilinear map:

Every linear map is semilinear, but the converse is not true in general.

It seems that (in Bourbaki style) one would say that if there exists a semilinear map with respect to a base ring R from module V to module W, then W has an induced R-module structure, and that a semilinear map with respect to a base ring R is accordingly an R-module homomorphism. Should the quoted statement therefore not be heavily qualified? —Quondum 16:03, 1 August 2016 (UTC)

Are there simple propositions, written in Peano language, but undecidable in Peano system?

By "simple" proposition, I mean any short proposition, e.g. less than twenty signs (and likewise). I think I have found one, but I wonder if my question is trivial and obvious. HOTmag (talk) 22:15, 1 August 2016 (UTC)

Have a look at Goodstein's theorem which is one where it is quite easy to see it is true, and there are links from that to other ones. Dmcq (talk) 23:03, 1 August 2016 (UTC)

I had already been quite aware of this theorem, and of the other theorems linked there (You can see what I had already written seven years ago on Talk:Paris–Harrington theorem), but please notice that Goodstein's theorem is not that "simple": That's why I added the comment about what I meant by "simple" (Really, after I'd explained I'd meant a statement composed of less than twenty signs [in Peano language] - I also added "and likewise", but please notice that one needs very much beyond "twenty" signs for writing Goodstein theorem, so that's not "likewise").

Anyways, our article about Goodstein theorem states that it "was the third example of a true statement that is unprovable in Peano arithmetic, after " G and ε0-induction (Btw, what is written ibid. is slightly incorrect, because the other statements meant - are G and ε0-induction - rather than "Gödel's incompleteness theorem and Gerhard Gentzen's 1943 direct proof of the unprovability of ε0-induction in Peano arithmetic " as indicated ibid.), but I think I have found a much shorter statement undecidable in Peano arithmetic, as I have already indicated in my first post: Actually, my short statement is composed of fifteen signs [in Peano language] only. HOTmag (talk) 02:42, 2 August 2016 (UTC)

People answering here are not expected to research your background. I answered the question that way because it is about as close as I know to an answer to the question. Also the answer I gave indicates it is very unlikely that what you are talking about already exists. Anything like that would make the news and there would be a link to an article about it. No the question is not simple and obvious. Dmcq (talk) 09:14, 2 August 2016 (UTC)

I think, that the claim (disproved two thousand years ago by the ancient Greeks) which claims (about the natural numbers with one as the smallest number) - that the square root of two is rational - i.e. that ∃x∃y(2⋅x⋅x=y⋅y), is undecidable in Peano Arithmetic.

Why do I think so? because - not only can't this claim be proved in Peano Arithmetic (of course) - but I think this claim can't be disproved in Peano Arithmetic either, because I think that for disproving this claim one needs to lean - on the fact that every fraction (a/b) equals an irreducible fraction (c/d) - i.e. on the fact that ∀(a,b)∃(c,d)( (a⋅d=b⋅c) ∧ ∀(r,s,t)( ((r⋅s=c)∧(r⋅t=d)) → (r=1)) ), but I think the latter fact is unprovable in Peano Arithmetic.

Why do I think the latter fact is unprovable in Peano Arithmetic? Because I think the latter fact can only be proved by leaning on the fact, that every natural number - greater than one and not being a prime - is a finite product of prime numbers; However, I think that, not only can't the last fact be proved in Peano Arithmetic, but the last fact can't be phrased in Peano language either.

Am I right? HOTmag (talk) 11:56, 2 August 2016 (UTC)

We can show the number of prime factors is finite within the first order theory by showing that it is less than or equal to the original number. Going up through the numbers to that limit and counting off prime factors as one goes is something that can then be done using the induction axiom. This shows that the number of prime factors of a number is a natural number and in fact is less than or equal to the original number. Dmcq (talk) 12:48, 2 August 2016 (UTC)

I suspect you are wrong, because the "original" natural number you're talking about - is not given in advance as a "finite" number. Please note that Peano Arithmetic does not exclude infinite natural numbers. For more details see our article: Non-standard model of arithmetic. HOTmag (talk) 14:23, 2 August 2016 (UTC)

Well if you want to do that fine - but if one defines finite as meaning the result is always a natural number then that argument will prove that the number of prime factors of any natural number is a natural number even in a non-standard Peano arithmetic. And one can also prove that every fraction is equal to an irreducible fraction. That is because the law of induction is an axiom. It is true even if there are strange non-standard natural numbers. By the way Goodstein's theorem is not necessarily true in a non-standard Peano arithmetic. Dmcq (talk) 16:36, 2 August 2016 (UTC)

I've always agreed that the number of prime factors of any natural number is a natural number. I've just claimed, that not every natural number must be "finite" - in the sense needed for proving (in Peano Arithmetic) that every fraction is equal to an irreducible fraction. Anyways, I still wonder how you're going to use the law of induction, for proving that every given fraction is equal to an irreducible fraction - when the given fraction is a ratio between two different infinite natural numbers. HOTmag (talk) 17:02, 2 August 2016 (UTC)

As you said the axioms don't talk about finite. There is no such thing as infinite either. The concept is not needed within Peano Arithmetic nor does it mean anything. The natural numbers behave to all intents and purposes as if they are normal standard natural numbers even when you've got a non-standard model. The induction axiom ensures that. Proving every fraction can be reduced to an irreducible one is quite easy. Just do the same as I said for counting the prime factors but use as a limit the denominator. Then we can set up function which gives p/q but with any common factor greater than 1 but less than or equal to count removed and then count up to q. Te induction axiom will then say that the fraction is equal to a fraction with no common factor greater than 1 and less than or equal to the denominator. You are getting confused thinking the induction will never actually reach that limit but the induction axiom is an axiom and there is no arguing with the axioms. Dmcq (talk) 20:28, 2 August 2016 (UTC)

Of course the axiom of induction does not care about whether the natural numbers are finite or infinite. It's true any way, and I've always agreed to that. However, I'm a bit frustrated you don't get my point. So, to make the whole process shorter, let's focus on how you are using the axiom of induction for proving that every fraction is equal to an irreducible fraction.

So, the axiom of induction (in its strong form you're probably talking about) states the following, for any predicate φ:

• If both:

1) φ(1), and

2) For every n, if every k < n satisfies φ(k), then φ(n),

Then every n satisfies φ(n).

I'd like to know how you prove, that a given fraction p/q - is equal to an irreducible fraction (Just bear in mind that p,q are natural numbers, whether finite or not). So please tell me both - what is exactly your φ - regarding the fraction p/q, and how you prove #2 - regarding this specific φ.

HOTmag (talk) 07:42, 3 August 2016 (UTC)

φ(n) is the statement that there do not exist a and b with $0<b<n$ such that $aq=pb$. However, we will not be applying induction as you expect---rather, we will be applying the contrapositive. This is the standard method of showing that a set has a least element; in this case, the set is the complement of φ.

Clearly φ(1) holds and $\phi (q+1)$ fails. So #2 fails, meaning there is some n with $\phi (n)\wedge \neg \phi (n+1)$. Then it must be that there is an a with $aq=pn$, meaning $p/q=a/n$, and this is irreducible, as if it were otherwise it would contradict $\phi (n)$.--2406:E006:178C:1:180:CB7A:4A8E:F1F (talk) 11:17, 3 August 2016 (UTC)

It seems like you've skipped too many necessary logical steps, so I find your argument invalid - at least from the formal point of view, whereas from the intuitive point of view - I suspect I couldn't get it - probably because of the formal errors.

Here are a few examples:

Quotation:"So #2 fails, meaning there is some n with $\phi (n)\wedge \neg \phi (n+1)$."

Please notice that the fact of #2 failing, means there is some n and some k ≤ n (e.g. k = 1), with $\phi (k)\wedge \neg \phi (n+1)$, but this does not mean that k = n as you're trying to say.

Quotation: "Then it must be that there is an a with $aq=pn$".

That's trivial, e.g. a = p, n = q.

Quotation: "and this is irreducible".

I suspect you're wrong. Check: a = n = p = q = 2.

HOTmag (talk) 12:48, 3 August 2016 (UTC)

I've elided a few details, but nothing of consequence. None of the complaints you list are errors. Addressing them in order: 1) That is not how you negate an implication. 2) n is already given. You do not have the freedom to set it equal to q. 3) You suspect wrongly. It is irreducible for the reason given.--2406:E006:178C:1:180:CB7A:4A8E:F1F (talk) 13:02, 3 August 2016 (UTC)

Now I got it, thank you! So I would rephrase your proof, in a better way (in my opinion), as following:

Let, p,q be two natural numbers. So there exists a natural number $a$ satisfying $p/q=a/q$. So, by the well-ordering principle, being equivalent to [a consequence of] the Axiom of induction, there must exist the smallest natural number $n$ for which there exists a natural number $a$ satisfying: $p/q=a/n$. Hence $a/n$, which is equal to $p/q$, is irreducible. QED.

Anyways, I suspect you didn't have to mention that: "Clearly φ(1) holds...So...there is some n with $\phi (n)$...", did you? HOTmag (talk) 14:12, 3 August 2016 (UTC)

I may be missing something, but it seems to me that there is something wrong in this logic. I don't see that the well-ordering principle is logically equivalent to the axiom of induction, assuming a first order system, which admits nonstandard models. Consider a nonstandard model in which there is an element that cannot be reached by repeated application of the 'S' operator, let's say ω. Think of the model as being the set N ∪ (ω + Z), which seems to satisfy the axioms. The outcome is that if φ(0) ∧ ¬φ(ω) is true, it would be incorrect to conclude that ∃k(φ(k) ∧ ¬φ(k + 1)). —Quondum 00:27, 4 August 2016 (UTC)

@Quondum, please note that the well-ordering principle does not say that ∃k(φ(k) ∧ ¬φ(k + 1)), but rather that φ(n) for some n and ¬φ(k) for every k<n. HOTmag (talk) 11:24, 4 August 2016 (UTC)

Induction is logically equivalent to well-ordering for sufficiently rich classes of sets. E.g., induction for all sets is equivalent to well-ordering for all sets; induction for first-order definable sets is equivalent to well-ordering for first-order definable sets. Well-ordering for arbitrary sets fails in nonstandard models of arithmetic, but so does arbitrary induction: let φ be the predicate which holds of precisely the standard elements. Then φ(0), and φ(n) implies φ(n+1), yet φ does not hold for all elements.

Here's the general proof: suppose X is a nonempty set that you wish to prove has a least element. Let φ(n) be the relation: there is no $k<n$ with $k\in X$. Then φ(0) holds vacuously, yet φ does not hold for all numbers, as we assumed that X was nonempty. So the other hypothesis of induction must fail, meaning there is an n with $\phi (n)\wedge \neg \phi (n+1)$. The only number less than n+1 but not less than n is n, so we can conclude that $n\in X$. But also n is the least element of X, by $\phi (n)$.--2406:E006:178C:1:149C:C636:A25:6A5B (talk) 05:28, 4 August 2016 (UTC)

Well-ordering works like that for natural numbers because of the induction axiom, but I was avoiding it and just using the axiom of induction straightforwardly as for general well-ordering there may be elements with no immediate predecessor and one has to prove the induction for limit elements. Dmcq (talk) 10:06, 4 August 2016 (UTC)

Well-ordering principle doesn't care about whether there are elements with no immediate predecessor. The principle just says that if $\phi (n)$ for some $n$ belonging to a well-ordered set - whether $n$ is a limit element or not, then that set contains its smallest element $t$ satisfying $\phi (t)$. HOTmag (talk) 11:00, 4 August 2016 (UTC)

The complaint people have here is your saying that well ordering is equivalent to the axiom of induction when it is not. One can get to well ordering from the axiom of induction but not the other way around. Yes well ordering can be used for your purpose but it simply is not equivalent in general. Dmcq (talk) 12:49, 4 August 2016 (UTC)

Agreed one must distinguish the axiom from the principle. I was objecting to the statement "Clearly φ(1) holds and φ(q+1) fails. So #2 fails, meaning there is some n with φ(n) ∧ ¬φ(n+1)." I don't see < as a well-ordering; if it was, I could concede that it would be valid to conclude that. —Quondum 14:52, 4 August 2016 (UTC)

I've just replaced the words "equivalent to" by the words "a consequence of". HOTmag (talk) 15:01, 4 August 2016 (UTC)

Okay, so how is the well-ordering principle a consequence of the axiom of induction? My example of a nonstandard model seems to an example that violates the principle, but does not violate the axiom of induction. To recap:

• The well-ordering principle says that every subset of the model has a least element. My model has a subset, namely ω+Z, that has no least element under the ordering <. Thus, < is not a well-ordering in this model.
• The axiom of induction states that, for all n, a predicate being true for every element less than n implies its truth for n, and it is true for n=0, then it is true for n. This means that a lot of predicates can be shown true for all n, even for nonfinite n, despite < not being a well-ordering.

Or did I get that wrong, and somehow one can prove from the axiom that < is a well-ordering? —Quondum 19:53, 4 August 2016 (UTC)

@Quondum, please notice that what is only provable by First order Axiom of induction is about the least element satisfying a given First order proposition, rather then about the least element belonging to a given subset. So, really your subset ω+Z has no minimum, but First order Peano language can formulate no proposition φ(x) satisfied only by every x belonging to your subset. HOTmag (talk) 20:46, 4 August 2016 (UTC)

If you have a look at Peano axioms#Inequalities i gives a proof that well-ordering follows from strong induction, strong induction follows from induction fairly straightforwardly. Going the other way requires the small lemma that every natural number except 0 must be the successor of another natural number. Dmcq (talk) 22:30, 4 August 2016 (UTC)

I think we're at odds about which Peano system we're talking about (first or second order). Never mind. —Quondum 05:27, 5 August 2016 (UTC)

First-order considering the induction axiom to be an axiom scheme. Dmcq (talk) 07:24, 5 August 2016 (UTC)

You have to be fairly careful in discussing these things — Peano arithmetic is a weak enough system that a lot of things that you take for granted in informal mathematical reasoning are either not expressible or not provable. In this case, the language of arithmetic has no way of even stating the claim "< wellorders the naturals", much less proving it. You can't state it in the form "every nonempty set has a <-least element", because arithmetic doesn't know about sets, and you can't state it in the form "there is no infinite descending <-chain", because arithmetic doesn't know about infinite.

That said, we can look at the issue a bit via the back door, by looking at models of set theory that are not ω-models; that is, their wellfounded part does not include the ordinal ω. If you look at the objects that such a model thinks are the natural numbers, you get a nonstandard model of Peano arithmetic (perhaps even of true arithmetic).

So we can ask, does such a model satisfy the proposition "< wellorders the naturals"? The answer is yes, it does. But that doesn't mean that the < of the model really wellorders the naturals of the model. It means the model thinks it does. There is a subset of the "naturals" of the model that does not have a least element — but that subset is not in the model. Similarly, there is an infinite descending chain, but the chain is not an element of the model.

Finally, HOTmag, Peano arithmetic is definitely strong enough to prove that sqrt(2) is irrational (in the form you have stated it). If you still have doubts about it, it would be worth working the argument through. --Trovatore (talk) 06:45, 7 August 2016 (UTC)

The way you indented your response shows it's was intended to address User:Dmcq, but finally you surprisingly mentioned my name at the end of your response - as if it were intended to address...me, so now I'm a bit confused about who you were addressing: was it Dmcq, or me (or perhaps both of us)?

Anyways, as for your last paragraph (in which you've mentioned my name) about the proof of the irrationality of the square root of two: I had already noticed this a few days ago, as you can realize by reading the paragraph I wrote on August 3 (on this thread) which begins with the words: "Let, p,q be two natural numbers". In that paragraph, I have presented the simplest argument (easily able to be converted into PA language) that explains why every fraction must be equal to an irreducible fraction [while the square root of two does not equal to any irreducible fraction - as easily provable in PA], Hence, it's easily provable (in PA) that the square root of two is irrational (by just converting the well-known Greek argument into Peano language, which is a very easy task - once one has proved in PA that every fraction must be equal to an irreducible fraction). HOTmag (talk) 07:56, 7 August 2016 (UTC)

First order Peano arithmetic does include sets. It just doesn't include predicates as logical variables. That's why induction is an axiom scheme. Saying something is infinite can be considered as equivalent to saying one can assign a different element to each natural number. The actual finite is a bit more difficult, at most one can say that the elements can all be paired off with the natural numbers less than or equal to a given one but of course with some non-standard model that might not actually be finite. It doesn't actually matter much though as far as any proofs are concerned. a ≤ b is defined by there being a c such that a+c=b. Dmcq (talk) 17:11, 7 August 2016 (UTC)

The first-order language of arithmetic does not know about sets. There is no way to express the claim "every nonempty set has a <-least element. You just can't get started. --Trovatore (talk) 17:22, 7 August 2016 (UTC)

You've lost me. What first-order language of arithmetic are we talking about that does not include first-order logic? A predicate P(x) simply says if x is in a set or not. Dmcq (talk) 18:16, 7 August 2016 (UTC)

Don't confuse sets, which are extensional, with (definable) predicates, which are intensional. Sets are arbitrary ways of picking some things and not others, and if they happen to follow a rule, that's "accidental" as it were.

But maybe we're just not understanding each other. Why don't you give an outline of how you would attempt to express the claim "every nonempty set has a <-least element" as a sentence (or even infinitely many sentences) of first-order arithmetic. Then I can address that more specifically.

(By the way I may not get back to it right away; the trails call....) --Trovatore (talk) 18:27, 7 August 2016 (UTC)

Additionally, how would you - Dmcq - express (in Peano language) the claim that every number is finite? HOTmag (talk) 19:17, 7 August 2016 (UTC)

Why not just say what you mean? I'm not a fan of Platonic dialogue. And I never said I could formulate something that would say something was actually finite, only that saying there was some natural number such that all the natural numbers satisfied by the predicate are less than or equal to that is as good as saying only a finite number satisfy it. But that for non-standard model that may not actually be finite. A bit like in the Mikado 'When Your Majesty says "Let a thing be done", it’s as good as done, practically it is done, because Your Majesty’s will is law.' ;-) Dmcq (talk) 21:18, 7 August 2016 (UTC)