w1

1. For each of the following items (a) and (b), determine whether the propositions in it are logically equivalent. Justify your answer.

   (a) \((p\land\lnot q)\land(q\land\lnot p)\text{ and }\lnot p\land q\)

   ​

   (b) \(\neg p\lor q\text{ and }(q\land p)\lor\neg p\)

   ​

   ‍

2. Let A,B and C be three sets. Find the formular that describe each of the following Venn diagrams, using only intersections, conjunction and complements.

   ​

   (a) ​

   (b) ​

   (c) ​

3. Let \(A\) and \(B\) be two sets. Show that \(P(A)\subseteq\ P(B)\Leftrightarrow A\subseteq B\), where \(P(X)\) is the set of all subsets of \(X\).

   ​

4. The relation \(I_X=\{(x,x):x\in X\}\) is called the identity relation on \(X\). Let \(R\) be a relation on \(X\). Prove that \(R\) is antisymmetric, if and only if, \(R\cap R^{-1}\subseteq I_X\)

   Proof

   \(\Rightarrow\)) Suppose tjat \(R\) is antisymmetric then take element \((x,y)\in R\cap R^{-1}\Rightarrow(x,y)\in R~and~(x,y)\in R\Rightarrow ~_xR_y~and~_xR^{-1}y\Rightarrow ~_xR_y~and~_yRx\Rightarrow x=y\Rightarrow(x,y)=(x,x)\in I_x\)

   Therefore \(R\cap R^{-1}\subseteq I_x\)

   \(\Leftarrow\)) Suppose that \(R\cap R^{-1}\subseteq I_x\), that if \(~_xR_y~and~_yRx\Rightarrow ~_xRy~and~_xR^{-1}_y\Rightarrow (x,y)\in R~and ~(x,y)\in R^{-1}\Rightarrow(x,y)\in R\cap R^{-1}\subseteq I_x\Rightarrow x=y\)

   ‍

5. Let \(X\), \(Y\) and \(Z\) be non-empty sets. Let \(f : X → Y\) and \(g : Y → Z\) be functions. Prove that:

   (a) If \(g\circ f\) is injective, then \(f\) is injective.

   We need to prove f is injective, it is equivalent to take \(f(x_1)=f(x_2)\) (y1=y1,prove x1=x2)then prove \(x_1=x_2\)

   Now since \(f(x_1)=f(x_2)\), then \(g(f(x_1))=g(f(x_2))\)

   Now \(g\circ f\) is injective by hypothesis and we have \((g\circ f)(x_1)=(g\circ f)(x_2)\Rightarrow x_1=x_2\Rightarrow f\) is injective

   \(g\circ f\) is injective\(\Rightarrow\)​\(g(f(x_1))=g(f(x_2)),x_1=x_2\).

   Since \(x_1=x_2\), \(f(x_1)=f(x_2)\) has to be true.

   Apparently, \(f\) is injective.

   ‍

   (b) If \(f\) and \(g\) are surjective, then \(g\circ f\) is surjective.

   Suppose that \(f\) and \(g\) are surjective, Let \(z\in Z\) as \(g\) is surjective, there exists \(y\in Y\) such that \(z=g(y)\) and as \(f\) is surjective, there exists \(x\in X\) such that \(y=f(x)\).

   Hence \(z=g(y)=g(f(x))=(g\circ f)(x)\) and thus \(g\circ f\) is surjective.

‍