2
$\begingroup$

Use the result of exercise 1 to prove if A is infinite and B finite and B is a finite subset of A then A\B is infinite

Exercise 1 Let A,B be disjoint finite sets. and A≈m. and B≈n,then. A ∪ B ≈ m + n. Conclude that the union of two finite sets is finite.

Note: problem comes from A book of set Theory by Pinter

Attempted proof (Caveat Lector: let the reader beware... My knowledge of infinite set is shaky I can use induction and mapping)

I proved exercise 1. (Complete rewrite)

Write A=(A\B)$\cup$ B (1)

Using $A \cup B $ from exercise 1 we get A\B=($A\cup B)\cap B^{c}$ (2)

Now suppose that A has a denumerable subset B and A is finite; that is, A ≈ n, B ⊆ A, and B ≈ ω. So B$\subset$(A\B)$\cup$ B.

A\B can’t be finite since A is infinite If a$\in$A\B then a$\in B^{c}$ then $B^c$ is infinite which is contradiction since B is finite

Hence A/B is infinite

Help

$\endgroup$
  • $\begingroup$ Do you mind correcting the very first line? $\endgroup$ – Cornman Nov 29 '20 at 5:06
  • $\begingroup$ To me it is unclear what you have to show. $\endgroup$ – Cornman Nov 29 '20 at 5:07
  • $\begingroup$ If A is infinite, then $A\cup B$ cannot be finite. $\endgroup$ – Moosh Nov 29 '20 at 5:15
  • $\begingroup$ I didn't find the problem yet. Can you write precisely.? $\endgroup$ – Aman Pandey Nov 29 '20 at 5:17
  • $\begingroup$ Corrected it@Cornman. I have to show A\B is infinite given A is infinite,B finite and B$\subset$ A $\endgroup$ – Eudoxus Nov 29 '20 at 12:42
0
$\begingroup$

A few things:

  • $A\setminus B = \{x \in A: x \notin B\}$. Thus $$A\setminus B = A\cap B^\complement$$ There is no reason to union in all the elements of $B$ before you remove them by intersecting with $B^\complement$.
  • You deduce

$A\setminus B= ((A\setminus B)\cup B)\cup B)\cap B^\complement$

So $A\setminus B$ and $B$ are disjoint.

Any argument by which you could get "$A\setminus B$ and $B$ are disjoint" from $A\setminus B= ((A\setminus B)\cup B)\cup B)\cap B^\complement$ would work far more easily from your statement (2): $A\setminus B= (A\cup B)\cap B^\complement$. Or more easily yet from (what I assume is the definition Pinter gives for $A\setminus B$): $A\setminus B = A\cap B^\complement$. You were quite clearly heading in the wrong direction and evidently just decided to fake it, hoping your reader would be equally lost and assume that you actually had demonstrated something.

That $A\setminus B$ and $B$ are disjoint is something so obvious that it is questionable whether it needed to be demonstrated at all. By the set-builder definition I gave, it is provable by noting that $x \in A\setminus B \implies x \notin B$, therefore there is no $x$ which is in both $A\setminus B$ and $B$. If you insist on a "set-algebraic" proof, then $$(A\setminus B) \cap B = (A \cap B^\complement)\cap B = A\cap(B^\complement\cap B) = A\cap\varnothing = \varnothing$$

  • You are not keeping track of your own assumptions:

Now suppose that $A$ has a denumerable subset $B$ and $A$ is finite; that is, $A \approx n, B \subseteq A$, and $B \approx \omega$. So $B\subset (A\setminus B)\cup B$.

$A\setminus B$ can’t be finite since A is infinite ...

Further, you make no use of any of the items above in the rest of your argument, so why did you mention them? The only thing you used was that $A$ is infinite, which is a hypothesis of the theorem.

If $a\in A\setminus B$ then $a\in B^\complement$ then $B^\complement$ is infinite which is contradiction since $B$ is finite.

I assume you are showing that $A\setminus B \subseteq B^\complement$, which would indeed imply $B^\complement$ is infinite (assuming that it has already been proven that a class with an infinite subclass is itself infinite). But $B^\complement$ being infinite does not in anyway contradict $B$ being finite. In fact the complement of every finite set is infinite. Complements of sets are not sets under Pinter's set theory. They are proper classes, and proper classes are always infinite.


If you want to use exercise 1 to prove this, proof by contradiction is needed. But what you are trying to prove is "$A\setminus B$ is infinite", so the assumption you need to make is the opposite: "$A\setminus B$ is finite". When you arrive at a contradiction, it means that the assumption that led you to it is false, and if "$A\setminus B$ is finite" is false, then its opposite "$A\setminus B$ is infinite" will be true.

So you have the hypotheses of the theorem:

  • $A$ is infinite.
  • $B$ is finite.

And the assumption you are trying to disprove:

  • $A\setminus B$ is finite.

You also have the already-proven theorem:

  • If $C$ and $D$ are both finite, then so is $C\cup D$.

Can you see how to combine these to arrive at a contradiction?

$\endgroup$
  • $\begingroup$ 1. (2) is easier like you said so I overdid it. I was thinking of going this route math.stackexchange.com/a/3144632/837396. 2. I know what A\B means. I did research on this site on this theorem and combined the info I got into the expression for A\B.3.A proof by contradiction,ok. 4. I got the statement you referred from one of Pinter’s proofs. ,It fit the hypothesis, so I thought ,so I used it and try to show the rest (5). I was not trying to fake it. I did give the Caveat Lector at the beginning to indicate my proof probably sucked.. @PaulSinclair $\endgroup$ – Eudoxus Nov 30 '20 at 1:45
  • $\begingroup$ What are sets C and D, l thought they were A and B $\endgroup$ – Eudoxus Nov 30 '20 at 8:45
  • $\begingroup$ In Exercise 1, "$A$" and "$B$" were letters assigned to the two arbitrary sets involved in that theorem. But in this exercise, the labels $A$ and $B$ are assigned to specific sets relating to this problem, not the problem of exercise 1. So when quoting the Exercise 1 result, I changed the labels to ones not used in this problem. It is now up to you to decide which sets involved in this problem should play the roles of $C$ and $D$ when applying the results of exercise 1. This sort of relabeling is a very common, and very necessary, part of mathematics. $\endgroup$ – Paul Sinclair Nov 30 '20 at 19:47

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.