0

Let $R$ be a relation on $\mathbb{N}\times \text{power set}(\mathbb{N})$, defined as $$(a,A)R(b,B)\iff A\setminus B\subseteq\{a,b\}$$

Determine which of the properties reflexivity, symmetry, antisymmetry, and transitivity the relation $R$ possesses. Determine whether it is a partial order or an equivalence relation.

It is reflexive.

I'm having trouble with symmetry.

It seems symmetric to me, though.

Let $(a, A) R (b, B)$. Therefore, $A\setminus B$ is a subset of $\{a, b\}$.

Is $(b, B) R (a, A)$ i.e., is $B\setminus A$ a subset of $\{b, a\} = \{a, b\}$?

Well, I don't know. So, I started constructing a counterexample.

We want $(a, A) R (b, B)$, i.e., $A\setminus B$ is a subset of $\{a, b\}$, BUT $(b, B)\require{cancel} \cancel{R}(a,A)$ , i.e., $B\setminus A$ is NOT a subset of $\{a, b\}$.

Does this mean that $B\setminus A$ is a proper superset of $\{a, b\}$ i.e., is the opposite of "subset" - "proper superset"?

Let's start constructing the differences: $A\setminus B= \{1, 2\}$ and let $a = 1, b = 2$. We want $B\setminus A$ to be a superset of $\{a, b\}$, so it must have at least one more element: $B\setminus A = \{1, 2, 3\}$. Well, is that possible? How should $A$ look like?

$A = \{1, 2, \ldots\}$ (due to $A\setminus B = \{1,2\}$). What about B? $B = \{3, 1, 2, \ldots\}$ (due to $B\setminus A = \{1, 2, 3\}$).

Well, this directly violates $A\setminus B =\{1,2\}$. This means that $B$ does not contain $2$ as an element. But then $B\setminus A$, on the other hand, contains $2$ as an element. It's impossible.

So, I think the relation $R$ is symmetric. If what I asked above is true:

Let's assume that $B\setminus A$ is a proper superset of $\{a, b\}$, i.e., $\{a, b\}$ is a proper subset of $B\setminus A$.

This means that $a, b$ are from the difference $B\setminus A$, i.e., $a, b$ are from $B$ but not from $A$.

We have $A\setminus B$ is a subset of $\{a, b\}$. From here, I want to conclude that $\{a, b\}$ is a subset of $A$, which directly contradicts "$a, b$ are not from $A$", but I'm not sure if I can.

Let's consider the general case $A\setminus B$ is a subset of $C$. Does this imply $C$ is a subset of $A$?

The standard procedure for proving "$C$ is a subset of $A$": let $c$ be from $C$. Well, yeah, but here we can't conclude anything from this.

We can take an element $x$ from $A$ but not from $B$, so it will also be from $C$. And what's the point of this?

SAQ
  • 367
  • 1
    The inclusion $A\setminus B\subset {a,b}$ is saying that $A\setminus B$ can't be "too big." The way to violate symmetry would be to have $A\setminus B$ be a small set while $B\setminus A$ is large. The easiest way to do this is if $A=\varnothing$ and $B=\mathbb{N}$. –  Feb 09 '24 at 11:44
  • 2
    The negation of $B\setminus A\subset {a,b}$ is not "$B\setminus A$ is a proper superset of ${a,b}$". For example, ${3}$ is not a subset of ${1,2}$, nor is it a proper superset of it.

    "Negation" does not mean "opposite." The opposite of short is tall, but the negation of short is "not short," which isn't a synonym for "tall", because someone can be average height.

     –  Feb 09 '24 at 11:51
  • @jwhite, thank you! May I ask you for the transitivity, as I have troubles saying if the relation is transitive, or not, as well? – SAQ Feb 09 '24 at 12:55
  • In general, for any three sets, $A\setminus C\subset (A\setminus B)\cup (B\setminus C)$. This is because $a\in A\setminus C$ iff $a\in A$ and $a\notin C$. Then if $a\notin B$, $a\in A\setminus B$, and if $a\in B$, $a\in B\setminus C$.

    So in this setting, if $A\setminus B\subset {a,b}$ and $B\setminus C\subset {b,c}$, we know $$A\setminus C\subset (A\setminus B)\cup (B\setminus C)\subset {a,b}\cup {b,c}={a,b,c}.$$ If the relation were transitive, we would need to know that $A\setminus C\subset {a,c}$.

     –  Feb 09 '24 at 13:01
  • So if we know that $A\setminus C\subset {a,b,c}$ and we ask whether it must be the case that $A\setminus C\subset {a,c}$, we have to ask whether $A\setminus C$ can contain $b$. If it cannot, we have transitivity. If it can, then you've found a counterexample (assuming ${a,b,c}\neq {a,c}$, which means we need $b$ to be distinct from $a$ and $c$). –  Feb 09 '24 at 13:03
  • @jwhite, I am not really sure I see why $$A\setminus C \subseteq (A\setminus B)\cup (B\setminus C)$$ for arbitraty sets $A, B, C$. Let $x\in A\setminus C,$ so $x\in A$ and $x \notin C$. We should show that $x$ also lies in the RHS. How can this be done? – SAQ Feb 09 '24 at 13:15
  • This is written a few comments above. Consider two cases: Case $1$, $x\in B$. Then $x\in B\setminus C$, which is in the RHS. Case $2$: $x\notin B$, then $x\in A\setminus B$, which is in the RHS. –  Feb 09 '24 at 13:25
  • @jwhite, thank you, I got it! But now I don't see why $b$ couldn't be from $A\setminus C$. I think it can. How do I construct a counterexample though? – SAQ Feb 09 '24 at 13:30
  • Let us continue this discussion in chat. – SAQ Feb 09 '24 at 13:31

1 Answers1

0

Consider possible elements of $A$ and $B$ that are neither $a$ nor $b$ and how they impact the evaluation of the relations.

Let's say $c$ is such and consider all $A, B\subseteq\{a,b,c\}$.

Complete the truth table and examine the result.

$$\boxed{\begin{array}{c:c|c:c} c\in A& c\in B & A\smallsetminus B\subseteq\{a,b\}&B\smallsetminus A\subseteq\{a,b\}\\\hline \mathrm T&\mathrm T\\\hdashline\mathrm T&\mathrm F\\\hdashline \mathrm F&\mathrm T\\\hdashline \mathrm F& \mathrm F\end{array}}$$

Graham Kemp
  • 129,094
  • I am not sure I understand exactly what your idea is, but is this useful for the transitivity for example, as I have troubles saying if the relation is transitive, or not, as well? – SAQ Feb 09 '24 at 12:52
  • I am not sure what we are supposed to right in the first row below $A\setminus B\subseteq{a,b}$. How do we say if it's true or false? – SAQ Feb 09 '24 at 12:59
  • @SAQ If $A$ and $B$ both contain $c$, then $A\setminus B$ will not contain $c$ and is therefore a subset of ${a,b}$. So you write $\mathrm T$. – Graham Kemp Feb 10 '24 at 02:32