1

I want to show that there is no bijection from finite set $X$ to the set $X - \{x\}$. But I don't want to use any of the rules of cardinality or Cantor–Bernstein–Schroeder theorem etc.

Is there a more basic proof ?

efendi
  • 13
  • $f : N \to N/{1} f(x)=x+1$ is a counterexample – Ishan Banerjee Feb 19 '13 at 09:16
  • 5
    What is your definition of finite? The property you are requesting can be taken as the definition of finite sets... – Emanuele Paolini Feb 19 '13 at 09:18
  • I would think you could assume there was a bijection $f$, and look at $f(x), f(f(x))$ and so on. You should encounter a problem after a while, but you will need the concept of cardinality to tell if and when it will happen. – Arthur Feb 19 '13 at 09:22
  • 4
    @Arthur If you don't use cardinality at all, i don't see a difference between finite and infinite sets. – Dominic Michaelis Feb 19 '13 at 09:25
  • @EmanuelePaolini The usual definition of "finite" is "in bijective correspondence with some natural number". This is indeed equivalent to the nonexistence of a bijection with a proper subset, but proving the reverse direction uses the Axiom of Choice so in some contexts it's important to keep in mind which property is the defining property. – Trevor Wilson Feb 19 '13 at 15:58

2 Answers2

4

Well you can prove this by induction on the number of elements in $X$.

If $X$ has one element, then this is obvious, because then $X=\{x\}$ and $X\setminus\{x\}=\varnothing$. Clearly there is no injection from a non-empty set into the empty set.

Suppose this holds for sets of $n$ elements, i.e. if there is an injection from a set of $n$ element into itself then it is a surjection. Let $X$ be a set of $n+1$ elements, and pick some $x\in X$.

Let $X'=X\setminus\{x\}$, then $X'$ is a set with $n$ elements. If there was an injection $f\colon X\to X'$ then the restriction of $f$ to $X'$ (denoted by $f\upharpoonright X'$) is an injection from $X'$ into itself, so by our induction hypothesis it has to be surjective. Let $x'=f(x)$ then $x'\in X'$.

Because $f\upharpoonright X'$ is surjective there is some $y\in X'$ such that $f(y)=x'$, but now we have that $f(y)=f(x)$ and since $f$ was injective we have that $y=x$ which is a contradiction because $x\notin X'$. Therefore there is no such injection.

Asaf Karagila
  • 393,674
  • isn't that a cardinality arguement ? – Dominic Michaelis Feb 19 '13 at 09:51
  • I have a bit of difficulty understanding the induction. The statement being proved is that an injection $X\to X$ has to be surjective. So wouldn't it be better to start with an injection $f:X\to X$, assume it is not surjective, and then choose $x\in X$ not in the image of $f$? (The rest of the argument then works, though I would formulate "Let $x'=f(x)\in X'$".) Choosing $x$ before $f$ seems to not quite lead to the desired statement, at least not directly. – Marc van Leeuwen Feb 19 '13 at 10:02
  • Is a proof possible without some form of cardinality being brought into picture? –  Feb 19 '13 at 10:04
  • @Dominic: Yes, it is a cardinality argument. But this is not one dependent on a Cantor-Bernstein like argument. As a whole, no it is impossible to do this without appealing to some sense of cardinality. Because we have to use the fact the set is finite, which itself a cardinality related property. – Asaf Karagila Feb 19 '13 at 10:08
  • @Marc: Yes, you could assume that $f$ is an injection which is not surjective and pick a point not in its range, but then you would have to argue that restricting it to the set without the point is injective and so on. This is really the same argument, mainly because this is really a proof that $\forall x\forall f(f\colon X\to X\setminus{x}\text{ is not injective})$, and we can exchange the order of the two universal quantifiers here. – Asaf Karagila Feb 19 '13 at 10:10
  • 2
    @OrangeHarvester: See my comment to Dominic. Finiteness is cardinality argument. You cannot prove this claim without the asserting that the set is finite, and therefore you must resort to some cardinality argument. Any other argument is essentially this one. But there are no "rules of cardinality" here, except that restricting an injection is an injection. – Asaf Karagila Feb 19 '13 at 10:11
  • 2
    @DominicMichaelis: Of course finiteness is a condition on cardinality, and you cannot prove this without using finiteness. But that does not make this a cardinality argument, like saying "sets with $n$ and $n+1$ elements have different cardinality, so there can be no bijection", which argument would in fact be circular. Here finiteness is used as "a set whose number of elements is a natural number, i.e., accessible by Peano induction", and that does not implicitly assume natural numbers have different cardinals. – Marc van Leeuwen Feb 19 '13 at 10:11
  • Ok I did interpret the question different. – Dominic Michaelis Feb 19 '13 at 10:13
  • @AsafKaragila that is what I thought. thanks. –  Feb 19 '13 at 10:28
1

This one is wrong, cause for example there are bijections from $[0,1]$ to $(0,1]$.
For finite sets it is true, but I don't see how a proof shall work without cardinality arguments. I hope you will correct me if i am wrong, but the only difference between a finite and an infinite set is its cardinality, so if you don't use this one, your proof would imply that for every set this is true. But as i mentioned, for infinite sets it isn't true so you must use the cardinality.

Edit: Maybe there is a proof without cardinality, as I didn't listen to topology I won't be able to do it rigorous, but let's take this Definition of finite:
We call a set $A$ finite if the topological space $(A,T)$ is Hausdorff iff $T$ is the discrete topology.
Any bijection between discrete finite Topological spaces is a homoeomorphism. Now maybe we can show that one of the homotopie groups aren't equal (since the 0th is just a set we have to take a higher one).
If I am right we have to show that the free group with $n$ and $n-1$ generators aren't the same, maybe this works without cardinality.

Martin Sleziak
  • 53,687
Dominic Michaelis
  • 19,935
  • yes assume $X$ is countable and finite. – efendi Feb 19 '13 at 09:16
  • if you don't want to use cardinality at all, i don't think the finite will give you any benefits – Dominic Michaelis Feb 19 '13 at 09:19
  • Uhh, correct me if I am wrong, homotopy groups of discrete spaces are trivial. No? – Asaf Karagila Feb 19 '13 at 11:56
  • Oh i did mean we make a simplicial complex of them – Dominic Michaelis Feb 19 '13 at 13:51
  • I see. The problem with this sort of argument, that while clever (if it works), in order to verify its usefulness you have to verify that nowhere along the way you used the pigeonhole principle, or the fact that proper subset of a finite set has a smaller size; and it's tough because those two are useful things, especially for essentially-finite objects (i.e. objects which behave in a similar way to finite sets). But hey, maybe it works! – Asaf Karagila Feb 19 '13 at 20:51
  • @Asaf i started this one in a new post http://math.stackexchange.com/questions/308445/topological-way-to-show-if-x-finite-than-there-is-no-bijection-to-x-setminu – Dominic Michaelis Feb 19 '13 at 21:32