Computer Sciences > GATE 2024 SET-1 > Set Theory
Let A and B be non-empty finite sets such that there exist one-to-one and onto functions (i) from A to B and (ii) from A × A to A ∪ B. The number of possible values of |A| is

Correct : 1

To find the number of possible values of |A|, let us represent the cardinality of the finite sets as |A| = n and |B| = m, where n, m ≥ 1.
Analyze Condition (i):
• There is a one-to-one and onto (bijective) function from A to B.
• This implies that both sets have the exact same number of elements:
    |A| = |B| → n = m

Analyze Condition (ii):
• There is a one-to-one and onto (bijective) function from A × A to A ∪ B.
• This means their cardinalities must also be equal:
    |A × A| = |A ∪ B|

Let us calculate the size of both sides using the fact that n = m:
• |A × A| = |A| × |A| = n · n = n2
• For the union, we use the principle of inclusion-exclusion:
    |A ∪ B| = |A| + |B| - |A ∩ B| = n + n - |A ∩ B| = 2n - |A ∩ B|

Equating the two sizes:
    n2 = 2n - |A ∩ B|

Solve for n:
Rearranging the equation to isolate the intersection size:
    |A ∩ B| = 2n - n2

Since |A ∩ B| represents a count of elements, its value must be greater than or equal to 0:
    2n - n2 ≥ 0 → n(2 - n) ≥ 0

Since A is a non-empty finite set, we know n ≥ 1. For the inequality to hold true, the term (2 - n) must be greater than or equal to 0:
    2 - n ≥ 0 → n ≤ 2

This limits the allowable integer values for n to just 1 or 2.

Similar Questions

Suppose U is the power set of the set S = {1,2,3,4,5,6}. For any T ∈ U, let |T| denote the number of elements in T and T′ denote the complement of T. For any T,...
#28 MCQ
For a set A, the power set of A is denoted by 2A. If A = {5,{6},{7}}, which of the following options are TRUE? I. ∅ ∈ 2A II. ∅ ⊆ 2A III. {5,{6}} ∈ 2A IV. {5,{...
#74 MCQ
A binary relation R on N x N is defined as follows: (a, b) R (c, d) if a
#97 MCQ

Related Topics

No tags found

Unique Visitor Count

Total Unique Visitors

Loading......