MHB Proving Set Equivalence with Set Differences?

  • Thread starter Thread starter A.Magnus
  • Start date Start date
  • Tags Tags
    Equivalence Set
AI Thread Summary
The discussion focuses on proving the set equivalence between two sets, S and T, under the condition that the differences of the sets are equinumerous. The initial proof attempts to establish a bijection from S to T based on the existence of a bijection between the differences of the sets. However, flaws are identified in the logic, particularly regarding the identity function and the definition of a function's domain. A corrected approach is proposed, suggesting an explicit construction of a bijection that combines the existing bijection with the identity function on the intersection of the sets. The conversation emphasizes the importance of rigor in proving bijections and clarifying definitions related to functions.
A.Magnus
Messages
138
Reaction score
0

I am working on a set equivalent (the textbook refers as "equinumerous" denoted by ~) as follows:

If $S$ and $T$ are sets, prove that if $(S\backslash T) \sim (T\backslash S)$, then $S \sim T$.​

Here is my own proof, I am posting it here wanting to know if it is valid. (It may not be as elegant as the textbook's proof though.)

(1) We do not consider the cases of $S \subseteq T$, $T \subseteq S$ or $S \cap T = \emptyset$ since they lead to trivial solutions. We consider only the case where $S \cap T \ne \emptyset$. See the Venn diagram above.
(2) $(S \backslash T) \sim (T \backslash S)$ implies the existence of bijection $f: (S\backslash T) \to (T\backslash S)$. Here we need to prove the existence of bijection $g: S \rightarrow T$ to show $S \sim T$.
(3) Looking at the diagram, we need to prove only the existence of bijection $h: (S \cap T) \rightarrow T$ in order to prove the existence of bijection $g: S \rightarrow T$, since the bijection $f: (S \backslash T) \rightarrow (T \backslash S)$ is given.
(4) For all $x \in S \cap T,$ we have $ x \in S$ and $x \in T$. Hence the function $h: (S \cap T) \rightarrow T$ is in fact $h: T \rightarrow T$, which is an identity function. Since by textbook's theorem an identity function is always bijective, therefore $h: (S \cap T) \rightarrow T$ is indeed bijective.
(5) Hence there exists bijection $g: S \rightarrow T$, implying that $S \sim T$, as desired.

Thank you so much for your time and gracious help. ~MA
 

Attachments

  • VennDiagram.jpg
    VennDiagram.jpg
    8.7 KB · Views: 137
Last edited:
Physics news on Phys.org
Let $S=\{1,2\}$ and $T=\{2,3\}$. Then $S\cap T=\{2\}$. But the identity function from $S\cap T$ to $T$ is not a bijection, since these sets have different number of elements.

Also, strictly speaking a function $f:A\to B$ is a triple $(f,A,B)$ where $f\subseteq A\times B$ satisfying a couple of properties. In this sense one cannot arbitrarily change the function domain $A$. So saying "The function $h:S\cap T\to T$ is in fact $h:T\to T$" is inaccurate.
 
You have a bijection $f:(S\setminus T)\to(T\setminus S)$; you need to extend it to a function $F:S\to T$. The obvious candidate is the following:
$$F:S\to T;\ F(x)=\begin{cases}f(x) &\text{if}& x\in S\setminus T, \\\\ x &\text{if}& x\in S\cap T.\end{cases}$$
All you need to do now is to prove that $F:S\to T$ is a bijection.
 
Evgeny.Makarov said:
Let $S=\{1,2\}$ and $T=\{2,3\}$. Then $S\cap T=\{2\}$. But the identity function from $S\cap T$ to $T$ is not a bijection, since these sets have different number of elements.

Also, strictly speaking a function $f:A\to B$ is a triple $(f,A,B)$ where $f\subseteq A\times B$ satisfying a couple of properties. In this sense one cannot arbitrarily change the function domain $A$. So saying "The function $h:S\cap T\to T$ is in fact $h:T\to T$" is inaccurate.

Thank you for your time. Apparently my logic was flawed. ~MA
 
Olinguito said:
You have a bijection $f: (S\setminus T)\to(T\setminus S)$; you need to extend it to a function $F:S\to T$. The obvious candidate is the following:
$$F:S\to T;\ F(x)=\begin{cases}f(x) &\text{if}& x\in S\setminus T, \\\\ x &\text{if}& x\in S\cap T.\end{cases}$$

All you need to do now is to prove that $F:S\to T$ is a bijection.


Thank you again for pointing this function out. The easiest way I can think of proving $F$ is bijective is by showing that both $F$ and $F^{-1}$ is injective. Is there any other simpler way? Thank you again for your time and gracious helps. ~MA
 
Last edited by a moderator:
MaryAnn said:
The easiest way I can think of proving $F$ is bijective is by showing that both $F$ and $F^{-1}$ is injective.
What do you mean by $F^{-1}$?
 
Evgeny.Makarov said:
What do you mean by $F^{-1}$?

Opps! I don't understand why my mind strayed off. I am sorry. Let's do these:

(a) If $x \in S \backslash T$, the $f: (S \backslash T) \rightarrow (T \backslash S)$ is given as bijection by the problem.
(b) If $x \in S \cap T$ on the other hand, the $F(x) = x$ is an identity function and therefore it is a bijection. Hence $F(X)$ is a bijection.

Let me know and thank you again for all your times and gracious helps. ~MA
 
MaryAnn said:
Opps! I don't understand why my mind strayed off.
I didn't mean to say that $F^{-1}$ is out of place in this context. I just wanted to point out that inverse function may have slightly different definitions, and I was wondering what statement exactly regarding inverse functions you were using to show that $F$ is bijections. A potential complication is that one of the definitions allows $F^{-1}$ only when $F$ is already proven to be a bijection.

MaryAnn said:
(a) If $x \in S \backslash T$, the $f: (S \backslash T) \rightarrow (T \backslash S)$ is given as bijection by the problem.
(b) If $x \in S \cap T$ on the other hand, the $F(x) = x$ is an identity function and therefore it is a bijection.
I agree.

MaryAnn said:
Hence $F(X)$ is a bijection.
What statement are you using to justify this conclusion? The fact that you are trying to prove is rather simple, so the proof should be detailed. I think you made a leap here that is somewhat more than the intended level of detail allows.

I recommend using the definition of bijection to prove that $F$ is one.
 
This is how I would do the problem (it may be the same solution as the one in your textbook).

Olinguito said:
$$F:S\to T;\ F(x)=\begin{cases}f(x) &\text{if}& x\in S\setminus T, \\\\ x &\text{if}& x\in S\cap T.\end{cases}$$

First, prove that $F$ is injective. Note that as $T\setminus S$ and $S\cap T$ are disjoint, we have that for any $x\in S$, $F(x)\in T\setminus S\ \iff\ x\in S\setminus T$ (and similarly $F(x)\in S\cap T\ \iff\ x\in S\cap T$). Suppose $F(x_1)=F(x_2)$, $x_1,x_2\in S$. If $F(x_1),F(x_2)\in T\setminus S$, then $x_1,x_2\in S\setminus T$ and so $f(x_1)=F(x_1)=F(x_2)=f(x_2)$ and so, as $f$ is injective, we have $x_1=x_2$. If $F(x_1),F(x_2)\in S\cap T$, then $x_1,x_2\in S\cap T$ and so $x_1=F(x_1)=F(x_2)=x_2$. Hence $F$ is injective.

Now prove it’s surjective. Let $y\in T$. If $y\in T\setminus S$, then $y=f(x)$ for some $x\in S\setminus T$, by surjectivity of $f$, whence $y=f(x)=F(x)$. If $y\in S\cap T$, then $y=F(y)$. This shows that $F$ is surjective. QED.
 
Last edited:
  • #10
Some $S\setminus T$ (at least three) have to be changed to $T\setminus S$.
 
Back
Top