lets-A-and-B-be-two-finite-sets-proof-or-give-a-counter-example-that-A-B-A-B-A-B-

Question Number 1672 by 123456 last updated on 30/Aug/15

lets A and B be two finite sets, proof (or give a counter example) that

∣ A \cup B ∣⩽∣ A \cap B ∣ \Rightarrow A = B

Answered by Rasheed Soomro last updated on 01/Sep/15

Case−1 When A∩B=∅ , ∣ A∩B ∣=0 SubCase (a) At least one of A and B is nonempty. Say A is nonempty ∣ A ∣>0 ∧ ∣ B ∣≥0 ⇒∣ A ∣+∣ B ∣>0 ∣ A ∪B ∣=∣ A ∣+∣ B ∣>0 [A and B are disjoint sets.]....I ∣ A∩B ∣=0.............................................................II ∣ A∪B ∣>∣ A∩B ∣ [From I and II]∣ In this subcase ∣ A∪B∣ ≰ ∣ A∩B ∣ Not concerned the result to prove. SubCase (b)When A=∅ and B=∅ , ∣ A ∣=0 and ∣B ∣=0. ∣ A∪B ∣=∣ A ∣+∣ B ∣=0+0=0 .............................I ∣ A∩B ∣=0........................................................II ∣ A∪B ∣= ∣ A∩B ∣⇒A=B=∅ [From I and II] ∣ A∪B ∣=∣A∪B ∣⇒ A=B Proved the result in this subcase. Case−2 When A∩B≠∅ i−e A and B are overlapping sets. SubCase (a) A  B ∧ B  A means A∩B ⊆ A ∧ A∩B ⊆B ∣ A∪B ∣=∣A∣+∣B∣−∣ A∩B ∣ A∩B ⊂ A⇒∣A∩B ∣< ∣A∣ , A∩B ⊂ B⇒∣A∩B∣ < ∣B∣ ⇒ 2∣A∩B∣<∣A∣+∣B∣ ⇒ ∣A∩B∣ <∣A∣+∣B∣−∣A∩B∣ ⇒∣A∩B∣<∣A∪B∣ ⇒∣A∪B∣>∣A∩B∣ Not concerned with the result to prove. SubCase (b) One of A and B is subset of other Say A⊆B ⇒ ∣A∣≤∣B∣ A∪B =B⇒∣A∪B∣=∣B∣ A∩B =A⇒∣A∩B∣=∣A∣ ∣A∣≤∣B∣⇒ ∣A∩B∣≤∣A∪B∣⇒∣A∪B∣≥∣A∩B∣ ⇒∣A∪B∣>∣A∩B∣_(Not concerned) ∨ ∣A∪B∣=∣A∩B∣ SubCase (c) A⊆B ∧ B⊆A i−e A=B Continue

\boldsymbol Case - 1 \boldsymbol W hen \boldsymbol A \cap \boldsymbol B = \emptyset, ∣ \boldsymbol A \cap \boldsymbol B ∣= 0

\boldsymbol SubCase (\boldsymbol a) \boldsymbol At \boldsymbol least \boldsymbol one \boldsymbol of \boldsymbol A \boldsymbol and \boldsymbol B \boldsymbol is \boldsymbol nonempty .

Say \boldsymbol A is nonempty

∣ \boldsymbol A ∣> 0 \land ∣ \boldsymbol B ∣⩾ 0 \Rightarrow∣ \boldsymbol A ∣ + ∣ \boldsymbol B ∣> 0

∣ \boldsymbol A \cup \boldsymbol B ∣=∣ \boldsymbol A ∣ + ∣ \boldsymbol B ∣> 0 [\boldsymbol A and \boldsymbol B are disjoint sets .] \dots . \boldsymbol I

∣ \boldsymbol A \cap \boldsymbol B ∣= 0 \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots . \boldsymbol II

∣ A \cup \boldsymbol B ∣>∣ \boldsymbol A \cap \boldsymbol B ∣ [From \boldsymbol I and \boldsymbol II] ∣

In this subcase ∣ \boldsymbol A \cup \boldsymbol B ∣ ≰ ∣ \boldsymbol A \cap \boldsymbol B ∣

\boldsymbol Not \boldsymbol concerned \boldsymbol the \boldsymbol result \boldsymbol to \boldsymbol prove .

\boldsymbol SubCase (\boldsymbol b) \boldsymbol When \boldsymbol A = \emptyset \boldsymbol and \boldsymbol B = \boldsymbol \emptyset, ∣ \boldsymbol A ∣= 0 and ∣ \boldsymbol B ∣= 0 .

∣ \boldsymbol A \cup \boldsymbol B ∣=∣ \boldsymbol A ∣ + ∣ \boldsymbol B ∣= 0 + 0 = 0 \dots \dots \dots \dots \dots \dots \dots \dots \dots . . \boldsymbol I

∣ \boldsymbol A \cap \boldsymbol B ∣= 0 \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots . . \boldsymbol II

∣ \boldsymbol A \cup \boldsymbol B ∣= ∣ \boldsymbol A \cap \boldsymbol B ∣\Rightarrow \boldsymbol A = \boldsymbol B = \boldsymbol \emptyset [From \boldsymbol I and \boldsymbol II]

∣ \boldsymbol A \cup \boldsymbol B ∣=∣ \boldsymbol A \cup \boldsymbol B ∣\Rightarrow \boldsymbol A = \boldsymbol B

\boldsymbol Proved \boldsymbol the \boldsymbol result \boldsymbol in \boldsymbol this \boldsymbol subcase .

\boldsymbol Case - 2 \boldsymbol When \boldsymbol A \cap \boldsymbol B \neq \boldsymbol \emptyset \boldsymbol i - \boldsymbol e \boldsymbol A \boldsymbol and \boldsymbol B \boldsymbol are \boldsymbol overlapping \boldsymbol sets .

\boldsymbol SubCase (\boldsymbol a) \boldsymbol A ⊊ \boldsymbol B \land \boldsymbol B ⊊ \boldsymbol A m e a n s \boldsymbol A \cap \boldsymbol B \subseteq \boldsymbol A \land \boldsymbol A \cap \boldsymbol B \subseteq \boldsymbol B

∣ \boldsymbol A \cup \boldsymbol B ∣=∣ \boldsymbol A ∣ + ∣ \boldsymbol B ∣ - ∣ \boldsymbol A \cap \boldsymbol B ∣

\boldsymbol A \cap \boldsymbol B \subset \boldsymbol A \Rightarrow∣ \boldsymbol A \cap \boldsymbol B ∣< ∣ \boldsymbol A ∣, \boldsymbol A \cap \boldsymbol B \subset \boldsymbol B \Rightarrow∣ \boldsymbol A \cap \boldsymbol B ∣ < ∣ \boldsymbol B ∣

\Rightarrow 2 ∣ \boldsymbol A \cap \boldsymbol B ∣<∣ \boldsymbol A ∣ + ∣ \boldsymbol B ∣

\Rightarrow ∣ \boldsymbol A \cap \boldsymbol B ∣ <∣ \boldsymbol A ∣ + ∣ \boldsymbol B ∣ - ∣ \boldsymbol A \cap \boldsymbol B ∣

\Rightarrow∣ \boldsymbol A \cap \boldsymbol B ∣<∣ \boldsymbol A \cup \boldsymbol B ∣

\Rightarrow∣ \boldsymbol A \cup \boldsymbol B ∣>∣ \boldsymbol A \cap \boldsymbol B ∣

\boldsymbol Not \boldsymbol concerned \boldsymbol with \boldsymbol the \boldsymbol result \boldsymbol to \boldsymbol prove .

\boldsymbol SubCase (\boldsymbol b) \boldsymbol One \boldsymbol of \boldsymbol A \boldsymbol and \boldsymbol B \boldsymbol is \boldsymbol subset \boldsymbol of \boldsymbol other

\boldsymbol Say \boldsymbol A \subseteq \boldsymbol B \Rightarrow ∣ \boldsymbol A ∣⩽∣ \boldsymbol B ∣

\boldsymbol A \cup \boldsymbol B = \boldsymbol B \Rightarrow∣ \boldsymbol A \cup \boldsymbol B ∣=∣ \boldsymbol B ∣

\boldsymbol A \cap \boldsymbol B = \boldsymbol A \Rightarrow∣ \boldsymbol A \cap \boldsymbol B ∣=∣ \boldsymbol A ∣

∣ \boldsymbol A ∣⩽∣ \boldsymbol B ∣\Rightarrow ∣ \boldsymbol A \cap \boldsymbol B ∣⩽∣ \boldsymbol A \cup \boldsymbol B ∣\Rightarrow∣ \boldsymbol A \cup \boldsymbol B ∣⩾∣ \boldsymbol A \cap \boldsymbol B ∣

\Rightarrow \underset{N o t c o n c e r n e d}{∣ \boldsymbol A \cup \boldsymbol B ∣>∣ \boldsymbol A \cap \boldsymbol B ∣} \lor ∣ \boldsymbol A \cup \boldsymbol B ∣=∣ \boldsymbol A \cap \boldsymbol B ∣

\boldsymbol SubCase (\boldsymbol c) \boldsymbol A \subseteq \boldsymbol B \land \boldsymbol B \subseteq \boldsymbol A \boldsymbol i - \boldsymbol e \boldsymbol A = \boldsymbol B

\boldsymbol Continue

Answered by Rasheed Soomro last updated on 01/Sep/15

∣A∪B∣≤∣A∩B∣ ⇒ A=B ⇒ ∣A∪B∣<∣A∩B∣ ⇒ A=B_(−) ∨ ∣A∪B∣=∣A∩B∣ ⇒ A=B_(−) First we will prove that[ ∣A∪B∣<∣A∩B∣ ⇒ A=B_(−) ] is false for any A and B. Then we will prove : ∣A∪B∣=∣A∩B∣ ⇒ A=B_(−) { ((A∩B ⊆ A)),((A∩B ⊆ B)) :}⇒ { ((∣A∩B ∣≤ ∣A∣)),((∣A∩B ∣≤ ∣B∣)) :}⇒2∣A∩B∣≤∣A∣+∣B∣ ⇒∣A∩B∣ ≤ ∣A∣+∣B∣−∣A∩B∣ ⇒∣A∩B∣≤ ∣A∪B∣ [ ∵ ∣A∪B∣=∣A∣+∣B∣−∣A∩B∣ ] ⇒∣A∪B∣ ≥ ∣A∩B∣ ⇒∣A∪B∣≮ ∣A∩B∣ Proof for ∣A∪B∣=∣A∩B∣ ⇒ A=B On the contrary suppose A≠B Then there must be a member x which belongs to one of A and B and doesn′t belong to other. Say x ∈ A ∧ x ∉ B ⇒ x ∈ A∪B but x ∉ A∩B ⇒ ∣A∪B∣≠∣A∩B∣ Which contradicts the given [ ∣A∪B∣=∣A∩B∣ ] Hence A=B (proved) ∣A∪B∣=∣A∩B∣ ⇒ A=B (More specific) Or we can say also, ∣A∪B∣≤∣A∩B∣ ⇒ A=B (Not specific)

∣ A \cup B ∣⩽∣ A \cap B ∣ \Rightarrow A = B

\Rightarrow \underline{∣ A \cup B ∣<∣ A \cap B ∣ \Rightarrow A = B} \lor \underline{∣ A \cup B ∣=∣ A \cap B ∣ \Rightarrow A = B}

First we will prove that [\underline{∣ A \cup B ∣<∣ A \cap B ∣ \Rightarrow A = B}] is false

for any \boldsymbol A and \boldsymbol B . Then we will prove :

\underline{∣ A \cup B ∣=∣ A \cap B ∣ \Rightarrow A = B}

{\begin{cases} \boldsymbol A \cap \boldsymbol B \subseteq \boldsymbol A \\ \boldsymbol A \cap \boldsymbol B \subseteq \boldsymbol B \end{cases} \Rightarrow {\begin{cases} ∣ \boldsymbol A \cap \boldsymbol B ∣⩽ ∣ \boldsymbol A ∣ \\ ∣ \boldsymbol A \cap \boldsymbol B ∣⩽ ∣ \boldsymbol B ∣ \end{cases} \Rightarrow 2 ∣ \boldsymbol A \cap \boldsymbol B ∣⩽∣ \boldsymbol A ∣ + ∣ \boldsymbol B ∣

\Rightarrow∣ \boldsymbol A \cap \boldsymbol B ∣ ⩽ ∣ \boldsymbol A ∣ + ∣ \boldsymbol B ∣ - ∣ \boldsymbol A \cap \boldsymbol B ∣

\Rightarrow∣ \boldsymbol A \cap \boldsymbol B ∣⩽ ∣ \boldsymbol A \cup \boldsymbol B ∣ [∵ ∣ \boldsymbol A \cup \boldsymbol B ∣=∣ \boldsymbol A ∣ + ∣ \boldsymbol B ∣ - ∣ \boldsymbol A \cap \boldsymbol B ∣]

\Rightarrow∣ \boldsymbol A \cup \boldsymbol B ∣ ⩾ ∣ \boldsymbol A \cap \boldsymbol B ∣

\Rightarrow∣ \boldsymbol A \cup \boldsymbol B ∣≮ ∣ \boldsymbol A \cap \boldsymbol B ∣

\boldsymbol Proof \boldsymbol for ∣ \boldsymbol A \cup \boldsymbol B ∣=∣ \boldsymbol A \cap \boldsymbol B ∣ \Rightarrow \boldsymbol A = \boldsymbol B

On the contrary suppose \boldsymbol A \neq \boldsymbol B

Then there must be a member x which belongs to

one of \boldsymbol A and \boldsymbol B and {doesn}^{'} t belong to other .

Say x \in \boldsymbol A \land x \notin \boldsymbol B

\Rightarrow x \in \boldsymbol A \cup \boldsymbol B but x \notin \boldsymbol A \cap \boldsymbol B

\Rightarrow ∣ \boldsymbol A \cup \boldsymbol B ∣\neq∣ \boldsymbol A \cap \boldsymbol B ∣

Which contradicts the given [∣ \boldsymbol A \cup \boldsymbol B ∣=∣ \boldsymbol A \cap \boldsymbol B ∣]

Hence \boldsymbol A = \boldsymbol B (p r o v e d)

∣ \boldsymbol A \cup \boldsymbol B ∣=∣ \boldsymbol A \cap \boldsymbol B ∣ \Rightarrow \boldsymbol A = \boldsymbol B (\boldsymbol More \boldsymbol specific)

\boldsymbol Or \boldsymbol we \boldsymbol can \boldsymbol say \boldsymbol also,

∣ \boldsymbol A \cup \boldsymbol B ∣⩽∣ \boldsymbol A \cap \boldsymbol B ∣ \Rightarrow \boldsymbol A = \boldsymbol B (\boldsymbol Not \boldsymbol specific)

Commented by 112358 last updated on 01/Sep/15

In your proof of ∣A∪B∣=∣A∩B∣⇒A=B you correctly proved the implication by proving the contrapositive of the statement (A≠B⇒∣A∪B∣≠∣A∩B∣). But, I was confused a bit when reading it where you said ′Which contradicts!′ because then it sounds as if the result is never true given A≠B,which is employed in the method of proof by contradiction. It doesn′t seem necessary to put in that line of text. You finished the essence of the proof when you showed that ∣A∪B∣≠∣A∩B∣. p⇒q is logically equivalent to ∽q⇒∽p.

I n y o u r p r o o f o f ∣ A \cup B ∣=∣ A \cap B ∣\Rightarrow A = B

y o u c o r r e c t l y p r o v e d t h e i m p l i c a t i o n

b y p r o v i n g t h e c o n t r a p o s i t i v e o f

t h e s t a t e m e n t (A \neq B \Rightarrow∣ A \cup B ∣\neq∣ A \cap B ∣) .

B u t, I w a s c o n f u s e d a b i t w h e n

r e a d i n g i t w h e r e y o u s a i d^{'} W h i c h

c o n t r a d i c t s!^{'} b e c a u s e t h e n i t s o u n d s

a s i f t h e r e s u l t i s n e v e r t r u e g i v e n A \neq B, w h i c h

i s e m p l o y e d i n t h e m e t h o d o f

p r o o f b y c o n t r a d i c t i o n . I t {d o e s n}^{'} t

s e e m n e c e s s a r y t o p u t i n t h a t l i n e

o f t e x t . Y o u f i n i s h e d t h e e s s e n c e

o f t h e p r o o f w h e n y o u s h o w e d

t h a t ∣ A \cup B ∣\neq∣ A \cap B ∣ .

p \Rightarrow q i s l o g i c a l l y e q u i v a l e n t t o

∽ q \Rightarrow∽ p .

Commented by 112358 last updated on 01/Sep/15

V e r y g o o d a n a l y s i s o v e r a l l!

Commented by Rasheed Soomro last updated on 01/Sep/15

ThankSSssssss for guidance! Use of proper language in Mathematics, specially in logic is basic need. I am not much confident regarding language. However in above answer by ′ Which contradicts ′ I mean contradicts the given. If P is given and you reached at ∼P what should you say! Given is ∣A∪B∣=∣A∩B∣ but you reached at ∣A∪B∣≠∣A∩B∣. Is this not contradiction? Anyway you have provided a good alternate way of saying same thing!

Thank S \boldsymbol Sss s s s s for guidance!

Use of proper language in M athematics, specially in logic

is basic need . I am not much confident regarding language .

However in above answer by^{'} Which contradicts^{'} I mean

contradicts the given . If P is given and you reached at \sim P

what should you say! Given is ∣ \boldsymbol A \cup \boldsymbol B ∣=∣ \boldsymbol A \cap \boldsymbol B ∣ but you reached

at ∣ \boldsymbol A \cup \boldsymbol B ∣\neq∣ \boldsymbol A \cap \boldsymbol B ∣ . Is this not contradiction ?

Anyway you have provided a good alternate way of saying

same thing!

Commented by 123456 last updated on 01/Sep/15

p:∣A∪B∣=∣A∩B∣ q:A=B p→q=(∼q)→(∼p) A≠B⇒∣A∪B∣≠∣A∩B∣

p :∣ A \cup B ∣=∣ A \cap B ∣

q : A = B

p \to q = (\sim q) \to (\sim p)

A \neq B \Rightarrow∣ A \cup B ∣\neq∣ A \cap B ∣

Commented by 112358 last updated on 01/Sep/15

Yes. I understand what you mean. Ijust saw the correction you made. I now see how you decided to argue the proof in such a way that saying ′contradiction found′ makes sense.

Y e s . I u n d e r s t a n d w h a t y o u m e a n .

I j u s t s a w t h e c o r r e c t i o n y o u m a d e .

I n o w s e e h o w y o u d e c i d e d t o

a r g u e t h e p r o o f i n s u c h a w a y

t h a t s a y i n g^{'} c o n t r a d i c t i o n {f o u n d}^{'}

m a k e s s e n s e .

Commented by Rasheed Soomro last updated on 01/Sep/15

T h a n k s s s s s s!

T h a n k s s s s s s!

Facebook Tweet Pin

lets-A-and-B-be-two-finite-sets-proof-or-give-a-counter-example-that-A-B-A-B-A-B-

Leave a Reply Cancel reply