I would be extremely grateful for any help in understanding this question concerning infinite sets.
Take S to be the set of real numbers from 0 to 1000.
Presumably there is a 1 to 1 function mapping S onto the set of real numbers from 0 to 10, and I expect f(x) = x/100 to be one such function.
But suppose the function was f(x) = x/n, where n is arbitrarily large?
Surely this means that the infinite set S can be mapped on to any real interval, even of infinitesimal size?
In the limit as n à ∞, would that mean that S can be mapped onto any single real number? But then it would no longer be a 1 to 1 function, but ∞ à 1?
Going the other way, the set S could have been mapped onto ever ‘wider’ subsets of the Reals, 0 to 1,000,000,000, then 0 to a googolplex, eventually 0 à ∞, or -∞,à ∞?
Ultimately, couldn’t the entire infinite set of Reals be mapped onto an infinitesimal interval at any single chosen real number? What would happen in the limit as the interval tends to 0? Would it be as though any real number somehow ‘contains’ all real numbers? As though a point can give rise to infinity, and infinity can collapse into a point? [Would similar logic hold for complex numbers?]
If you can sort out my understanding, perhaps by pointing me in the direction of a few articles for me to read, I would be very grateful.
Thank you very much for your time.
Absolutely it could! To show this, we'll show that any interval (a,b) is isomorphic (as a set!) to the interval (0,1), and then show that (0,1) is isomorphic (again, as sets!) to .Going the other way, the set S could have been mapped onto ever ‘wider’ subsets of the Reals, 0 to 1,000,000,000, then 0 to a googolplex, eventually 0 à ∞, or -∞,à ∞?
For starters, we'll let be defined by f(x) = a + x(b - a), and let a,b) \rightarrow (0,1) " alt=" ga,b) \rightarrow (0,1) " /> be defined by So long as these maps are left and right inverses of one another, they're isomorphic. Thus,
and , as claimed. Thus, a bijection exists, and the sets are isomorphic.
Now to show that (0,1) is isomorphic to and, since the composition of bijections is itself a bijection, we'll be finished. But, that part is really quite trivial. Take, say, to be defined as . This function is a bijection (you can check it if you like), so (0,1) is isomorphic to the set of reals.
As an immediate consequence, your set S could indeed be mapped by a bijection onto intervals with a much larger diameter, or even on to the set of reals themselves!
Thank you for your very swift replies, CaptainBlack and Math Major. Things are getting much clearer.
The set of Reals can be mapped to an interval, as long as it is finite.
There are bijective mappings, but this would not be needed if all that was required was to cover all Reals in the domain?
A finite interval, no matter how small, can be mapped to the set of Reals.
This mapping could be bijective, but would at least need to be surjective in order to generate all Reals?
Although the interval cannot be shrunk to a specific 'point'/number on the number line, if there is any uncertainty/probability associated with a number, then an interval would be implicit?
I've just realised that the direction I am taking may well be leading the discussion out of the sub-forum. Apologies.
Thank you for your clarifications.
Fred
You are correct that it is not required to have a bijective map from (a,b) to the reals in order to associate each real number with some . I used bijections as it's conveniently easier to prove their existence. Alternatively, (because every bijection has an inverse bijection), the set of reals can be mapped to any interval (a,b) by a bijection. However, no singleton {x} can be surjectively mapped to the set of reals. This should be somewhat clear, for if is any map, then by the definition of a map, there exists a unique element of the range, such that f(x) = r. Pick a real number t such that t = r+1, and we know that f(x) != t, so there is at least one element of the reals that is not mapped to be f, and thus such a surjection cannot exist.
Countable set - Wikipedia, the free encyclopedia has a nice introduction to the notions that might clear up any lingering misgivings about (0,1) having the same cardinality as
Thanks, Math Major, for your detailed explanations.
The Wiki reference was also very interesting.
What most intrigues me is that the unaccountably infinite set of Reals can be 'generated' (by a variety of functions and mappings) from an interval of almost zero 'diameter'/length.
Could we get some sort of lower bound on the 'smallest' size of that interval/set?
Does that almost infinitesimal interval/set have to have the same cardinality as the Reals, aleph1?
Or could it instead be a countable infinite set (aleph0), and a mapping that maps each element in the set to an unaccountably infinite subset of the Reals, such that all the Reals would be covered?
But I suppose there would be no way to guarantee full coverage of the Reals? One would always be able to design a number that could not be generated by the countable infinite set of mappings being used?
Regards
Fred
Sets have the same cardinality if and only if there exists a bijective map between them. The lowest infinite cardinality is , or being "countably infinite". An easy way to think about a countably infinite set is that it's a set whose members can be listed in some meaningful way without missing any. That is to say, for the natural numbers, we could write (0, 1, 2, ...). Clearly, I can't write out all the natural numbers, but if you imagine continuing my list infinitely, it shouldn't be hard to see that I would capture every natural number.
Nonetheless, we can give a more formal definition to countably infinite - a set is countably infinite if and only if there exists a bijection . Note that this definition is just a formal way of saying what I just described (do you see why?). Many familiar sets are also countably infinite - , the set of all rational numbers; , the set of all integers; and the set of all algebraic numbers, to name a few. I should note here that it's not uncommon for the word "countable" to sometimes mean finite sets and countably infinite sets, and others will use countable to strictly mean the countably infinite case. When in doubt, you should always clarify.
We can make an interesting remark here about a situation that will come up again when we discuss the uncountable case. Note that , but and . That is, every natural number is an integer, but not every integer is a natural number. This slightly counter-intuitive notion is one that comes up quite often in discussions of cardinality. Finite notions of size do not necessarily translate into the infinite case.
As you are clearly aware from your previous posts, there are also infinite sets for which no such bijection exists. We call these sets "uncountable". One very familiar set of this kind is , or the set of real numbers. As previously demonstrated, has the same cardinality as any interval for and . Also of interest, and x both share the so called cardinality of the continuum, or the cardinality of the reals.
I'll take a quick moment to clarify some notions on functions and their relation to cardinality. Let and be two sets. If there exists an injective map , then we say that where the absolute value-looking bars denote cardinality. If there exists a surjection , then we can conclude that . Since a bijection takes care of both of these cases, it is a necessary and sufficient condition for two sets to have equal cardinality for there to be a bijection between them. So, we've answered one of your questions. No countable set can be surjectively mapped on to an uncountable set. For, if it could, then its cardinality would be at least that of the uncountable set, which we're supposing is false.
The Cantor-Bernstein-Schroeder theorem gives us an interesting tool for comparing cardinality. If there is an injective map and an injective map , then there is a bijection , or .
By Cantor's Theorem, we know that a bijection between a set and a set's powerset cannot exist. Thus, . This shows us that there is no "largest" cardinality and that uncountable sets, unlike countably infinite sets, do not all have the same cardinality.
I think I've answered (though not always explicitly) most of your questions here. If I didn't explain something well enough, or if it's not clear, feel free to ask!