1.   (a) Let θ be a binary relation on a set A which is not necessarily transitive.

Define a binary relation θ *  on A as follows: for any a,b ∈ A, aθ* b if and only if there exists a sequence a1 ,a2 , . . . ,ak  ∈ A, where k ≥ 2 is an integer (which relies on a and b), such that a = a1 ,b = ak  and ai θ ai+1  for all i = 1, 2, . . . ,k − 1.

θ *  is called the transitive closure of θ .

Prove that θ *  is a transitive relation on A.

(b) Let (T,r) be a rooted tree. Denote the set of nodes of (T,r) by V .

Let θ be the binary relation defined by

θ  =  {(a,b) | a,b ∈ V, a is a parent of b}.

(i) Show that θ is not transitive. 

(ii) Let θ *  be the transitive closure of θ and a,b ∈ V .

Describe what relation holds between a and b if aθ * b .

2. Define the two binary relations θ and θ¯ on Z × Z by

(a) θ = {(a, b) : a1 a2 − b1 b2  is even},

(b) θ¯ = {(a, b) : a1  > b1  or a2  > b2 }.

(i) Verify for each of the two relations which of the following properties are satisfied: transitivity, reflexivity, comparability, symmetry, asymmetry, antisymmety.

(ii) Which property(ies) are gained/lost if “even” is replaced by “odd” in θ, and if “a1  > b1  or a2  > b2”is replaced by“a1  ≥ b1  or a2  ≥ b2”in θ¯?

Carefully explain your answers by providing proofs or counterexamples. 

3. Let A = {(3, 2, −2), (3, 1, −1), (−4, 2, 1), (3, −1, 1), (3, −1, −1), (4, −2, 1), (−1, 1, 1)}.

(a) List the lexicographic order of A, and find the greatest and least elements of A.

(b) For the Pareto order on A, use the Boolean matrix representation to find the Pareto-maximal and Pareto-minimal element sets Pmax (A) and Pmin (A), and the Pareto greatest and least elements (if any) of A.

(c) Let f : R3  → R3  be defined by

f(x) = (x1 + x2 ,x1 + x3 ,x2 + x3 )

for all x  =  (x1 ,x2 ,x3 ) ∈ R3 .

Denote the lexicographic order on R3  by L.

You may freely use the results from the lecture that L is reflexive, transitive, antisymmetric, and comparable.

Define θ L  by

θ L  = {(a, b)|a, b ∈ A,f(a)Lf(b)}.

(i) Determine whether θ L  satisfies the properties of reflexivity, transitivity, anti- symmetry, and comparability.

(ii) Determine all maximal/minimal elements and greatest/least elements in A with respect to θ L .

4. For the upcoming planting season, Farmer Q has four options:

a1 : Plant corn;

a2 : Plant wheat;

a3 : Plant soybeans;

a4 : Use the land for grazing.

The profits associated with these actions are influenced by the amount of rainfall, which could be one of four states:

θ 1 : Heavy rainfall;

θ2 : Moderate rainfall;

θ3 : Light rainfall;

θ4 : Drought season.

The profit matrix in (thousands of dollars) is estimated as

θ 1         θ2      θ3           θ4

−5

0

−10

10

(a) Which course of action should the farmer take if he uses

(i) Wald’s maximin criterion;            (ii) Hurwicz’s maximax criterion;       (iii) Savage’s minimax regret criterion; (iv) Laplace’s criterion?

(b) For each α  ∈ [0, 1] determine the action(s) that is/are imposed by Hurwicz’s

α-criterion.