The bijection problem the natural numbers and the even numbers
My math is at high school level so bear with me.
One definition of an infinite set I know of is that an infinite set is in bijection with a proper subset of itself.
Bijection, as I understand it, means that we can pair one item in a set with exactly one item in another. For example take two sets {a, e, i, o, u} and (3, 9, 2, 7} The bijection would be a3, e9, i2, u7
Now let's take two infinite sets:
1) Natural numbers N = {1, 2, 3,...}
2) Even numbers E = {0, 2, 4,...}
E is a proper subset of N and according to the definition of infinite sets E is in bijection with N. For any element y in N there's exactly one element in E that's (2y - 2) I.e. 1 in N is paired with 0 in E, 2 in N is paired with 2, 3 in N is paired with 4 in E, so and so forth.
In terms of cardinality or largeness or magnitude N = E. They are both infinite and in an equivalent way.
However, let's do something different. We take the same sets N and E. We know that N has the even numbers. So we pair the members of E with the even numbers in N. We can do that perfectly and with each member of E in bijection with the even number members of N. What now of the odd numbers in N? They have no matching counterpart in E.
Doesn't this mean N > E?
What's wrong with my argument?
Thanks
One definition of an infinite set I know of is that an infinite set is in bijection with a proper subset of itself.
Bijection, as I understand it, means that we can pair one item in a set with exactly one item in another. For example take two sets {a, e, i, o, u} and (3, 9, 2, 7} The bijection would be a3, e9, i2, u7
Now let's take two infinite sets:
1) Natural numbers N = {1, 2, 3,...}
2) Even numbers E = {0, 2, 4,...}
E is a proper subset of N and according to the definition of infinite sets E is in bijection with N. For any element y in N there's exactly one element in E that's (2y - 2) I.e. 1 in N is paired with 0 in E, 2 in N is paired with 2, 3 in N is paired with 4 in E, so and so forth.
In terms of cardinality or largeness or magnitude N = E. They are both infinite and in an equivalent way.
However, let's do something different. We take the same sets N and E. We know that N has the even numbers. So we pair the members of E with the even numbers in N. We can do that perfectly and with each member of E in bijection with the even number members of N. What now of the odd numbers in N? They have no matching counterpart in E.
Doesn't this mean N > E?
What's wrong with my argument?
Thanks
Comments (133)
That's not how we say it. Rather, we say the cardinality of N equals the cardinality of E.
card(N) = card(E)
Quoting TheMadFool
The even numbers in N are just the members of E. So your pairing is just pairing the members of
E with the members of E.
Quoting TheMadFool
No.
N > E
means
Both hold: (1) there is a pairing from E to a proper subset of N and (2) there is no pairing between N and E.
But there is a pairing between N and E, so it is not the case that N > E. The fact that there is a pairing from E to a proper subset of N (e.g. the pairing misses the odd numbers in N) does not contradict that still there is a pairing between N and E.
/
I recommend this terminology ('<->' means 'if and only if'):
f is an injection from S into T <-> (f is a one-to-one function & the domain of f is S & the range of S is a subset of T) [note: here the range of f might not be a proper subset of T since it is allowed that the range of f is T]
f is a surjection from S onto T <-> (f is a function & the domain of f is S & the range of S is T) [note: here f might not be a one-to-one function]
f is a bijection from S to T <-> (f is an injection from S into T & f is a surjection from S onto T)
S is equinumerous with T <-> there is a bijection from S to T
S is dominated by T <-> there is an injection from S into T
S is strictly dominated by T (i.e., S < T) <-> (there is an injection from S into T & there is no bijection from S to T)
If you like I can recommend a few textbooks in first order predicate logic and then set theory that would provide you with a self-course in this subject. Then you would not be prone to confusions about the subject.
My argument is like Cantor's diagonal argument regarding the absence of bijection between the real numbers and the natural numbers
N = {1, 2, 3, 4, 5, 6, 7, 8, 9,...}
E = {0, 2, 4, 6, 8, 10, 12, 14, 16,...}
Now pair the even numbers in N to the members of E
(2,0), (4,2), (6,4), (n,n-2),... There's a bijection but it leaves the odd numbers in N without a matching pair. In other words card(N) > card(E)
Cantor proved that there does not exist a surjection from the one set onto the other, peforce that there is no bijection between them. (No surjection from N onto R, perforce no bijection between them).
Your argument just points out that one particular function is not a bijection from the one set onto the other (it's not a bijection from E onto N) The fact that one particular function is not a bijection from the one set onto the other does not prove that no other function that is a bijection from one set onto the other. And indeed we prove that there is a bijection from the one set onto the other.
Cantor proved that there is no surjection from N onto R.
But we also know that there is a bijection between N and E.
It is a clear logical fallacy to infer that because some particular function is not a bijection between N and E that therefore there is no function that is bijection between N and E.
I offered to recommend some starting books on this subject so that you can inform yourself to avoid the fallacies and confusions to which you are prone.
is typically demonstrated using a 'one to one' correspondence as shown.
N: 1 2 3 4 5 6 ...
E: 2 4 6 8 10 12 ...
This is contradicted by:
1. Random sampling of integers results in an average of 50% even E, 50% odd D.
Statistics can be verified in the real world, and is useful in applications of probability.
2. In the above example, removing E from N leaves D, removing E from E leaves nothing, so where is the logic? An odd feature of this example is the appearance of the same integers in both sets.
The 'bijection' for example 1 defines y=2x, as a mapping from N to E. The results are not about the size of sets, but the definition used for mapping.
Representing the first 'one to one' correspondence above in a rectangular form, partitioned into subsets:
1 2 4 8...
3 6 12 24...
5 10 20 40...
...
The odd integers, all listed in column 1, are paired with the column of even integers to the right.
The remaining even integers in each column are paired with the column to the right.
The pairing is independent of direction.
The odd are paired 1 to 1 with an even.
The first subset of even (col 2) is paired with odd (col 1) and even (col 3).
The remaining even are paired with two columns.
Not all pairings are 1 to 1, and each integer appears only once.
A true example of a 1-1 correspondence, "there are as many even integers as odd integers "
D: 1 3 5 7 9 11 ...
E: 2 4 6 8 10 12 ...
A set without limit (infinite) is not measurable, since boundaries enable measurement.
I have a straight stick with one end. Can anyone tell me its length?
No, your not doing that.
Quoting TheMadFool
Do understand what you are making with a bijection: every member of E has a pair in N and vice versa. That is a bijection, one to one correspondence. You are now somehow assuming it wouldn't be a bijection, but either a surjection or an injection.
The idea is most easily understood like this:
Natural number N: 1, 2, 3, 4, 5,...
Then multiply EVERY natural number by two.
:1x2, 2x2, 3x2, 4x2, 5x2,....
Then you get even numbers.
E:2, 4, 6,8, 10,...
And you can do with let's say by 10 000.
Hence there is a bijection between
N: 1,2,3,4,5...
and the infinite series
:10 000, 20 000, 30 000, 40 000, 50 000,...
even if there is 9 999 numbers "in between".
Quoting TheMadFool
Others have pointed it out. I second their criticisms. This is, however, a fascinating subject, and I also second the notion that you should pick up a book on it. There is room for philosophical criticism of the assumptions involved, but I don't see even room for invalidating relatively trivial results. If one learns the game, then such results are trivially true within the game. Whether this or that game is better in various sense is another question.
No. Sorry. The equivalence is defined as the mathematical existence of a bijection. Mathematicians are well aware that they are different sets. And 'statistics can be verified in the real world' is anything but an obvious truth --assuming that it has a definite meaning in the first place.
While some mathematicians have little interest in philosophy and may ignore fascinating questions, they aren't slouches when it comes to actual math. Pure math is about as squeaky clean as it gets. The game has rules. What the game means when held against the 'real world' is a non-mathematical question. And the rules were established so that math wouldn't be a sloppy philosophical conversation.
Quoting sandman
https://en.wikipedia.org/wiki/Measure_(mathematics)
[quote=Wiki]
In mathematical analysis, a measure on a set is a systematic way to assign a number to each suitable subset of that set, intuitively interpreted as its size. In this sense, a measure is a generalization of the concepts of length, area, and volume. A particularly important example is the Lebesgue measure on a Euclidean space, which assigns the conventional length, area, and volume of Euclidean geometry to suitable subsets of the n-dimensional Euclidean space Rn. For instance, the Lebesgue measure of the interval [0, 1] in the real numbers is its length in the everyday sense of the word, specifically, 1.
[/quote]
The measure of Q is 0. But Q has no boundary on its left or right (on the real line.) It also has infinitely many elements.
Sure.
Starting from the fact that we don't know the answer to the Continuum Hypothesis. Which tells us quite plainly that we still don't understand everything about mathematical infinity.
Right. And then one can think about constuctivism, finitism, etc. Or whether math is ultimately justified within a culture by its application. Its 'internal' justification (proofs) aren't necessarily why it is trusted or esteemed, especially as proofs get too complex for non-experts.
On forums I see those who appear to have no training approaching it 'metaphysically,' seemingly assuming that mathematicians themselves do it this way. But that misses what's essential, that it's a game with rules. It's agnostic about things outside those rules, even if particular mathematicians philosophize.
One can still ask philosophical questions about the 'frame' or set rules that makes this argument possible (set theory and classical logic), but the argument itself is beautiful and mind-opening. Because I call it beautiful or mind-opening, I do imply that the argument has intuitive content. But the argument doesn't depend on this intuitive content.
It truly is mind opening. Even now it's a puzzle for us just what it opens to us.
When we show with Cantor's diagonal argument that there isn't a bijection between N and R, it's not anymore such a simple proof that we are used to, but an reductio ad absurdum proof. And this has profound implications, which shows itself with the Continuum Hypothesis.
Furthermore, we get using a similar technique as the diagonal argument, Gödel's incompleteness theorem's and Turing's answer to the Entscheidungsproblem. And in another way Russell's paradox. All of them in one way or another use what I'd call a negative self-reference.
Indeed. I have also studied those other results, especially in Kleene's Mathematical Logic. When I was first exposed to cardinality issues, I was, frankly, amazed and seduced. And I was myself guilty of raising objections I wasn't qualified to raise, too impatient to do the work required. Though I eventually did the work and saw the futility of merely intuitive/metaphysical approach. A person should probably write (at least) a few hundred proofs before philosophizing much about mathematics.
FWIW, I do think self-reference is one of the centers of philosophical opportunity. (Strange loops!)
Natural numbers N = {1, 2, 3, 4, n, ...}
Even numbers E = {2, 4, 6, 8,, 2n...}
2 = 2 x 1
4 = 2 x 2
6 = 2 x 3
.
.
.
n = 2n
This then is used to "prove" that the set E is equivalent to set N
I get that and thanks for clarifying.
However I can see another pairing (1-to-1 correspondence) of numbers in the two sets as follows:
N = {2, 4, 6, 8,...,1, 3, 5,...} As you can see I've divided the set N into two parts viz. the even numbers and the odd numbers but note they're included in the same set N
The set of even numbers E = {2, 4, 6, 8,...}
As you can I see can form a pairing (1-to-1 correspondence) between E and the even numbers in set N like so: (2,2), (4,4), etc. and that leaves the odd numbers without a corresponding pair in the set E.
Basically two different bijections are possible. One agrees with Cantor's "proof" but the other contradicts Cantor. You'll have to show that Cantor's bijection is the correct one and the alternative is nonsensical. Can you do that?
NOTE: I've excluded zero from the set of even numbers for simplification purposes
I'm guessing that an infinite number of bijections are possible. We can flip segments of length k and proceed as before. This works for any k >= 2.
For instance, let k = 3.
Then f = { (1,6),(2,4),(3,2),(4,12),(5,10),(6,8),...}.
Note that a function is itself just a set of ordered pairs (satisfying a condition that ensures an unambiguous output).
But all we need for equivalence, by definition, is a single bijection.
Quoting TheMadFool
Note that sets are not ordered. {1,2} = {2,1}, for instance. The order is in the bijection. And, as you know, the easiest bijection is [math] f(n) = 2n,[/math] with inverse [math] f^{-1}(e) = e/2.[/math] The alternative bijections mentioned above probably have complicated algebraic forms, despite the simplicity of the idea behind them.
Quoting TheMadFool
What you say is a contradiction. A 1-to-1 correspondence is a bijection. As I understand you, you are presenting [math] g : E \to N [/math] such that [math] g(e) = e [/math]. Because odd numbers are not in the range of g, this function is not a surjection, though it is an injection (1-to-1). A bijection is simultaneously a surjection and an injection. https://en.wikipedia.org/wiki/Bijection
Please consider that there are uncountably many functions from E to N. One can use a diagonal argument to prove this. Assume not. Well clearly [math]f_k(e) = ke [/math] is a countably infinite family of functions. So the functions from E to N are at least countably infinite. So by our assumption (in pursuit of a contradiction), we can arrange the functions from E to N in an countably infinite list [math] f_n [/math]. Then we define our diagonal function [math] f(e) = f_e(e) +1 [/math] where the [math]f_n[/math] is the nth function in a merely countable list of functions from E to N.
Since [math] f(n) = f_n(n) + 1[/math], it differs from every [math]f_n[/math] at [math]n[/math] and is not on the list, despite being a function from E to N. Contradiction! The point of the list [math] f_n [/math] was to catch all functions from E to N. Hence our assumption that such functions are countable is incorrect. And they are at least countable, so they must be uncountable. Or you can interpret this as: since any possible listing allows for its own diagonal function not on that list, no listing gets them all (providing a bijection from N to the set of those functions.) Every listing casts a shadow or has a blind spot. We just slash diagonally to get something not on the list.
It's not surprising that you can find one such function that isn't a bijection. I'm guessing (someone feel like proving it?) that the probability of picking a bijection randomly is 0. Is the subset of bijections countably infinite? Sounds like a fun question.
Quoting TheMadFool
Keep in mind that this is just one kind of equivalence. It only has as much metaphysical weight as a philosopher feels like giving it. Mathematicians can all agree that X is proven without having to agree on what that means outside of mathematics. 'There exists' has a formal meaning. If [math] x \in \Bbb R [/math] and [math] x \ne 0 [/math], then [math] \exists y \in \Bbb R [/math] such that [math] xy = 1 [/math]. That's an axiom. It's a rule that allows you to put a new piece on the board. Despite the intuitions and applications that quietly drive the 'game,' the game itself is 'safer' than that. Computers can, in theory, check proofs. In practice this is not often considered necessary or desirable.
It's like learning a language. Once you learn it, lots of proofs are easy to judge for their correctness.
No, that's a great source of confusion. If there exists a bijection between two sets, even a single one, even if there are plenty of functions that aren't bijections, then we DEFINE the two sets as being cardinally equivalent. It's a definition, not a proof.
Given the naturals N and the evens E, there exists a bijection. So we say, by definition, that the two sets have the same cardinality. The fact that there are many functions between the two sets that aren't bijections is irrelevant. The condition is an existential, not universal, quantification. If out of all the functions from one set to another there happens to be a single one that's a bijection, then the two sets are cardinally equivalent, by definition.
As has been noted, this is not the only way to compare the relative sizes of sets. There's the subset relation. Clearly E is a proper subset of N so E is "smaller" than N with respect to the proper subset relation
Yet another way that was mentioned a few posts back is natural density, also known as asymptotic density. Using this method we see that the limit as n gets large of the proportion of even numbers among the first n numbers goes to 1/2. So the natural density of E in N is 1/2. Likewise the natural density of the multiples of 3 in N is 1/3; and the natural density of the primes is 0. [Proof by the interested reader for that last assertion].
So there are lots of ways to compare the relative size of sets. Cardinality happens to be one way. It's not a very fine-grained one. For example the intervals [0,1] and [0,2] of real numbers have the same cardinality, since there's a bijection between them: namely f(x) = 2x. But [0,1] has length 1 and [0,2] has length 2. The generalization of the idea of length is called measure, and it's yet another way to compare the relative size of sets. In fact measure theory underlies modern probability theory, so it's very important. But as we saw with the intervals, cardinality does not respect measure. In that sense cardinality is a very crude way of thinking about the relative sizes of sets.
Just as we use a hammer for one thing and a spatula for another and a torque wrench for yet something else, mathematicians have a lot of tools in the toolbox. Cardinality, as defined by bijection, is just one tool, to be used as appropriate.
Quoting TheMadFool
Cantor's definition of cardinal equivalence via bijection is not right or wrong. It's a definition. In the past 140 years it has proven to be both interesting and useful, which is why it's stuck around. But it's not the only way of comparing sets; and it's neither right nor wrong. It's just one of the tools in the mathematical toolbox. E and N have the same cardinality. The natural density of E in N is 1/2. And E is indeed a proper subset of N. All three points of view are equally valid. One or the other viewpoint might be more useful in a particular context.
That's where the problem is isn't it?
The definition is inadequate for the reason that, on one hand, Cantor's "preferred" bijection leads to an equivalence between the set of even numbers and natural numbers but on the other hand there exists another bijection that shows that the set of natural numbers is not equivalent to the set of natural numbers.
It's a definition. It can't be right or wrong.
You do agree that there exists at least one bijection between N and E, namely f(n) = 2n. You agree with that, yes?
Then by definition the two sets have the same cardinality. That's all it means. If there exists a bijection, then the sets are said to have the same cardinality.
It's true that there are many functions between E and N that aren't bijections, but it only takes one to satisfy the definition.
Do you agree that even if you don't like the definition, E and N satisfy it by virtue of that one bijection?
Quoting TheMadFool
But no. The existence of a non-bijection doesn't prove anything. As long as there's a single bijection, the definition is satisfied. Not because it's right or wrong, but because that's the definition.
If a definition leads to a contradiction?
It doesn't.
Do you agree that there exists at least one bijection from E to N?
If you agree, then you must agree that E and N have the same cardinality, because the definition says that there must be at least one bijection between them, and this is manifestly the case.
ps -- It's like a guy who cheats on his wife. She says to him, "You're a cheater." He says no! Think about all the times I DIDN"T cheat on you.
But that's not the point. If you cheat once, that's the definition of a cheater. If you cheated Monday but not on Tuesday or Wednesday, you can't say you're not a cheater because you didn't cheat on Wednesday. Right? The definition is doing it once.
Likewise the definition of cardinal equivalence is that there's at least one bijection. It doesn't matter that some other function isn't a bijection.
That's not technically Cantor's diagonal argument. That proof comes into use only with the reals R.
Quoting TheMadFool
Please understand you are not talking of a bijection! It isn't a bijection if one group has more members.
It's either an injection or an surjection. It's the most simple math there is an actually one of the most hardest.
And, if I understand your thought correctly, you are basically saying that there's an injection from E to N. But when you can prove there's a bijection, it doesn't go that it's only an injection.
Yet, understand that you are talking about infinite series. Have you ever heard about the Hilbert Hotel?
I don't presuppose a finite stick. They are the norm. Given the definition of infinite, without limit or boundary, and the fact that infinite is not a number or quantifier, a one ended stick is not measurable/quantifiable. You already described the futility of such an effort.
Cantor was an illusionist and fooled many people.
I read Cantor's biography. It helps to understand his motivation to write.
I agree, ignorance is abundant.
Quoting fishfry
So there was nothing wrong when Socrates defined humans as featherless bipeds and someone came along with a chicken plucked of all its feathers and declared "this is a human"? After all there was/is at least one human that fit the definition.
However I am actually talking about there being an injection correspondence between even numbers and natural numbers and so bijection correspondence isn't the only game in town. Ergo, the set of even numbers isn't equivalent to the set of natural numbers.
From a programmer's point of view, cardinality equivalence between two sets is about their expressibility through each other.
card(N) = card(E) tells me that if I want to define an encoding of the elements of E through the elements of N, or N through elements of E, I can. Thus, I can write/store n to represent "the n-th even number", and 2*n to represent "the ordinal n". In any case, as long as I standardize my representation upfront, I am going to be able to decode it uniquely later.
card(N) < card(R) tells me that I can never represent a real number through a natural number, no matter how I try to tip-toe around the issue. I can muster the strangest encodings, but it is logical impossibility. Thus, I will be able to express only some real numbers ordinally (or even out of order), but not all of them.
P.S. Thus your dilemma can be rephrased as the ability to encode some set and a strictly smaller set through the same representation set. This may be awkward in some sense, but it is just a fact of life.
It's like as if someone told you that Sarah and Anil are the same age, and you objected that Sarah is a woman and Anil is a man, Sarah is American and Anil is Indian, Sarah is smaller than Anil, so how could they be equivalent?! Cardinality is just one measure of sets, nothing less, nothing more. Get over this already.
Your post helped me to clarify my view.
If 'there are as many even integers as integers' is replaced with 'my new set has as many elements as E', then it makes sense.
'indoctrinate'
cause to believe something: to teach somebody a belief, doctrine, or ideology thoroughly and systematically, especially with the goal of discouraging independent thought or the acceptance of other opinions
Somehow this word seems appropriate, if applied to yourself.
First, there are no experts, just some people with more experience than others.
The example in question:
N={1 2 3 4 5 6 7 8 ...}
E={2 4 6 8 10 12 14 16...}
A one to one correspondence of E to N, with the conclusion 'there are as many even integers as there are integers'.
Why are the same integers on both sides of the correspondence?
1 is linked to 2, and 2 is linked to 4, i.e. all even integers have 2 links, all odd have 1 link, and each integer is unique.
And with that you might show us how you can 'approach infinity'.
Not in direct opposition to this statement, but just a remark...
Some educators are stuck on introducing maximum controversy when they present their students with novel abstractions. Expressions such as "as many as", I think, have to be reserved to already familiarized audiences, but some teachers find it particularly amusing to thrust the "inside jokes" of mathematics directly to the uninitiated.
Not it doesn't. Because it doesn't meet the definition of ">", here is the definition:
X > Y if and only if there is an injection from Y to X, but there is no injection from X to Y.
I can only implore you to carefully re-read what I and others have written. Perhaps Cantor's beautiful ideas will come to you at some point. Perhaps not.
:clap: :ok: :up:
I really hope so too.Thanks.
[Direction is not a factor in forming a sequence.]
[A well known mathematician, whose name escapes me, when asked to define mathematics replied "a manipulation of symbols". I was impressed by such a concise and accurate description.]
a quote by Cantor, Source: Ewald, W., From Kant to Hilbert, Oxford 1996.
"[… Mathematics is in its development entirely free and is only bound in the self-evident respect that its concepts must both be consistent with each other, and also stand in exact relationships, ordered by definitions, to those concepts which have previously been introduced and are already at hand and established. In particular, in the introduction of new numbers, it is only obligated to give definitions of them which will bestow such a determinacy and, in certain circumstances, such a relationship to the other numbers that they can in any given instance be precisely distinguished. As soon as a number satisfies all these conditions, it can and must be regarded in mathematics as existent and real
"… the essence of mathematics lies entirely in its freedom".]"
We know what Cantor thought.
Cantor was most concerned with his standing in the mathematical community, beyond his bouts of depression. In publishing papers on the nature of infinity through his transfinite numbers, he claimed it was a supernatural revelation. Maybe expecting acceptance through authority, which does occur even in modern times. The well known mathematicians of that period didn't accept his ideas initially, so skepticism is not new.
He associated the truly infinite with GOD. He should have left it there.
The informal talk of 'flipping the bits along the diagonal' is just handy way of describing a function not on the list, [math] f : N \to \{0,1\} [/math]. You have yet to show that you know enough about math to lecture me about sequences.
Quoting sandman
Formalism is one way to think of things. It has its problems, but so do perhaps all -isms that try to tell the final truth. Math is only interesting, it seems to me, because of its practical and/or intuitive appeal. Even if we think of it from a distance as a system of dead symbols, we then have to reason intuitively about that system. In the same way a chess player has an intuitive grasp of what is going on, even as, importantly, a computer can check the legality of moves. This doesn't mean that kings and knights exist in some magical realm. But it's safe to talk about chess players sharing intuitions that make playing the game possible. This is just sufficiently intersubjective concepts, not unlike us talking now in a shared language.
Here's a great book:
https://www.amazon.com/Analysis-History-Undergraduate-Texts-Mathematics/dp/0387770313
Practice and intuition came before a relatively settled foundation. The real numbers are at the center of both practice and intuition. While you have focused on Cantor, the nature of the real numbers as theoretical entities is just as strange and philosophically questionable. Why aren't you railing against the 'superstition' that 2 has a square root? Have you ever seen it? It's a theoretical construction.
And Cantor's motivations or philosophy or theology, whatever one thinks of it, doesn't stick to his ideas. Unless you are also ready to call Newtonian physics a scam too,
https://en.wikipedia.org/wiki/Isaac_Newton%27s_occult_studies
Because these issues fascinate you, it's possible that you'll end up a mathematician. I was disturbed by Cantor once too, but I kept on thinking and reading and eventually got some formal education in the discipline. I suggest a book like this one: https://www.amazon.com/Concise-Introduction-Mathematics-Third-Chapman/dp/1439835985
Thank you for being so gracious. Not always my experience around here and I appreciate it.
Let me see if I can respond directly to your plucked chicken remark. In that case there is an underlying reality, namely the existence, or the fact, of human beings. Our existence on earth logically and historically precedes any formal description of the matter. So when we say, "A human is a featherless biped," we are NOT actually defining what it means to be human. A human is so much more complex than any mere formalization could encapsulate. So at best when we say "A human is a featherless biped," what we are doing is laying down the rules for a formal, logical treatment of what it means to be human. And if we are wise we will recognize that. Personally I believe in science but I oppose scientism.
Now when it comes to sets, the matter is totally different.
In this case there is no underlying reality. There is no "setness" that we are trying to formalize. Rather, sets are whatever satisfies the rules we're writing down. Before the rules are written down, there are no sets! Unlike with humans, whose existence precedes any humanly contingent theory of them.
So you may be thinking, "This bijection business might be logically correct, but it doesn't match my beliefs about sets." But the right way to think about it is: "The knight in chess moves the way it does because that is the rule. And sets behave the way they do because those are the rules!" We must learn to adjust our intuitions to the symbology. We have to cast off our intuitions and just do exactly what the symbols say. That's the essence of learning math.
[Now if you want to talk about the "unreasonable effectiveness" of math in the real world then that's another subject. But math must be taken on its own terms! It need not conform to reality nor does it, most of the time].
In high school they tell you that sets are collections, but as we all know Russell ruined Frege's day be discovering that this cannot possibly be. Ever since then, set is an undefined term just as point and line are undefined terms in Euclidean geometry.
If you want to know what a set is, the answer is that nobody has any idea what a set is. A set is whatever satisfies the rules of set theory. In fact set theorists like to mess around with different rules to see what kinds of crazy sets they can come up with.
So when we see a plucked chicken we may fairly say, "Oh, our formal characterization was good as far as it went, but it needs to be refined. How about featherless bipedal mammals?" Then someone will shave a gorilla and we'll be off to the races again. A formal system can never completely capture every aspect of reality.
Whereas with sets, that thought process doesn't happen because sets don't exist outside of the rules we stipulate for them. There is no underlying reality to appeal to. Sets are what the rules say they are. So when we say two sets are cardinally equivalent if there's at least one single solitary lonely bijection between them; then that is the absolute truth of the matter. Because in set theory, the rules precede the reality. With humans, the reality precedes the rules.
tl;dr: It's chess not chickens.
Or as Charles Sanders Peirce aptly put it, mathematics is the science that draws necessary conclusions about purely hypothetical states of things.
Quoting tim wood
Ironically, there is a countably infinite number of cardinals, only the smallest of which is itself countable.
I was thinking of the generalized continuum hypothesis--the idea that for any infinite set of a given cardinal (aleph_n), its power set is always of the next higher cardinal (2^aleph_n = aleph_n+1), with no cardinals in between and no largest such cardinal. Those cardinals are obviously in one-to-one correspondence with the natural numbers; i.e., countably infinite.
I wouldn’t label it ‘superstition’, but an abstraction, like point, line, circle, the continuum, etc., all mental constructs for purposes of measurement. They are practical conveniences
Or as Bertrand Russel said, "Mathematics may be defined as the subject in which we never know what we are talking about, nor whether what we are saying is true."
Quoting aletheist
This is not true. There's a proper class of Alephs, indexed by the proper class of ordinal numbers. After [math]\aleph_0, \aleph_1, \aleph_2, \dots[/math] come [math]\aleph_\omega, \aleph_{\omega + 1}[/math], and onward forever; too many Alephs to ever be captured in a set.
https://en.wikipedia.org/wiki/Aleph_number
Thanks for the correction.
OK, but then many mathematicians would agree with you. To me math is something like the formalization of intuitions. I like formalism, but it doesn't speak to the beauty many find in it. And when I and other math people I know are doing math, we need intuition to write proofs and make sense of proofs.
That said, at some points proofs become too long. No one can remember all of the steps. One has to trust the machinery of what one has proved but no longer keeps in mind. Or one uses machinery that one hasn't checked. We can switch into a playing-with-symbols mode, and sometimes we have to. In short, no philosophy of mathematics gets it quite right for me. They all focus on this or that aspect. I will say that I'm not a Platonist, since I don't think a community can see around its own eyes. Shared intuitions are plausible. More feels like reaching.
I was using the "plucked chicken" example to only point out what I think is important in math - consistency. I'm vaguely aware that we can add/delete axioms and build entirely new worlds of numbers and geometry. As must follow inconsistencies between such worlds are expected. The only example I can think of to explain this is that in non-euclidean space the sums of a triangle need not equal 180 degrees.
However, each mathematical world however constructed must be internally consistent i.e. the axioms and definitions within a given system shouldn't lead to contradictions.
In the case of the bijection, defined as each element of one set being paired with exactly one element in another set, when applied to the sets natural numbers and even numbers we certainly do arrive at the conclusion that there's a bijection between these sets.
Yet, following the same principle - pairing one element to another of these two sets - we arrive at a situation where every even number is paired with an even number in the set of natural numbers with the odd numbers left unpaired. Here we have what I think is an inconsistency - the same rule (pairing elements of one set with elements of another) producing, depending on the way you do the pairing, different, actually contradictory, results. Math can't have contradictions can it?
I'm not sure I understand your point. Some examples that come to mind:
* The unit interval [0,1] can be bijected to the interval [0,2] but neither set is well-ordered in its usual order and both are uncountable sets full of irrationals (and some rationals too).
* Ok you say but at least in that case the obvious bijections preserve order. But how about bijecting [0,1] to the open unit interval (0,1)? Then there's a bijection but it does not preserve order.
* The naturals biject to the rationals and the rationals in their usual order are not well-ordered.
* For that matter the naturals can be bijected to the integers and the integers are not well-ordered.
* In fact any set whatsoever may be well-ordered as a consequence of the axiom of choice.
* And finally, and counterintutively, the reals might be well-ordered even in the absence of the axiom of choice.
Well-ordering doesn't have anything to do with bijections. I can't understand the point you're making.
ps -- One more item.
* Even two well-ordered sets may not be bijectable. There are uncountable well-ordered sets.
There is no contradiction. The definition of cardinal equivalence is that there exists at least one bijection between the two sets. I don't know why you have a psychological block against grokking that.
Guy robs a bank, gets caught. In the interrogation room the detective says, "Fred we know you're the bank robber." Fred says, "Oh you are wrong. Here is a list of all the banks in the state that I didn't rob. I even have a notarized statement to that effect from the manager of every single bank in the country that I did not rob."
Is Fred a bank robber? Yes of course. He robbed a bank! He robbed one single solitary bank and DIDN'T rob all the others. But he's a bank robber.
It's an existential quantification, "there exists," and not a universal one, "for all." Someone is a bank robber if they ever robbed a bank, even if there are many banks they didn't rob. Two sets are cardinally equivalent if there is a bijection between them, even if -- as must ALWAYS be the case -- there are maps between them that are not bijections.
Someone murders someone, they're a murderer. No use parading before the jury the seven billion human beings they DIDN"T murder. That lady cop in Dallas a few months ago who shot a guy sitting in his living room eating ice cream. She was convicted of murder. She's in prison as we speak, ten years if I recall. No use trying to point to all of her neighbors who she didn't kill. She killed one guy. That makes her a murderer in the eyes of the law.
Why is this simple point troubling you? If you're on the jury do you say, "Well, the prosecutor showed that she murdered someone. But she didn't murder EVERYONE." You find her not guilty on that basis? Of course not! Right?
Even Hitler didn't murder EVERYONE. You think he got a bad rap? LOL.
What? There's no order-preserving bijection between [0,1] and (0,1). Yet there is most definitely a bijection But why would I need to Google bijection? Perhaps you can point to the paragraph on Google that you are referring to.
Can you please be specific in your objection?
* Do you agree that there's a bijection between [0,1] and (0,1), the closed and open unit intervals in the real numbers, respectively?
* Do you understand that such a bijection could not possibly be order-preserving?
Quoting tim wood
What is the usual order on the rationals? You aren't sure? Come on, man. The usual order is the usual order.
Well, reading the re
Quoting tim wood
Pi and 47. I see that you are not familiar with the notion of well-ordering the reals, or well-orderings in general. If you were you could not ask this question.
Quoting tim wood
Which can be well-ordered: definitely using the axiom of choice; and possibly even in the absence of choice.
Quoting tim wood
Wow. Just wow. What is it with this forum? Tim, you're as wrong as wrong can be.
Of course I'm perfectly used to people on this forum being wrong about some mathematical topic and getting insulting when their ignorance is pointed out. The old forum was never this nasty but this place is. But on the mathematical facts, well you haven't presented any.
Define [math]f: [0,1] \rightarrow [0,2][/math] by [math]f(x) = 2x[/math]
Claim: [math]f[/math] is a bijection.
Proof: We will proceed by showing that [math]f[/math] is injective and surjective.
Injective subproof:
[math]f[/math] is injective when and only when for all [math]x,y[/math], [math]f(x) = f(y)[/math] implies [math]x=y[/math]. Let [math]x,y \in [0,1][/math] be arbitrary, then assume (for conditional proof) that [math]f(x)=f(y)[/math], by the definition of [math]f[/math] this implies [math]2x=2y[/math] which in turn implies [math]x=y[/math]. So [math]f[/math] is injective.
Surjective subproof:
[math]f[/math] is surjective when and only when for all [math]y \in [0,2][/math] there exists [math]x \in [0,1][/math] such that [math]y = f(x)[/math]. Let [math]y[/math] in [math][0,2][/math] be arbitrary, then consider [math]x=y/2[/math]. Firstly, this is in [math][0,1][/math] because the minimum of [math]x[/math] is [math]0[/math] and the maximum is [math]1[/math]. Then we evaluate [math]f(x) = f(y/2) = 2y/2 = y[/math]. Since [math]y[/math] was arbitrary, [math]f[/math] is surjective.
Therefore [math]f[/math] is injective and surjective. By definition, [math]f[/math] is bijective.
Two sets are of equal cardinality when and only when a bijection exists between them. [math]f[/math] exists (it is a well defined function (proof omitted) between [math][0,1][/math] and [math][0,2][/math]). Therefore [math][0,1][/math] and [math][0,2][/math] are of equal cardinality.
Regarding the order preserving bit. This function is total order preserving because it's monotonic increasing. But the definition of bijection or being of equal cardinality does not require order preservation. There are easy finite set examples for this. An infinite set example is [math]f:\mathbb{R}^+ \rightarrow \mathbb{R}^+[/math] with [math]f(x) = 1/x[/math] - this one is a bijection that reverses inequalities (it's monotonic decreasing).
Neither of these say anything about well orders; the order above is the standard total order on the reals, rather than any well ordering. The ordering has sets which do not have a least element. (Real) sets with a least element contain their greatest lower bound (which is their set minimum) - and an interval like [math](0,1)[/math]'s greatest lower bound is [math]0[/math], which isn't in the set by definition. So the standard order on the reals isn't a well order; because there's at least one subset of it which does not have a least element.
Wait ... @tim wood was confused about THAT?? I didn't mention it because it's so obvious, at least to anyone who would jump into a discussion of bijections. Thanks for pointing out that I gave @Tim too much credit. I thought he was confused about the far more tricky bijection between [0,1] and (0,1).
It's just in case. I think you need to check your math privilege. :yum:
"Can you even imagine? They don't even understand Ito integrals..." (paraphrased discussion excerpt from the staff room)
I just don't understand the insult culture around here. Over the past couple of years I've had to take extended breaks from this forum because someone started piling on personal insults at me over technical matters on which they happened to be flat out wrong. Not because I can't snap back; but because I'm perfectly capable of snapping back, and that's not what I'm here for. I'd suggest to members that whenever they throw an insult in lieu of a fact, perhaps they should consider whether they've got any facts.
For me it can be difficult to tell whether something's technical or not if I'm unfamiliar with it. Knowing what's relevant to what in a technical matter is part of getting to know the technical matter. In the absence of that information, or a sufficiently well explained link between the technical matter and the discussion topic, it can feel extremely patronising. I think there's a hierarchy here.
(1) Basic math literacy to general public: "They can't multiply fractions, can you even imagine!"
(2) Math education to basic math literacy: "They can't do calculus, can you even imagine!"
(3) Undergrad math education to math education: "They can't do the Gram-Schmidt process, can you even imagine!"
(4) Graduate math education to undergrad math education becomes field specific.
(5) Research math to graduate math becomes subfield specific.
Ok then what's wrong with, "Can you please explain yourself," versus, "My drill sergeant says you should suck it up, buttercup." What is the point? I do hang out on the Craigslist forums, where "Fuck you moron" is regarded as just as intellectually appropriate as quoting Aquinas. If this place is devolving to the CL forums I can play too. Hey @tim wood go fuck yourself. Everyone happy now? As if I don't know how to be an Internet jerk. I come to this forum in the hopes that I DON'T have to be an Internet jerk just to hold my own in a conversation.
Unfortunately almost no one is cordial in argument all the time. It pays to be understanding when someone gets uppity. Though it's hard to remain understanding when someone gets uppity.
:rofl: :rofl:
You just keep repeating yourself. Is this North Korea? :joke:
Quoting tim wood
What do you mean well ordered? Kindly explain.
I gave you a worked example.
A bijection between evens and odds.
The set of all even numbers is given by {2k} for k in {0,1,2,...,}
The set of all odd numbers is given by {2k+1} for k in {0,1,2,...}
The even numbers look like {0,2,4,6,...}
The odd numbers look like {1,3,5,7,...}
Define f from the odds to the evens by f(x) = x-1
If x is odd, then x-1 is even. So this works.
f is an injection: f(y) = f(x) => y-1 = x-1 => y=x
f is a surjection: any even number is of the form 2k for some k, then 2k+1 is odd, then f(2k+1)=2k
f is therefore a bijection.
2 sets have the same cardinality if they have a bijection between them. f is a bijection between the evens and the odds. Therefore the evens and the odds have the same cardinality.
(If you want to work through the case for the evens or odds to the naturals; f(k) = 2k is a bijection from the naturals to the evens, f(k) = 2k+1 is a bijection from the naturals to the odds.)
With regards to the order stuff, this is an order preserving function
assume x
That order is also a well order. Take some nonempty subset of the naturals. Assume for reductio that it does not have a least element. Let some element x belong to the set, then this element cannot be 0 (all others are greater). Then this element cannot be 1 (all others are greater and it can't be 0). Then this element cannot be 2 (all others are greater and it can't be 0 or 1)... Then this element cannot be x (all others are greater and it cannot be in {0,1,2,...,x-1}). This holds for arbitrary x by induction. Then arbitrary x isn't in the subset. Then the subset is empty. Contradiction. Therefore the set is well ordered. Call an even (odd) less than another even (odd) when it is less than it in this order on the naturals. That is also a well order through the same argument and symbol substitution.
Edit: this well order does not require the well ordering principle to construct. Therefore there are sets that can be well ordered without the well ordering axiom. This says nothing about whether well orders are first order predicable/definable for arbitrary sets in general, but shows that there are first order predicable well orders (well, once you rewrite the f^n thing into a formula using x+n for some n to save quantifying over a function symbol by instead quantifying over the variable n).
You know, when you repeatedly encounter what looks like a special term in a largely unfamiliar area, the smart thing to do is to look it up, instead of making up your own definition.
To those who wish to engage Tim in a mathematical discussion it may help to know that he is firmly convinced that "all mathematics is counting." This hangup may help to explain the difficulties that he is having with rationals and reals.
There's really only one order like this.
You have a set like the naturals: {0,1,2,3,...} which are presented in their standard order with the successor function S (@SophistiCat "counting") always giving the "next" element in that order. The successor function for the naturals will be called S.
You define a bijection f from the naturals onto some countable set, giving {f(0),f(1), f(2), f(3), ...}. This set also needs a similar successor function T. But you additionally require that f(S(x) ) = T f( x ); the mapping of a successor is the successor of the mapping. (successor functions are how you move right step by step)
If you have that x
It's not much of a definition of well ordered. You're artificially constraining math with a poor definition (if you think it's necessary that we accept your definition).
Fishfry, you appear to be very sensitive. From my experience, if someone points out to you, your misguided way, you take it as an insult. This is philosophy, so you ought to learn to take this as an attack on the ideology which has guided you, rather than an attack on your person.
The problem with your argument is that the described function is not bijective. Instead, you have constructed an injection from the set of even numbers to the set of natural numbers. From this, you are only permitted to conclude that the set of even numbers has at least as many elements as the set of natural numbers. If you combine this with an injection from the set of natural numbers to the set of even numbers, then you can conclude that a bijection exists. Because these sets are countable, this bijection is constructible (and is given by the standard map from the natural numbers to the even numbers).
How about learning actual math? Set theory in this case. It's easy in our time. Just google it. I'll even give a link here: Well-order. Or here: Well ordered set or Well-ordering principle.
Or just watch the video short video:
Showing that you don't quite understand what others are talking about isn't a great argument.
Quoting ssu
Thanks for bearing with my stubbornness but have a look at what I say below:
A = {x, y, z} B = {r, s, t} and C = {l, m}
Cantor got it right if his claim is that quantity/number is simply an abstraction of what is common between sets - specifically the possibility of putting their members in a 1-to-1 correspondence in such a way that each element in one set is paired with one and only one member in the other set with no element in either set left unpaired. This is called bijection I believe.
[Assume the notation that n(A) means the cardinality or number of set A.]
n(A) = n(B) because of the bijection between them. One way for the bijection is as follows:
x ---- r, y ---- s and z ---- t
The argument that the set of natural numbers has the same cardinality as the set of even numbers, i.e. a bijection is possible, is exactly like the above with one exception - we're dealing with infinite sets.
So far so good.
Consider now the set A and set C. There is no bijection between them and the set A has one extra member that doesn't have a counterpart in the set C. We then say n(A) > n(C) i.e. set A is bigger than set c. The attempt to pair the members of sets A and C will look like:
x ---- l, y ---- m, z ---- ???
The set theoretic way of saying n(A) > n(C) is that set C can be put in a 1-to-1 correspondence with a proper subset of set A.
There's no issue with any of what I've said so far. To summarize we agree on the following:
Facts:
[b]1. Two sets have the same cardinality if and only if there's a bijection between them
2. A set G has a cardinality greater than a set H if and only if the there's a bijection between set H and a [i]proper subset of G[/i][/b]
[Definition: a set K is a proper subset of a set L if and only if all members of set K are present in set L and the set L has at least one member which isn't a member of set K].
Since all of you are on Cantor's side it implies that you understand the argument that the cardinality of the set of natural numbers is equal to the cardinality of the set of even numbers. This result follows naturally from fact 1 above.
However, we still have to consider fact 2 by which we can determine inequality of cardinality of sets
The set of natural numbers N = {1, 2, 3, 4,...}
The set of even numbers E = {0, 2, 4, 6,...}
It's clear that N can be separated into two proper subsets viz. the set of even numbers V = {0, 2, 4, 6,...} and the set of odd numbers, D = {1, 3, 5, 7,...}
Notice how set E has a bijection with set V and set V is a proper subset of set N. If so, then in accordance with fact 2 above, n(E) < n(N) i.e. the set of even numbers is less than the set of natural numbers.
This presents a problem doesn't it? One of what I called facts leads to the infinity of natural numbers having the same cardinality as the infinity of even numbers while the other (fact 2) leads us to the conclusion that the set of natural numbers is greater, not equal, than the set of natural numbers.
Comments...
https://en.wikipedia.org/wiki/Galileo%27s_paradox
I share Galileo's rather than Cantor's opinion, but I am in the minority.
100 °C
What is your point exactly?
https://www.compoundchem.com/2016/03/22/boiling-point/
In each finite segment of the naturals, the number of naturals is approximately twice that of the even naturals. Yet each natural can be doubled to give a one-to-one correspondence to the even naturals. This is Galileo's paradox - by one measure, the cardinality of the two sets is different, by another measure its the same.
What Cantor did was to ignore half the paradox and define 'size' in terms purely in terms of one-to-one correspondence. That is expressing an opinion on the nature of size that is incompatible with all finite subsets of the naturals - so yes MATHS IS OPINION - and in my opinion Cantor got it wrong.
Infinity is by definition unmeasurable so it has no size - how can you assign a measure to something that only exists in our minds and our minds says goes on forever?
If you disagree, tell me the size of the naturals. And no alpeh-zero is not the answer - that's a symbol without meaning.
Yes and the rules set theory defines are broken. If something goes on forever, you can't count it - even with an infinity of time it is not possible to measure something that goes on forever. This is what Galileo recognised and what Cantor ignored - and it leads to spurious results, such as the number of naturals is the same as the number of rationals - how can anyone swallow that? For each natural, there is an infinite number of rationals... One-to-one correspondence gives nonsense results.
- Infinity does not exist - see the OP - so this whole conversation is about MARSH GAS
- Even if infinity existed, finity is a subset of infinity and what works for infinity needs to work for finity also. One-to-one correspondence does not work for both so it is flawed
- You are very closed minded. You think that maths has it 100% correct - that is an unbelievably naive assumption to make. At what point in the past was human knowledge 100% correct? At what point in the future will it be 100% correct? It was not, is not and will never be 100% correct. The blind (=you) swallow everything without question. I question things. Now I may be wrong but at least I keep an open mind rather than just dumbly reciting the received 'wisdom'.
OK give me an example of an actually infinite set from nature.
Quoting tim wood
Arithmetic is defined, actual infinity has no sound definition. So its fair game for the open-minded.
You seem to have a childish obsession with point scoring through cryptic remarks.
I believe that an actually infinite set or some substance that extends 'forever' cannot exist in reality. We can only imagine such things.
Transfinite maths and reality are greatly in opposition. ?+1=? tells us that there exists something, that when it is changed, it does not change. This is not the reality I live in. I doubt that it is even possible to define a viable virtual reality that supports the 'features' of transfinite maths - how can something change and not change at the same time?
I believe that for example, non-euclidean geometry maybe telling us something about our reality and it is possible to build logical virtual realities on that basis. But infinite set theory... no.
No.
As we are talking of infinite sets, they aren't 'inequal'. They are indeed 'equal'.
You just take the set of N and multiply every number in N by two and presto! You have the set of even numbers.
It's the same if you would take the set of natural numbers and multiply every number with 1 000 000 and then the new set would be like Sn = ( 0, 1 000000, 2 000000, 3 000000, 4 000000,...) Now you would notice that there's a huge gap between the numbers, 999 999 numbers between every one. But this is simply the strange thing that you get with infinite sets. And basically again this is the Hilbert Hotel, which I remarked on the first page of this thread! (even if the picture seems not to be working)
Quoting TheMadFool
Again no!
An infinite set is a set which is equivalent to a proper subset of itself. You can find the proofs online, similar as what I gave above.
This is false. For example, [math]\mathbb{N}^+[/math] is a proper subset of [math]\mathbb{N}[/math] and the function [math]f(n) = n - 1[/math] is a bijection from [math]\mathbb{N}^+[/math] to [math]\mathbb{N}[/math], but the cardinality of both sets is [math]\aleph_0[/math]. However, it is classically true that [math]A < B[/math] iff there is an injection from [math]A[/math] to [math]B[/math] but no surjection.
I'm not sure what he meant, but a bijection is both an injection and a surjection.
But to your question: a set is infinite if and only if it is equivalent to one of its proper subsets. And this counters your argument. You are making the mistake of thinking about an infinite set as finite.
The proof of this actually refutes your idea: See for example here, Proof 1
You see with a finite set it isn't so: a finite set can not be in one-to-one correspondence with one of its proper subsets.
Thanks for the reply. I understand that another definition for an infinite set is a set that is equivalent (bijection possible) to a proper subset of itself.
I think I get it now. The proper subset of the infinite set itself has to be infinite. The number of elements in a proper subset B of a finite set A is necessarily less than the number of elements in the set A. n(B) < n(A) so long as A and B are finite.
When we then consider infinite sets X and Y such that X is a proper subset of Y then n(X) = n(Y).
It seems that a difference in terms of members, so long as the proper subset of the other, the parent set, is itself infinite, doesn't translate into a numerical difference.
Imagine A = {s, d, f, h} and the proper subset B = {d, f}
The difference between the two A - B = {s, h} = C can be numerically represented as n(C) = 2
However with infinite proper subsets of infinite sets, the difference is zero.
n(set of natural numbers) - n(set of even numbers) = infinity - infinity = zero because both are, well, infinite. In other words the fact that the set of even numbers don't contain odd numbers and that the set of natural numbers is the union of odd and even numbers didn't translate into a numerical difference like it does with finite sets.
The set of even numbers E = {0, 2, 4, 6,...}
Putting all the fancy terms aside, by inspection, in some cases there are even integers in N corresponding to even integers in E. That is a one to one.correspondence only if you ignore the identity of the elements. Eg. there are as many pcs of trash in bag 1 as in bag 2. Then,removing E from both sides, D (odd) = {}..
Yep, you got it! :up:
This is btw. crucial to understand before the next step: comparing the natural numbers to the reals, which gets people really confused and asking a lot of questions. Just look at the thread Is Cantor wrong about more than one infinity.
Basically in infinite set the real question is can you get the numbers well ordered or not. Every non-empty well-ordered set has a least element. In layman terms, it's a question of can you list the numbers in the infinite set in such fashion that you can be sure to write every number. If you can do that, then the infinite set is of the same size as the natural numbers.
Hopefully this explains my comment. If [math]f[/math] is a function from a set [math]A[/math] to a set [math]B[/math], then [math]f[/math] is
Intuitively, an injection maps unique elements of its domain to unique elements of its range; a surjection has every element of its range mapped to by some element of its domain; and a bijection has every element of its range mapped to by a unique element of its domain. We have the following theorems:
You should convince yourself of the following facts. If [math]f : A \rightarrow B[/math] is
These observations justify the following definition of an ordering relation on the cardinal numbers:
From the above discussion, it should be clear that [math]|A| < |B|[/math] iff there is an injection from [math]A[/math] to [math]B[/math] but no bijection. This means that every injection from [math]A[/math] to [math]B[/math] must fail to be surjective (i.e., for every injection there exist elements of [math]B[/math] that the injection misses, although those elements will be different in different cases).
In classical mathematics, we can show that the ordering relation is total. By "classical," I mean mathematics with the axiom of choice. If we assume a constructive framework where the axiom of choice (law of excluded middle, double negation elimination, etc.) fails, the discussion becomes more complicated. IIRC, the "bijection between a set and a proper subset of itself" definition of infinity fails in a constructive setting, you cannot show that the ordering relation is total, an injective function does not imply the existence of a surjection from its image to its domain, and so forth.
I think Enderton's Elements of Set Theory is a good introduction to these topics.
Can you have a look at what I said below. It seems wrong and right.
Quoting TheMadFool
Consider two infinite sets A and B of equal cardinality i.e. n(A) = n(B) = infinity
Shouldn't n(A) - n(B) = 0?
Yet n(set of natural numbers, infinite) - n(set of even numbers, infinite) = n(set of odd numbers, infinite) which is infinite indicating that infinity - infinity = infinity
Quoting quickly
Thanks. I'll just stick to the simple.
You can't do that.
Quoting TheMadFool
The subtraction operation on infinite cardinals is not well defined. For example, let [math]2\mathbb{N}[/math] denote the set of even numbers and [math]2\mathbb{N} + 1[/math] the set of odd numbers. It is easy to see that
However,
Thus, we cannot say that [math]\aleph_0 - \aleph_0 = 1[/math] or [math]\aleph_0 - \aleph_0 = \aleph_0[/math]. There are some technical conditions under which you can define a subtraction operation, but they are beyond the scope of this question.
Really? Consider N={1,2,3,...} and S={1,9} No 1:1 correspondence. You are missing "equivalence"
"A" proper subset? Not "The", I think.
You quoted me out of context. Thanks anyway.
Remember that Infinity is an endless series, not a number. Many would disagree with you if you treated infinity as a number! Some would say that infinity minus infinity is indeterminate. The following are considered to be indeterminate in form:
If you think that taking out the even numbers from the natural numbers you'll the odd numbers left, then you are thinking of a finite set. A finite set can not be in one-to-one correspondence with one of its proper subsets while an infinite one can be. Remember that you are talking about sets that are of INFINITE length. And because they are infinite, then you have the rule that part is as large as the whole: an infinite set is a set which is equivalent to a proper subset of itself.
Beyond finite instances, cardinalities are not numbers. They are equivalence classes.
Thanks. I get it, more or less.
N as E, I can accept that. That however does not justify the statement 'there are as many even integers as integers. The first statement is about a measure of a set, the second is about the identity of the elements, which contradicts statistics. Math concepts should be consistent.
Infinity is not an integer, or any type of number, and definitely not a quantifier.
It's a relation/condition of having no limit or boundary. Measurement requires boundaries. The application of 'rules of measurement for finite objects' cannot be applied to 'infinite objects. 'To measure an immeasurable object' is a contradiction of terms No one has yet explained how to measure a stick with one end (of infinite length). His extended alephs depend on his diagonal argument which is false, since he doesn't explain why the complementary sequence is already there before he constructs the one that isn't there! His work in other areas of math may be satisfactory, but there is a category for his 'supernatural revelation' of transfinite numbers, 'recreational mathematics'. He was a self appointed spokesman, and always anxious about his status in the mathematical community. It helps to research the person and their motivation before and during their theorizing. If you propose an idea from an authority figure, that would surely promote credibility. Then use symbols from the Hebrew alphabet! It sounds more like a public relations promotional strategy than a mathematical conception.
There is no issue of comprehension concerning 'infinity' as a useful abstraction, as in most of science, vs reality. The issue is knowing the difference.
I still haven't seen the average household with 2.3 children.
A quote by Cantor in his favor:
Ewald, W., From Kant to Hilbert, Oxford 1996.
"The old and oft-repeated proposition “Totum est majus sua parte” may be applied without proof only in the case of entities that are based upon whole and part; then and only then is it an undeniable consequence of the concepts “totum” and “pars”. Unfortunately, however, this “axiom” is used innumerably often without any basis and in neglect of the necessary distinction between “reality” and “quantity”, on the one hand, and “number” and “set”, on the other, precisely in the sense in which it is generally false. [An] example may help to explain. Let M be the totality (n) of all finite numbers n, and M¢ the totality (2n) of all even numbers 2n. Here it is undeniably correct that M is richer in its entity, than M¢; M contains not only the even numbers, of which M¢ consists, but also the odd numbers M¢¢ . On the other hand it is just as unconditionally correct that the same cardinal number belongs to both the sets M and M¢. Both of these are certain, and neither stands in the way of the other if one
heeds the distinction between reality and number."
The issue is the present day interpolation/misinterpretation 'there are as many even integers as integers'. The correspondence is a quantitative comparison of two sets. It is not a comparison of two classes of integers.
M could be the set of traditional married people.
W could be the set of married women.
P could be all male-female pairs formed from M
A 1-1 correspondence from P to W, does not mean 'there are as many women as people'.
Rock and roll Brother Tim. Thanks for the kind words. It's all good.
I haven't read the intervening posts so perhaps some of these points have been covered. I did want to toss in my two cents about uncountable bijections, and how the subject of bijections relates to the subject of well-ordering. In short, it doesn't at this level. It's not an unreasonable thing to think, as I came to learn. But bijections are defined between sets; and sets have no inherent order. The sets {a,b,c} and {c,b,a} are the exact same set. Any maps between them, including bijections, pertain only to the elements and not to any order properties the sets might have.
Of course there are ordered sets, along with the order preserving bijections between them. Among these are the well-ordered sets, which lead to the beautiful topic of the ordinal numbers. I could talk about the ordinals all day. But not right now, because they're peripheral to the subject of basic bijections. I hope you'll take this on faith now, and the following examples will bring out this point. In this post I'll limit myself to discussing bijections.
Now I'm going to walk through six bijections between uncountable sets.
(1) The question arises: Can there be a bijection between uncountable sets?
Suppose there were such a thing. What's the most obvious example we could think of? How about the identity map on the reals; that is, the function [math]f : \mathbb R \to \mathbb R[/math] given by [math]f(x) = x[/math].
This function should look familiar to everyone who took analytic geometry in high school. Its graph is a straight line through the origin making an angle of 45 degrees or [math]\frac{\pi}{4}[/math] radians with the positive [math]x[/math]-axis. This is such a familiar mathematical object that we never stop to think that it's a bijection between two uncountable sets.
We now have at least one example of a bijection between uncountable sets. And in passing we've proven a theorem.
Theorem: Every set is cardinally equivalent to itself.
Proof: The set's identity function provides the required bijection.
In other words, cardinal equivalence is a reflexive relation.
(2) Even though the real numbers aren't well ordered, the identity map preserves the usual order on the reals. (The usual order is the one we learned in grade school). So maybe bijections are related to order properties after all??? But no. Consider the bijection [math]f[/math] from the reals to itself given by [math]f(x) = x[/math] everywhere except that [math]f(0) = 1[/math], [math]f(1) = 2[/math], and [math]f(2) = 0[/math].
This bijection does not preserve order, because [math]0 < 2[/math] but [math]f(0) > f(2)[/math]. And you can see that we could easily cook up far more complicated nested cycles and loops and tricks that would make bijections as complicated as we want. So we can see that order properties are a separate consideration from whether or not a function is a bijection.
By the way we have a familiar name for a bijection from a set to itself: a permutation. Permutations of finite sets are more familiar to us, but you can permute infinite sets as well. Every permutation of a set is a bijection from that set to itself; and most of them are completely random, they don't preserve order or any other property.
(3) The function between [math][0,1][/math] and [math][0,2][/math] given by [math]f(x) = 2x[/math], with inverse function [math]f(x) = \frac{x}{2}[/math].
This has already been mentioned earlier in the thread. There are two points of interest.
* This bijection shows that bijections do not necessarily preserve length. And in general, bijections don't necessarily preserve measure, the abstract generalization of length, area, volume, etc. A circle of radius 1 is bijectively equivalent to a circle of radius 2. Bijections don't preserve measure. Good to know.
* Both [math]f(x) = 2x[/math] and its inverse [math]f(x) = \frac{x}{2}[/math] are continuous in the sense of freshman calculus. Very informally, their graphs can be drawn without lifting your pencil from the paper.
In the mathematical discipline of topology, two topological spaces are regarded as equivalent if there is such a bi-continuous bijection between them (meaning the bijection and its inverse are both continuous). The intuitive meaning is that we can stretch or shrink or twist one space into the other without ripping or tearing or poking holes. If you've ever seen one of those illustrations of a donut being turned into a coffee cup, that mathematical trick is done using a continuous bijection.
https://en.wikipedia.org/wiki/File:Mug_and_Torus_morph.gif
(4) The continuous bijection between [math](- \frac{\pi}{2}, \frac{\pi}{2})[/math] and [math]\mathbb R[/math] given by [math]f(x) = \tan x[/math], with inverse [math]\arctan(x)[/math].
The tangent function is usually defined as sine over cosine, but it's more helpful to think of it as the function that inputs an angle, and outputs the slope of the line through the origin making that angle with the positive [math]x[/math]-axis. If you think of a clock with a single hand that goes from 6 counterclockwise to 12, as the angle goes from [math]-\frac{\pi}{2}[/math] to [math]\frac{\pi}{2}[/math], the slope goes from [math]- \infty[/math] to [math]+ \infty[/math]. That is, the tangent function is a bijection from the open interval [math](-\frac{\pi}{2}, \frac{\pi}{2})[/math] to the entire real line [math]\mathbb R[/math]. Its inverse, the arctangent, maps the entire real line to the the open interval [math](-\frac{\pi}{2}, \frac{\pi}{2})[/math].
Since both the tangent and the arctangent are continuous, we see that a bounded open interval is topologically equivalent to the entire real line. Not only do bijections fail to preserve finite lengths; they can't even distinguish between finite and infinite lengths. And topology can't tell the difference either. You can take the tiniest imaginable open interval of the real numbers, and stretch it like taffy till it becomes the entire real line.
(5) "Cantor's surprise." For any positive integer [math]n[/math], the [math]n[/math]-dimensional Euclidean space [math]\mathbb R^n[/math] has the same cardinality as the real numbers.
Cantor originally thought that the real numbers had cardinality [math]\aleph_1[/math]; and the plane [math]\mathbb R^2[/math] had cardinality [math]\aleph_2[/math], and Euclidean 3-space [math]\mathbb R^3[/math] had cardinality [math]\aleph_3[/math], and so forth. [In math, [math]n[/math] dimensional space just means the set of all [math]n[/math]-tuples of real numbers, with pointwise addition and scalar multiplication by reals, just as with the usual x-y plane and x-y-z space. Nothing to do with "time as the fourth dimension" or rolled-up dimensions in string theory or any other physical interpreation. That's sometimes a point of confusion.]
He was surprised to realize that in fact all finite-dimensional Euclidean spaces have the same cardinality. Here's the proof. We'll show that the open unit interval and the open unit square have the same cardinality. That is, we'll show a bijection between the real numbers strictly between 0 and 1, and the set of ordered pairs in the x-y plane each of whose coordinates are strictly between 0 and 1.
Suppose [math](x,y)[/math] is a point in the open unit square with decimal representations [math]x = .x_1 x_2 x_3 ...[/math] and [math]y = . y_1 y_2 y_3 ...[/math] respectively. We map the pair [math](x,y)[/math] to a single real number by interleaving the digits to get [math].x_1 y_1 x_2 y_2 x_3 y_3 ...[/math].
It's clear that you can reverse this process. Given any real number you can de-interleave its digits to get a pair of real numbers. We can extend the result from the unit interval to the entire real line via the tangent/arctangent. Of course this bijection is highly discontinuous, it has no nice properties at all.
You can clearly interleave [math]n[/math]-digits this way, and that's the proof. When Cantor discovered this result he wrote to his friend Dedekind: "I see it but I don't believe it!"
We saw earlier that bijections don't necessarily preserve length or volume. Now we see that bijections don't necessarily preserve dimension. It's good to keep in mind the limitations as well as the utility of bijections.
Quibble: One could note that some real numbers have two distinct decimal representation, such as [math]\frac{1}{2} = .5000... = .4999...[/math], possibly messing up the bijection. But there are only countably many such problematic reals, and we can formalize the principle that "countable sets never make a difference in uncountability arguments." The problem can be fixed.
(6) Can we find a bijection between [math][0,1][/math] and [math][0,1)[/math]? There must be one but it's tricky.
First, why must there be a bijection? We've seen earlier that there's a bijection between [math](0,1)[/math] and the entire real line. And [math][0,1][/math] and [math][0,1)[/math] are both proper subsets of the real line and proper supersets of [math](0,1)[/math]. So both of those cardinalities are squeezed between two equal cardinalities. In other words if [math]|X|[/math] is the cardinality of the set [math]X[/math], then:
[math]|(0,1)| \leq |[0, 1)| \leq |[0,1]| \leq |\mathbb R |[/math], but the first and last cardinalities are equal via the tangent/arctangent. So [math][0,1][/math] and [math][0,1)[/math] must have the same cardinality; after all they only differ by a point.
If you've seen the story of the Hilbert hotel, you know that you can always shift each guest to the next higher room, in effect "losing a guest." And if you were to move each guest to the next lower-numbered room, the hotel would still be full and you'd have an extra guest with no room! This is the basic idea behind adding or getting rid of endpoints in all these kinds of problems.
In this case we pick out a countable subset of [math][0,1][/math], and "Hilbert shift" away that pesky 1 at the right end. Here's the function [math]f : [0,1] \to [0,1)[/math]:
[math]
f(x) = \left\{
\begin{array}{ll}
\frac{x}{2} & \text{if }x\in \{1, \frac{1}{2}, \frac{1}{4}, \frac{1}{8}, \dots\}\\
\\
x & \text{otherwise}\\
\end{array}
\right.
[/math]
[Something funny about the markup, ignore those brl things, the forum software put them in].
Everything gets mapped to itself; except that 1 goes to 1/2, 1/2 goes to 1/4, 1/4 goes to 1/8, and so on. We've "made the 1 disappear" by Hilbert-shifting it to the "next room" as it were, and we have our bijection.
Here's a picture of what happens. 1 goes to 1/2, 1/2 goes to 1/4, and so forth. Every point has somewhere to go, and nothing replaces the point at 1. It disappears like the guest in the first room of the Hilbert hotel.
I have not followed all these posts for a while so I don't know if this is still a point of confusion. I just want to assure you that I never could have possibly said any such thing; for the simple reason that I don't have any idea what that means.
The point that you were hung up on before is that the definition of a bijection says that there exists at least one bijection between two sets. The fact that a million other functions between the sets don't happen to be bijections is irrelevant. It's an existential condition. If it rained for five minutes today and was otherwise sunny, it's still true that "it rained today." I hope someone's been able to clarify that for you.
Quibble-wise this is not true. Originally, a cardinal was the class of all sets with that cardinality. The trouble is that those classes are proper classes and not sets; and we want to define cardinals as sets so that we can use the rules of set theory on them.
I wrote a longer exposition but I'll just shorthand this and provide the links.
Case 1: Assume the axiom of choice. Then given a set [math]X[/math], the axiom of choice says that [math]X[/math] can be well-ordered; that is, there is some ordinal [math]\alpha[/math] such that [math]X[/math] and [math]\alpha[/math] are in bijection. Since the proper class of ordinals is well-ordered, there must therefore be a least such ordinal that's cardinally equivalent to [math]X[/math]. We define that as the cardinal of [math]X[/math].
For example [math]\omega[/math] is the ordinal corresponding to the natural numbers; and by this definition, [math]\aleph_0 = \omega[/math]. And [math]\aleph_1[/math] is defined as the first uncountable ordinal, [math]\omega_1[/math]. (Yes there are uncountable ordinals, even without the axiom of choice. How counterintuitive is that!)
Case 2: Assume the negation of choice. Then there's some set that can't be well-ordered so we can't use the idea as in case 1. Instead (I'm going to just fly through this for sake of brevity and supply the links if anyone's interested) the cardinal of a set is the set of sets bijectively equivalent to the given set whose rank is the same as that set. The idea is that each set has a "born on" date called its rank; and the collection of all ranks forms the Von Neumann hierarchy. Each level is a set, and the union of all the levels is the universe of sets. So given some set, we find the level at which it first appears; and we defined its cardinal as the set of all bijectively equivalent sets at that level.
This isn't supposed to make sense if you haven't seen it. As I noted, I drafted but didn't post a much longer exposition of these matters which would not be of interest to anyone who's not already studying advanced set theory.
The main point is that this is how you define cardinal numbers these days. They're no longer equivalence classes of sets that themselves aren't sets. That was a problem so it got fixed at the expense of needing to do some technical work.
https://en.wikipedia.org/wiki/Ordinal_number
https://en.wikipedia.org/wiki/Cumulative_hierarchy
https://en.wikipedia.org/wiki/Von_Neumann_universe
https://en.wikipedia.org/wiki/Scott%27s_trick
That's what I meant.
Interesting. Thanks. Nice exposition. I only took one course in set theory almost sixty years ago and it was Halmos' Naive book. When he started discussing towers and chains it seemed medieval and it was hard to stay motivated.
I recall seeing that problem about [0,1] and [0,1) on a PhD exam some years ago. I don't think I would have gotten it in the time allowed! :worry:
It's easy to prove beyond a shadow of a doubt that if you associate each integer N with the even integer 2N, that is a bijection between the set of integers and the set of even integers.
You may not like this definition; you may be unwilling to accept this definition (of being the same size). But you can't argue with the fact that there exists a bijection between Z and 2Z (the symbols mathematicians use for the integers and the even integers, respectively).
Someone pointed out that if you could select an integer at random (in some sense; this is very tricky to define!), then only 50% of the time would you select an even integer.
This is a valid point, but it doesn't affect the fact that Z and 2Z have the same cardinality.
What it does point out is the fact that the density of the even integers, in the integers, is only 1/2.
In case this interests you: Suppose X is a subset of the (let's say positive) integers. Let X_n mean the numbers in X that are no larger than the integer n. The fraction X_n / n tells what fraction of the first n positive integers — that is, the set {1, 2, 3, ..., n} — happens to be in the set X.
IF that fraction X_n / n approaches a limit (call it L) as n approaches infinity, THEN the set X is said have density equal to L in the positive integers. (It may be fun to try to find a set X of positive integers for which that fraction X_n / n does not approach a limit as n approaches infinity. There are many such examples.)
I disagree. Imagine (literally imagine) the dense set of odd numbers lined up in normal fashion with the natural numbers. The latter is greater. You can put 3 next to 2 from the odd the the naturals, and do that to infinity. But how does this not distort the infinity of the odd numbers? We already said it has half the density
Sorry for the intrusion. Just checking a link and now can't get rid of it! See my new thread. :sad:
Doubling the density of the odd numbers in order to get a cardinality equal to the naturals.
I think density is the true cardinality, and when you double the density in order to get the cardinality of the odd to equal that of the naturals you've made an invalid move
https://www.encyclopediaofmath.org/index.php/Density_of_a_set
It's not that difficult