Economic

Binary Relations

Dr Damien S. Eldridge

Australian National University

20 February 2021

D. S. Eldridge (ANU) Binary Relations 20 February 2021 1 / 24

Readings 1

Corbae, D, MB Stinchcombe, and J Zeman (2009), An introduction to mathematical analysis for economic theory and econometrics, Princeton University Press, USA: Chapter 2 (pp. 15-71).

Kolmogorov, AN, and SV Fomin (1970), Introductory real analysis (revised English edition), Translated and Edited by RA Silverman, Dover Publications, USA: Chapter 1 (pp. 1-36).

Gravelle, H, and R Rees (1981), Microeconomics, Longman Group, Hong Kong: Chapter 3 (pp. 55-95).

D. S. Eldridge (ANU) Binary Relations 20 February 2021 2 / 24

Readings 2

Kreps, DM (1990), A course in microeconomics, Harvester Wheatsheaf, Great Britain: Chapter 2 (pp. 17-69).

Mas-Colell, A, MD Whinston and JR Green (1995), Microeconomic theory, Oxford University Press, USA: Chapters 1-3 (pp. 5-104).

Rubinstein, A (2006), Lecture notes in microeconomic theory: The economic agent, Princeton University Press, USA: Chapters 1-4 (pp. 1-51).

Varian, HR (1992), Microeconomic analysis (third edition, WW Norton and Sons, USA: Chapter 7 (pp. 94-115).

D. S. Eldridge (ANU) Binary Relations 20 February 2021 3 / 24

Definition of a Binary Relation

A binary relation R on a set A compares two elements from the set A.

Formally, a binary relation on the set A is a non-empty subset of the Cartesian Product A×A.

In other words, R ⊆ A×A such that R 6= ∅. If the binary relation holds for the particular elements a ∈ A and b ∈ A, this is denoted by either (a, b) ∈ R or aRb.

If (a, b) ∈ R, then (a, b) is called a “labelled pair” for the binary relation R.

D. S. Eldridge (ANU) Binary Relations 20 February 2021 4 / 24

“Less Than Or Equal To” Relation Example

Table: Graphical Representation of the Relation “Less Than or Equal To” (≤) on the set 𝟏,𝟐,𝟑,𝟒,𝟓 × 𝟏,𝟐,𝟑,𝟒,𝟓 .

𝒙 ≤ 𝒚

𝒚

1 2 3 4 5 𝒙

1 ü ü ü ü ü 2 ü ü ü ü 3 ü ü ü 4 ü ü 5 ü

Table: Graphical Representation of the Relation “Strictly Less Than” (<) on

the set 𝟏,𝟐,𝟑,𝟒,𝟓 × 𝟏,𝟐,𝟑,𝟒,𝟓 .

𝒙 < 𝒚

𝒚 1 2 3 4 5

𝒙

1 ü ü ü ü 2 ü ü ü 3 ü ü 4 ü 5

Table: Graphical Representation of the Relation “Equal To” (=) on the set

𝟏,𝟐,𝟑,𝟒,𝟓 × 𝟏,𝟐,𝟑,𝟒,𝟓 .

𝒙 = 𝒚

𝒚 1 2 3 4 5

𝒙

1 ü 2 ü 3 ü 4 ü 5 ü

D. S. Eldridge (ANU) Binary Relations 20 February 2021 5 / 24

“Strictly Less Than” Relation Example

Table: Graphical Representation of the Relation “Less Than or Equal To” (≤) on the set 𝟏,𝟐,𝟑,𝟒,𝟓 × 𝟏,𝟐,𝟑,𝟒,𝟓 .

𝒙 ≤ 𝒚

𝒚

1 2 3 4 5 𝒙

1 ü ü ü ü ü 2 ü ü ü ü 3 ü ü ü 4 ü ü 5 ü

Table: Graphical Representation of the Relation “Strictly Less Than” (<) on

the set 𝟏,𝟐,𝟑,𝟒,𝟓 × 𝟏,𝟐,𝟑,𝟒,𝟓 .

𝒙 < 𝒚

𝒚 1 2 3 4 5

𝒙

1 ü ü ü ü 2 ü ü ü 3 ü ü 4 ü 5

Table: Graphical Representation of the Relation “Equal To” (=) on the set

𝟏,𝟐,𝟑,𝟒,𝟓 × 𝟏,𝟐,𝟑,𝟒,𝟓 .

𝒙 = 𝒚

𝒚 1 2 3 4 5

𝒙

1 ü 2 ü 3 ü 4 ü 5 ü

D. S. Eldridge (ANU) Binary Relations 20 February 2021 6 / 24

“Equal To” Relation Example

Table: Graphical Representation of the Relation “Less Than or Equal To” (≤) on the set 𝟏,𝟐,𝟑,𝟒,𝟓 × 𝟏,𝟐,𝟑,𝟒,𝟓 .

𝒙 ≤ 𝒚

𝒚

1 2 3 4 5 𝒙

1 ü ü ü ü ü 2 ü ü ü ü 3 ü ü ü 4 ü ü 5 ü

Table: Graphical Representation of the Relation “Strictly Less Than” (<) on

the set 𝟏,𝟐,𝟑,𝟒,𝟓 × 𝟏,𝟐,𝟑,𝟒,𝟓 .

𝒙 < 𝒚

𝒚 1 2 3 4 5

𝒙

1 ü ü ü ü 2 ü ü ü 3 ü ü 4 ü 5

Table: Graphical Representation of the Relation “Equal To” (=) on the set

𝟏,𝟐,𝟑,𝟒,𝟓 × 𝟏,𝟐,𝟑,𝟒,𝟓 .

𝒙 = 𝒚

𝒚 1 2 3 4 5

𝒙

1 ü 2 ü 3 ü 4 ü 5 ü

D. S. Eldridge (ANU) Binary Relations 20 February 2021 7 / 24

Proper Subset Relation Example

U = {1,2,3}. 2U = {∅,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}. A ∈2U are row set headings in the following table. B ∈2U are column set headings in the following table. A⊆B ∅ {1} {2} {3} {1,2} {1,3} {2,3} {1,2,3} ∅ Y Y Y Y Y Y Y Y {1} Y Y Y Y {2} Y Y Y Y {3} Y Y Y Y {1,2} Y Y {1,3} Y Y {2,3} Y Y {1.2,3} Y

D. S. Eldridge (ANU) Binary Relations 20 February 2021 8 / 24

Weak Subset Relation Example

U = {1,2,3}. 2U = {∅,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}. A ∈2U are row set headings in the following table. B ∈2U are column set headings in the following table. A⊂B ∅ {1} {2} {3} {1,2} {1,3} {2,3} {1,2,3} ∅ Y Y Y Y Y Y Y {1} Y Y Y {2} Y Y Y {3} Y Y Y {1,2} Y {1,3} Y {2,3} Y {1.2,3}

D. S. Eldridge (ANU) Binary Relations 20 February 2021 9 / 24

Set Equality Relation Example

U = {1,2,3}. 2U = {∅,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}. A ∈2U are row set headings in the following table. B ∈2U are column set headings in the following table. A=B ∅ {1} {2} {3} {1,2} {1,3} {2,3} {1,2,3} ∅ Y {1} Y {2} Y {3} Y {1,2} Y {1,3} Y {2,3} Y {1.2,3} Y

D. S. Eldridge (ANU) Binary Relations 20 February 2021 10 / 24

Potential Properties of Binary Relations

There are many potential properties that might be satisfied by some binary relations but not by others.

Some of these properties are inconsistent with others, so that no one binary relation can satisfy them all.

Some of these properties include the following.

Weak Completeness: If (a, b) ∈ A×A such that a 6= b, then either (a, b) ∈ R or (b, a) ∈ R or both. Strong Completeness: If (a, b) ∈ A×A, then either (a, b) ∈ R or (b, a) ∈ R or both. Reflexivity: If (a, a) ∈ A×A, then (a, a) ∈ R. Irreflexivity: If (a, a) ∈ A×A, then (a, a) /∈ R. Symmetry: If (a, b) ∈ R and a 6= b, then (b, a) ∈ R. Anti-Symmetry: If (a, b) ∈ R and a 6= b, then (b, a) /∈ R. Transitivity: If (a, b) ∈ R and (b, c) ∈ R, then (a, c) ∈ R.

D. S. Eldridge (ANU) Binary Relations 20 February 2021 11 / 24

Equivalence Relations

A binary relation R ⊆ A×A is called an “equivalence relation” on A if it is reflexive, symmetric and transitive.

If x ∈ A and R is an equivalence relation on A, then the “equivalence class for x” is defined as Ex = {a ∈ A : (a, x) ∈ R}. If Ex and Ey are both equivalence classes for an equivalence relation R defined on a set A, then either Ex = Ey or EX ∩Ey = ∅. We will denote the collection of all unique (that is “non-equal”) equivalence classes in the set A that are generated by the equivalence relation R as A/R.

Note that this expression uses a forward-slash, not a back-slash. The latter denotes set exclusion, which is a very different concept.

A partition of a set A is a collection of non-empty disjoint subsets of A whose union is all of A.

If R is an equivalence relation on A, then the collection A/R is a partition of A

D. S. Eldridge (ANU) Binary Relations 20 February 2021 12 / 24

Examples of Equivalence Relations

The equality relation (=) is an equivalence relation on N, Z, Q, R and C.

The set equality relation (=) is an equivalence relation on the power set 2A, where A = {1, 2, 3}. The indifference relation (∼) for an individual with rational preferences is an equivalence relation on the individual’s consumption set (X ).

This is an important equivalence relation in economics.

D. S. Eldridge (ANU) Binary Relations 20 February 2021 13 / 24

Ordered Sets

A binary relation R ⊆ A×A is said to be a partial ordering on the set A if it is reflexive, transitive and anti-symmetric.

If this is the case, then the set A is said to partially ordered by the binary relation R.

A binary relation R ⊆ A×A is said to be an ordering on the set A if it is reflexive, transitive, anti-symmetric and weakly complete.

Equivalently, a binary relation R ⊆ A×A is said to be an ordering on the set A if it is strongly complete, transitive and anti-symmetric. Note than an ordering is a partial ordering that is weakly complete. If this is the case, then the set A is said to ordered by the binary relation R.

An ordered set A is said to be “well ordered” if every non-empty subset of A has a unique smallest element.

That is, if X ⊆ A such that X 6= ∅, then there exists x̂ ∈ X such that x̂ < x for all x ∈ X .

D. S. Eldridge (ANU) Binary Relations 20 February 2021 14 / 24

Examples of Ordered Sets

Partially ordered sets.

The sets N, Z, Q and R are partially ordered by the equality relation (=). The power set 2A for any finite set A is partially ordered by the weak subset relation (⊆).

Ordered sets.

The sets N, Z, Q and R are ordered by the weak inequality relation >. he sets N, Z, Q and R are not ordered by the equality relation (=). The power set 2A for any finite set A is not ordered by the weak subset relation (⊆).

Well ordered sets.

The set N is well-ordered by the weak inequality relation >. The set {x ∈ Q : 0 < x < 1} is not well-ordered because there is no smallest rational number in this set. The set {x ∈ Q : 0 6 x 6 1} is not well-ordered because {x ∈ Q : 0 < x < 1}⊂ {x ∈ Q : 0 6 x 6 1} and there is no smallest rational number in the set {x ∈ Q : 0 < x < 1}.

D. S. Eldridge (ANU) Binary Relations 20 February 2021 15 / 24

Some Useful Results about Ordered Sets

Every non-empty subset of a well-ordered set is itself well-ordered.

The Cartesian product of two well-ordered sets is itself a well ordered set.

The Cartesian product of a finite number of well-ordered sets is itself a well-ordered set.

(The Well-Ordering Theorem): Every set can be well-ordered. (This was proved by Zermelo in 1904.)

(The Axiom of Choice): Given any set A, there is a “choice function” f such that f (X) ∈ X for every non-empty X ⊆ A

D. S. Eldridge (ANU) Binary Relations 20 February 2021 16 / 24

Rational Relations

A binary relation R ⊆ A×A is “rational” if it is weakly complete, reflexive and transitive.

Equivalently, a binary relation R ⊆ A×A is “rational” if it is strongly complete and transitive.

The reason for this is that a binary relation is strongly complete if it is both weakly complete and reflexive.

Some examples.

The weak inequality “less than or equal to” (6) is rational on N, Z, Q and R. The weak inequality “less than or equal to” (>) is rational on N, Z, Q and R. The strict inequality “less than” (6) is not rational on N, Z, Q and R because it is not reflexive (and hence not strongly complete). The strict inequality “greater than” (>) is not rational on N, Z, Q and R because it is not reflexive (and hence not strongly complete). Equality (=) is not rational on N, Z, Q and R because it is not weakly complete (and hence not strongly complete).

D. S. Eldridge (ANU) Binary Relations 20 February 2021 17 / 24

Economic Application: Weak Preference Relations Part 1

Suppose that % is a weak preference relation on a consumption set X .

Most of the time, we will want to assume that % is a rational binary relation on X . The reason for this is that rational weak preference relations provide a theory of consistent choice behaviour.

Strong completeness of % guarantees that the individual can always directly compare any two consumption bundles.

Strong completeness combines two other subsidiary properties that are known as weak completeness and reflexivity.

Transitivity of % guarantees that the individual can indirectly directly compare any two consumption bundles.

Strong completeness and transitivity together allow the individual to construct a ranking of all possible consumption bundles.

D. S. Eldridge (ANU) Binary Relations 20 February 2021 18 / 24

Economic Application: Weak Preference Relations Part 2

Consider a weak preference relation % defined on a consumption set X (or, more precisely, defined on the Cartesian product of the consumption set with itself, X ×X ). The weak preference relation is weakly complete if, for all (x, y) ∈ X ×X such that x 6= y, it is the case that either (i) x % y but y 6% x or (ii) y % x but x 6% y, or (iii) both x % y and y % x. The weak preference relation is said to be reflexive if x % x for all x ∈ X . (Alternatively, we could write this as “the weak preference relation is said to be reflexive if x % x for all (x, y) ∈ X ×X . The weak preference relation is strongly complete if, for all (x, y) ∈ X ×X , it is the case that either (i) x % y but y 6% x or (ii) y % x but x 6% y, or (iii) both x % y and y % x. Note that strong completeness simply combines the properties of weak completeness and reflexivity.

D. S. Eldridge (ANU) Binary Relations 20 February 2021 19 / 24

Economic Application: Weak Preference Relations Part 3

Consider a weak preference relation % defined on a consumption set X (or, more precisely, defined on the Cartesian product of the consumption set with itself, X ×X ). The weak preference relation is transitive if, for all (x, y, z) ∈ X ×X ×X such that both (i) x % y and (ii) y % z, it is the case that x % z.

A weak preference relation that is both strongly complete and transitive is said to be rational.

D. S. Eldridge (ANU) Binary Relations 20 February 2021 20 / 24

Economic Application: Weak Preference Relations Part 4

Sometimes, we will want to assume more than just rationality of the weak preference relation. Other properties that we will sometimes assume include the following.

Desirability Assumptions: Local non-satiation, monotone, strongly monotone.

These capture, to varying extents, the idea that “more is preferred to less”.

Curvature Assumptions: Convexity, strict convexity. These capture, to varying extents, the idea that “averages are preferred to extremes”.

Regularity Assumptions: Continuity, Differentiability, Smoothness (n times continuously differentiable for some large n ∈ N), Inada conditions.

These might be describes as the “picky technical details” assumptions.

Further information about these properties can be found in Gravelle and Rees (1981), Kreps (1990), Mas-Colell et al (1995), Rubinstein (2006) and Varian (1992).

D. S. Eldridge (ANU) Binary Relations 20 February 2021 21 / 24

Economic Application: Weak Preference Relations Part 5

Suppose that % is a rational weak preference relation on a consumption set X .

Rational weak preference relations can sometimes be represented by utility function.

A function U : X −→ R is a utility function representation of % if x % y ⇐⇒ f (x) > f (y). A necessary, but not sufficient, condition for a utility function representation of % to exist is that % be rational.

One set of sufficient conditions for utility function existence is that X be countable (that is, either finite or countably infinite) and % be rational. Another set of sufficient conditions for utility function existence, which will work even when X is uncountable, is that % be both rational and continuous. (This result, which was established by Gerard Debreu, actually guarantees the existence of a continuous utility function.)

D. S. Eldridge (ANU) Binary Relations 20 February 2021 22 / 24

Economic Application: Weak Preference Relations Part 6

The weak preference relation (%) can be used to construct the strict preference relation (�) and the indifference relation (∼).

x � y if and only if both (a) x % y and (b) y 6% x. x ∼ y if and only if both (a) x % y and (b) y % x.

If the weak preference relation is rational, then in general, neither the strict preference relation nor the indifference relation will be be rational.

The strict preference relation cannot be rational because it is not reflexive (and hence it is not strongly complete). The indifference relation will, in general, not be rational because it will not be weakly complete (and hence not be strongly complete). The exception is the case where an individual is indifferent between every possible consumption bundle.

D. S. Eldridge (ANU) Binary Relations 20 February 2021 23 / 24

Economic Example: Lexicographic Preferences

The weak preference relation for Lexicographic preferences on R2+ is defined as follows.

Suppose that x = (x1, x2) ∈ R2+ and y = (y1, y2) ∈ R2+. x % y if either:

(a) x1 > y1; or (b) Both (i) x1 = y1 and (ii) x2 > y2.

This definition can be extended to define lexicographic preferences on RL+ for L > 2.

Lexicographic basically means “dictionary, or alphabetic, ordering”.

The weak preference relation for lexicographic preferences is rational, strongly monotone and strictly convex. So in many respects, lexicographic preferences are very well behaved.

However, the weak preference relation for lexicographic preferences on R2+ is not continuous. Furthermore, it cannot be represented by a utility function.

D. S. Eldridge (ANU) Binary Relations 20 February 2021 24 / 24