Object permanence for children is interesting but not the best example. Far more interesting is the fact that children fundamentally don't understand geography at a young age because they can't see it and have to imagine it, and geography breaks something down into types (city, village, country etc.) and there's a hierarchy. Understanding geography is close to the sorts of abstract thinking required of programming.

Small children have a great deal of problems with "Paris is in France. We are in Paris." They also have almost no concept of distance as related to geography because they have no internal map of the world. So when you drive out of Paris you are still in France, but if you drive over the border into Belgium you are in another country.

So, teach kids geography.

I experienced this while teaching LOGO to small children (yes, this was years ago). Given a LOGO turtle and a set of instructions it's fascinating to watch them work out how to draw a square.

PS You might think showing small children a map or satellite view would help, but it doesn't help (much) because they have no internal way of breaking down the data presented into what they experience.