What would make a function reflexive, transitive, and/or symmetric?

Question

A binary relation $R$ is a subset of the Cartesian product between two sets $X$ and $Y$, containing a set of ordered pairs $\{(x,y) : x \in X, y \in Y\}$. $R$ is a function if each element of $X$ is the first component of at most one ordered pair, injective if each element of $Y$ is the second component of at most one ordered pair, surjective if each element of $Y$ is the second component of at least one ordered pair, and bijective if it is both injective and surjective. Surjectivity and injectivity are independent of functionality; eg, a relation can be surjective and/or injective without being a function, as they are not composite relation types like bijections and equivalence relations.

So, can a function also be symmetric, transitive, total and/or reflexive? Would the definitions then, for a function $f : X \rightarrow Y$, be:

• Symmetric: $f(x) = y \rightarrow f(y) = x$
• Transitive: $f(x) = y, f(y) = z \rightarrow f(x) = z$
• Total: $f(x) = y \lor f(y) = x$
• Reflexive: $f(x) = x$

Intuitively, the identity function $f(x) = x$ is all of these, $f(x) = -x$ is total and symmetric, no injection is transitive, no function is transitive if $x \neq y \neq z$, and every surjective function is total, but are there others? Is there an arithmetic function between numbers that's symmetric, or that's transitive, or both? If so, what is it (or are they) and if not, why not?

Answer 1

Here are some ideas that can help: For $f:\mathbb{R} \longrightarrow \mathbb{R}$ to be symmetric you need $f(f(x))=x$ (because we need if $(x,y) \in f$, then $(y,x) \in f$. Now functions of the form $f(x)=x$ and $f(x)=-x+c$ will satisfy this condition.

Answer 2

I would prefer to speak about a "functional relation" here rather than a "function", because the latter wording implies that the only thing you're planning to do with it is to apply it to inputs, and here you're doing something quite different.

That being said, here are some comments on your observations:

$f(x)=−x$ is total and symmetric,

In general a function whose relational representation is symmetric is known as an involution. Written functionally, the condition is $f(f(x))=x$ for all $x$ in the domain.

no injection is transitive

The identity function is an injection whose relation is transitive.

every surjective function is total

No. For example $f(x)=x+1$ is surjective $\mathbb R\to \mathbb R$, yet we have neither $f(\pi)=235$ nor $f(235)=\pi$.

If "total" is taken to imply reflexivity, the only functions whose relations are total are the empty function and the unique function $\{x\}\to \{x\}$ for a singleton set $\{x\}$.

If "total" means only that different elements must be related one way or the other (such that, e.g., "$<$" counts as a total order), we also get (a) constant functions when $|X|=2$, and (b) cyclic permutations of a set with 2 or 3 elements.

no function is transitive if $x\ne y\ne z$

We don't speak about a relation being transitive for a particular triple of $(x,y,z)$. It's the entire relation that is either transitive or not, meaning that the property has to hold for all such triples.

In functional notation, "transitive" comes down to $f(f(x))=f(x)$ -- in other words, whether the function is idempotent.

---

$f(x)=|x|$ is an example of a function that is idempotent ("transitive") but not an involution ("symmetric").

$f(x)=-x$ is an involution ("symmetric") but not idempotent ("transitive").

The only function $X\to X$ that is both idempotent and an involution is the identity function.

Answer 3

The identity function $1_X \colon X \to X$ on a set $X$ induces an equivalence relation on $X$ since it partitions $X$ into its singleton sets.

A function $f \colon X \to X$ is symmetric if and only if $f(f(x))=x$ for all $x \in X$, so $f$ must be an involution, which is to say $f^2 = 1_X$.

If $\lvert X \rvert > 2$, then $f \colon X \to X$ cannot be total. In particular any total relation is reflexive. If $f(x) \neq x$ for some $x \in X$, then $x$ is not related to $x$, so $f$ is not reflexive. So the only possible total function is the identity $1_X$. But the identity function cannot relate two distinct elements $x \neq y$.