3
$\begingroup$

Prove the cardinality of $\mathbb{Z}$ and $\mathbb{N}$ is the same.

For the cardinality to be the same, there must exists a bijective function $f:\mathbb{N}\mapsto\mathbb{Z}$. If there exists a bijective function, then there exists an inverse $g:\mathbb{Z}\mapsto\mathbb{N}$ of it.

Suppose there exists such function. Then if $n\in\mathbb{N}$ and $z\in\mathbb{Z}$,

\begin{align} (g\circ f)(n)&=n\\ g(f(n))&=n\\ g(z)&=n\\ f(g(z))&=f(n)\\ z&=f(n)\\ f(n)&=f(n)\\ f(n)-f(n)&=0\\ 0&=0 \end{align}

Clearly this is true, so there exists such bijective function. Which means $\mathbb{Z}$ and $\mathbb{N}$ have the same cardinality.


But I feel this is incorrect, because if instead of $\mathbb{Z}$ and $\mathbb{N}$ I have to prove the equality of the cardinalities of $\mathbb{Z}$ and $\mathbb{R}$, the conclusion would be the same, but clearly this is not true.

$\endgroup$
  • 1
    $\begingroup$ Why not just construct a bijective function? It's pretty easy for $\Bbb Z$ and $\Bbb N$. $\endgroup$ – Bobbie D Feb 28 '17 at 13:45
  • 4
    $\begingroup$ Also, you're right to feel it's incorrect. Starting by assuming the proposition you want to prove and then showing that a consequence of that proposition is a true statement is not enough to say the proposition is true. $\endgroup$ – Bobbie D Feb 28 '17 at 13:46
  • 1
    $\begingroup$ There is no "more general solution". You know that you must construct a bijection, so do it. Hint: start a function $f$ from $\mathbb{N}$ to $\mathbb{Z}$ by sending each even number $n$ to $n/2$. What part of $\mathbb{Z}$ hasn't been covered? What's left in $\mathbb{N}$ to work with? $\endgroup$ – Ethan Bolker Feb 28 '17 at 13:55
  • 1
    $\begingroup$ What is the question actually? Do you want us to prove (or give hint(s)) for the proposition that you mentioned at the beginning or to explain why exactly the argument of the form (i.e., if the consequence of a proposition is true then the proposition is true) isn't valid? Please clarify this in your post. $\endgroup$ – user 170039 Feb 28 '17 at 14:01
  • 2
    $\begingroup$ "Suppose $-2 = 2$. Then, squaring both sides, $4=4$, Clearly this is true, so my supposition is correct" $\endgroup$ – AakashM Feb 28 '17 at 14:20
1
$\begingroup$

Claim: The union of two countably infinite sets is countably infinite.

Proof Sketch: Let $A$ and $B$ be countably infinite, witnessed by functions $f: \mathbb{N} \rightarrow A$ and $g: \mathbb{N} \rightarrow B$. Construct a new function $h: \mathbb{N} \rightarrow A \cup B$ where $h(2k) = f(k)$ and $h(2k+1) = g(k)$ (i.e., map even natural numbers to elements of $A$ and odd ones to elements of $B$). It remains to check that $h$ is a bijection.


Since $\mathbb{Z}$ is the union of positive $\mathbb{N}$ with negative $\mathbb{N}$ (with a slight modification depending on whether you think $0$ is an element of $\mathbb{N}$), we can apply the claim to conclude the countability of $\mathbb{Z}$ without explicitly constructing a bijection from $\mathbb{N}$ to $\mathbb{Z}$. (Of course, the bijection I constructed in the claim is basically the one you might have used anyway.)

$\endgroup$
  • 1
    $\begingroup$ Of course $h$ is only a bijection if $A$ and $B$ are disjoint. Otherwise the elements in the intersection have two values in their pre-image, one even and one odd. $\endgroup$ – celtschk Aug 1 at 20:21
4
$\begingroup$

This appears to be your argument, boiled down to the essentials:

"If a bijection exists, then it follows that 0=0. Clearly 0=0 is true. Therefore a bijection must exist."

The problem is that this is NOT a valid argument. This is an instance of a logical fallacy known as 'Affirming the Consequent'.

$\endgroup$
1
$\begingroup$

The rationale behind a proof by contradiction is to make an assumption, derive a contradictory statement and conclude the negation of your assumption. What you do in your "proof" is somehow the opposite: You make an assumption, you derive a tautology and claim that your assumption is true. This is not a sound argument. The reason is that any statement (even contradictory ones) implies all tautologies.

Now regarding constructive and non-constructive proof. First of all you should keep in mind that in principle a direct construction is preferable to an indirect proof. This is because a direct construction gives you more information: Not only does it guarantee the existence of an object but it also gives a description of that object. Secondly, a non-constructive proof is not necessarily more general that a constructive one. The argument can be as ad-hoc as a direct construction of a bijection between $\mathbb{N}$ and $\mathbb{Z}$. It's also the case that a constructive proof can very well be very general: Think for example of an algorithm that for a huge class of pairs of sets gives you a bijection between the elements of the pairs.

Proving an existential statement (like the existence of a function) is more commonly done by direct constructions. It is much more rare to show the existence of an object without directly describing it. These proofs seem to involve some critical use of the law of excluded middle, since intuitionistically the existence of an object is tantamount to its description.

Of course you can provide a non-constructive proof, but it will be superfluous. For example, your proposed solution in the answers in needlessly complicated. Just saying that $g$ is the desired bijection is already a proof.

$\endgroup$
-3
$\begingroup$

Suppose such bijective function $f:\mathbb{N}\mapsto\mathbb{Z}$ doesn't exist.

Let $z\in\mathbb{Z}$ and $n\in\mathbb{N}$.

Then $\forall f:\mathbb{Z}\mapsto\mathbb{N}:(\text{$f$ is not a injection $\lor$ $f$ is not a surjection})$.

\begin{align} \forall f:\mathbb{N}\mapsto\mathbb{Z}:(\text{$f$ is not a injection } \lor \text{$f$ is not a surjection})\\ \forall f:((\exists n_1,n_2:\lnot(f(n_1)=f(n_2)\implies n_1=n_2))\lor(\exists z:z\neq f(n))\\ \forall f:((\exists n_1,n_2:(f(n_1)=f(n_2)\land n_1\neq n_2))\lor(\exists z:z\neq f(n))\\ \end{align}

If this is false we are done.

Let $f:\mathbb{N}\mapsto\mathbb{Z}$ be arbitrary. We now need to show $(\exists n_1,n_2:(f(n_1)=f(n_2)\land n_1\neq n_2))\lor(\exists z:z\neq f(n))$.

If $\exists n_1,n_2:(f(n_1)=f(n_2)\land n_1\neq n_2)$ we have $n_1\neq n_2$ and applying $f$ to both sides:

$$f(n_1)\neq f(n_2)\tag{contradiction}$$

We concluded that $\exists n_1,n_2:(f(n_1)=f(n_2)\land n_1\neq n_2)$ must be false, so for the condition to be true $\exists z:z\neq f(n)$ must be true. So we need to find a function that takes a natural number as argument and maps it to the whole range of integers. Because we can construct a surjective function

$$ g(n)=\begin{cases} n/2 & \text{$n$ is even}\\ -(n-1)/2 & \text{$n$ is odd} \end{cases} $$

that takes a natural number and can return every value of the integers the last statement is false, which means that supposing a bijective function $f$ does not exist has lead to a contradiction. Hence, a bijective function must exist. So the cardinality of $\mathbb{Z}$ and $\mathbb{N}$ must be the same.

$\endgroup$
  • $\begingroup$ Why the downvote? $\endgroup$ – Garmekain Feb 28 '17 at 16:01
  • 1
    $\begingroup$ I didn't downvote; however I find you're making the argument unnecessarily complicated: just showing that $g$ is bijective proves directly the statement. $\endgroup$ – egreg Feb 28 '17 at 16:14

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.