Timeline for Deriving a relation in a group based on a presentation
Current License: CC BY-SA 2.5
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 13, 2010 at 20:52 | comment | added | Joel David Hamkins | Sridhar, Yes, I agree. And I think there is a general universal-algebraic theorem along these lines also, about deriving equations from other equations. Yet, with both methods in the general case you basically have c.e. sets that are Turing equivalent to the halting problem, so there is a fundamental equivalence in the methods from the prespective of computability. | |
| Feb 13, 2010 at 20:15 | comment | added | Sridhar Ramesh | Goedel's completeness theorem for full first-order logic certainly works, but we hardly need go that far. Of course if x^6 = 1, it can be derived from this presentation, and purely by equational/algebraic reasoning from the specified relations on the generators and (instances of) the group identities. Why? Because we can clearly take a quotient of the free group on these generators which imposes all and only the relations which can be derived in this manner, and, pretty much by definition, that resulting group is the one referred to by this presentation. | |
| Feb 13, 2010 at 16:32 | comment | added | Steve Huntsman | One could attack this with simulated annealing. Take $(2q)$-ary strings representing presented elements of a group with $q$ generators, then run a parser to replace a substring chosen uniformly at random from the substrings in a (growable) database of words equal to the identity. If the resulting word is shorter, keep it. If it is longer, keep it with probability given by a Gibbs factor. Run this until you get your desired word in the database. Does anyone know if (something like) this might be more efficient than deterministic approaches? | |
| Feb 13, 2010 at 16:16 | comment | added | Joel David Hamkins | Yes, if one has a computable (same as recursive=old fashioned terminology) set of axioms, then the set of theorems will be computably enumerable, since one can search through all possible proofs in a formal proof system. For example, one can computably enumerate all possible Tietze transformations, and if there is one leading to the desired identity, you will eventually find it, so this gives a computable procedure. Of course, this method is useless in practice, but it does show that the general problem is computable. The computer systems you mention, for example, use much better algorithms. | |
| Feb 13, 2010 at 16:06 | comment | added | Steve D | I like it! I do have a question about your last paragraph. The relations which hold in my group are a recursive set (is the same as what you said?), so is it also true the sequence of Tietze transformations to arrive at any relation is also a recursive set? So when you say "search through... all proofs", we can actually enumerate all possible paths to proving this relation? | |
| Feb 13, 2010 at 15:42 | history | answered | Joel David Hamkins | CC BY-SA 2.5 |