The term "Object-Orientation" was coined by Dr. Alan Kay, so he is the authoritative source on what it means, and he defines it thus:
OOP to me means only messaging, local retention and protection and hiding of state-process, and extreme late-binding of all things.
Let's break that down:
- messaging ("virtual method dispatch", if you are not familiar with Smalltalk)
- state-process should be
- locally retained
- protected
- hidden
- extreme late-binding of all things
Implementation-wise, messaging is a late-bound procedure call, and if procedure calls are late-bound, then you cannot know at design time what you are going to call, so you cannot make any assumptions about the concrete representation of state. So, really it is about messaging, late-binding is an implementation of messaging and encapsulation is a consequence of it.
He later on clarified that "The big idea is 'messaging'", and regrets having called it "object-oriented" instead of "message-oriented", because the term "object-oriented" puts the focus on the unimportant thing (objects) and distracts from what is really important (messaging):
Just a gentle reminder that I took some pains at the last OOPSLA to try to remind everyone that Smalltalk is not only NOT its syntax or the class library, it is not even about classes. I'm sorry that I long ago coined the term "objects" for this topic because it gets many people to focus on the lesser idea.
The big idea is "messaging" -- that is what the kernal of Smalltalk/Squeak is all about (and it's something that was never quite completed in our Xerox PARC phase). The Japanese have a small word -- ma -- for "that which is in between" -- perhaps the nearest English equivalent is "interstitial". The key in making great and growable systems is much more to design how its modules communicate rather than what their internal properties and behaviors should be. Think of the internet -- to live, it (a) has to allow many different kinds of ideas and realizations that are beyond any single standard and (b) to allow varying degrees of safe interoperability between these ideas.
(Of course, today, most people don't even focus on objects but on classes, which is even more wrong.)
Messaging is fundamental to OO, both as metaphor and as a mechanism.
If you send someone a message, you don't know what they do with it. The only thing you can observe, is their response. You don't know whether they processed the message themselves (i.e. if the object has a method), if they forwarded the message to someone else (delegation / proxying), if they even understood it. That's what encapsulation is all about, that's what OO is all about. You cannot even distinguish a proxy from the real thing, as long as it responds how you expect it to.
A more "modern" term for "messaging" is "dynamic method dispatch" or "virtual method call", but that loses the metaphor and focuses on the mechanism.
So, there are two ways to look at Alan Kay's definition: if you look at it standing on its own, you might observe that messaging is basically a late-bound procedure call and late-binding implies encapsulation, so we can conclude that #1 and #2 are actually redundant, and OO is all about late-binding.
However, he later clarified that the important thing is messaging, and so we can look at it from a different angle: messaging is late-bound. Now, if messaging were the only thing possible, then #3 would trivially be true: if there is only one thing, and that thing is late-bound, then all things are late-bound. And once again, encapsulation follows from messaging.
Similar points are also made in On Understanding Data Abstraction, Revisited by William R. Cook and also his Proposal for Simplified, Modern Definitions of "Object" and "Object Oriented".
Dynamic dispatch of operations is the essential characteristic of objects. It means that the operation to be invoked is a dynamic property of the object itself. Operations cannot be identified statically, and there is no way in general to exactly what operation will executed in response to a given request, except by running it. This is exactly the same as with first-class functions, which are always dynamically dispatched.
In Smalltalk-72, there weren't even any objects! There were only message streams that got parsed, rewritten and rerouted. First came methods (standard ways to parse and reroute the message streams), later came objects (groupings of methods that share some private state). Inheritance came much later, and classes were only introduced as a way to support inheritance. Had Kay's research group already known about prototypes, they probably would have never introduced classes in the first place.
Benjamin Pierce in Types and Programming Languages argues that the defining feature of Object-Orientation is Open Recursion.
So: according to Alan Kay, OO is all about messaging. According to William Cook, OO is all about dynamic method dispatch (which is really the same thing). According to Benjamin Pierce, OO is all about Open Recursion, which basically means that self-references are dynamically resolved (or at least that's a way to think about), or, in other words, messaging.
As you can see, the person who coined the term "OO" has a rather metaphysical view on objects, Cook has a rather pragmatic view, and Pierce a very rigorous mathematical view. But the important thing is: the philosopher, the pragmatist and the theoretician all agree! Messaging is the one pillar of OO. Period.
Note that there is no mention of inheritance here! Inheritance is not essential for OO. In general, most OO languages have some way of implementation re-use but that doesn't necessarily have to be inheritance. It could also be some form of delegation, for example. In fact, The Treaty of Orlando discusses delegation as an alternative to inheritance and how different forms of delegation and inheritance lead to different design points within the design space of object-oiented languages. (Note that actually even in languages that support inheritance, like Java, people are actually taught to avoid it, again indicating that it is not necessary for OO.)