Monday 17 March 2008

What is this Property?

I'm not a mathematician, just a computer scientist with an interest in maths, so please excuse the simplifications and inaccurarcies in this. I'm going to describe this with some rigour, but I'm bound to get things slightly wrong, please bear with me.

In maths, a function is defined as a relation between the members of two sets, S and R, that produces members of the third set T. Looking at it another way, the set T is defined by the function. Some functions, taking two arguments from the same set S, always produce members of that set S. Addition across the natural numbers is an example of that: for any two numbers greater than 0, the sum will always be a number greater than 0. There are many functions that behave like this.

Functions have properties. A property describes a rule that a function obeys for given sets of parameters. From a mathematics perspective, these properties are interesting. For example, addition across the natural numbers is associative. This means that no matter what order the parameters to the addition function are arranged, the answer will be the same: 2 + 3 = 3 + 2. Fairly simple and obvious, right? But from the same property we can also say 2 + (5 + (6 + 11)) = (2 + (5 + 6) + 11). This is interesting because once we know that a function has the associative property we can arrange the parameters of the function without changing the meaning: this is useful in proofs.

There are many, many of these properties, and most of the interesting ones have names: associative, commutative, distributive. For the last year I've been trying to find out if another property I've noticed also has a name.

Take the function minimum across the natural numbers. Given the sets {4, 6, 100, 1, 43} and {1} minimum gives the same answer: 1. The result of the function minimum is determined by only a single member of the set, no matter how large the set.

Take the function and across the booleans. Given the set {true, true, true, false, true} the answer is false. It doesn't matter how many true's are in the set, the answer will always be false.

And I'm sure you can imagine other functions that behave like this. My question is: does this property have a name, and if it does, what?

If I was more of a mathematician, I'm sure I could actually describe this property a lot more accurately. In fact, I'm not entirely sure there is a consistent property here, and I have no idea if it's interesting if it does exist. But I notice this often, and it sure feels like it should have a name.

Functions whose result is determined by a single member of the parameter set, irrespective of the size of that set: do these have a common property?

1 comment:

Robbie said...

Note that both your examples, while looking like functions on sets, are actually the unique extension of a commutative associative binary operation.

In fact, they're both the same example - and is really "min" applied to {false, true} where false < true.

For binary operations, the property boils down to a op b being one of a or b. This makes it feel a lot like min (or max if you're left handed).

I feel like i've seen a name in an old set theory book i can't find right now, and all my attempts to google my guesses have turned up other things.