Sam Hardin

2022-07-03

Prove if a relation is left-total and right-unique
In this exercise, we are dealing with Tuple sets.
So let $M\subset P\left(A×\mathbb{N}\right)$ be the set of all legal tuple sets. P (X) denotes the power set of a set X. Now, Let the tuple set operation be defined as $+$ so that $+$: $M×M\to M$.
Prove or disprove that + is left-total and right-unique.
These types of relations are uncommon in English, it seems. So, it's a bit difficult for me to understand how to prove it.
To my knowledge, a left-total relation means that, e.g. if $\mathrm{\forall }x\in A$ $\mathrm{\exists }y\in N$ $\left(x,y\right)\in M$, i.e. for every $x\in A$ there exists (at least) one $y\in N$, so that $\left(x,y\right)\in M$.

Maggie Bowman

Expert

Step 1
Note that $+$ is a function, and functions are just special cases of relations.
Hence, for left-totality of $+$, you wish to show that for any pair $\left({m}_{1},{m}_{2}\right)\in M×M$, that we can find $m\in M$ where ${m}_{1}+{m}_{2}=m$ (to use the usual conventions for operations). That is, essentially, left-totality for function relations amounts to ensuring each input has an output.
Step 2
At present, this is not satisfied. How would you define ${m}_{1}+{m}_{2}$ for two tuples of different sizes? (I assume we add them in the "usual" way, namely pointwise.) For instance, if $\left(1,2\right),\left(1,2,3,4\right)\in M$, how would $\left(1,2\right)+\left(1,2,3,4\right)$ be defined? In fact even if M is limited to tuples of the same size, you won't necessarily have the desired property unless A is closed under addition.
Right-uniqueness is another property expected of functions (notice how these two relate? We're showing + is a function!); namely, any input goes to at most one output. Whenever the addition of tuples is defined, then it inherits this property from that of the addition of elements of + (if present).

Do you have a similar question?