Question

Let A be a set with a partial order R. For each a∈A, let Sa= {x∈A: xRa}. Let F={Sa: a∈A}. Then F is a subset of P(A) and thus may be partially ordered by ⊆, inclusion.
a) Show that if aRb, then Sa ⊆ Sb.
b) Show that if Sa ⊆ Sa, then aRb.
c) Show that if B⊆A, and x is the least upper bound for B, then Sx is the least upper bound for {Sb:b∈B}

Answer 1

Answer:

See proofs below

Step-by-step explanation:

a) Suppose that aRb. Let y∈Sa , then y∈A and yRa. We have that yRa and aRb. Since R is a partial order, R is a transitive relation, therefore yRa and aRb imply that yRb. Now, y∈A and yRb, thus y∈Sb. This reasoning applies for all y∈Sa that is, for all y∈Sa, y∈Sb, threrefore Sa⊆Sb.

b) Suppose that Sa⊆Sb. Since R is a partial order, R is a reflexive relation then aRa. Thus, a∈Sa. The inclusion Sa⊆Sb implies that a∈Sb, then aRb.

c) Denote this set by S={Sb:b∈B}. We will prove that supS=Sx with x=supB.

First, Sx is an upper bound of S: let Sb∈S. Then b∈B and since x=supB, x is an upper bound of B, then bRx. Then b∈Sx. Now, for all y∈Sb, yRb and bRx, then by transitivity yRx, thus y∈Sx. Therefore Sb⊆Sx for all Sb∈S, which means that Sx is an upper bound of S (remember that the order between sets is inclusion).

Now, let's prove that Sx is the least upper bound of S. Let Sc⊆A be another upper bound of S (in the set F). We will prove that Sx⊆T.

Because Sc is an upper bound, Sb⊆Sc for all b∈B. Thus, if y∈Sb for some b, then y∈Sc. That is, if yRb then yRc. In particular, bRb then bRc for all b∈B. Thus c is a upper bound of B. Byt x=supB, then xRc. Now, for all z∈Sx, zRx and xRc, which again, by transitivity, implies that z∈Sc. Therefore Sx⊆Sc and Sx=sup S.