1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.