First, I want to mention that I do not believe that the argument I am about to present has no flaws in it. Clearly it is wrong, I'm just not sure why and I was wondering if someone can help me figure it out. Suppose we can us the axiom of countable choice. What I want to do is partition any infinite set into a countable union of countable (or finite) sets. This is clearly absurd given that then any set would be countable and I understand that, I just want to know what is wrong with this argument.

First I wish to construct a 1-1 function g such that $g(A)=A_0$, $g(A_n)=A_{n+1}$, where $A_{n+1}\subset A_n\subset A$, and $\cap_{n=0}^\infty A_n$ is Dedekind finite.

One can show that if A is Dedekind infinite (and I can use the axiom of countable choice so every infinite set is Dedekind infinite right?) then $|A|=|A\cup\{A\}|$. So now, take $f_1(A\cup\ \{A\})=A$ to be the 1-1 function needed for $|A|=|A\cup\ \{A\}|$. Take $f_1(A)=A^1_0$ and $f_1(A^1_n)=A^1_{n+1}$. Now, if $\cap_{n=0}^\infty A^1_n$ is Dedekind finite (and ordinary finite) then we are done. (Let's define $A^1*=A\backslash A^1_0$ and $A^1*_n=A^1_n\backslash A^1_{n+1}$. We are done because $\cap_{n=0}^\infty A^1_n$ is finite and $A^1*\cup (\bigcup_{n=0}^\infty A^1*n)=A$. But I believe that every $A^1*_n$ only has a finite amount of elements in it. It definitely only has a countable amount of elements in it.)

Otherwise, meaning if $\cap_{n=0}^\infty A^1_n$ is not finite, take $A^2=\cap_{n=0}^\infty A^1_n$. I believe that $f_1(A^2)=A^2$, given that $f_1$ is 1-1. Now, given that $A^2$ is a Dedekind infinite set, we know that $|A^2\cup\ \{A^2\}|=|A^2|$. Take $f_2$ to be a 1-1 function such that $f_2(A^2\cup\ \{A^2\})=A^2$. Take $f_2(A^2)=A^2_0$ and $f_2(A^2_n)=A^2_{n+1}$. Take $A^3=\cap_{n=0}^\infty A^2_n$. Now, if $A^3$ is Dedekind finite then stop the process, otherwise continue as before. (Meaning preform the steps in this and the previous paragraph over and over again.)

In this manner one can find a family of sets $f_1$, $f_2$, $f_3$... $f_n$. Restrict $f_1$ to $A\backslash A^2$, $f_2$ to $A^2\backslash A^3$, $f_3$ to $A^3\backslash A^4$ and so on. The family of the functions f, with these new restrictions, is either countable or finite. Take $g=\bigcup_{n=1}^\infty f_n$ in the case where the family is countable, and take $g=$ the union of $f_n$ for finite n, in the case in which the family is finite. This union is a function (I believe that this is true, but it might not be true) given that the f's are restricted appropriately, as will be demonstrated. (I don't want g to be a set of functions, I want it to be a function).

Now take $g(A)=A_0$, $g(A_n)=A_{n+1}$. I believe that, $A_{n+1}\subset A_n$, and $\cap_{n=0}^\infty A_n$ is Dedekind finite. We know that $g(\cap_{n=0}^\infty A_n)=\cap_{n=0}^\infty A_n$ and so we see that $\cap_{n=0}^\infty A_n$ is Dedekind finite. Otherwise the function $f_n$ 'associated' with or restricted to $\cap_{n=0}^\infty A_n$ would not be used and a function $f_{n+1}$, which has the property $f_{n+1}(\cap_{n=0}^\infty A_n \bigcup \{\cap_{n=0}^\infty A_n\})=\cap_{n=0}^\infty A_n$, would be used. But then $g(\cap_{n=0}^\infty A_n)\not=\cap_{n=0}^\infty A_n$. (This is the most important part of my argument and it is the part that probably goes wrong, I just want to know why it is wrong).

We can also see that g is 1-1, for each $f_n$ is restricted 'appropriately.' For example, $f_1(y)\not=x$ such that $x\in A^2$ and $y\in A\backslash A^2$, given that $f_1(A^2)=A^2$ and $f_1$ is 1-1. Similarly, $f_n(y)\not=x$ such that $x\in A^{n+1}$ and $y\in A^n\backslash A^{n+1}$, given that $f_n(A_{n+1})=A_{n+1}$ and $f_n$ is 1-1. It follows from this that g is also 1-1. Thus g satisfies the function that we were looking for.

Please don't tell me that $\cap_{n=0}^\infty A_n$ should clearly not be Dedekind finite. I agree that it should not be Dedekind finite, but look at the two last paragraphs and tell me why the argument in them does not work. I also do not need counterexamples for the claim that one can partition any set into a countable union of countable sets, so don't just say that this argument is clearly wrong. Tell me why it is clearly wrong.

Finally, let's definite $A^*=A\backslash A_0$ and $A^*_n=A_n\backslash A_{n+1}$. One can see that $A^*\bigcup (\bigcup_{n=0}^\infty A^*n)=A$ and that these subsets of A are disjointed from one another. They are also countable and the amount of elements in each one should, I believe, be countable. No one needs to answer this question, but if you do answer this question please read it carefully and tell me what parts of the argument are wrong. Again, don't just tell me that my consequence is clearly absurd and so I must have made a mistake. Also, I am sure that I made a couple of mistakes while writing this out, so if you find any please tell me nicely. Thanks for your help.

Also, someone told me that Dependent Choice is required for defining my functions $f_n$. I am not sure why this is true, there seems to be no choice in anything that I did and they are not restricted arbitrarily. Can someone explain why Dependent Choice is required? Regardless, even if choice is required just add it as a assumption to the argument.

  • 1
    $\begingroup$ I find that key paragraph a bit hard to follow, but it seems to me all you're doing is starting with a set and removing one element at a time countably many times, then taking what's left and removing one element at a time from it countably many times, and repeat this whole process countably many times. Obviously the core of what remains if uncountable to begin with cannot be chipped down to countable by removing a countable number of things a countable number of times. I'll keep trying to read that paragraph and see if I can decipher it. $\endgroup$ – Gregory Grant Feb 16 '16 at 2:18
  • $\begingroup$ I completely agree with you, but then do you believe that $g(\cap_{n=0}^\infty A_n)=\cap_{n=0}^\infty A_n$ or not. If it does not then we have a problem (because that the real intersection will only be a subset of this intersection), if it does then it must not be infinite, otherwise the process described would not have allowed for this intersection to be the 'real' intersection. $\endgroup$ – Yitzchak Shmalo Feb 16 '16 at 2:23
  • $\begingroup$ @MattSamuel Thanks. $\endgroup$ – Yitzchak Shmalo Feb 16 '16 at 2:40

The problem occurs in the sixth paragraph, where you argue that the intersection of the $A_n$s is Dedekind-finite. Indeed, there's no reason for it to be: consider the example where $A=\mathbb{Z}$ and $f: A\cup\{A\}\rightarrow A$ is defined by $f(z)=z+1$ for $z\ge 0$, $f(z)=z$ for $z<0$, and $f(\{A\})=0$. Then $\bigcap A_n=\{z\in \mathbb{Z}: z<0\}$ is Dedekind-infinite.

Now, we can find an $f$ such that $\bigcap A_n$ is empty! But this just pushes the problem onto another step, where you argue that $f$ only removes countably many elements at once. Consider $A=\mathbb{R}$, $g(x)=x+1$ if $x\ge0$ and $x-1$ if $x<0$.

  • $\begingroup$ So what Gregory Grant said is not true? $\endgroup$ – Yitzchak Shmalo Feb 16 '16 at 2:28
  • $\begingroup$ @YitzchakShmalo No, what he wrote is absolutely true: he wrote "Obviously the core of what remains if uncountable to begin with cannot be chipped down to countable by removing a countable number of things a countable number of times". My point is, you are removing uncountably many things each time! The sets $A^*_n$ are not countable. $\endgroup$ – Noah Schweber Feb 16 '16 at 4:23
  • $\begingroup$ How are you removing an uncountable amount of things every time? Let's look at what $f_1$ is removing altogether. Suppose we find $f_1$ in the classical manner. We find a subset of the set A which is countable, we map $\{A\}$ to the first element in this countable subset and so on. We map everything else in A to itself. This will give us a $f_1$, right? Now, $f_1$ will only remove a countable amount of elements, by the inductive step described. (Every time it removes a element.) The same will be true for $f_2$ and all $f_n$, no? So how can g remove a uncountable amount of elements? $\endgroup$ – Yitzchak Shmalo Feb 16 '16 at 5:20
  • $\begingroup$ @YitzchakShmalo My examples above show sets $A$ with functions $g$ such that your requirement "a 1-1 function g such that $g(A)=A_0$, $g(A_n)=A_{n+1}$, where $A_{n+1}\subsetneq A_n\subsetneq A$, and $\bigcap A_n$ is Dedekind finite", and for these $g$s, an uncountable set is removed each time. In your comment above, you appear to already be assuming that $A$ is a countable union of countable sets. $\endgroup$ – Noah Schweber Feb 16 '16 at 5:28
  • $\begingroup$ @YitzchakShmalo AHA! I see where I misunderstood you. You're quite right that only one element is being removed at each stage - however, you need uncountably many $f_\alpha$s to exhaust all of $A$! There's no reason why $\bigcap A_n$ needs to be Dedekind-finite if you only use countably many $n$s. (My error was that I skimmed your argument and assumed that all you were doing here was getting a $g$ satisfying the line I quote above, which would yield a function which removed uncountably many elements each time.) $\endgroup$ – Noah Schweber Feb 16 '16 at 5:31

Let me address the last paragraph.

Dependent Choice is exactly what you need in order to construct a sequence by recursion, where at each step there are many viable candidates for the chosen element, but the choice also depends on previous choices.

If a set is Dedekind-infinite there is an uncountable collection of functions which "push one element in". If it's just countable there are already continuum many of those (compose any permutation of $\Bbb N$ with the map $x\mapsto x+1$ to establish a lower bound).

So why should you pick one $f_n$ over the other? You shouldn't. Moreover, if you choose one function, then the resulting $A_n$ might be different from if you chose a different injection. So the choice of $f_n$ depends very much on what were $f_0,\ldots,f_{n-1}$.

  • $\begingroup$ Now I get it. Very cool, thanks. $\endgroup$ – Yitzchak Shmalo Feb 16 '16 at 6:25

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.