Re: [math-fun] Parenthesizing
Rich politely shielded me from the jeers of the rest of the list in pointing out an "algebraic" identity that applies to 3 as it does to any number, namely: (a^a)^(a^a) = (a^(a^a))^a In general, if K and L are two different exponentiation-towers, then (a^K)^L = a^(KL) = (a^L)^K. This inspires two new questions: (1) Is this "KL law" the only algebraic law that exponentiation-towers obey in general, or are there other such general relations not inferrable from the KL law? (2) In particular for a=3, are there any equivalences that aren't true for general a? (Probably a careful reading of Guy and Selfridge [1973], cited by Neil earlier, would answer both questions.) On Wed, Nov 29, 2017 at 2:30 PM, <rcs@xmission.com> wrote:
(3^3)^(3^3) = (3^(3^3))^3 = 3^(3^4) = 3^81 . The 3 and 3^3 in the exponent are multiplied, which commutes.
Rich
-----------
Quoting Allan Wechsler <acwacw@gmail.com>:
I got my head in a little twist over this whole thread. Reassure me: do all the different parethesizations of 3^3^3^...^3, for n 3's, give different values? The original problem (using principle values of a^b) is interesting because i is special, right?
On Wed, Nov 29, 2017 at 9:46 AM, James Propp <jamespropp@gmail.com> wrote:
Apropos of parenthesizing exponential towers, here's an easier question
(probably not new): Look at all the (Catalan-many) ways to parenthesize a_1 - a_2 - ... - a_n. Not all are distinct as linear functions of a_1, a_2, ..., a_n; e.g.,
(a - (b - c)) - d = a - (b - (c - d)).
How many different functions can be obtained? I don't know the answer. Is it 2^(n-2)?
Jim Propp _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
In the case where a=3, note that: 3^(3^3) = 3^(3*3*3) = ((3^3)^3)^3 Call the first form x and the last form y. They have different numbers of threes, but we can balance them by using equal numbers of x and y, e.g. x^y = y^x i.e.: (3^(3^3))^(((3^3)^3)^3) = (((3^3)^3)^3)^(3^(3^3)) You can do the same thing for any integer. E.g. in the case of a=4: 4^(4^4) = 4^(4*4*4*4) = (((4^4)^4)^4)^4 Tom Allan Wechsler writes:
Rich politely shielded me from the jeers of the rest of the list in pointing out an "algebraic" identity that applies to 3 as it does to any number, namely:
(a^a)^(a^a) = (a^(a^a))^a
In general, if K and L are two different exponentiation-towers, then (a^K)^L = a^(KL) = (a^L)^K. This inspires two new questions:
(1) Is this "KL law" the only algebraic law that exponentiation-towers obey in general, or are there other such general relations not inferrable from the KL law?
(2) In particular for a=3, are there any equivalences that aren't true for general a?
(Probably a careful reading of Guy and Selfridge [1973], cited by Neil earlier, would answer both questions.)
Ah, good. So there are always "special" relations, at least for positive integers, that are true for one number but not any others. That answers my question (2) pretty definitively. On Wed, Nov 29, 2017 at 5:28 PM, Tom Karzes <karzes@sonic.net> wrote:
In the case where a=3, note that:
3^(3^3) = 3^(3*3*3) = ((3^3)^3)^3
Call the first form x and the last form y. They have different numbers of threes, but we can balance them by using equal numbers of x and y, e.g.
x^y = y^x
i.e.:
(3^(3^3))^(((3^3)^3)^3) = (((3^3)^3)^3)^(3^(3^3))
You can do the same thing for any integer. E.g. in the case of a=4:
4^(4^4) = 4^(4*4*4*4) = (((4^4)^4)^4)^4
Tom
Allan Wechsler writes:
Rich politely shielded me from the jeers of the rest of the list in pointing out an "algebraic" identity that applies to 3 as it does to any number, namely:
(a^a)^(a^a) = (a^(a^a))^a
In general, if K and L are two different exponentiation-towers, then (a^K)^L = a^(KL) = (a^L)^K. This inspires two new questions:
(1) Is this "KL law" the only algebraic law that exponentiation-towers obey in general, or are there other such general relations not inferrable from the KL law?
(2) In particular for a=3, are there any equivalences that aren't true for general a?
(Probably a careful reading of Guy and Selfridge [1973], cited by Neil earlier, would answer both questions.)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
A different kind of "exponentiation" is logical implication (-->), which has the same relation to conjunction that exponentiation has to multiplication, inasmuch as the equivalence between p --> (q --> r) and (p and q) --> r resembles the equality between (c^b)^a =and c^(ba). Do all the Catalan-many parenthesizations of p_1 --> p_2 --> ... --> p_n yield distinct Boolean functions? Jim Propp On Wednesday, November 29, 2017, Allan Wechsler <acwacw@gmail.com> wrote:
Ah, good. So there are always "special" relations, at least for positive integers, that are true for one number but not any others. That answers my question (2) pretty definitively.
On Wed, Nov 29, 2017 at 5:28 PM, Tom Karzes <karzes@sonic.net <javascript:;>> wrote:
In the case where a=3, note that:
3^(3^3) = 3^(3*3*3) = ((3^3)^3)^3
Call the first form x and the last form y. They have different numbers of threes, but we can balance them by using equal numbers of x and y, e.g.
x^y = y^x
i.e.:
(3^(3^3))^(((3^3)^3)^3) = (((3^3)^3)^3)^(3^(3^3))
You can do the same thing for any integer. E.g. in the case of a=4:
4^(4^4) = 4^(4*4*4*4) = (((4^4)^4)^4)^4
Tom
Allan Wechsler writes:
Rich politely shielded me from the jeers of the rest of the list in pointing out an "algebraic" identity that applies to 3 as it does to any number, namely:
(a^a)^(a^a) = (a^(a^a))^a
In general, if K and L are two different exponentiation-towers, then (a^K)^L = a^(KL) = (a^L)^K. This inspires two new questions:
(1) Is this "KL law" the only algebraic law that exponentiation-towers obey in general, or are there other such general relations not inferrable from the KL law?
(2) In particular for a=3, are there any equivalences that aren't true for general a?
(Probably a careful reading of Guy and Selfridge [1973], cited by Neil earlier, would answer both questions.)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On Fri, Dec 1, 2017 at 8:52 AM, James Propp <jamespropp@gmail.com> wrote:
A different kind of "exponentiation" is logical implication (-->), which has the same relation to conjunction that exponentiation has to multiplication, inasmuch as the equivalence between p --> (q --> r) and (p and q) --> r resembles the equality between (c^b)^a =and c^(ba).
This isomorphism is called "Currying" after Haskell Curry. It works in any monoidal closed category. In particular, as you suggest below, by the Curry-Howard isomorphism logical implication corresponds to the "arrow type" or internal hom in the category of sets and functions.
Do all the Catalan-many parenthesizations of p_1 --> p_2 --> ... --> p_n yield distinct Boolean functions?
That doesn't quite parse. The expression with arrows in it is a type, which describes a set of functions. You could ask whether any two parenthesizations of p_1 --> p_2 --> ... --> p_n are equal as sets, but that's a category-theoretic "evil", since it depends on the representation you choose; instead you can ask whether the sets are isomorphic. The answer is yes; for example, (3^(3^3))^(((3^3)^3)^3) = (((3^3)^3)^3)^(3^(3^3)) thought of combinatorically exhibits an isomorphism between the sets. Comparing two functions for equality, both of whose type is the same parenthesization of p_1 --> p_2 --> ... --> p_n, does make sense, but it has nothing to do with moving around the parens. -- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
I think Mike is thinking of my question in a different way than I intended. If p, q, and r range over the set {0,1}, then (p-->q)-->r is one Boolean function on {0,1}^3 and p-->(q-->r) is another; they are different ternary Boolean functions because they have different truth-tables. Do all five of the Boolean functions obtained by parenthesizing p-->q-->r-->s have distinct truth-tables? What about the fourteen Boolean functions obtained by parenthesizing p-->q-->r-->s-->t? Etc. Jim Propp On Fri, Dec 1, 2017 at 11:09 AM, Mike Stay <metaweta@gmail.com> wrote:
On Fri, Dec 1, 2017 at 8:52 AM, James Propp <jamespropp@gmail.com> wrote:
A different kind of "exponentiation" is logical implication (-->), which has the same relation to conjunction that exponentiation has to multiplication, inasmuch as the equivalence between p --> (q --> r) and (p and q) --> r resembles the equality between (c^b)^a =and c^(ba).
This isomorphism is called "Currying" after Haskell Curry. It works in any monoidal closed category. In particular, as you suggest below, by the Curry-Howard isomorphism logical implication corresponds to the "arrow type" or internal hom in the category of sets and functions.
Do all the Catalan-many parenthesizations of p_1 --> p_2 --> ... --> p_n yield distinct Boolean functions?
That doesn't quite parse. The expression with arrows in it is a type, which describes a set of functions. You could ask whether any two parenthesizations of p_1 --> p_2 --> ... --> p_n are equal as sets, but that's a category-theoretic "evil", since it depends on the representation you choose; instead you can ask whether the sets are isomorphic. The answer is yes; for example,
(3^(3^3))^(((3^3)^3)^3) = (((3^3)^3)^3)^(3^(3^3))
thought of combinatorically exhibits an isomorphism between the sets.
Comparing two functions for equality, both of whose type is the same parenthesization of p_1 --> p_2 --> ... --> p_n, does make sense, but it has nothing to do with moving around the parens.
-- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On Fri, Dec 1, 2017 at 10:01 AM, James Propp <jamespropp@gmail.com> wrote:
I think Mike is thinking of my question in a different way than I intended.
If p, q, and r range over the set {0,1}, then (p-->q)-->r is one Boolean function on {0,1}^3 and p-->(q-->r) is another; they are different ternary Boolean functions because they have different truth-tables.
Do all five of the Boolean functions obtained by parenthesizing p-->q-->r-->s have distinct truth-tables?
What about the fourteen Boolean functions obtained by parenthesizing p-->q-->r-->s-->t?
Oh, I see, sorry. The truth value of the implication p_1 --> p_2 --> ... --> p_n is itself a function 2^n -> 2, and you'd like to compare different functions of that signature. I don't know, offhand. I need to think about it. -- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
participants (4)
-
Allan Wechsler -
James Propp -
Mike Stay -
Tom Karzes