Prove that if is countably infinite and is countably infinite for each , then is countably infinite.
I was taught that in order to show that a set is countably infinite, we need to either find a proper subset with the same cardinality, or find a bijective function from the domain to the codomain. However, I'm not sure how to attack this proof; I don't know if I'm supposed to use the above method since I'm not just proving that one set is countably infinite.
This seems to be where I always get stuck with proofs that deal with infinite sets. I know that I need to find a bijection, but does that mean that I have to give a specific example of a bijection, or do I just need to somehow show that one exists without specifically giving an example?
This would imply that the set is infinite, but not necessarily countable.
Every function is from the domain to the codomain. You probably mean from the set to a proper subset. Again, this would mean that the set is infinite, but not necessarily countable.or find a bijective function from the domain to the codomain.
Either works unless there are specific directions from your instructor.I know that I need to find a bijection, but does that mean that I have to give a specific example of a bijection, or do I just need to somehow show that one exists without specifically giving an example?
See this thread and the Wikipedia article.
It depends on what the exercise asks for. Ordinarily, we work in classical mathematics, where to prove existence it is not required to show a specific example. If the exercise asks for you to prove that there exists a bijection, then all you have to do is prove is that there exists a bijection.
However, if the context is constructive mathematics, then any proof of existence requires showing a specific example. But you can pretty much suppose that the context isn't constructive mathematics unless it were explicity stated to be.
Actually it is a bit of both of those. For each there is a bijection
As a lemma: there is a bijection between define m,n)\mapsto 2^{2m-1}(2n-1)" alt="\Psim,n)\mapsto 2^{2m-1}(2n-1)" />.
For this question we will use
Now if then
But also is countably infinite there is a bijection
Now we are ready to construct a bijection .
.
Now it is FUN to show that is a bijection.
Not to dispute that proof, but merely to point out that Phi is a choice function, thus the proof shows existence but does not give a specific example (as you say, it is "a bit of both", perhaps in the sense of "given some choice function, we then define our desired bijection").
as i understand it "all countable sets are set-isomorphic". so to exhibit the bijection in question, what is really needed is a bijection:
.
hopefully you can see that the infinite cartersian product has a bijection:
(send the index to the first coordinate, and the element of the indexed set to the second coordinate)
and that in turn, there is a bijection:
(Cantor's first diagonal method comes in handy, here, but other bijections are possible).
now, just send an element of the index in the union to its corresponding copy of (send the ith index element to the ith factor) and send the element of each set to its corresponding element of
(it's possible that we may wind up sending elements which lie in two or more to multiple elements of , in which case we just keep the first assignment, strike out repetitions, and re-number accordingly).
oh dear, you are right (Cantor's 2nd diagonal argument works for that just as well as for the real numbers).
in fact, what i meant was what the OP actually posted, i was just trying to get away from an infinite union of copies of Z, which would, of course, just be Z again. so what i should have used was a disjoint union, not the product.
my apologies.
What do you mean by that? An isomorphism involves two structures, not just two sets. Do you mean isomorphic with regard to the the structure <set membership>? Then, no, not all such structures where the sets are countable are isomorphic.
What we do have is that any two denumerable (i.e., countably infinite) sets are equinumerous.
a set-isomorphism is just a fancy word for bijection. membership induces additional structure on sets (making a poset out of P(X)). "isomorphism" is essentially a categorical notion, not limited just to "sets with structure".
explicitly, if you have a bijection between set A and set B, then saying whether of not A and B are the "same set" depends on your notion of "same". the typical categorical notion is that two sets of the same cardinality are indistiguishable.
i mean, sure the reverse inclusion tower Z-->2Z-->4Z-->8Z--> differs from 2Z-->4Z-->8Z--> in that one has "an extra set", but you have no way of knowing that what is called "two" in the second tower is known by the name "one" in the first tower.
but your answer intrigues me. are you aware of an example of two countably infinte sets with no lattice isomorphism of power sets between them? i'd be interested in seeing it.....