1
$\begingroup$

Background:

Theorem - If $A\subseteq \mathbb{N}_n$ then $A$ is a finite set and $|A|\leq n$.

Question:

Let $A$ be a finite set and $B$ be some set. If $A$ is a finite set, then $A\cap B$ is a finite set.

Attempted proof:

Let $A$ be a finite set and let $C = A\cap B$. If $C = \emptyset$ then $C$ is finite. Suppose $C \neq \emptyset$, since $C\subseteq A$, the set $A\neq \emptyset$ and there exists $k\in\mathbb{N}_k$ such that $A\sim \mathbb{N}_k$. That is, there exists $k\in\mathbb{N}$ and there exists a one-to-one correspondence $f:A\to\mathbb{N}_k$. The restriction of $f$ on the set $C$ $f|_C$ is a one-to-one function from $C$ onto $f(C)$. Therefore, $C\sim f(C)$. By theorem above, some $f(C)$ is a subset of $\mathbb{N}_k$, $f(C)$ is a finite set therefore since $C\sim f(C)$, $C$ is finite as well.

I am not sure if this is completely right, any feedback or other approaches would be appreciated.

$\endgroup$
  • 1
    $\begingroup$ I don't know too much about set theory, so perhaps this is overly simplistic. However, since $C = A \cap B$ is a subset of $A$, then $\lvert C \rvert \le \lvert A \rvert \le n$. Thus, mustn't $C$ be a finite set as well just from this, i.e., that $A$ is a finite set? $\endgroup$ – John Omielan Feb 21 '19 at 6:56
  • $\begingroup$ Looks good. It would have helped to understand what you are doing if you had written a few more words instead of just Background and Question. Like: our definition of a finite set is... We already know/have proved that... I now want to use that to prove... $\endgroup$ – Carsten S Feb 21 '19 at 7:58
2
$\begingroup$

Hint $:$ $A \cap B \subseteq A.$

$\endgroup$
  • $\begingroup$ The user perhaps need a proof using the given "background" in the question $\endgroup$ – Why Feb 21 '19 at 7:32
2
$\begingroup$

Since $A\cap B\subseteq A$, we have an obvious injection

$$A\cap B \to A$$

$\endgroup$
  • $\begingroup$ He perhaps need a proof using the given background: Theorem - If $A\subseteq \mathbb{N}_n$ then $A$ is a finite set and $|A|\leq n$. $\endgroup$ – Why Feb 21 '19 at 7:34
  • 1
    $\begingroup$ The OP should provide definitions of all things mentioned, as this is very elementary. $\endgroup$ – user370967 Feb 21 '19 at 7:35
  • 1
    $\begingroup$ thats is also true $\endgroup$ – Why Feb 21 '19 at 7:37
1
$\begingroup$

1) $A$ is finite: Then $A\cap B$ is finite,

since $A \cap B \subset A$.

Let $A$={$x_1,x_2,.....,x_n$}$, x_i$ are distinct , $1 \le i \le n$, $n$ is the number of elements of $A$.

Let $n_1$ be the smallest positive integer s.t.

$x_{n_1} \in A\cap B$.

Let $n_2$ be the smallest pos.. integer $n_2 >n_1$ s.t.

$x_{n_2} \in A\cap B$.

Let $n_l$ be the smallest pos. integer $n_l >n_{l-1}$ s.t.

$x_{n_l} \in A\cap B$.

This process comes to an end after $m \le n$ steps.

$A\cap B=${$x_{n_1},x_{n_2},. x_{n_m}$}.

Left to do:

Find a bijection $A\cap B$ $ \rightarrow $ $J_m$, where $J_m=${$1,2,...m$}.

$\endgroup$
0
$\begingroup$

Suppose $A\cap B$ is infinite. Then we have $x_1,x_2,x_3,....$ all in $A\cap B$. But then each of them is also in $A$. Then $A$ has ininite cardinality. A contradicition.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.