## Wednesday, June 2, 2010

### how to prove it - ch4, sec4.4(Ordering Relations)

This section talks about mathematical meaning of ordering elements of sets, finding smallest, finding minimal element of a set with respect to a particular relation.

Antisymmetric Relation: Intuitively, its opposite of a symmetric relation. Formally, Suppose R is a relation on set A. Then R is antisymmetric if $\forall x \in A \forall y \in A (xRy \land yRx \rightarrow x = y)$

So, in an antisymmetric relation, For two different x and y if $xRy$ then $(y,x) \notin R$. It, in some sense, is saying that "y is atleast as large as x". And, this though motivates to think about the "ordering".

Suppose R is a relation on a set A.
Partial ordering: R is called a partial ordering on A(or just partial ordering if A is clear from the context) if it is reflexive, transitive and antisymmetric.

Total ordering: R is called a total ordering on A if it is partial order and $\forall x \in A \forall y \in A (xRy \lor yRx)$

So, in case of total ordering, its possible to compare any two elements of A as one of the two ordered pairs formed by them must be in the relation.

Suppose R is a partial ordering on A and $B \subseteq A$.

Smallest and Minimal: Then $b \in B$ is called the R-smallest(or just smallest if R is clear from the context) element of B if $\forall x \in B (bRx)$.
It is called an R-minimal(or just minimal) if $\lnot \exists x \in B (xRb \land x \neq b)$

Largest and Maximal: These are exactly opposite of Smallest and Minimal respectively. $b \in B$ is called the R-largest element of B if $\forall x \in B (xRb)$.
It is called an R-maximal if $\lnot \exists x \in B (bRx \land x \neq b)$

lower bound and upper bound: Then $a \in A$ is called a lower bound for B if $\forall x \in B (aRx)$. Similarly, it is called an upper bound if $\forall x \in B (xRa)$

The only difference between a lower bound and smallest element of B is that smallest element has to be in B while its not mandatory for lower bound.

Least Upper Bound(lub) and Greatest Least Bound(glb): Simply speaking, smallest from the set of all upper bounds of B is called lub and largest from the set of all lower bounds of B is called the glb. LUB is also called "supremum"(sup) and GLB is also called "infimum"(inf).

=============================================================================================
Ex-1
(a) Reflexive: Yes
Transitive: Yes
Antisymmetric: Yes

Hence, it is partial order.

It is not total order as none of (a,c) or (c,a) are in R.

(b) Reflexive: Yes
Transitive: Yes
Antisymmetric: No as (-4,4) and (4,-4) both are in R

Hence, it is not partial order.

(c) Reflexive: Yes
Transitive: Yes
Antisymmetric: Yes

Hecne, it is partial order.

It is not total order as none of (4,-4) or (-4,4) are in R

Ex-2
(a) Reflexive: Yes
Transitive: Yes
Antisymmetric: Yes

It is partial order. It is also total order.

(b) Reflexive: Yes
Transitive: Yes
Antisymmetric: Yes

It is partial order. It is also total order.

(c) Reflexive: Yes
Transitive: Yes
Antisymmetric: Yes

It is partial order. It is also total order.

Ex-3
(a) Set of Minimal elements = {2}
Set of Maximal elements = {3,4}
smallest = 2
largest = does not exist

least upper bound = does not exist
greatest lower bound = 2

(a) Set of Minimal elements = {1}
Set of Maximal elements = does not exist
smallest = 1
largest = does not exist

least upper bound = 2
greatest lower bound = 1

(c) Set of Minimal elements = {$\emptyset$}
Set of Maximal elements = {$x \in P(N)$ | x has exactly 5 elements}
smallest = $\emptyset$
largest = does not exist

least upper bound = does not exist
greatest lower bound = $\emptyset$

Ex-4 ($\rightarrow$) Suppose R is both symmetric and antisymmetric. Let x,y be arbitrary elements of A s.t. $(x,y) \in R$. Since R is symmetric, so $(y,x) \in R$. Since R is antisymmetric, so $x = y$. Thus, $(x,y) \in i_A$. Since x,y are arbitrary, so $R \subseteq i_A$

($\leftarrow$) Suppose $R \subseteq i_A$. Let x,y be arbitrary elements of A s.t. $(x,y) \in R$. It follows from the assumption that $(x,y) \in i_A$, hence $x = y$. Thus $(y,x) \in R$. Since x,y are arbitrary, it follows that R is both symmetric and antisymmetric

Ex-5 Suppose R is a partial order on A and $B \subseteq A$.

Let x be an arbitrary element of B. Then $(x,x) \in B X B$, also $(x,x) \in A X A$, so $(x,x) \in R$. Thus $(x,x) \in R \cap (B X B)$. Since x is arbitrary, so $R \cap (B X B)$ is reflexive on B

Let x,y,z be arbitrary elements of B s.t. $(x,y) \in R \cap (B X B)$ and $(y,z) \in R \cap (B X B)$. It follows that $(x,y) \in R$ and $(y,z) \in R$. Since R is a partial order on A, so R is transitive and hence $(x,z) \in R$. Also $(x,z) \in B X B$. Thus $(x,z) \in R \cap (B X B)$. Since x,y,z are arbitrary so $R \cap (B X B)$ is transitive on B

Let x,y be arbitrary elements of B s.t. $(x,y) \in R \cap (B X B)$. Then $(x,y) \in R$. Since R is partial order and hence antisymmetric on A, so $(x,y) \in R \land (y,x) \in R \rightarrow x = y$. So $(x,y) \in (R \cap (B X B)) \land (y,x) \in (R \cap (B X B)) \rightarrow x = y$. Since x,y are arbitrary so $R \cap (B X B)$ is antisymmetric on B

Thus $R \cap (B X B)$ is partial order on B.

Ex-6 Since $R_1$ and $R_2$ both are partial order on A. So both are reflexive, transitive and antisymmetric on A.
(a) Yes.

Let x be an arbitrary element of A. It follows that $(x,x) \in R_1$ and also $(x,x) \in R_2$. Then $(x,x) \in R_1 \cap R_2$. Since x is arbitrary, so $R_1 \cap R_2$ is reflexive on A

Let x,y be arbitrary elements of A s.t. $(x,y) \in R_1 \cap R_2$. Then $(x,y) \in R_1$ and $(x,y) \in R_2$. Since $R_1$ and $R_2$, both are antisymmetric so, $(x,y) \in R_1 \land (y,x) \in R_1 \rightarrow x = y$ and $(x,y) \in R_2 \land (y,x) \in R_2 \rightarrow x = y$. Thus $(x,y) \in R_1 \cap R_2 \land (y,x) \in R_1 \cap R_2 \rightarrow x = y$. Since x,y are arbitrary so $R_1 \cap R_2$ is antisymmetric on A

Let x,y,z be arbitrary elements of A s.t. $(x,y) \in R_1 \cap R_2$ and $(y,z) \in R_1 \cap R_2$. Then $(x,y) \in R_1$ and $(y,z) \in R_1$, $(x,y) \in R_2$ and $(y,z) \in R_2$. Since both are transitive on A, so $(x,z) \in R_1$ and $(x,z) \in R_2$. So $(x,z) \in R_1 \cap R_2$. Since x,y,z are arbitrary so $R_1 \cap R_2$ is transitive on A

Hence $R_1 \cap R_2$ is Partial order on A

(b) No. Here is a counterexample.
A = {1,2,3}

$R_1$ = {(1,1), (2,2), (3,3), (1,2)}

$R_2$ = {(1,1), (2,2), (3,3), (2,3)}

$R_1 \cup R_2$ = {(1,1), (2,2), (3,3), (1,2), (2,3)}

clearly its not transitive as $(1,2) \in R_1 \cup R_2$ and $(2,3) \in R_1 \cup R_2$, but $(1,3) \notin R_1 \cup R_2$. Hence $R_1 \cup R_2$ is not partial order on A.

Ex-7 Suppose $R_1$ is partial order on $A_1$, $R_2$ is partial order on $A_2$ and $A_1 \cap A_2 = \emptyset$
(a) Let x be an arbitrary element of $A_1 \cup A_2$. So either $x \in A_1$ or $x \in A_2$. So either $(x,x) \in R_1$ or $(x,x) \in R_2$. Then $(x,x) \in R_1 \cup R_2$. Since x is arbitrary so $R_1 \cup R_2$ is reflexive on $A_1 \cup A_2$

Let x,y be arbitrary elements of $A_1 \cup A_2$ s.t. $(x,y) \in R_1 \cup R_2$. Let us consider following exhaustive set of cases
Case#1: $x \in A_1$ and $y \in A_1$
Then $(x,y) \in R_1 \land (y,x) \in R_1 \rightarrow x = y$. Thus, $(x,y) \in R_1 \cup R_2 \land (y,x) \in R_1 \cup R_2 \rightarrow x = y$

Case#2: $x \in A_2$ and $y \in A_2$
by a similar argument as above case, $(y,x) \in R_1 \cup R_2$

Case#3: $x \in A_1$ and $y \in A_2$
Then $(x,y) \notin R_1$ and $(x,y) \notin R_2$, hence $(x,y) \notin R_1 \cup R_2$. That is contradictory to our assumption, hence this case is not possible

Case#4: $x \in A_2$ and $y \in A_1$
This case is also not possible for the same reason as above.

Thus $(x,y) \in R_1 \cup R_2 \land (y,x) \in R_1 \cup R_2 \rightarrow x = y$. Since x,y are arbitrary so $R_1 \cup R_2$ is antisymmetric on $A_1 \cup A_2$

Let x,y,z be arbitrary elements of $A_1 \cup A_2$ s.t. $(x,y) \in R_1 \cup R_2$ and $(y,z) \in R_1 \cup R_2$. Let us consider following exhaustive set of cases
Case#1: $(x,y) \in R_1$ and $(y,z) \in R_1$
Then $(x,z) \in R_1$ and hence $(x,z) \in R_1 \cup R_2$

Case#2: $(x,y) \in R_2$ and $(y,z) \in R_2$
Then $(x,z) \in R_2$ and hence $(x,z) \in R_1 \cup R_2$

Case#3: $(x,y) \in R_1$ and $(y,z) \in R_2$
Since $A_1 \cap A_2 = \emptyset$, so $y$ can not belong to both $A_1$ and $A_2$ and hence this case is not possible

Case#4: $(x,y) \in R_2$ and $(y,z) \in R_3$
For same reason as above, this case is also not possible.

Thus $(x,z) \in R_1 \cup R_2$. Since x,y,z is arbitrary so $R_1 \cup R_2$ is transitive on $A_1 \cup A_2$.

Hence $R_1 \cup R_2$ is partial order on $A_1 \cup A_2$

(b) It can be proven by using the similar arguments as in part(a)

(c) Suppose $R_1$ and $R_2$ are total orders. Let $x \in A_1$ and $y \in A_2$. Then neither (x,y) nor (y,x) will be in $R_1 \cup R_2$. And hence its not total order. On the other hand, $(x,y) \in A_1 X A_2$, so $R_1 \cup R_2 \cup A_1 X A_2$ is total order.

Ex-8 Let x be an arbitrary element of A and y be an arbitrary element of B. Since R is partial order, so xRx and similarly ySy. Thus $((x,y),(x,y)) \in T$. Since x,y is arbitrary, so T is reflexive in (A X B)

Let x,v be arbitrary elements of A and y,w be arbitrary elements of B. Suppose $((x,y),(v,w)) \in T$ and $((v,w),(x,y) \in T$. Since $((x,y),(v,w)) \in T$, so $(x,v) \in R$ and $(y,w) \in S$. Also since $((v,w), (x,y)) \in T$, so $(v,x) \in R$ and $(w,y) \in S$. Since R and S are antisymmetric, it follows that x = v and y = w. Thus, (x,y) = (v,w). Since x,y,v,w are arbitrary so T is antisymmetric

Let x,y,z be arbitrary elements of A and u,v,w be arbitrary elements of B s.t. $((x,u),(y,v)) \in T$ and $((y,v),(z,w)) \in T$. It follows that $(x,y) \in R$ and $(u,v) \in S$, $(y,z) \in R$ and $(v,w) \in S$. Since R and S both are transitive, hence $(x,z) \in R$ and $(u,w) \in S$. Thus $((x,u),(z,w)) \in T$. Since x,y,z,u,v,w are arbitrary so T is transitive.

Hence T is partial order in A X B

Suppose R and S is total order. Let $(x,u) \in A X B$ and $(y,v) \in A X B$ and x,y be arbitrary elements of A and u,v be arbitrary elements of B. It follows that either $(x,y) \in R$ or $(y,x) \in R$ and either $(u,v) \in S$ or $(v,u) \in S$. Let us consider following case,

Case#: $(x,y) \in R$ and $(v,u) \in S$
Clearly, neither $((x,u),(y,v)) \in T$ nor $((y,v),(x,u)) \in T$. And, hence T is not total order.

Ex-9 Let x be arbitrary element of A and y be arbitrary element of B. So $(x,x) \in R$ and $(y,y) \in S$. Thus $((x,y),(x,y)) \in L$. Since x,y are arbitrary so L is reflexive in A X B

Let x,y be arbitrary elements of A and u,v be arbitrary elements of B. Suppose $((x,u),(y,v)) \in L$ and $((y,v),(x,u)) \in L$. Then $(x,y) \in R$ and also $(y,x) \in R$. Hence x = y. And then $(u,v) \in S$ and $(v,u) \in S$, then u = v. Thus (x,u) = (y,v). Since x,y,v,u are arbitrary so L is antisymmetric

Let x,y,z be arbitrary elements of A and u,v,w be arbitrary elements of B s.t. $((x,u),(y,v)) \in L$ and $((y,v),(z,w)) \in L$. It follows that $(x,y) \in R$ and $(y,z) \in R$, then $(x,z) \in R$. Now consider following cases
Case#1: $x \neq z$
Then $((x,u),(z,w)) \in L$

Case#2: x = z
Since $(x,y) \in R$ and $(y,z) \in R$. Since x = z, so $(y,x) \in R$ as well. Since R is antisymmetric, so y = x. It follows that $(u,v) \in S$ and $(v,w) \in S$, then $(u,w) \in S$. Then $((x,u),(z,w)) \in L$

Thus $((x,u),(z,w)) \in L$. Since x,y,z,u,v,w are arbitrary so L is transitive. Hence L is partial order on A X B

Suppose R and S are total order. Let (x,u) and (y,v) be arbitrary elements of A X B. It follows that either $(x,y) \in R$ or $(y,x) \in R$ and either $(u,v) \in S$ or $(v,u) \in S$. Let us consider the case when $(x,y) \in R$ and $(v,u) \in S$ and x = y, then It is not necessary that one of the two ordered pairs formed by (x,y) and (y,v) are in L. Hence L is not total order.

Ex-10 Let x and y be arbitrary elements of A.
($\rightarrow$) Suppose $(x,y) \in R$. Let u be an arbitrary element of $P_x$. It follows that $(u,x) \in R$. R is partial order on A and hence transitive, so $(u,y) \in R$. Thus $u \in P_y$. Since u is arbitrary, so $P_x \subseteq P_y$.

($\leftarrow$) Suppose $P_x \subseteq P_y$. Clearly, $x \in P_x$ because $(x,x) \in R$. Then, it follows from our assumption that $x \in P_y$ also, so $(x,y) \in R$.

Ex-11 D = {$(x,y) \in Z^+$ X $Z^+$ | x divides y}
B = {$x \in Z | x > 1$}

D-Minimal elements of B are all the prime numbers = {2,3,5,7,...}

As there is no element in B that divides every other element in B, so there does not exist a smallest element.

Ex-12 The implicit relation in this exercise is the subset-of relation.

given: B = {$X \subseteq R | X \neq \emptyset \land \forall x \forall y ((x \in X \land x < u =" {$x" x =" {$x" style="font-weight: bold;">Ex-13 Let x be an arbitrary element of A. Then$(x,x) \in R$, so$(x,x) \in R^{-1}$also. Since x is arbitrary, so$R^{-1}$is reflexive in A Let x,y be arbitrary elements of A s.t.$(x,y) \in R^{-1}$and$(y,x) \in R^{-1}$. Then$(y,x) \in R$and also$(x,y) \in R$. But since R is antisymmetric, so x = y. Since x,y are arbitrary, so$R^{-1}$is antisymmetric Let x,y,z be arbitrary elements of A s.t.$(x,y) \in R^{-1}$and$(y,z) \in R^{-1}$. Then$(y,x) \in R$and$(z,y) \in R$. Since R is transitive, so$(z,x) \in R$. Thus$(x,z) \in R^{-1}$. Since x,y,z are arbitrary so$R^{-1}$is transitive Hence$R^{-1}$is partial order in A. Suppose R is total order. Let x,y be arbitrary elements of A. Then either$(x,y) \in R$or$(y,x) \in R$. Thus either$(y,x) \in R^{-1}$or$(x,y) \in R^{-1}$. Hence$R^{-1}$is total order too. Ex-14 (a) Let$b \in B$and b is R-largest element of B iff$\forall b \in B (xRb)$iff$\forall b \in B (bR^{-1}x)$iff b is the$R^{-1}$-smallest element of B (b) Let$b \in B$and b is R-maximal element of B iff$\lnot \exists x \in B (bRx) \land x \neq b$iff$\lnot \exists x \in B (xR^{-1}b) \land x \neq b$iff b is the$R^{-1}$-minimal element of B Ex-15 (a) Suppose b is the$R_1$-smallest element of B. Let x be arbitrary element of B. It follows that$(b R_1 x)$. Since$R_1 \subseteq R_2$, so$(b R_2 x)$. Since x is arbitrary, so b is$R_2$-smallest element of B also. (b) Suppose b is the$R_1$-minimal element of B. Then$\lnot \exists x \in B (x R_1 b) \land x \neq b$. Since$R_1 \subseteq R_2$, so$\lnot \exists x \in B (x R_2 b) \land x \neq b$. Hence b is$R_2$-minimal element of B also. Ex-16 Suppose b is the largest element of B. We'll prove by contradiction. Assume b is not the maximal element of B, then we can chose a particular element x in B s.t.$(b R x)$and$x \neq b$. But b is the largest element of B so its not possible. Hence b is the maximal element of B. Again we will use contradiction to prove that b is the only maximal element. Assume there exists another maximal element called c. Then,$\lnot \exists x \in B (c R x) \land x \neq c$. Since b is largest element of B, so$(c R b)$. Thus, (c = b). Hence b is the unique maximal element of B. Ex-17 Suppose b is the one and only minimal element of a subset(calling it B) of a partially ordered set with respect to a relation called R. Assume there exists a smallest element$c \in B$. Then$(c R b)$. But since b is the only minimal element, so (b = c). Hence b is the smallest element also. So if the smallest element *exists* then it is b. But it may not exist at all. So, the given statement is not true. I cheated and looked for this counterexample in the hints section. A = {R X R} R = {((x,y),(u,v)) \in A X A | x \leq u \land y \leq v} B = {(0,0)}$\cup$({1} X$R$) Let us first prove that R is partial order on A. Let x, y be arbitrary elements of A. clearly$((x,y),(x,y)) \in R$as ((x = x) and (y = y)). Thus R is reflexive on A. Let x,y,u,v be arbitrary elements of A s.t.$((x,y),(u,v)) \in R$and$((u,v),(x,y)) \in R$. Then$(x \leq u) and (u \leq x)$,$(y \leq v) and (v \leq y)$. So, (x = u) and (y = v) and hence (x,y) = (u,v). Thus R is antisymmetric on A Let x,y,z,u,v,w be arbitrary elements of A s.t.$((x,u),(y,v)) \in R$and$((y,v),(z,w)) \in R$. Then$x \leq y$and$y \leq z$, hence$x \leq z$. Also$u \leq v$and$v \leq w$, hence$u \leq w$. Thus$((x,u),(z,w)) \in R$. Thus R is transitive. Hence R is partial order on A. clearly (0,0) is one and only minimal element of B but it is not the smallest as pairs like ((0,0),(1,-1)) are not in R. Ex-18 (a) ($\rightarrow$) Suppose x is arbitrary element of A and x is an upper bound of$B_1$. Let y be an arbitrary element of$B_2$. Then we can chose a z in$B_1$s.t. (yRz). Since x is an upper bound of$B_1$, so$zRx$. Since R is transitive, so$yRx$. Since y is arbitrary element of$B_2$, so x is an upper bound of$B_2$. ($\leftarrow$) It can be proven by using exactly a same statement as above. (b) Suppose$B_1$and$B_2$are disjoint. We'll prove by contradiction. Let$b \in B_1$be a maximal element of$B_1$. Since$b \in B_1$, so we can choose an element x in$B_2$s.t.$bRx$. Since$B_1$and$B_2$are disjoint, so$b \neq x$. Since$x \in B_2$, so we can choose a$y \in B_1$s.t. (xRy). Since (bRx) and (xRy), so$b \neq y$as R is antisymmetric. Since R is transitive, so (bRy), which is a contradiction as b is a maximal element of B. Thus no maximal element exists for$B_1$. By similar argument, we say that no maximal element exists for$B_2$also. Ex-19 (a) Let us try to analyze the theorem, and in the process we'll try to find out what is wrong with the given proof. given: R is a total order on A,$B \subseteq A$goal: every element of B is either the smallest or the largest element of B i.e.$\forall b \in B$(b is smallest)$\lor$(b is largest). Let b be arbitrary element of B. given: R is a total order on A,$B \subseteq A$, b is arbitrary element of B goal: either b is smallest or b is largest i.e.$\forall x \in B (bRx)\lor\forall x \in B (xRb)$ah.. so flaw in the given proof is that it proves that$\forall x \in B ((bRx) \lor (xRb))$wherease what we need to prove is that$(\forall x \in B (bRx))\lor(\forall x \in B (xRb))$and clearly, two statements are not equivalent (b) Given theorem is incorrect and here is the counterexample. A = {1,2,3} R = {(1,1), (2,2), (3,3), (1,2), (2,3), (1,3)} B = {1,2,3} We can see that, in this case R is total order on A but 2 is neither smallest nor largest element of B Ex-20 (a) Suppose b is the smallest element of B. Let$a \in A$be an arbitrary lower bound of B and x be an arbitrary element of B. Then (aRx). Let us choose x = b, so (aRb). So b is larger than a. Since a is arbitrary, so b is the greatest lower bound of B (b) Suppose b is the largest element of B. Let$a \in A$be an arbitrary upper bound of B and x be an arbitrary element of B. Then (xRa). Let us choose x = b, then (bRa). So b is smaller than a. Since a is arbitrary, so b is the least upper bound of B Ex-21 (a) Suppose x be an arbitrary element of U and y is some element in A s.t. (xRy). Let b be an arbitrary element of B. Since x is an upper bound of B, so (bRx). Since (bRx) and (xRy), R is transitive so (bRy). Thus y is also an upper bound of B, hence$y \in U$. (b) Let b be an arbitrary element of B and u be an arbitrary element of U. It follows that (bRu). Since u is arbitrary, so b is clearly a lower bound of U. Since b is arbitrary, so every element of B is a lower bound for U. (c) Suppose x is the greatest lower bound of U. In part(b) we proved that every element of B is a lower bound of U, so x must be larger than all of them and hence x is an upper bound of B. But, all the elements of U are upper bounds of B and x is lower bound of U, so x must be the least upper bound of B. Ex-22 Suppose$B_1 \subseteq B_2$. Let$b_1$be arbitrary element of$B_1$, then$(b_1 R x_1)$. It follows from our assumption that$b_1 \in B_2$. So$(b_1 R x_2)$, hence$x_2$is also an upper bound of$B_1$. Since$x_1$is least upper bound of$B_1$, so it is smaller than any other upper bound of$B_1$, hence$(x_1 R x_2)$. Ex-23 There are two parts to be proven. 1. Least upper bound of$F$is$\cup F\cup F$is the union of all the sets in$F$. so clearly every element of$F$is a subset of$\cup F$, hence$\cup F$is clearly an upper bound of$F$. Let X be an arbitrary element of$P(A)$s.t. X is upper bound of$F$. Let f be an arbitrary element of$\cup F$, then we can choose a set B in$F$s.t.$f \in B$. Since X is upper bound of$F$, so$B \subseteq X$and hence$f \in X$. Since f is arbitrary, so$\cup F \subseteq X$. Since X is arbitrary so$\cup F$is the least upper bound of$F$.$\cap F$is greatest lower bound of$F$can also be proven using a similar argument. And, here it goes...$\cap F$is clearly a lower bound of$F$as$\forall S \in F (\cap F \subseteq S)$Let X be an arbitrary element of$P(A)$s.t. X is lower bound of$F$. That implies,$\forall S \in F (X \subseteq S)$So,$X \subseteq \cap F$Since X is arbitrary so$\cap F$is the greatest lower bound of$F$#### 9 comments: 1. This comment has been removed by the author. 2. Solution 18 (b) is not correct. Specifically the way anti-symmetric property is being used to conclude is not proper. 3. Solution 2.b is incorrect. The relation is NOT antisymmetric. 2.c is a little ambiguous depending on whether or you assume two different countries can have the same population. 4. Your solution to 9 is also incorrect. L *is* a total order. To see why, assume two cases: either (a, b)L(a', b') or ¬[(a, b)L(a', b')]. If (a, b)L(a', b'), then of course (a, b)L(a', b') ∨ (a', b')L(a, b) is true. If it's not true, then either ¬aRa' or (a = a')∧¬bSb'. In each case, it's easy to prove that a'Ra∧(a = a' → b'Sb), so (a', b')L(a, b) as required. 5. I am confused about the solution to #15 - so what if R1 ⊂ R2? Why does it follow that if this is true then if bR1x then bR2x? I would see why, if bR2x, and R1 ⊂ R2, then certainly bR1x. But I don't see why the above is true. Your proof just says it is lol 6. In the antisymmetry proof in problem 5, you forgot to set the condition that$(y, x) \in R \cap (B \times B)\$.

1. Same problem with problem 6(a). Don't know if I'm missing something.

7. For 3(c) shouldn't the set of natural numbers, N, be the l.u.b? N∈P(N) and ∀x∈B(x⊆N).

1. If you consider a subset of N, that is not itself N, then you can find an element that is not in the chosen subset but is in N. You can then construct a set containing the element, such that the set is an element of B. This set would be subset of N but not of the subset we first considered.