Can I Systematically Determine the Cardinality of a Finite Set?

Question

Is there any way you can, in a systematically manner, determine the cardinality of a finite set in which the elements are given by a specific expression?

For example, let $A$ be a set $\ A=\{1,2,3,4,5,6\}$ and $B$ be a set defined by: $$B=\biggl\{\frac{a-b}{a+b} : a,b\in A\biggl\}$$ My question is thus, can I somehow determine the cardinality of the set without having to calculate and enumerate each and every element?

Answer 1

It's really dependent on how you built the set. The thing that can make things rather tricky is when things in the set are equal only one thing is counted. So usually inequalities are easy but the exact number you'd have to eleminate all equivalent elements.

For example, let $A$ be a set $\ A=\{1,2,3,4,5,6\}$ and $B$ be a set defined by: $$B=\biggl\{\frac{a-b}{a+b} : a,b\in A\biggl\}$$

Since $|A|=6$ and you are taking two elements in $A$ you get the easy inequality $|B| \le 6^2=36$.

Since $B$ has at least $1$ element $1 \le |B|$

Enumerateing through the values and evaluating them in the function $\frac{a-b}{a+b}$ i get the following table

$\begin{array}{rrrrrr} 0 & \frac{1}{3} & \frac{1}{2} & \frac{3}{5} & \frac{2}{3} & \frac{5}{7} \\ -\frac{1}{3} & 0 & \frac{1}{5} & \frac{1}{3} & \frac{3}{7} & \frac{1}{2} \\ -\frac{1}{2} & -\frac{1}{5} & 0 & \frac{1}{7} & \frac{1}{4} & \frac{1}{3} \\ -\frac{3}{5} & -\frac{1}{3} & -\frac{1}{7} & 0 & \frac{1}{9} & \frac{1}{5} \\ -\frac{2}{3} & -\frac{3}{7} & -\frac{1}{4} & -\frac{1}{9} & 0 & \frac{1}{11} \\ -\frac{5}{7} & -\frac{1}{2} & -\frac{1}{3} & -\frac{1}{5} & -\frac{1}{11} & 0 \end{array}$

So sorting out all the duplicates:

$$B=\left\{0, \pm\frac{1}{2}, \pm\frac{1}{3}, \pm\frac{2}{3}, \pm\frac{1}{4}, \pm\frac{1}{5}, \pm\frac{3}{5}, \pm\frac{1}{7}, \pm\frac{3}{7}, \pm\frac{5}{7}, \pm\frac{1}{9}, \pm\frac{1}{11}\right\}$$

So it looks like in your example $|B|=23$

Answer 2

In a systematic manner, determine the cardinality of any finite set? No. For this one, without having to calculate and enumerate each and every element? Ok. The possible combinations of values for $a$ and $b$ are $36$. From them, we must remove duplicates. That is, when we get the same result for different values of $a$ and $b$. When this happens, we have:

$$\dfrac{\alpha-\beta}{\alpha+\beta}=\dfrac{\gamma-\delta}{\gamma+\delta} $$

We cross multiply them to get: $\left(\alpha-\beta\right)\left(\gamma+\delta\right)=\left(\gamma-\delta\right)\left(\alpha+\beta\right) $. Multiplying and eliminating common terms gives: $$\alpha\delta=\beta\gamma$$ Now, either $\alpha=\beta $ (and thus $\gamma=\delta )$, or not. There are $6$ cases for which $\alpha=\beta $ (and thus $\dfrac{\alpha-\beta}{\alpha+\beta}=0 $). We count only one, so we subtract $5$ from $36$ $(=31)$. We need to find how many duplicates are there for $\alpha\neq\beta $. If we write the number $\left(\alpha\delta\right) $ as a product of prime numbers, it will have the form: $$p_{1}^{n_{1}}p_{2}^{n_{2}}...p_{k}^{n_{k}}$$ But because $\alpha\delta\leq36 $, only in one case we have more than two distinct primes: $2\cdot3\cdot5=30 $. This gives $3$ products of the form $\alpha\delta $: $2\cdot15=30 $, $6\cdot5=30 $ and $3\cdot10=30 $. Since $10$ and $15$ are not in $A$, we have no duplicates. So, $\left(\alpha\delta\right) $ must be of the form: $$p_{1}^{n_{1}}\cdot p_{2}^{n_{2}}$$ Now, $\left(\alpha\delta\right) $ can be writen as a product of two numbers in several ways:

$$\alpha\delta=p_{1}^{n_{1}}\cdot p_{2}^{n_{2}}=p_{1}^{n_{1}-1}\cdot\left(p_{1}\cdot p_{2}^{n_{2}}\right)=p_{1}^{n_{1}-2}\cdot\left(p_{1}^{2}\cdot p_{2}^{n_{2}}\right)=...=p_{1}^{0}\cdot\left(p_{1}^{n_{1}}\cdot p_{2}^{n_{2}}\right) $$

We notice that, in order to have $p_{1}^{k}\cdot p_{2}^{l}\in A $, that is: $p_{1}^{k}\cdot p_{2}^{l}\leq6 $, we must have $k,l\leq2 $. Thus, $$n_{1},n_{2}\in\left\{ 0,1,2\right\}$$

Since $\alpha,\delta\leq6$, we must have $p_{1},p_{2}\leq5 $. But if one of the primes is $5$, for example, $p_{2}=5 $, then it is not possible to express $\left(\alpha\delta\right) $ as a product in two different ways: $p_{1}^{k}\left(p_{1}^{l}\cdot5\right)=p_{1}^{m}\left(p_{1}^{n}\cdot5\right) $. So $l=n=0 $, else $\left(p_{1}^{l}\cdot5\right),\left(p_{1}^{n}\cdot5\right)\notin A $. But then, $\left(p_{1}^{l}\cdot5\right)=\left(p_{1}^{n}\cdot5\right) $ and thus $p_{1}^{k}=p_{1}^{m} $. So: $$p_{1},p_{2}\in\left\{ 2,3\right\}$$

If one of the primes is $3$, then its exponent must be always $0$ or $1$, because for $k>1 , p_{l}^{k}>6 $. So we have the following possible cases:

1. $1\cdot2^{2}=2\cdot2$. Then,

   $a=1\wedge b=2$ or $a=2\wedge b=1$ $(1)$

   or $a=4\wedge b=2$ or $a=2\wedge b=4$ $(2)$

2. $2\cdot3=1\cdot\left(2\cdot3\right)$. Then,

   $a=2\wedge b=1$ or $a=1\wedge b=2$, same as $(1)$,

   or $a=2\wedge b=6$ or $a=6\wedge b=2$ $(3)$,

   or $a=3\wedge b=1$ or $a=1\wedge b=3$ $(4)$

   or $a=3\wedge b=6$ or $a=6\wedge b=3$ $(5)$.

3. $2^{2}\cdot3=2\cdot\left(2\cdot3\right)$. Then,

   $a=4\wedge b=2$ or $a=2\wedge b=4$, same as $(2)$,

   or $a=4\wedge b=6$ or $a=6\wedge b=4$ $(6)$,

   or $a=3\wedge b=2$ or $a=2\wedge b=3$ $(7)$,

   or $a=3\wedge b=6$ or $a=6\wedge b=3$, same as $(5)$.

Putting these valus in $\dfrac{a-b}{a+b} $, for all possible cases, we get:

1. $\dfrac{2-1}{2+1}=\dfrac{1}{3} $ and $\dfrac{1-2}{1+2}=-\dfrac{1}{3} $

2. $\dfrac{4-2}{4+2}=\dfrac{1}{3} $ and $\dfrac{2-4}{2+4}=-\dfrac{1}{3} $

3. $\dfrac{6-2}{6+2}=\dfrac{1}{2} $ and $\dfrac{2-6}{2+6}=-\dfrac{1}{2} $

4. $\dfrac{3-1}{3+1}=\dfrac{1}{2} $ and $\dfrac{1-3}{1+3}=-\dfrac{1}{2} $

5. $\dfrac{6-3}{6+3}=\dfrac{1}{3} $ and $\dfrac{3-6}{3+6}=-\dfrac{1}{3} $

6. $\dfrac{6-4}{6+4}=\dfrac{1}{5} $ and $\dfrac{4-6}{4+6}=-\dfrac{1}{5} $

7. $\dfrac{3-2}{3+2}=\dfrac{1}{5} $ and $\dfrac{2-3}{2+3}=-\dfrac{1}{5} $

These are $14$ cases from which - to remove duplicates - we must count only $6$. So we subtract $8$ from $31$ and we get $23$ possible different values for $\dfrac{a-b}{a+b} $. Thus $$\left|B\right|=23$$

Answer 3

Let's solve the general problem.Consider $A=\{ 1,2,....,n \}$ and $B=\{ {a-b\over a+b}:a,b\in A \}$.

Now, note that ${a\over b}= {c\over d}\Leftrightarrow {a-b\over a+b} ={c-d\over c+d}$ i.e there is a one to one correspondence between $B$ and $S= \{ {a\over b} : a,b\in A \} $.So, we have to find cardinality of $S$.

Now, if the least form of $a\over b$ is $c\over d$ then $gcd(c,d)=1$ and $c,d\in A$ as $1\le c\le a\le n$ and $1\le d\le b\le n$.So, the problem is to find the pair of numbers $c,d\in A$ such that $gcd(c,d)=1$.

Now, for $c>d$, for a chosen $c$, $d$ can be chosen in $\phi (c)$ ways. So, the number $c\over d$ s.t. $c\over d$ $>1$ and $gcd(c,d)=1$ are $\sum_{r=2}^{n} \phi (r)$ in numbers.Now for the numbers $e\over f$ $<1$ and $gcd(e,f)=1$, we just interchange the position of $c$ and $d$ in $c\over d$ $>1$ and $gcd(c,d)=1$.So, they are also in $\sum_{r=2}^{n} \phi (r)$ in numbers.

Now at last just consider ${1\over 1}=1$, which was not in previous cases.Hence the required result is $2 \sum_{r=2}^{n} \phi (r) +1$=$2 \sum_{r=1}^{n} \phi (r) -1$. For particularly your problem, $n=6$ and $2 \sum_{r=1}^{n} \phi (r) -1=23$