Mathamatical Proof: Show that |S union T| = |S|+|T|-|S inter

I

ifoan

New member
Joined
Oct 19, 2006
Messages
36
Since I'm needing to do proofs and I don't know how to do it, I'm practicing. Can anyone tell me if this is a valid proof?

Let \(\displaystyle S\) and \(\displaystyle T\) be sets. Show that \(\displaystyle \mid S \cup T \mid = \mid S \mid + \mid T\mid - \mid S\cap T\mid.\)

Let \(\displaystyle S=T\)

Then it follows that \(\displaystyle \mid S \cup T \mid = \mid T \mid\)

It also follows that \(\displaystyle \mid S \mid = \mid T \mid\)

Thus, we can say \(\displaystyle \mid T \mid = \mid T \mid + \mid T \mid - 0\) (because \(\displaystyle S \cap T = 0\) if \(\displaystyle S=T\))

Thus, it can't be true because the right hand side would be double the left side.
 
Re: Mathamatical Proofs

ifoan said:
Since I'm needing to do proofs and I don't know how to do it, I'm practicing. Can anyone tell me if this is a valid proof?

Let \(\displaystyle S\) and \(\displaystyle T\) be sets. Show that \(\displaystyle \mid S \cup T \mid = \mid S \mid + \mid T\mid - \mid S\cap T\mid.\)

Let \(\displaystyle S=T\)

Then it follows that \(\displaystyle \mid S \cup T \mid = \mid T \mid\)

It also follows that \(\displaystyle \mid S \mid = \mid T \mid\)

Thus, we can say \(\displaystyle \mid T \mid = \mid T \mid + \mid T \mid - 0\) (because \(\displaystyle S \cap T = 0\) if \(\displaystyle S=T\))

Thus, it can't be true because the right hand side would be double the left side.
Click to expand...

For one thing, your proposition is true. Also, you can't assume S=T. Thirdly, if S = T, then it is true that |S|=|T|, but how did did you come to the conclusion that |S \(\displaystyle \cap\) T| = 0? If S=T then |S|=|T| = |S \(\displaystyle \cup\) T| = |S \(\displaystyle \cap\) T|.

You need to prove this with two arbitrary sets S and T. You can't assume that S=T or S \(\displaystyle \subset\) T or T \(\displaystyle \subset\) S. You may be able to use the fact that at least one of them has to be true, though.
 
That is totally not the case.
\(\displaystyle \left| {S \cup T} \right| = \left| S \right| + \left| T \right| - \left| {S \cap T} \right|\) is the most basic counting principle known as inclusion/exclusion.
The idea of proving it strictly depends on the axioms one adopts.
In fact, some authors actually use that as an axiom.

Generally speaking, we can start with:
\(\displaystyle \begin{array}{l}
\mbox{AXIOM: } S \cap T = \emptyset \Rightarrow \left| {S \cup T} \right| = \left| S \right| + \left| T \right| \\
\left| {S \cup T} \right| = \left| S \right| + \left| {T\backslash S} \right|\quad \& \quad \left| T \right| = \left| {T\backslash S} \right| + \left| {S \cap T} \right| \\
\left| {S \cup T} \right| + \left| {S \cap T} \right| = \left| S \right| + \left| {T\backslash S} \right| + \left| {S \cap T} \right| = \left| S \right| + \left| T \right| \\
\left| {S \cup T} \right| = \left| S \right| + \left| T \right| - \left| {S \cap T} \right| \\
\end{array}.\)

But this is by no means the only to proceed.
 
Re: Mathamatical Proofs

daon said:
if S = T, then it is true that |S|=|T|, but how did did you come to the conclusion that |S \(\displaystyle \cap\) T| = 0? If S=T then |S|=|T| = |S \(\displaystyle \cup\) T| = |S \(\displaystyle \cap\) T|.
Click to expand...


your right, |S|=|T| = |S \(\displaystyle \cup\) T| = |S \(\displaystyle \cap\) T|.

i did the intersection wrong. the intersection is all the elements that the two sets have alike..so it would be the same as T.

why can't i assume S=T?
 
Wouldn't it be right because:

Let \(\displaystyle S=T\)

Then it follows that \(\displaystyle \mid S \cup T \mid = \mid T \mid\)

It also follows that \(\displaystyle \mid S \mid = \mid T \mid\)

Thus, we can say \(\displaystyle \mid T \mid = \mid T \mid + \mid T \mid - \mid T \mid\)

Then:
\(\displaystyle \mid T \mid = \mid T \mid\)

or is my logic all wrong?
 
ifoan said:
Wouldn't it be right because:

Let \(\displaystyle S=T\)

Then it follows that \(\displaystyle \mid S \cup T \mid = \mid T \mid\)

It also follows that \(\displaystyle \mid S \mid = \mid T \mid\)

Thus, we can say \(\displaystyle \mid T \mid = \mid T \mid + \mid T \mid - \mid T \mid\)

Then:
\(\displaystyle \mid T \mid = \mid T \mid\)

or is my logic all wrong?
Click to expand...

Well, if you are assuming S=T then you are proving your statement only for those sets that are equal. What if S were {1, 2, 3} and T were {2, 3, 4}? Then you couldn't use your general argument.

You need to start with "Let S, T be sets." S and T may be disjoint, they may be equal, they may have some elements in common. You don't know anything about S and T other than that they are a collection of objects.
 
pka said:
ifoan said:
is my logic all wrong?
Click to expand...
What? You did not like my proof?
Click to expand...

whoops sorry pka, i didn't even see that

are you assuming S intersection T is 0?

So then we have:
\(\displaystyle \left| {S \cup T} \right| = \left| S \right| + \left| T \right| \\\)

From that, we can assume that:
\(\displaystyle \left| {S \cup T} \right| = \left| S \right| + \left| {T\backslash S} \right|\quad \& \quad \left| T \right| = \left| {T\backslash S} \right| + \left| {S \cap T} \right|\)

so then it follows that:
\(\displaystyle \left| {S \cup T} \right| + \left| {S \cap T} \right| = \left| S \right| + \left| {T\backslash S} \right| + \left| {S \cap T} \right| = \left| S \right| + \left| T \right|\)

Thus:
\(\displaystyle \left| {S \cup T} \right| = \left| S \right| + \left| T \right| - \left| {S \cap T} \right|\)

did i understand it correctly?
 
No the whole point is that S & T may intersect.
BUT, S & T\S do not intersect; nor do T\S & T\(\displaystyle \cap\)S.
 
You must log in or register to reply here.
Top