I need to prove that:
if A is an infinite set and x is some element such that x is not an element of A,
then (A union {x}) is equipotent to A.

The thing is I know it's relatively easy to prove it with cardinal numbers, but thing is I cannot use any notion of cardinals because the exercise comes before that part of the course.

I tried three approaches:

  • Considered the contrapositif: if A and A union {x} are not equivalent then A and A union {x} are finite. Then I tried several ways to prove it but none was satisfying, first assume they are countable so they are both equipotent to N and arrive at a contradiction. But then I arrive at uncountables and I freeze. I tried to utilize the theorem that there is always a countable set in an uncountable one, then I assume the cases where A (uncountable) - (countable set) = some set B. I then consider B finite arrive at a contradiction, then assume B is countable also arrive at a contradiction and then uncountable... and I freeze. I thought about doing the step again and proceed by induction since i will always have these three cases where 2 of them are absurd. But then what?
  • I then decided to take a different approach, much more simple: take the definition of an infinite set specifically that if A is an infinite set then there is a proper subset S that is equipotent to it. Since A is a subset of A union {x} somehow or another i need to conclude it. The thing is the quantification: not any proper subset is equipotent to the parent's...
  • I then tried the other definition of an infinite set: that an infinite set has an injective function: A -> A ; that is injective but not surjective. I do not know however how to proceed about it then.

Any suggestions or help will be really appreciated. If it helps, the exercise is in the countable chapter of the course, and we finished: finite, infinite and countable. So its rather in the beginning of the course.

  • $\begingroup$ When you say "equivalent", I assume you mean "have the same cardinality". (There are many kinds of equivalence in mathematics, of which this is only one). $\endgroup$ – Henning Makholm Mar 17 '16 at 23:28
  • $\begingroup$ Are you sure the definitions of "infinite" you depend on in the second and third approach are the definitions presupposed by the question? Usually these two definitions lead to a concept that is called Dedekind-infinite, which is not necessarily the same as the usual "infinite" unless the Axiom of Choice holds. $\endgroup$ – Henning Makholm Mar 17 '16 at 23:33
  • $\begingroup$ it is equipotent I am sorry, the ~ relation defined as: to sets A and B are equivalent (A~B) if there exists a bijection (A->B). $\endgroup$ – popololvic Mar 17 '16 at 23:35

Let's construct a bijection between $A$ and $A\cup {x}$.

We know that A is infinite so for each $i\in \mathbb{N}$ you can choose an element $a_i\in A$ such that $\forall i,j\in \mathbb{N}:a_i = a_j \implies i=j$. Now map $x$ to $a_0$, map $a_i$ to $a_{i+1}$, and map all other elements on themselves.

Do you see that this is a bijection?

  • $\begingroup$ I see it, thank you. The part where I can choose an element ai in A, is it because every infinite set has a countable one as a subset and therefore it makes sense to talk about the 'ith element' ? $\endgroup$ – popololvic Mar 17 '16 at 23:39
  • 1
    $\begingroup$ @popololvic exactly $\endgroup$ – Jens Renders Mar 17 '16 at 23:40
  • $\begingroup$ (1) It is not true that you can choose $a_i\in A$ "in a unique way." Quite the contrary, there are infinitely many choices for $a_1,$ then infinitely many choices for $a_2,$ and so on. (2) You neglected to say that the chosen elements $a_i$ are distinct, i.e., $a_i\ne a_j$ whenever $i\ne j;$ that is needed for your argument to work. $\endgroup$ – bof Mar 18 '16 at 0:15
  • $\begingroup$ "In a unique way" is a vague statement in english. What I ment here is that the chosen $a_i$ is unique for that $i$, i.e. no other number gets the same element. Your (1) and (2) are the same problemem, I will edit to make it more clear $\endgroup$ – Jens Renders Mar 18 '16 at 0:21

Your third approach looks most promising to me. Assuming that the definition of "infinite" you cite is indeed the one that applies in the question, let $f$ be such a function and $y$ be some element of $A$ that is not in the range of $f$ (certifying that $f$ is not surjective). Then map $f^n(y)$ to $f^{n+1}(y)$ and every other element of $A$ to itself.

  • $\begingroup$ Perfect. I think the fact that I let f be a injective and not surjective function is better than just saying it that since I can choose a in A in a unique way. However should I use the fact that every infinite set has a countable set in order to talk about the 'nth' element of the function? $\endgroup$ – popololvic Mar 17 '16 at 23:43
  • $\begingroup$ @popololvic: If you already knows that the infinite set has a countably infinite subset, then the bijection that verifies that the subset is countable is exactly the $a_i$ sequence Jens needs. $\endgroup$ – Henning Makholm Mar 17 '16 at 23:46
  • $\begingroup$ Perfect. Thank you guys. $\endgroup$ – popololvic Mar 17 '16 at 23: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.