Thread: properties of functions problem

Let S be a set and A, B and C be finite subsets of S. Consider the functions:
I. sum(numbers) = sum of the numbers
II. count(A) = number of elements in A
III. int(A, B) = intersection of A and B
IV. uni(A, B) = union of A and B
V. dif(A, B) = difference of A and B
Then,
a) Write the type of each of the previous functions
b) Express each the counting rules for
i. A – (B U C)
ii. A U B U C
iii. A – B
as compositions of the previous functions
c) For each of these compositions: are they injective? Are they onto?


I have no clue how to approach this problems any suggestions??

a) The type probably means the domain (the set from which a function takes input) and codomain (what the function returns). E.g., for count, the input is a finite set and the output is a natural number. I would write this as

count: FinSet -> nat

where FinSet (or choose another name) is the collection of finite sets and nat is the set of natural numbers.

For int (intersection), there are two inputs and one output, all of which are finite sets. (Aside: intersection, of course, is defined not only on finite sets, but this seems to be the setting of this problem. This also avoids some technical difficulties because "the collection of all sets" is not really a set, while "the collection of finite sets" is a set.) There are several ways to write it, and the right way is just a convention that is used in your course, e.g.:

int: FinSet, FinSet -> FinSet
int: FinSet x FinSet -> FinSet
int: FinSet -> FinSet -> FinSet

The first notation just says that there are two arguments. In the second variant, x is Cartesian product, which produces the set of pairs. The third variant may be used in some programming languages.

I am not exactly sure about the sum function because its argument is written as "numbers" and not as a set, say, A, like for count. The question is whether the same argument used twice is also summed twice. If so, then the argument is not a set (but a multiset) because in a set each element occurs only once.

b) It's a little strange. "Express each the counting rules for..." First, should it say "each of the"? Second, what is a "counting rule"? My best guess is that you need to write functions that return the sizes of the given sets. E.g., for A – (B U C) it is probably

count(dif(A, uni(B, C)))

Let's call this function f(A, B, C).

c) This question seems to be clear. For example, to determine if the function f above is injective or not, you need to find out if there are two different triples of sets: (A1, B1, C1) and (A2, B2, C2) such that f(A1, B1, C1) = f(A2, B2, C2). An equivalent question is, given n such that f(A, B, C) = n, can you reconstruct uniquely A, B, and C? This seems unlikely.

This is my guess; you may want to ask the instructor about what exactly has to be done. It does not mean that you don't know how to solve the question because first you need to be sure what the question is.