Wikipedia:Reference desk/Archives/Mathematics/2010 October 22

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 22

Polynomial degree vs order

Reading both Wikipedia and Wolfram I see that order and degree can be used interchangeably. But I was fairly certain that when I researched the same thing about 5 years ago the definitions were slightly different. In the next paragraph I do not state a fact, I am simply stating my previous (most likely erroneous) understanding.

I remember the "degree" being defined as the exponent of the highest order term, so a parabola would be 2nd degree. The order (and this is where I'm confused) was defined as the number of variables in the particular class of polynomial, so a general parabola would be 3rd order. A general 2nd degree polynomial of the form a*x^2 + b (no linear term), would be 2nd order.

Was it once defined like this or must I have been getting bad information?

196.211.175.2 (talk) 09:56, 22 October 2010 (UTC) Eon

The words degree and order are used interchangeably, according to degree of a polynomial. Bo Jacoby (talk) 12:37, 22 October 2010 (UTC).

I don't recall seeing the definition of order you described. But it's very possible that this definition is common in a particular place or you've seen it used by a particular author. -- Meni Rosenfeld (talk) 13:58, 22 October 2010 (UTC)

I've always used the word "degree" for things like the exponent in x³, and said that the degree of a polynomial is the exponent of the highest-degree (not highest-order) term. "Order", on the other hand, I use for differential operators; thus one can speak of a second-order differential equation. I think that's the way I was taugth to use those terms in school. But I know that in some eras the word "order" has been used the way I use the word "degree", and that some people are not fastidious. Michael Hardy (talk) 18:43, 22 October 2010 (UTC)

For a power series, order can refer to the smallest exponent that has a non-zero coefficient. Quantling (talk) 20:33, 26 October 2010 (UTC)

typesetting a long stream of numbers in Latex?

How do I typeset 114813069527425452423283320117768198402231770208869520047764273682576626139237031385665948631650626991844596463898746277344711896086305533142593135616665318539129989145312280000688779148240044871428926990063486244781615463646388363947317026040466353970904996558162398808944629605623311649536164221970332681344168908984458505602379484807914058900934776500429002716706625830522008132236281291761267883317206598995396418127021779858404042159853183251540889433902091920554957783589672039160081957216630582755380425583726015528348786419432054508915275783882625175435528800822842770817965453762184851149029376 so that it wraps and stuff? It just goes off the edge of the page now, so that only one line is visible... 84.153.179.167 (talk) 13:52, 22 October 2010 (UTC)

Insert \allowbreak in places where you want to allow it to break. You'd probably also need to mark the paragraph with \raggedright, as there will be no stretchable spaces on the lines.—Emil J. 14:14, 22 October 2010 (UTC)

If you want to allow a line break after every digit, and if you need to do this repeatedly, here's a macro:

\def\longnumber#1{\raggedright$\dolongnumber#1\stop}
\def\dolongnumber#1{\ifx\stop#1$\else#1\allowbreak\expandafter\dolongnumber\fi}

\longnumber{1148130695274254524232833201177...965453762184851149029376}

—Emil J. 14:28, 22 October 2010 (UTC)

Now I wonder: does anyone have a clue why the syntax highlighter coloured the first occurrence of "#1" black, the second one pink, and the other three blue?—Emil J. 15:19, 22 October 2010 (UTC)

I think it is confused by the (apparently) unpaired dollar signs. The anomaly changes somewhat if I replace them with \begin{math} and \end{math}, and goes away if I remove them completely. –Henning Makholm (talk) 15:40, 22 October 2010 (UTC)

I see. Thank you.—Emil J. 16:40, 22 October 2010 (UTC)

With hindsight, the \raggedright was a bad idea, as it spill over to subsequent paragraphs, and cannot be easily confined. Here is a better implementation:

\def\longnumber#1{$\dolongnumber#1\stop}
\def\dolongnumber#1{\ifx#1\stop$\else#1\allowbreak\hskip0pt plus.5pt\expandafter\dolongnumber\fi}

\longnumber{1148130695274254524232833201177...965453762184851149029376}

It inserts a slightly stretchable space after every digit to allow proper justification. Here's the same kind of thing with a bit of syntactic trickery:

\def\longnumber{\def\relax##1{##1\allowbreak\hskip0pt plus.5pt\relax}\relax}

$\longnumber1148130695274254524232833201177...965453762184851149029376$

—Emil J. 13:55, 25 October 2010 (UTC)

Redefining \relax is very much asking for trouble, even though it happens to work safely in the intended use case. It won't work with LaTeXy \begin{math}/\end{math}, nor for a primitive $$display$$. –Henning Makholm (talk) 15:38, 25 October 2010 (UTC)

That's why I called it a trickery, it's basically for fun, and it's designed to work only in the exact way I used above (a sequence of digits between single dollars). If that's a problem, use the previous solution (which however also relies on some assumptions on the token sequence in its argument, it won't process correctly stuff like \longnumber{123\bar{4}567}). If I were serious about it I'd also define a skip register for that "0pt plus .5pt".—Emil J. 15:57, 25 October 2010 (UTC)

if you had to brute-force a number but could be told some of the digits

If you had to brute-force a number but could be told some of the digits, would you rather have the n most significant or the n least significant digits - or wouldn't it make a difference? —Preceding unsigned comment added by 93.186.23.239 (talk) 14:07, 22 October 2010 (UTC)

If you do not know (or suspect) anything else about the number, it makes no difference. If you do, it depends on the other expected properties of the number.—Emil J. 14:37, 22 October 2010 (UTC)

all right, you're trying to factor a large composite number into its exactly two large random primes, and I'm telling you about the n most or least significant digits of the larger of them. Is the only reason you would prefer the former that the last digit is odd, so you already have slightly more information about it? Or would you have any other reason to prefer one over the other? Thank you.

You also know that it is coprime with 5 (if the digits are decimal digits). This is already a good reason (just oddness of primes essentially halves your search space if given the most significant digits), but I would also prefer the most significant digits because then the brute force requires me to sieve primes out of an interval, which is somewhat easier then to sieve them from the set of numbers with given ending (however, this is only relevant if you are really going to find the factors by brute force; if you are using a more sophisticated factoring algorithm, it may have quite different preferences as to which extra information on the factors is more useful, and it may well happen that it cannot use either of them).—Emil J. 15:37, 22 October 2010 (UTC)

I am struggling to see how you can say anything useful about the factorisation of the number if you are only told some of its digits and that it is a semiprime. For example, if you know the number is 1231x, it could be 13 x 947 = 12311, or 7 x 1759 = 12313 or 109 x 113 = 12317 or 97 x 127 = 12319. Gandalf61 (talk) 16:04, 22 October 2010 (UTC)

No, that wouldn't be an example of the kind the OP is describing. An example may be that you need to factor 12317 and know that one of the factors is 11x. –Henning Makholm (talk) 16:19, 22 October 2010 (UTC)

Yes (OP here, my IP has changed though) . If you were trying to factor 5725797461 would you rather know that the larger of them begins 75... or ends ...679 -- you only get to learn one of these things. Extrapolating, would you rather learn the first or the last hundred digits of a 1000-digit prime factor of an even larger composite number you were trying to factor into its exactly two large prime factors? 84.153.222.131 (talk) 18:03, 22 October 2010 (UTC)

Quotients

Resolved

I'm looking for a command in either Maple or Maxima to compute the quotient of a polynomial ring by a gradient ideal. I can do some simple examples by hand, but I don't know a general method. For example, let ƒ(x,y) = x² + y^k where k is a positive integer. I have

${\mathcal {A}}=\mathbb {R} [x,y]/\left\langle f_{x},f_{y}\right\rangle =\mathbb {R} [x,y]/\langle x,y^{k-1}\rangle \cong \mathbb {R} \langle 1,y,y^{2},\ldots ,y^{k-2}\rangle .$

Provided that the gradient vector field has an algebraically isolated zero at x = y = 0 the result will be a finite dimensional real vector space. Algebraically isolated zero means that the zero is isolated when x and y are considered as complex variables, and not just real. For example, can anyone calculate the vector space (called the local algebra) when ƒ(x,y) = x³ + xy^k?

${\mathcal {A}}=\mathbb {R} [x,y]/\left\langle f_{x},f_{y}\right\rangle =\mathbb {R} [x,y]/\langle 3x^{2}+y^{k},xy\rangle \cong \ldots \ ?$

More importantly, does anyone know a command in either Maple or Maxima to compute the quotient? — Fly by Night (talk) 15:10, 22 October 2010 (UTC)

I know what an ideal is, and I know what a gradient is, but what is a "gradient ideal"? Neither article so much as mentions the other word. –Henning Makholm (talk) 15:46, 22 October 2010 (UTC)

The thing in the denominator of my quotients above. For a function ƒ : Rⁿ → R the gradient ideal of ƒ is given by

$I_{f}:=\left\langle {\frac {\partial f}{\partial x_{1}}},\ldots ,{\frac {\partial f}{\partial x_{n}}}\right\rangle .$

It should really be thought of as an ideal in the ring of analytic function germs, but you can get away with thinking of R[x,y] instead. It's quite a common term. Google Scholar returns about 140 hits. — Fly by Night (talk) 15:54, 22 October 2010 (UTC)

It confused me that it looked as if "gradient ideal" was linked to something that ought to explain that particualar construction. Also, I'm not used to the angle bracket notation here; the texts I grew up with used round parentheses for "the ideal generated by such-and-such". –Henning Makholm (talk) 16:09, 22 October 2010 (UTC)

Ah, I see. Looking around on Google seems to show a mixture of rounded and angled brackets for the gradient ideal. Maybe it's not common in traditional ring theory, but the gradient ideal is an application of ring theory to another subject. So you'd have non-ring-theorists using rings and ideals. Maybe that would explain the non-familiar notation. — Fly by Night (talk) 17:59, 22 October 2010 (UTC)

In your example $\mathbb {R} [x,y]/\langle 3x^{2}+y^{k},xy\rangle$: When you quotient out (xy), all mixed terms drop out, so you have, R(1,x,y,x²,y²,x³,y³,...) left. Now quotient out (3x²+y^k). Then you can rewrite y^(k+1) as -3x²y which drops out because xy=0. Similarly, x³=x(-1/3)y^k=0. Then you're left with R(1,x,x²,y,y²,...,y^k), but x² is (-1/3)y^k, so your final space is R(1,x,y,y²,...,y^k).

This is hardly an example of a general method, of course. And the multiplicative structure of the quotient ring is lost when you write it simply as a vector space, but I suppose that is what you want? –Henning Makholm (talk) 16:09, 22 October 2010 (UTC)

It's a method to calculate the index at a singular point of a gradient vector field. You work out the quotient and then make a multiplication table of the spanning elements. You fill it in, modulo the gradient ideal. Then you find a linear map that takes the class of the determinant of the Hessian of ƒ to 1. The simplest one would send [det(Hess_ƒ)] to 1 and every other class to 0. This maps changes the k-by-k multiplication table into a k-by-k matrix. The signature of which is the index of the singular point of the gradient vector field. See here if your interested. (N.B. They use round brackets for ideals in this article.) — Fly by Night (talk) 18:12, 22 October 2010 (UTC)

You might want to try the SINGULAR CAS. I believe that it specialise in this sort of calculation.--Salix (talk): 19:44, 22 October 2010 (UTC)

I've just looked at the website, and it looks perfect. Thanks a lot Salix. I shall download it now. — Fly by Night (talk) 20:04, 22 October 2010 (UTC)

Scenario: Traveling to Pandora as seen in James Cameron's movie Avatar

I've been trying to figure out how long it would take to get to the fictional moon Pandora from Earth in the movie Avatar—at a specific faster-than-light speed—, but the unit conversions have been tedious. My problem is based on a few assumptions and definitions. I've laid them out as follows:

• Assumptions & Considerations:
  • Assume that fast than light travel is possible.
  • Either assume that time dilation does not occur or is not a concern.
  • Either assume that I'm not killed by the speed or that it is not a concern.
  • Assume their is no need for acceleration/deceleration time.
• Definitions:
  • The distance from Earth to Pandora is 4.37 light years.
  • One year is 31,557,600 seconds.
  • The speed of light is 186,282.397 miles per second.
• Givens:
  • The speed I'm traveling at is 5 trillion miles per nanosecond.
• Problems:
  • I would like the speed converted to miles per second—no rounding please.
  • I would like to know how long it would take me to get their—no rounding please.
  • I would like a real world comparison as to how quick that time is (example, 0.25 seconds is the blink of an eye).

--Melab±1 ☎ 19:02, 22 October 2010 (UTC)

Google is neat for unit conversions: 4.37 light years / 5e12 miles/ns, assuming short-scale trillions. –Henning Makholm (talk) 19:16, 22 October 2010 (UTC)

Thank you, but I need all three of my problems answered and I also do not know if Google's unit conversions use the definitions I have defined. --Melab±1 ☎ 19:48, 22 October 2010 (UTC)

Well, OK. 5 trillion is usually 5x10¹², and this occurs 10⁹ times per second, giving an exact speed of 5x10²¹ miles per second. At your definition, a light year is 5.87862537 x 10¹² miles (for a standardised definition, see light year). That makes a total distance of 2.56895929 × 10¹³ to a level of accuracy that's only true if Pandora was exactly 4.37 light years away. Divide the latter by the former, and you get 5.13791857 nanoseconds. That's less than the time it takes light to cover two metres, to give an example. That really short period of time is quite hard to quantify in everyday terms. Hope I've done this right, - Jarry1250 ^{[Who? Discuss.]} 20:23, 22 October 2010 (UTC)

I agree with the above calculations. Mine are... 5 trillion miles per nanosecond = 5*10^12 miles / (10^-9 sec) = 5*10^21 miles / sec = 5,000,000,000,000,000,000,000 miles / sec. 4.37 light years * 31,557,600 seconds / year * 186,282.397 miles / second = 5,878,625,371,567.2 miles * 4.37 = 25,689,592,873,748.664 miles. Distance = rate * time, so time = distance / rate (using the nonrelativistic approximation you seem to want). Here, travel time is 25,689,592,873,748.664 miles / (5*10^21 miles / sec) = 0.0000000051379185747497328 sec = 5.1379185747497328 nanoseconds. For scaling, about 5.14 nanoseconds in a second is the same ratio as about 2.5 minutes in a millenium. It should be noted that you're asking us to use wayyyyy too many significant figures in these calculations, and the speed is incredibly high. 67.158.43.41 (talk) 05:00, 23 October 2010 (UTC)

But faster than light travel isn't possible. Traveling exactly at the speed of light isn't possible either, unless you have zero mass or infinite energy: your mass increases with respect to your speed, so the faster you go the more energy you need to go faster. Close to the speed of light you would need almost infinite amounts of energy to accelerate your almost infinite mass. See this section of the Special Relativity article. Some theories hypothesise about anti-particles with negative mass travelling faster than the speed of light. Why don't you just assume the speed to be s, and the distance to by d? — Fly by Night (talk) 10:01, 23 October 2010 (UTC)

Generalization of ordinals

In ZFC, ordinals are equivalence classes of sets, since every set can be well-ordered in ZFC. In ZF+~AC, there are sets that cannot be well-ordered. Is there any way to organize these sets into equivalence classes that provide some notion of size similar to the ordinals? 99.237.180.170 (talk) 19:07, 22 October 2010 (UTC)

I'd quibble with the way you put it. There's no such thing as "sets in ZFC" or "sets in ZF+~AC"; there are only sets, and AC is either true of them, or it is not.

That said, yes, you can certainly get objects corresponding to cardinality, working in ZF alone. What you do is take equivalence classes up to the existence of a bijection. Unfortunately these are proper classes, so you use the Scott trick to cut them down to sets. --Trovatore (talk) 19:13, 22 October 2010 (UTC)

I think your terminology quibble is more Platonic than the mainstream mathematical culture makes it fashionable to be. But in that case, if you accept that the ZF axioms are true, then both of ZFC and ZF¬C will be consistent and thus have models. And the elements of such a model's universe are usually known as "sets" in that model, even though you may prefer to reserve the word for something more metaphysical. –Henning Makholm (talk) 19:31, 22 October 2010 (UTC)

Well, those objects are sets in the sense of the model, not in the sense of the theory. It's a critical distinction. --Trovatore (talk) 21:08, 22 October 2010 (UTC)

Like Henning Makholm, I stand by my original use of the word "sets." I don't see what you mean by "sets in the sense of the theory." To me, sets are objects described by the axioms of a set theory. I did consider using cardinality as you suggested, but I was hoping for something more specific. Maybe something with another axiom added to ZF¬C might work better for my purposes. Any more suggestions? 76.67.74.196 (talk) 22:04, 22 October 2010 (UTC)

The correct phrasing is ZFC proves that every set can be wellordered, not every set can be wellordered in ZFC. --Trovatore (talk) 23:17, 22 October 2010 (UTC)

I suspect what you mean is the correct phrasing is

"{Every set can be well-ordered} in ZFC

rather than

"Every set can be {well-ordered in ZFC}.

(The latter being meaningless.) Michael Hardy (talk) 16:57, 23 October 2010 (UTC)

No, I really don't. The mathematical standard is to talk like a Platonist whether you actually are one or not. This saves an immense amount of grief when it comes to things like expositions of the incompleteness theorems.

It's far cleaner in such cases to use the standard language, where a flat assertion of a statement is the same as the claim that the statement is true (disquotational truth) rather than provable. Then you can always make some sort of disclaimer afterwards about what interpretation you really have in mind. --Trovatore (talk) 17:49, 23 October 2010 (UTC)

This discussion is getting pretty far off topic. Returning to the original answer, doesn't the definition of the cardinal numbers depend on the ordinal numbers through cardinals like $\beth _{\omega }$, $\beth _{\omega +1}$, and $\beth _{2\omega }$? How can you name cardinals without the axiom of choice? Are the cardinals defined as equivalence classes, but they cannot be enumerated without the AC? 74.14.109.58 (talk) 20:01, 23 October 2010 (UTC)

No, without the AC there is no systematic enumeration of the cardinals; you cannot even always compare two cardinals to see whether one is larger than the other (the AC is equivalent to trichotomy between cardinals). Without AC there is no better general way of naming a cardinal than to exhibit a set (or many sets) of the cardinality you want to speak of. –Henning Makholm (talk) 20:12, 23 October 2010 (UTC)

A useful proxy in some contexts for such cardinalities is the notion of Borel reducibility of equivalence relations. If equivalence relation E is reducible to equivalence relation F, then the quotient space by E has cardinality less than or equal to the quotient space by F. See Borel equivalence relation for a bare start. An article I had ambitious plans for at one time but never got around to really developing. --Trovatore (talk) 20:17, 23 October 2010 (UTC)

Shoelace formula

Why does the shoelace formula work? --75.33.217.61 (talk) 19:59, 22 October 2010 (UTC)

Our article Shoelace formula explains (um, no it doesn't, but one easily sees that it is the case) how the formula can be expressed as a sum of cross products where each can be seen to be ±2 times the area of the triangle formed by the origin and two successive vertices.

The easiest case to convince onself of is when the polygon is convex and that the origin lies inside it. Draw lines from each vertex to the origin; this cuts it into a number of triangles that each corresponds to a cross product in the formula, and all of the cross products have the same sign.

For general polygons, the easiest approach may be to cut the polygon into triangles, and then show by induction on the number of triangles that the formula works and that the sum of the cross products is positive if the vertices are taken in clockwise (or is it anticlockwise? Never mind, one of them will turn out to work) order around the polygon. The base case for a single triangle is just a matter of calculation (the area of triangle ABC is ${\frac {|(B-A)\times (C-A)|}{2}}$, and the numerator can be rewritten using the distributive and anticommutative laws for the cross product, to give just the terms in the shoelace formula). In the induction case, add one triangle that shares one or two edges with the polygon you already have; the cross products corresponding to the shared edges will cancel each other out. –Henning Makholm (talk) 20:20, 22 October 2010 (UTC)

Reducing Transformation Arrays

Hi all, I'm looking for a way to reduce N 'transformation arrays' to a single transformation array without running through each individual transformation. Here's an example:

Given the alphabet, alpha = "abcd" and the transformation array, t1 = [4, 3, 2, 1]:

f(alpha, t1) = "dcba"

given t2 = [4, 2, 3, 1]

f(f(alpha, t1), t2) = "acbd"

So the first transformation we did was [4, 3, 2, 1] and the second was [4, 2, 3, 1] and the result was [1, 3, 2, 4]

I'm looking for a function, let's call it g(t1, ..., tN) to compute this. For instance:

g([4, 3, 2, 1], [4, 2, 3, 1]) = [1, 3, 2, 4]

Ideally I'd like for g(t1, ..., tN) to have a time complexity of O(n). If I actually do each of the transformations I can achieve O(n*m) where m is the length of the alphabet; thus, a time complexity of this, or worse, won't really help.

I'm not entirely sure if such a function can (does?) exist, but any ideas would be much appreciated!

Thanks!

24.147.249.232 (talk) 20:59, 22 October 2010 (UTC)

You cannot do better than O(nm); otherwise you don't have time to read all of the inputs!

(By the way, what you're referring to as a "transformation" is commonly known as a permutation) –Henning Makholm (talk) 21:06, 22 October 2010 (UTC)

Oh. Good point! I suppose a better question would be what's the optimal way to compute g(...)? I was hoping for a method where I could apply simple operations to each element, but that seems unlikely. The best method I've come up with, thus far, is (apologies for the poor pseudocode formatting!):

for(i in 0..m)

for(j in 0..n)

ndeck[j] = deck[permutations[i][j]]

deck = ndeck

Which is okay, but could be a lot faster if the last copy step didn't need to occur. Thus, perhaps my original question should have asked whether it's possible to do that innermost step in-place.

24.147.249.232 (talk) 22:16, 22 October 2010 (UTC)

Is this really the critical part of your entire program? Remember, premature optimization is the root of all evil. If it is critical, I would suggest unrolling the outer loop twice and shifting back and forth between two arrays:

for(i in 0,2,4,...,m-1)

for(j in 0..n)

decka[j] = deckb[permutations[i][j]]

for(j in 0..n)

deckb[j] = decka[permutations[i+1][j]]

Alternatively, you might also try to trace each element backwards through the permutations:

for(j in 0..n)

k = j

for(i in m..0)

k = permutations[i][k]

outj] = k

which seems to faster under an unit cost model, but is likely to have horrible cache locality. –Henning Makholm (talk) 23:00, 22 October 2010 (UTC)

Does the last copy step need to occur? It obviously depends on what goes on to be done with it and how modularised your code as a whole is, but if you've got space in memory for both deck and ndeck, can't you just carry on using ndeck once you're on the other side of the loop?

Thinking about it from another direction, would some recursion help? If you had a function to work out the end product of applying two re-orderings sequentially (even on a dummy "initial order" which you could then sub in your real data for at the end), you could just keep piling in pairs: t1 and t2, t3 and t4 ... up to tN-1, tN. Then you do it again to (the result from doing t1t2) and (the result from doing t3 and t4), etc. until you finally end up at the eventual answer. Obviously this is easiest to work for N a power of 2, but it's not difficult for some other N. Then again, that's probably only any practical use in speeding things up if you've got access to a parallel architecture where you can do all the initial pairs in parallel and then gradually bring them together. (So you use N/2 processes in your first go round, then N/4, then N/8 etc.) I'm rusty on all this, but it feels like it ought to be possible. --81.153.109.200 (talk) 10:36, 23 October 2010 (UTC)

GMAT scoring system

This page seems as good as any for my question, so here goes: On the math portion of the GMAT[1] I scored 50/95th percentile. Had I answered the last question correctly (it was not very hard; I had made my choice and was ready to press Next), was it probable that I might've raised my score? Thanks. 67.243.7.240 (talk) 21:31, 22 October 2010 (UTC)

I presume that by "50/95" you mean a score of 50 at the 95th percentile. You can see in the link you provided how an extra mark would increase the percentile score, assuming that you get one mark per correct answer. 92.24.178.5 (talk) 11:03, 23 October 2010 (UTC)

I don't know that one gets "one mark per correct answer"; thus my question hoping someone knows. 67.243.7.240 (talk) 23:48, 24 October 2010 (UTC)

Logic - deduction of axioms

Is it possible to deduce $\neg \neg p\Rightarrow p\,\forall \,p$ from $p\Rightarrow (q\Rightarrow p)\,\forall \,p,\,q$ and $(p\Rightarrow (q\Rightarrow r))\Rightarrow ((p\Rightarrow q)\Rightarrow (p\Rightarrow r))\,\forall \,p,\,q,\,r$? I'm studying on a logic theory course and I've been asked whether it is possible to deduce the third axiom we use from the first two? I strongly believe it isn't because otherwise we wouldn't need to take it as an axiom, but I'm not sure how to go about showing it. I know of most of the basic theorems by now (deduction, completeness etc), but I can't see any obvious way to get there. Could anyone please suggest anything? Thankyou, 62.3.246.201 (talk) 23:20, 22 October 2010 (UTC)

A typical way to prove that one axiom does not follow from the others, would be to exhibit a non-standard interpretation of the connectives that makes the two latter axioms (K and S, among friends) into tautologies but the first one into a non-tautology (while tautologies are still closed under whatever inference rules you have, such as modus ponens). This should be particularly easy because the two axioms you assume do not mention ¬ at all, so the only thing you need from an alternative truth table for ¬ is that it makes $\neg \neg p\rightarrow p$ into a non-tautology. –Henning Makholm (talk) 23:39, 22 October 2010 (UTC)

I'm sorry, I don't quite follow - what do you mean by 'exhibit a non-standard interpretation of the connectives'? Thankyou for the help :) 131.111.16.20 (talk) 11:53, 23 October 2010 (UTC)

Okay, let's take it more slowly then. A general method to show that some wff A cannot be proved from B, C, D is to define some set S of "special" well-formed formulas such that

1. B, C, D are all in S
2. A is not in S
3. For each rule of inference (such as modus ponens, which I suspect is actually the only one you have at the moment), if the rule allows you to infer a wff from wffs in S, then the wff you infer is also in S.

Then it's quite easy to show that no formal proof can ever contain a wff outside S, and in particular there's no formal proof that concludes A. (This ought to remind you of how soundness of the proof system was shown, where S was taken to be "all logically valid wffs").

I assume that by this point you have seen truth tables for ¬ and → and learned how to use them to determine whether a given formula is a tautology. My suggestion is then to invent your own crazy truth tables for the symbols, and then let S be all of those wffs that would have been "tautologies" under your crazy truth tables. –Henning Makholm (talk) 15:11, 23 October 2010 (UTC)

The axioms describe properties of the logical symbols $\neg$ and $\Rightarrow$. If you can find an interpretation that is true under two of the axioms, but not under a third, you have shown that the third does not follow from the other two. Try e.g. a three-valued logic. --Stephan Schulz (talk) 12:06, 23 October 2010 (UTC)

So just to be clear, there's no way to do this without going outside the realms of the 2-valued (just true/false) logic? I only ask because I'm being asked this question having been taught nothing but 2-valued logic on the course so far with no mention of other possibilities - basically we have covered basic propositional logic such as valuations, truth-tables (with only the values 0/1), the deduction, completeness, soundness, adequacy, Moor existence lemma, compactness and predictability theorems, the 3 axioms above and the deduction rule modus ponens. (I don't know how many of these things are course-specific and how many are widely known by these names so sorry if any of those sound unfamiliar!) I would usually happily read ahead on these things and I don't mean to sound glib or anything like that, it's just we've only been lectured on this material from scratch for the past 2 weeks (though I need to get my head around this for work due in just a week!), so I presume there must be some way to prove this using just 2-value logic - if that's what you meant Henning then please say, it's quite possible I misunderstood! Thankyou both for your patience, and if you can direct me to something I can read up on this via, rather than having to explain every step to a complete beginner (must be quite tiresome for you!) then I'd be very happy to do so, I'm just concerned I'm missing an easier way of doing this. Perhaps our lecturer expects us to deduce higher-valued logic for ourselves, it just seems a bit unlikely... Thanks again! 131.111.185.68 (talk) 21:01, 23 October 2010 (UTC)

The solution I have in mind does indeed stay within two values. It is a fairly standard technique, but by no means the only way to reach the goal, so there may or may not be hints in your text that point in another direction. (With the hints I've given so far, there are only 63 possible truth-table combinations to try out, most of which can be eliminated quickly, and all of which will yield to brute force. So you're not lost, though you might end up bored out of your skull unless you can think of a smarter way to home in on the right one).

The trouble with pointing to "something you can read up on" is that it is hard to know what will work for you better than the text you're already studying. Also it wouldn't do to simply point you to a complete solution; that way you would miss the learning experience of figuring it out yourself. (Except that it probably wouldn't work for exactly the same definitions your text is using. There are many slightly different ways to do formal logic, and they are all easily seen to be fairly unimportant variations of the same thing once you understand them in the first place. But until you get that basic understanding, it is best not to confuse oneself too much with alternative sources).

You syllabus so far sounds fairly standard, though the names "Moor existence lemma" and "predictability theorem" do not register with me. –Henning Makholm (talk) 22:01, 23 October 2010 (UTC)

Okay, I think I grasp the concept now - the 'not' and 'implies' symbols are literally just that - symbols. We can assign whatever meaning to them we want (we could say not(p) is always equal to 1, no matter what p, or not(p) has the same value as p, say): the reason I was finding it so hard was that I was retaining the meaning I'm used to for them, i.e. 0 implies 1 is true, 1 implies 0 is false, etc, rather than seeing we can define the values of p implies q, and not(p), to be whatever we want, and we just want to find a definition for which our 2 axioms and modus ponens are always tautologies (true no matter what values p,q,r take) and for which not(not(p)) implies p is -not- always true. So then, could we take implies under its normal meaning (always one except for 1 does not imply 0), given that we know this should make our 2 axioms and MP true (they do not involve the 'not' symbol so our definition of it is irrelevant with regards to these axioms), and take 'not' as not(p)=0 for p=0 or 1? So then not(not(1))=not(0)=0 which does not imply 1=p? 131.111.185.68 (talk) 01:41, 24 October 2010 (UTC)

Almost there, except 0→1 is 1. But 1→0 is 0. Nudge, wink. –Henning Makholm (talk) 02:28, 24 October 2010 (UTC)

Oh well, you can surely fix that one last mixup, so I'll pretend you that you've solved the problem, and feel free to point you to intuitionistic logic which explores what happens if one refuses to accept ¬¬p→p as an axiom. It turns out to be not quite as crazy as one would think at first; you may find it interesting. (Or it may make your head asplode, in which case don't sweat it. It usually takes several tries getting used to). –Henning Makholm (talk) 02:33, 24 October 2010 (UTC)

Ahh gotcha, so setting not(p)=1 and p=0, we get not(not(1))=1 which does not imply 0=p :) Thankyou so much for being so patient with me, I definitely owe you one! I will have a look at intuitionist logic the next time I'm feeling brave, all this is a bit of a brain-melter to say the least. Thanks again! Out of interest, where do the 'K' and 'S' ("among friends...") come from? Is there a list of standard axioms somewhere, each assigned a letter for conciseness or something like that? 131.111.185.68 (talk) 10:41, 24 October 2010 (UTC)

Hmm, after I've checked various sources, it may actually only be a small select circle of friends who call them that. I shouldn't have introduced them here. The reasoning I allude to is described in Combinatory logic#Logic, but has some fairly heavy prerequisites. If your brain is melting, you probably don't want to go there. –Henning Makholm (talk) 13:21, 24 October 2010 (UTC)

A simpler way to phrase the argument in this particular case would be: "Suppose we had a proof of ¬¬p→p. Then we would replace every subformula ¬φ anywhere in the proof with q, where q is any propositional variable that differs from p. Since none of the rules we use treat ¬φ specially, this substitution still leaves a valid proof. But that proof would conclude q→p which is manifestly not a tautology, so the assumed proof of ¬¬p→p cannot exist."

This may be what your teacher had envisioned. However, I couldn't find any hint for that version that wouldn't give it all away, and the method isn't as general. –Henning Makholm (talk) 13:44, 24 October 2010 (UTC)