Given 2 sets (X and Y) is it possible for $f: Y \to X $ to be a relation, or not?

Question

This question is from my Computational Theory course's homework. I completely understand functions and relations (I've taken numerous Calculus courses).

Here's a general example of what the question is asking:

We have 2 sets ($X$ and $Y$)

$X = \{1, 2, 3\}$

$Y = \{A. B, C\}$

So my question is as follows: is $\{(A,1), (B,2), (C,3)\}$ able to be function/relation? In other words, is going from $Y \to X $ rather than $X \to Y$ still able to be a function/relation, or does going from the co-domain to the domain not legal? I understand that a relation is a subset of $X\times Y$ (Cartesian product), but unsure of whether or not a subset of $Y\times X$ is.

Now, if the question were asking what $\{(1,A), (2,B), (3,C)\}$ is, I understand that it is a total function that is both onto and one to one. Does the same apply if the inputs/outputs are flipped? I could be over thinking this, but having the possible answer of the sets not being a relation is causing me to second guess myself.

Answer 1

In my opinion, it is vital to make clarifications. What do you mean by function? Function in the Discrete Mathematics (and in Calculus) is a relation from some domain to a co-domain with the following property $$ x_1 = x_2 \rightarrow f(x_1) = f(x_2)$$ where the function is represented by $f$. In other words, a function is a relation which maps not more than one element of co-domain in any element of domain. On the other side, in computational complexity theory, by function we do not mean such a thing, e.g. assume non-deterministic functions or probabilistic functions. By a function we mean a relation from some domain to some other co-domain. The way this map is defined is by a set of rules, known as algorithm. There might be functions which are not computable, e.g. Halting problem.

And at last, answering your question, I think you are asked to see if a function is computable or not! Not to check whether it is a function. I hope this helps you.

Update: Looking from the other side, if you want to ask whether or not the inverse is a function in calculus terms, the answer is "it depends"! Why? Since it cannot be a function if the function from domain to co-domain is not one-to-one.

Moreover, in Computational Complexity term, it might be or not a function, look at one-way functions for example which are not reversible.

Answer 2

A (binary) relation is a subset of a Cartesian product of two sets, no matter what name we happen to give those two sets. Indeed, given a relation $R,$ we have that $R\subseteq\operatorname{dom}(R)\times\operatorname{rng}(R).$ On the other hand, if $R\subseteq A\times B$ for some sets $A,B$ then $R$ is a relation.

In your particular example, this means that every subset of $X\times Y$ and every subset of $Y\times X$ is a relation.

Now, a relation $R$ is a function if and only if for every $a\in\operatorname{dom}(R)$ there exists a unique $b\in\operatorname{rng}(R)$ such that $(a,b)\in R.$ Note that $\{(1,A),(2,B),(3,C)\}$ and $\{(A,1),(B,2),(C,3)\}$ both satisfy this condition, so both are functions. The first is a function $X\to Y$ (read "from $X$ into $Y$") and the second is a function $Y\to X$ (read "from $Y$ into $X$")--both are perfectly fine.