3
$\begingroup$

Let X be an infinite set. Show that adding or subtracting a single point does not change its cardinality.

I have a plan but need help writing the actual proof. I need to show that it doesn't matter which point is removed, and then I can use the fact that X is in one-to-one correspondence with a proper subset to prove this.

$\endgroup$
-1
$\begingroup$

Let $X$ be the infinite set, $Y \subset X$ the set for which there's a bijection $Y \rightarrow X$ (which means $|Y|=|X|$), and $x$ some element in $X$.
Since there's at least one element "missing" in $Y$: $$|X|=|Y| \leq |X- \{x\}|$$ Using the same reasoning: $$|X- \{x\}| \leq |X|$$ Conclusion: $$|X- \{x\}| = |X|$$

$\endgroup$
1
$\begingroup$

Hint: show that there exists an injective map $\omega\to X$. Then it is possible to "hide" a single point by shifting $\omega$ up/down.

$\endgroup$
  • $\begingroup$ Could you elaborate further please? I understand what you're hinting at but I'm not sure how to execute it. $\endgroup$ – user2553807 Feb 5 '14 at 21:02
0
$\begingroup$

HINT: Given two elements $x,y\in X$ there is a permutation of $X$, $\pi$, such that $\pi(x)=y$ and $\pi(y)=x$.

$\endgroup$
  • $\begingroup$ How does that help in answering the question? I was trying to prove the same fact and the proof I thought of was the same as the one which Hagen Von Eitzen points to above. But I still interested in understanding how your hint solves the problem. $\endgroup$ – Fawzy Hegab Jan 26 '15 at 18:01
  • 1
    $\begingroup$ From the question, "and then I can use the fact that X is in one-to-one correspondence with a proper subset to prove this." Fix one such subset of $X$, call it $Y$. Now given any $x\in X$ use the hint to find an injection from $X\setminus\{x\}$ into $Y$; and if $x\notin X$ use the hint to find an injection from $X\cup\{x\}$ into $Y\cup\{y\}$ for some $y\in X\setminus Y$. $\endgroup$ – Asaf Karagila Jan 26 '15 at 18:06
0
$\begingroup$

How do you know you can define an object for every set in such a way that two sets are assigned the same object if and only if there's a bijection from one to the other? The axiom of choice states that for every set of nonempty sets, there is a choice function that assigns to each of those sets one of it's members. In Zermel-Fraenkel set theory, the axiom of choice is not provable. However in Zermelo-Fraenkel set theory, you can use Scott's trick to define an object for set set. It can be shown that that function satisfies reflexivity, symmetry, and transitivity. Some people say that despite the inexistence of a formal proof of the axiom of choice in ZF, the axiom of choice is obviously true so another formal system called ZFC is like ZF except that it adds the axiom of choice as an additional assumption. In ZFC on the other hand, the cardinality of a set is defined to be the smallest ordinal number such that there's a bijection from that ordinal number to that set. That can also be shown to satisfy reflexivity, symmetry, and transitivity. However, Scott's definition and the definition used in ZFC don't always agree with each other. For example, Scott's definition assigns to the empty set the ordinal number 1 and the ZFC definition assigns to the empty set the ordinal number 0. I don't know for sure but I think some people decided to use another definition of a cardinal number in ZF, that is, if a set can't be well-ordered, use Scott's definition of a cardinal number and if it can be well ordered, use the ZFC definition of the cardinality of a set. That way, if you just accept ZF as a true model of set theory but not ZFC, we can show that any informal English statement about cardinality that represents a true statement when used in the context of ZF will always represent a true when used in the context of ZFC, to avoid confusion. That doesn't mean all theorems of ZFC are true. Also if you assume the axiom of choice, you can show that the ZFC meaning about an informal English sentence about cardinality is true if and only if the ZF meaning is true.

In ZFC, you can show that removing an object from an infinite set always gets you a set of the same cardinality but in ZF, you can't. First I will answer the question in ZF then I will answer the question in ZFC. That's because I can use results I already proved in ZF for a proof in ZFC but not the other way around. In ZF and in ZFC, I define a finite set is a set that has a bijection to a finite ordinal number and an infinite set as a set that is not finite.

In ZF, suppose a set is infinite. If you remove an element from the set, then the resulting set must still be infinite but not necessarily the same cardinality. That's because when ever you add an element to a finite set, you get a finite set. All you can really show is that if you have an infinite set that has a countably infinite subset and you remove an element, you get a set with the same cardinality.

In ZFC, suppose a set is infinite. From the axiom of choice, we can derive the axiom of dependent choice. There is a way to remove one element. For each of those ways, there is a way to remove another element and so one. Therefore, there is a way to keep removing one element after another for ever. For each way of keeping on removing one element after another for ever, there is a set of all elements that will ever be removed. Therefore every infinite set has a countably infinite subset. Therefore, it can be proven in ZFC that if you remove an element from an infinite set, you will always get a set of the same cardinality.

$\endgroup$

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.