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)$ 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...
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$
This comment has been removed by the author.
ReplyDeleteSolution 18 (b) is not correct. Specifically the way anti-symmetric property is being used to conclude is not proper.
ReplyDeleteSolution 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.
ReplyDeleteYour 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.
ReplyDeleteI 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?
ReplyDeleteI 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
In the antisymmetry proof in problem 5, you forgot to set the condition that $(y, x) \in R \cap (B \times B)$.
ReplyDeleteSame problem with problem 6(a). Don't know if I'm missing something.
DeleteFor 3(c) shouldn't the set of natural numbers, N, be the l.u.b? N∈P(N) and ∀x∈B(x⊆N).
ReplyDeleteIf 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.
Delete