0

Question

Let $S$ be a relation defined on $\mathcal{P}(\mathbb{N})$ by $XSY$ if and only if $X \subseteq Y$ and $|X| \equiv |Y|$(mod $2$).

My method

My thought process was that since Antisymmetry means that...

If $XSY$ and $YSX$ if and only if $Y = X$. Therefore, if $X \subseteq Y$ then $Y$ is not a subset of $X$. So the first part is True.

The second part however is where I am a little confused about.

If $|X| \equiv |Y|$ (mod $2$), then $|Y| \equiv$ $|X|$ (mod $2$). Thus making this not Antisymmetric. At least this is what I thought of at the time.

Upon checking the answers, the answer that was given states that this relation is Antisymmetric. But I can't figure out why.

Can anyone help me to understand this? Did I understand it incorrectly?

Bryan Hii
  • 325

1 Answers1

1

You want to prove the claim for two separate relations. It's however about one relation, namely the intersection of the two.

We can prove it more generally: if $R$ is antisymmetric ($x\,R\,y\,R\,x\implies x=y$) then so is $R\cap S$ for any relation $S$.

Proof: assume $x\,(R\cap S)\,y\,(R\cap S)\,x$, then because of the intersection, we must have $x\,R\,y\,R\,x$ as well, but that already implies $x=y$.

Berci
  • 90,745