lets A and B be two finite sets, proof (or give a counter example) that ∣A∪B∣≤∣A∩B∣ ⇒ A=B


Question and Answers Forum

All Questions Topic List
Set Theory Questions
Previous in All Question Next in All Question
Previous in Set Theory Next in Set Theory
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 W hen A \cap B = \emptyset, ∣ A \cap B ∣= 0$ $SubCase (a) At least one of A and B is nonempty .$ $Say A is nonempty$ $∣ A ∣> 0 \land ∣ B ∣⩾ 0 \Rightarrow∣ A ∣ + ∣ B ∣> 0$ $∣ A \cup B ∣=∣ A ∣ + ∣ B ∣> 0 [A and B are disjoint sets .] . . . . I$ $∣ A \cap B ∣= 0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . II$ $∣ A \cup B ∣>∣ A \cap B ∣ [From I and II] ∣$ $In this subcase ∣ A \cup B ∣ ≰ ∣ A \cap B ∣$ $Not concerned the result to prove .$ $SubCase (b) When A = \emptyset and B = \emptyset, ∣ A ∣= 0 and ∣ B ∣= 0 .$ $∣ A \cup B ∣=∣ A ∣ + ∣ B ∣= 0 + 0 = 0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . I$ $∣ A \cap B ∣= 0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . II$ $∣ A \cup B ∣= ∣ A \cap B ∣\Rightarrow A = B = \emptyset [From I and II]$ $∣ A \cup B ∣=∣ A \cup B ∣\Rightarrow A = B$ $Proved the result in this subcase .$ $Case - 2 When A \cap B \neq \emptyset i - e A and B are overlapping sets .$ $SubCase (a) A ⊊ B \land B ⊊ A m e a n s A \cap B \subseteq A \land A \cap B \subseteq B$ $∣ A \cup B ∣=∣ A ∣ + ∣ B ∣ - ∣ A \cap B ∣$ $A \cap B \subset A \Rightarrow∣ A \cap B ∣< ∣ A ∣, A \cap B \subset B \Rightarrow∣ A \cap B ∣ < ∣ B ∣$ $\Rightarrow 2 ∣ A \cap B ∣<∣ A ∣ + ∣ B ∣$ $\Rightarrow ∣ A \cap B ∣ <∣ A ∣ + ∣ B ∣ - ∣ A \cap B ∣$ $\Rightarrow∣ A \cap B ∣<∣ A \cup B ∣$ $\Rightarrow∣ A \cup B ∣>∣ A \cap B ∣$ $Not concerned with the result to prove .$ $SubCase (b) One of A and B is subset of other$ $Say A \subseteq B \Rightarrow ∣ A ∣⩽∣ B ∣$ $A \cup B = B \Rightarrow∣ A \cup B ∣=∣ B ∣$ $A \cap B = A \Rightarrow∣ A \cap B ∣=∣ A ∣$ $∣ A ∣⩽∣ B ∣\Rightarrow ∣ A \cap B ∣⩽∣ A \cup B ∣\Rightarrow∣ A \cup B ∣⩾∣ A \cap B ∣$ $\Rightarrow \underset{N o t c o n c e r n e d}{∣ A \cup B ∣>∣ A \cap B ∣} \lor ∣ A \cup B ∣=∣ A \cap B ∣$ $SubCase (c) A \subseteq B \land B \subseteq A i - e A = B$ $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 A and B . Then we will prove :$ $\underline{∣ A \cup B ∣=∣ A \cap B ∣ \Rightarrow A = B}$ ${\begin{cases} A \cap B \subseteq A \\ A \cap B \subseteq B \end{cases} \Rightarrow {\begin{cases} ∣ A \cap B ∣⩽ ∣ A ∣ \\ ∣ A \cap B ∣⩽ ∣ B ∣ \end{cases} \Rightarrow 2 ∣ A \cap B ∣⩽∣ A ∣ + ∣ B ∣$ $\Rightarrow∣ A \cap B ∣ ⩽ ∣ A ∣ + ∣ B ∣ - ∣ A \cap B ∣$ $\Rightarrow∣ A \cap B ∣⩽ ∣ A \cup B ∣ [∵ ∣ A \cup B ∣=∣ A ∣ + ∣ B ∣ - ∣ A \cap B ∣]$ $\Rightarrow∣ A \cup B ∣ ⩾ ∣ A \cap B ∣$ $\Rightarrow∣ A \cup B ∣≮ ∣ A \cap B ∣$ $Proof for ∣ A \cup B ∣=∣ A \cap B ∣ \Rightarrow A = B$ $On the contrary suppose A \neq B$ $Then there must be a member x which belongs to$ $one of A and B and {doesn}^{'} t belong to other .$ $Say x \in A \land x \notin B$ $\Rightarrow x \in A \cup B but x \notin A \cap B$ $\Rightarrow ∣ A \cup B ∣\neq∣ A \cap B ∣$ $Which contradicts the given [∣ A \cup B ∣=∣ A \cap B ∣]$ $Hence A = B (p r o v e d)$ $∣ A \cup B ∣=∣ A \cap B ∣ \Rightarrow A = B (More specific)$ $Or we can say also,$ $∣ A \cup B ∣⩽∣ A \cap B ∣ \Rightarrow A = B (Not specific)$
	Commented by 112358 last updated on 01/Sep/15

	$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

	$Thank S 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 ∣ A \cup B ∣=∣ A \cap B ∣ but you reached$ $at ∣ A \cup B ∣\neq∣ A \cap 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 \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

	$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!$
Terms of Service
Privacy Policy
Contact: info@tinkutara.com

Question and Answers Forum