Why finiteness counts

Becoming aware of Finite Model Theory. Part 1 of n.

You arrive at a hotel, looking for a room. Unfortunately all rooms are occupied. Fortunately the hotel has countably infinite many rooms. So they move the guest of room 1 to room 2, guest of room 2 to room 3 etc so you can check in to room 1. (better don´t unpack your suitcase, in case the next guest arrives)

So compared to the real world the hotel doesn’t have to manage the occupation of its rooms, therefore it has to handle infinity, i.e. if one wants to deal with the above on a scientific level, one must be able to capture the concept of infinity formally.

Finite hotels (as well as ‘finite scientists’) don’t have to care about infinity; therefore they have to deal with the complexity of managing occupation. This can be done by keeping track of the number of empty rooms or by looking up all rooms for an empty one each time a guest arrives. The first approach is space consuming (since they have to write down the number empty rooms somewhere (i.e. space can be a piece of paper)). Instead the second approach requires time to go and check the rooms.

Thus there are two mutually exclusive things that can make occupation management interesting: infinity with all its ‘strange’ effects and the complexity (effort) of keeping track of ‘what’s going on’.

PS
Or how Neil Immerman puts it: “In the history of mathematical logic most interest has concentrated on infinite structures….Yet, the objects computers have and hold are always finite. To study computation we need a theory of finite structures.”

Modeling Theory and Abstraction Awareness in the gap btw rigour of science and relevance to engineering.
This entry was posted in Mathematics and tagged , , , , , , , , , , , , , , , . Bookmark the permalink.

9 Responses to Why finiteness counts

1. just me says:

or Ron Fagin: “… I take the direct product of an infinite family of relations, each of which has at least two tuples; so, the result is not only infinite but even uncountable. I shudder to think of a database practitioner’s reaction to an uncountable database!”

[Finite-model theory - a personal perspective]

2. wirosankis says:

Nice little example

3. TOTALLY AGREE!

4. unlisseMefs says:

Did you know, there’s a movie bout this as well.