This paper considers two distinct procedures to lexicographically compose two criteria for social or individual decision making. The first procedure composes two binary relations into one, and then selects its maximal elements. The second procedure first selects the set of maximal elements of the first binary relation, and then within that set, chooses the maximal elements of the second binary relation. We show several distinct sets of conditions for the choice functions representing these two procedures to satisfy non-emptiness and choice-consistency conditions such as contraction consistency (Chernoff, 1954) and path independence (Arrow, 1963). We also examine the relationships between the outcomes of the two procedures. Then, we investigate under what conditions the outcomes of each procedure is independent of the order of lexicographic application of two criteria. Examples for applications of the results in the economic environments are also presented.