Insights Blog
-- Browse All Articles --
Physics Articles
Physics Tutorials
Physics Guides
Physics FAQ
Math Articles
Math Tutorials
Math Guides
Math FAQ
Education Articles
Education Guides
Bio/Chem Articles
Technology Guides
Computer Science Tutorials
Forums
General Math
Calculus
Differential Equations
Topology and Analysis
Linear and Abstract Algebra
Differential Geometry
Set Theory, Logic, Probability, Statistics
MATLAB, Maple, Mathematica, LaTeX
Trending
Featured Threads
Log in
Register
What's new
Search
Search
Search titles only
By:
General Math
Calculus
Differential Equations
Topology and Analysis
Linear and Abstract Algebra
Differential Geometry
Set Theory, Logic, Probability, Statistics
MATLAB, Maple, Mathematica, LaTeX
Menu
Log in
Register
Navigation
More options
Contact us
Close Menu
JavaScript is disabled. For a better experience, please enable JavaScript in your browser before proceeding.
You are using an out of date browser. It may not display this or other websites correctly.
You should upgrade or use an
alternative browser
.
Forums
Mathematics
Set Theory, Logic, Probability, Statistics
Is there a "smallest" infinite subset of the naturals?
Reply to thread
Message
[QUOTE="Jarvis323, post: 6859877, member: 475688"] A few years ago I was thinking about these kinds of things. Like the apparent motivation of the OP, it stemmed from being unsatisfied with the idea that a "sparser" set is the same "size" as a less "sparse" one, and wanting to come up with a more interesting way to quantify infinite subsets of natural numbers. I don't think I made much progress in the end. But what I though was the right starting point was to think about the amount of information represented by the set. When you think about it, what makes the even numbers a different set than the natural numbers? You could just as well rename the natural numbers as if they had a different alphabet, and then { 2, 4, 6, 8, ...} is just the same set described with different symbols. This is what putting them into a bijection sort of amounts to. But the sets ARE fundamentally different, because these numbers have meaning outside of just being infinite sets of combinations of symbols. There is some amount of information providing this meaning that differentiates them. We can think of sets with our physical intuition as containers of objects, but is that really what they are? Or are they better characterized as some kind of body or system of information? First we need to have the information that defines the natural numbers and our encoding of them. Then you need more information to specify which ones to leave out or not. E.g., the even numbers come with a small amount of additional information compared with the natural numbers. In this sense, the set of even numbers represents more information. If we decide sets are fundamentally informational objects, then it makes sense to say the evens is larger. And both, despite being countably infinite in cardinality, are actually finite and quite small objects. We could try to formally define the size this way based on Kolmogorov complexity, where the size of the set is the size of the minimal program that enumerates it, relative to some computing model. There are some questions I personally don't know the answers to, and issues and consequences worth thinking about: (1) Some sets of natural numbers aren't computably enumerable. (2) The Kolmogorov complexity depends on the order of the elements in the set. Our minimal program can print the set in any order it wants. (3) I guess the subsets which cannot be printed by any finite program would have an infinite size. But conventionally a program has to be finite, so you need another model of computation besides, say Turing machines, to formalize this properly. Anyways, assuming you do, then you still have a similar annoying problem as the one which motivated this all in the first place, how to differentiate the "sizes" of these sets which are representations of infinite amounts of information. [/QUOTE]
Insert quotes…
Post reply
Forums
Mathematics
Set Theory, Logic, Probability, Statistics
Is there a "smallest" infinite subset of the naturals?
Back
Top