0

I pretty confused about how to deal with this. how can I determine for a relation ($R$) on a power set whether it is reflective, symmetric, transitive. When $A$ is the final amount and $P(A)$ is the power set. Consider the relation $R$ of $P(A) $ given by:

$sRt \iff |s| = |t|$

I know that a relation is considered an equivalence relation if it satisfies reflexive, symmetric and transitive properties but Im having trouble to figure out how to show that in my example.

Kenta S
  • 16,151
  • 15
  • 26
  • 53
Betis
  • 3
  • 1
    You do it in exactly the same way that you would normally... the only difference here is in flavor. Rather than dealing with "urelements", we are dealing with elements which are themselves also sets. That is okay though. So, consider $A={1,2,3,4}$ as an example. The power set of $A$ would be the set that includes all subsets of $A$. We would have two of our subsets are "related" if they are the same size... for example $|{1,2}|=|{1,4}|$ since these are both two-element subsets of $A$ but ${1}$ is not related to ${1,2,3}$ since they have different number of elements. – JMoravitz Dec 02 '19 at 15:42
  • Now... given an arbitrary choice of $A$, and given a particular subset of $A$ which we'll go ahead and call $s$, is it true that $|s|=|s|$, i.e. that $s$ has the same number of elements as $s$? Does that mean then that $s\mathcal{R}s$ and that $s$ is related to itself for our relation we are discussing? Does that mean that $\mathcal{R}$ is reflexive? Continue with the other properties. – JMoravitz Dec 02 '19 at 15:44
  • thanks a-lot for your help and time:) So if I understands it right, this relation is refleksive if A and the power set has same size. I will say it is because one of A's power set is itself "I means one of A's power set is {1,2,3,4}" aswell. Or am I wrong? and when we look at the symetric relation it says sRt then s = t and then t = s is also true and I guess if A's power set has same size then the power set must be equal to A. I guessing a little bit, I hope you can clear me out a bit. :) – Betis Dec 02 '19 at 16:03
  • The relation is reflexive if we have $sRs$ or equivalently $|s|=|s|$ for every $s\in\wp(A)$. (which of course is true). – drhab Dec 02 '19 at 16:20
  • @Betis "if $A$ and the power set has same size" Nonono... we are not talking about whether or not $A$ is related to $\mathcal{P}(A)$. We are asking whether or not elements of the power set of $A$ are related to other elements of the powerset of $A$... – JMoravitz Dec 02 '19 at 16:21
  • okay I see. thanks a lot :) – Betis Dec 02 '19 at 16:23
  • 1
    With the way you are using the word "powerset" here, it sounds like you are confused as to what a powerset is and are using the word where you mean to be using other words such as "subset." One of $A$'s subsets will be related to another of $A$'s subsets if the two subsets are the same size (regardless of whether or they are the same size as $A$ or the same size as the power set of $A$ or anything else) – JMoravitz Dec 02 '19 at 16:23

2 Answers2

1

In general if $f$ is a function that has set $X$ as domain then the relation $\sim$ on $X$ that is prescribed by:$$x\sim y\iff f(x)=f(y)$$is an equivalence relation.

To verify that we only need to check that the following conditions are satisfied:

  • $f(x)=f(x)$ for every $x\in X$ (reflexivity)
  • $f(x)=f(y)\implies f(y)=f(x)$ for all $x,y\in X$ (symmetry)
  • $f(x)=f(y)\text{ and }f(y)=f(z)\implies f(x)=f(z)$ (transitivity)

It is evident that these conditions are satisfied.

Now realize that in your case we are dealing with a function $|\cdot|$ that has powerset $\wp(A)$ as domain and that the relation $R$ is prescribed by:$$sRt\iff|s|=|t|$$

So what is said above immediately applies to your case.

drhab
  • 151,093
0

Given $A$ is nonempty set and assume $\mid A \mid=n$, then $\mid \mathcal{P}(A)\mid=2^n$. Take $p,q,r\in\mathcal{P}(A)$. We'll prove the relation is equivalence relation.

  1. Refleksive $pRq\iff \mid p\mid=\mid q\mid \iff \mid q\mid=\mid p\mid\iff qRp$
  2. Symmetric $pRq\iff \mid p\mid=\mid q\mid\Longrightarrow \mid q \mid=\mid p \mid\iff qRp$
  3. Transitive $pRq\iff \mid p\mid=\mid q\mid$, $qRr\iff \mid q\mid=\mid r\mid$, hence we get $$\mid p\mid=\mid q\mid=\mid r\mid \Longrightarrow \mid p\mid=\mid r\mid\iff pRr$$
PRASTYA SUSANTO
  • 155