Upper bound on the size of a Concept Lattice (Galois Lattice)? A context is a tuple $(O, A, R)$ where $O$ is the set of objects, $A$ the set of attributes and $R \subseteq O\times A$ is a relation. For $o \in O$ and $a \in A$ we read $oRa$ as the object $o$ possesses the attribute $a$.

For $P \subseteq O$ and $B \subseteq A$ we define $P'=\{a \in A |  \forall o \in P \, oIa \}$ and $B'=\{o \in O |  \forall a \in B \, oIa \}$.

$P'$ is the set of attributes shared by all object of $P$ and $B'$ is the set of objects having all the attributes of $B$.

A concept of the context $(O, A, R)$ is a couple $(P, B)$ where $P \subseteq O$ and $B \subseteq A$ such that $P'=B$ and $P=B'$.

The concepts may be organised according to a partial order in a structure called a concept lattice (or "galois" lattice). For more info check the wikipedia page on Formal Concept Analysis.

The number of concepts in a concept lattice is bounded by :


$2^{1+\sqrt{|R|}}$ as told in this paper (which mentions a result from this paper in german). Note that their upper bound is tighter - the one I give here is less precise.
$2^{|O|+|A|}$ according to this paper (which is presented as a trivial easy upper bound).


I dont understand why these upper bounds are that large.
Intuitively I would say that the number of concepts is bounded by $min(2^{|O|}, 2^{|A|})$. I get this intuition from the observation that since for any pair of concepts $(P_0, B_0)$ and $(P_1, B_1)$ we have $P_0=P_1$ iff $B_0=B_1$, then there can not be more concepts than the number of object sets neither than the number of attribute sets appearing in the lattice.

Could someone explain me if I did a mistake ?

Many thanks, Luz
As told in the previous comments, $min\{2^{|O|}, 2^{|A|}\}$ is a correct upper bound. 

When the parameter $R$ is also available, we can improve the upper bound to $min\{2^{|O|}, 2^{|A|}, 2^{1+\sqrt{|R|}}\}$