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 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 .] \dots . I

∣ A \cap B ∣= 0 \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots . 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 \dots \dots \dots \dots \dots \dots \dots \dots \dots . . I

∣ A \cap B ∣= 0 \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots . . 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 \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!