Zakon Vol 1, Ch2, Sec-6, Prob-19 : Cardinality of union of 2 sets

That is the basis for induction. Assume that it is true for A and B with k members. Then add a k+1st member to each, which makes m+ k+1, and A\cap B still has no members in common. Then A\cup B has m+ k+1+ n members. That's m+ (n+ k+1), the induction hypothesis.
  • #1
dawoodvora
5
0

Homework Statement




Show by induction that if the fi nite sets A and B have m and n elements,
respectively, then
(i) A X B has mn elements;
(ii) A has 2m subsets;
(iii) If further A [itex]\cap[/itex] B = [itex]\varphi[/itex], then A [itex]\cup[/itex] B has m+ n elements.

NOTE : I am only interested in the (iii) section of the problem. Section (i) and (ii), I was able to solve albeit with some help.

Homework Equations





The Attempt at a Solution


Here is the attempt at the solution

I am using mathematical induction to solve the query.

P(n) : |A| = m, |B| = n; |A [itex]\cup[/itex] B| = m + n if A [itex]\cap[/itex] B = [itex]\varphi[/itex].

Basis Step:

P(n = 1) to be proven as true.

Let A = { a1, a2,...am} => |A| = m
Let B = {b1} => |B| = 1

Now A [itex]\cup[/itex] B = {a1, a2,...am,b1}
|A [itex]\cup[/itex] B| = m + 1 elements, since A and B are disjoint(given) Thus P(1) holds true.
Basis Step is proven.

Let us redefine B = {b1, b2, ..., bk, bk+1} => |B| = k+1.
Also |A [itex]\cap[/itex] B| = [itex]\varphi[/itex]
Now consider Bk = {b1, b2,..., bk} => Bk [itex]\subset[/itex] B, |Bk| = k

Inductive hypothesis:
Assume P(k) holds true for n = k i.e.,

|A [itex]\cup[/itex] Bk| = m + k, when A [itex]\cap[/itex] Bk = [itex]\varphi[/itex]

Inductive Step:

Bk [itex]\subset[/itex] B => B = Bk [itex]\cup[/itex] {bk+1}
A [itex]\cup[/itex] B = A [itex]\cup[/itex] (Bk [itex]\cup[/itex] {bk+1}) = (A [itex]\cup[/itex] Bk) [itex]\cup[/itex] {Bk+1} = m + k + 1 = m + (k + 1) => P(k+1) holds true. Thus Induction is complete.

Somehow, I am not convinced with the solution that I have attempted. Please let me know if I am missing something.
 
Physics news on Phys.org
  • #2
dawoodvora said:

Homework Statement

Show by induction that if the finite sets A and B have m and n elements,
respectively, then
(i) A X B has mn elements;
(ii) A has 2m subsets;
This is wrong. What you have written is 2 times m while, in fact, A has 2m subsets. If you don't want to use LaTeX (as you have below) use 2^m.

(iii) If further A [itex]\cap[/itex] B = [itex]\varphi[/itex], then A [itex]\cup[/itex] B has m+ n elements.

NOTE : I am only interested in the (iii) section of the problem. Section (i) and (ii), I was able to solve albeit with some help.

Homework Equations


The Attempt at a Solution


Here is the attempt at the solution

I am using mathematical induction to solve the query.

P(n) : |A| = m, |B| = n; |A [itex]\cup[/itex] B| = m + n if A [itex]\cap[/itex] B = [itex]\varphi[/itex].

Basis Step:

P(n = 1) to be proven as true.

Let A = { a1, a2,...am} => |A| = m
Let B = {b1} => |B| = 1

Now A [itex]\cup[/itex] B = {a1, a2,...am,b1}
|A [itex]\cup[/itex] B| = m + 1 elements, since A and B are disjoint(given) Thus P(1) holds true.
Basis Step is proven.

Let us redefine B = {b1, b2, ..., bk, bk+1} => |B| = k+1.
Also |A [itex]\cap[/itex] B| = [itex]\varphi[/itex]
Now consider Bk = {b1, b2,..., bk} => Bk [itex]\subset[/itex] B, |Bk| = k

Inductive hypothesis:
Assume P(k) holds true for n = k i.e.,

|A [itex]\cup[/itex] Bk| = m + k, when A [itex]\cap[/itex] Bk = [itex]\varphi[/itex]

Inductive Step:

Bk [itex]\subset[/itex] B => B = Bk [itex]\cup[/itex] {bk+1}
A [itex]\cup[/itex] B = A [itex]\cup[/itex] (Bk [itex]\cup[/itex] {bk+1}) = (A [itex]\cup[/itex] Bk) [itex]\cup[/itex] {Bk+1} = m + k + 1 = m + (k + 1) => P(k+1) holds true. Thus Induction is complete.

Somehow, I am not convinced with the solution that I have attempted. Please let me know if I am missing something.
That's correct but seems overly complicated. If A and B have no members in common, [itex]A\cup B[/itex] contains every member of A and B- thus has m+ n members.
 

FAQ: Zakon Vol 1, Ch2, Sec-6, Prob-19 : Cardinality of union of 2 sets

What is the definition of "cardinality" in relation to sets?

Cardinality refers to the number of elements in a set. It is often denoted by the symbol |S|, where S is the set.

How is the cardinality of a set determined?

The cardinality of a set is determined by counting the number of distinct elements in the set.

What does the phrase "union of 2 sets" mean in this context?

In set theory, the union of two sets A and B is the set of all elements that are in A, in B, or in both A and B. It is denoted by A ∪ B.

Is there a formula for calculating the cardinality of the union of 2 sets?

Yes, the formula is |A ∪ B| = |A| + |B| - |A ∩ B|, where |A| represents the cardinality of set A, and |A ∩ B| represents the cardinality of the intersection of sets A and B.

Can the cardinality of the union of 2 sets ever be greater than the sum of the cardinalities of the individual sets?

No, the cardinality of the union of 2 sets can never exceed the sum of the cardinalities of the individual sets. This is because the union includes all elements from both sets, and any overlapping elements would be counted twice if added separately.

Similar threads

Back
Top