Re: Semigroup problem

On May 12, 7:16 am, William Elliot <ma...@xxxxxxxxxxxxxxxxxx> wrote:
On Sun, 11 May 2008 marc...@xxxxxxxxx wrote:

Let * be a semigroup operation that satisfies the following
properties:

all z exists x exists y (x * y = z).
all x all y (F(x) * G(y) = y * x).

The problem is: prove that * is commutative or find a counterexample
(finite if it is possible) to this claim.

Yes, we're interested in this problem. Are you?

Assume we work in first-order logic with equality. I will use “all”
for the universal quantifier and “exists” for the existential
quantifier. The symbol != denotes inequality. F and G are functions of
arity 1. * is function of arity 2. I will use infix notation for *. (%
will be a symbol for comment)

The axioms are:

all x all y exists z (x * y = z). % Closure
all x all y all z (x * (y * z) = (x * y) * z). % Associativity
all z exists x exists y (x * y = z). % Surjectivity
all x all y (F(x) * G(y) = y * x). % “Weak
commutativity”

On the ground of these axioms only try to prove:
all x all y (x * y = y * x). % Commutativity

Or try to find a model (finite if it’s possible) in which holds:
exists x exists y (x * y != y * x). % Non-commutativity

Marc
.

Relevant Pages

  • Re: Theories and (denumerable) models
    ... Let K be the predicate calculus with equality (i.e. in particular, ... toghether with the rest of the equality axioms). ... K has a denumerable model. ...
    (sci.logic)
  • Re: tedious sledding re set existence in FOL
    ... >>> forall x, forall y, forall z ... >>without equality, says that if x and y have the same members, they ... If you start out with the usual definition of set equality ... predicate) that actually uses the other axioms was a GOOD ...
    (sci.logic)
  • Re: Uncountable sets in CZF?
    ... What are the axioms? ... The first equality is presumably definition. ... empty theory. ... Sorry, Ross, wasting a little time on Usenet with you is already more ...
    (sci.math)
  • Re: PBZ: nonstandard math
    ... That model satisfies the two axioms, ... more than 120 degrees along the shortest arc separating them. ... satisfy the axioms and also eliminate the transitive property of equality. ...
    (sci.math)
  • Beginners Q: How to derive (x)(Ey)(x=y)
    ... from first order predicate calculus with equality, ... not necessarily all, free occurrences of x by y, and y is free for x. ... All Propositional Tautologies ...
    (sci.logic)
Loading