# If a set $A$ is finite then $A\cap B$ is a finite set.

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.

• 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? – John Omielan Feb 21 '19 at 6:56
• 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... – Carsten S Feb 21 '19 at 7:58

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

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

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

$$A\cap B \to A$$

• 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$. – Why Feb 21 '19 at 7:34
• The OP should provide definitions of all things mentioned, as this is very elementary. – user370967 Feb 21 '19 at 7:35
• thats is also true – Why Feb 21 '19 at 7:37

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$$}.

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.