Sam Hardin

Answered

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(A\times \mathbb{N})$ 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\times 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$ $(x,y)\in M$, i.e. for every $x\in A$ there exists (at least) one $y\in N$, so that $(x,y)\in M$.

In this exercise, we are dealing with Tuple sets.

So let $M\subset P(A\times \mathbb{N})$ 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\times 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$ $(x,y)\in M$, i.e. for every $x\in A$ there exists (at least) one $y\in N$, so that $(x,y)\in M$.

Answer & Explanation

Maggie Bowman

Expert

2022-07-04Added 14 answers

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 $({m}_{1},{m}_{2})\in M\times 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 $(1,2),(1,2,3,4)\in M$, how would $(1,2)+(1,2,3,4)$ 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).

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 $({m}_{1},{m}_{2})\in M\times 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 $(1,2),(1,2,3,4)\in M$, how would $(1,2)+(1,2,3,4)$ 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).

Most Popular Questions