Prove if a relation is left-total and right-uniqueIn this exercise, we are dealing with Tuple...

Sam Hardin

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 P ( A × 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 × M 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 x A y N ( x , y ) M, i.e. for every x A there exists (at least) one y N, so that ( x , y ) M.

Answer & Explanation

Maggie Bowman

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 ) M × M, that we can find m 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 ) 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).

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get your answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?