Miscellaneous · Q3: Is $A\subset B$ an equivalence relation on $P(X)$⁠?

Basics you need

Solution

1. See what $R$ looks like in small cases

   Here the elements being related are sets (the subsets of $X$⁠), not numbers. Two small cases:

   • If $X = \{a\}$⁠, then $P(X) = \{\varnothing, \{a\}\}$ has 2 members, and $R = \{(\varnothing,\varnothing),\ (\varnothing,\{a\}),\ (\{a\},\{a\})\}$⁠. The pair $(\{a\},\varnothing)$ is missing, because $a \in \{a\}$ but $a \notin \varnothing$⁠.
   • If $X = \{a,b\}$⁠, then $P(X) = \{\varnothing, \{a\}, \{b\}, \{a,b\}\}$ has 4 members, and $R$ has 9 pairs: the 4 pairs $(A,A)$⁠, plus $(\varnothing,\{a\})$⁠, $(\varnothing,\{b\})$⁠, $(\varnothing,\{a,b\})$⁠, $(\{a\},\{a,b\})$⁠, $(\{b\},\{a,b\})$⁠.
   Writing out a small case first shows what to expect before proving anything: arrows from each set to itself (so reflexive is likely), arrows that chain (so transitive is likely), and arrows that never come back (so symmetric should fail). These examples are only a guide; Steps 2 to 4 give the actual proofs for an arbitrary non-empty $X$⁠.
   Writing $A\,R\,B$ is the same as writing $(A,B)\in R$ (the Remark before Definition 3). A relation on $P(X)$ is a set of ordered pairs of subsets. Basics: what a relation is

2. Reflexive: is every subset contained in itself?

   Take any $A \in P(X)$⁠. Every element of $A$ is, trivially, an element of $A$⁠. So $A \subset A$⁠, that is $(A,A) \in R$⁠. Since $A$ was an arbitrary subset, $R$ is reflexive.

   Reflexivity must hold for every member of $P(X)$⁠, so we argue with an arbitrary subset $A$⁠. The definition of $A \subset B$ asks "is each element of $A$ also in $B$⁠?", and when $B$ is $A$ itself the answer is yes for each element. This includes $A = \varnothing$⁠, where $\varnothing \subset \varnothing$ holds by Basic 2.
   Under NCERT's convention, $\subset$ allows equality: $A \subset A$ is true. (See the last step for what changes if $\subset$ is read as "proper subset".)

3. Symmetric: fails, with an explicit counterexample

   Since $X$ is non-empty, it has at least one element; call it $x_0$⁠. Consider the two subsets $\varnothing$ and $X$⁠, both members of $P(X)$⁠.

   • $\varnothing \subset X$ (Basic 2), so $(\varnothing, X) \in R$⁠.
   • $x_0 \in X$ but $x_0 \notin \varnothing$⁠, so $X \not\subset \varnothing$⁠, and $(X, \varnothing) \notin R$⁠.

   The pair $(\varnothing, X)$ is in $R$ but its reverse is not. So $R$ is not symmetric.

   In fact symmetry fails whenever $A \neq B$⁠: if $A \subset B$ and $B \subset A$⁠, every element of each set lies in the other, so $A = B$⁠. Hence the only pairs of $R$ whose reverse is also in $R$ are the pairs $(A,A)$⁠.

   Symmetry is a "for all" statement, so one pair that breaks it settles the matter. We choose $\varnothing$ and $X$ because this pair exists for every non-empty $X$⁠, whatever its size, and the check uses nothing except the single element $x_0$⁠. This is exactly where the hypothesis "non-empty" is used: it guarantees $X \neq \varnothing$⁠, so the two sets really are different. When $|X| = 1$⁠, $P(X) = \{\varnothing, X\}$ has only 2 members and this is the only pair of different subsets there is; it still breaks symmetry.
   To show $B \not\subset A$⁠, exhibit one element of $B$ that is not in $A$⁠. Two sets are equal exactly when each is a subset of the other. Basics: proving and disproving

4. Transitive: containment passes along a chain

   Suppose $(A,B) \in R$ and $(B,C) \in R$⁠, that is $A \subset B$ and $B \subset C$⁠. Take any element $x \in A$⁠. Then

   $$x \in A \ \overset{A\subset B}{\Longrightarrow}\ x \in B \ \overset{B\subset C}{\Longrightarrow}\ x \in C.$$

   So every element of $A$ is in $C$⁠, that is $A \subset C$ and $(A,C)\in R$⁠. Hence $R$ is transitive.

   To prove $A \subset C$ we must show "every element of $A$ is in $C$", so we start with an arbitrary element $x$ of $A$ and follow it through the two given containments. Nothing about the size of the sets is used, so the argument works for all subsets at once. For example $\{1\} \subset \{1,2\} \subset \{1,2,3\}$ gives $\{1\} \subset \{1,2,3\}$⁠.
   Transitive: $(a,b)\in R$ and $(b,c)\in R$ imply $(a,c)\in R$ (Definition 3(iii)). Basics: reflexive, symmetric, transitive

5. Conclude, and how the answer depends on $X$

   $R$ is reflexive and transitive, but not symmetric. An equivalence relation needs all three properties, so $R$ is not an equivalence relation on $P(X)$.

   Size of $X$	Members of $P(X)$	Symmetric?	Equivalence?
   $|X| = 0$ (excluded by the question)	1: just $\varnothing$	yes: $R = \{(\varnothing,\varnothing)\}$	yes
   $|X| = 1$	2: $\varnothing, X$	no: $(\varnothing,X)\in R$⁠, $(X,\varnothing)\notin R$	no
   $|X| = n \ge 1$	$2^n$	no: same counterexample	no

   So the answer "No" holds for every non-empty $X$⁠, from one element upwards. The only set for which $R$ would be an equivalence relation is $X = \varnothing$⁠, where $P(X)$ has the single member $\varnothing$ and $R = \{(\varnothing,\varnothing)\}$⁠. That is why the question says "non empty".

   If $\subset$ were read as proper subset ($A \subset B$ and $A \ne B$⁠), the answer is still No, and for an extra reason: $A$ is never a proper subset of itself, so $R$ would not even be reflexive. It would still be transitive, and still not symmetric.

   Recording exactly which property fails, and for which $X$⁠, turns "No" into a complete justification. The edge cases are where a careless answer goes wrong: the counterexample needs two different subsets, and a non-empty $X$ always supplies them.
   Equivalence relation = reflexive + symmetric + transitive (Definition 4). Failing any one of them is enough to say "not an equivalence relation". Lesson: types of relations

Every fact used, and where it comes from