What Kind of Common Properties Does This Function Exhibit

Question

Suppose I have a function. Let's call it $f.$ I can describe some of its behavior in words. What I am wondering about is whether some of this behavior can be summarized by some known types of relations such as Reflexivity, transitivity, idempotency, and so on. In essence, I am trying to learn about the properties of this function.

Here is what I do know.

1. The function has a variable but FINITE arity; The order of arguments does not matter (commutative?); for my purposes, f(A) is equivalent to A. That is, when there is only one argument, it is the same as if the function has not been applied. When there is more than one argument, the function application "glues" these arguments together into a new entity. This is similar to set-union;.

2. f(f(A)) => A

3. f(f(A,B)) => f(A,B)
4. f(A,f(B)) => f(A,B)
5. f(f(A,B,C,...)) => f(A,B,C,...)

Some of the properties I listed may be redundant. As you can see, this is something resembling an idempotent function and a set-union function. What else can be said about it?

I would also be interested in how one could reduce the properties described above to a smaller set of axiomatic rules/properties from which the above can be reconstructed and built.

Answer 1

Let $X$ be some set and $X^*$ its Kleene star, i.e. the set or arbitrarliy long finite tuples of elements from $X$. Then $f$ can be considered a function $X^*\to X$. We can reduce the axioms to

1. $f$ is totally commutative, i.e. $f(x_1,...,x_n)=f(x_{\sigma(1)},...,x_{\sigma(n)})\;$ for any permutation $\sigma$.
2. $f(x)=x$.

To see that any of these axioms is completely necessary, lets look for functions which satisfy all of these axioms but one to show that none follows from the others. For this matter we denote by $f_i$ a function which follows all axioms but axiom $i$.

• Let $X=A^*$ for some alphabet $A$. Then $f_1$ can be chosen as concatenation. For example $$f(a,b,c,d)=abcd\in X.$$ Note that $abcd$ is considered a single element of $X$ and not a quadrupel. Concatenation is not commutative.
• Let $f_2$ be set-union, except that the union of a single set is $\varnothing$.

Set union would be one example function which follow above axioms. Other examples would be addition and multiplication where we can choose $X=\Bbb R$.