Hey /sci/. I'm having a hard time with getting intuition on why Cantor's Diagonal Proof is correct.
Does anyone know why I couldn't use the reasoning of this proof, replacing a Natural Number set analogue in place of the Real Number set and then use Cantor's reasoning (with the difference of numbers residing to the left of the decimal point and the list range being 1 to +ing) to claim that my Natural Number set analogue is uncountably infinite?
I don't want to rehash the Diagonal Proof, but I hope my question makes sense to mathbros.
>>7978273
edit>> "...with list range being 1 to +inf.."
>>7978273
i thought because the real numbers can not be displayed as such a set of sets
isn't that the point of the proof?
>>7978273
In cantours proof, the list of all numbers is supposedly Aleph Null in size, every number has a natural number assigned to it (S1,S2,Sn etc)
Just to make sure, you ask why it won't work for a list that is size Aleph right?
Anyway the proof works because there are Aleph Null digits in the decimal expression. That's the crux of the proof.
You can match a natural number for every S and therefor an index in the decimal expression for every S, because both are Aleph Null in size. Then you can use the neat trick with constructing a new number.
If the list of nums would be Aleph in size, you wouldn't be able to match a digit for every S, and the proof falls apart. It only works when you assume the number of real numbers=the number or digits in the decimal expression.
Hope this helps.
>>7978273
You can't have an infinite number of digits in a natural number. Think about what a base 10 expansion really means.
>>7978345
Are you telling me I cant sum arbitrary number of digits along arbitrary powers of ten?
>>7978337
Well, but given my hypothetical scenario, we start matching natural number set to a natural number set in disuguise. Isn't that how the diagonal proof starts?
Specifically, can't I, after initial matching, pull the card out of the Cantor's playbook and say that because I can diagonally combine incremented digits of the disguised set and produce a number that cannot possible have been in the original disguised set. Thereby proving by contradiction that there isn't a correspondence between my natural number set and my disguised natural number set that I asserted in beginning? Thereby demonstrating that my disguised natural number set is in fact alpeh-one?
>>7978373
Your wording is really confusing so I don't completely understand what you are saying here, but it may be helpful for you to try to run Cantor's argument on the set of binary sequences in which only a finite number of ones appear (this is a countable set: prime factorization gives a surjection from the naturals). The problem you run into is that there's no reason the "flipped" sequence has a finite number of 1's.
No you can't, that is exactly the point of the proof. Think about what exactly would be your S_0 in your pic in your setting.
With the naturals as the index set you can always start at 1 and always go +1 from there and get all the naturals this way. It does not work the same way with the reals. How do you walk through all the reals (or even only [0,1]) for that matter. ok you start at 0 and then go where?
>>7978273
>with the difference of numbers residing to the left of the decimal point and the list range being 1 to +ing
this is a different thing from natural numbers, natural numbers are all number you can write with a finite number of digits, no infinitely long digits allowed.
Infinitely long digits are something else, they are called p-adic numbers, and in fact thay have the same cardinality as the real numbers
https://en.wikipedia.org/wiki/P-adic_number
They are the alternative completion of the rational numbers.
An example would be ...99999, there sint a natural number like this, but in 10-adic this is equal to -1.
>>7978273
I can answer this.
First, the fact and manner in which you imply that it can't be done for an uncountably infinite set seems to imply that you are currently under the impression that there are two "types" of infinity: countable and uncountable. There is in fact a proper class of infinite cardinalities, and in fact [math] | \mathcal{P}(X) | > |X| [/math] for any set [math]X [/math], where [math] \mathcal{P} [/math] is the powerset operation and [math] |A| [/math] denotes the cardinality of [math] A [/math] (i.e. the class of sets equinumerous with [math] A [/math]).
First, if you're not familiar, [math] \omega [/math] is the set-theorist's word for [math] \mathbb{N} [/math].
The real numbers biject with the powerset of [math] \omega [/math] under, essentially, the map which sends, e.g. (0,1,1,0,1,0,1...) to {1,2,4,6,...} (the set of all numbers corresponding to a "1"). (I am skipping a negligible step here). Thus the diagonalization argument really shows that [math] |\mathcal{P} (\omega ) | > |\omega | [/math].
Now, the standard proof of the general case [math] | \mathcal{P}(X) | > |X| [/math] does not use a direct analogue of the diagonalization argument. (It actually uses something that is imo even more elegant.)
One can interpret your question as wondering if it can instead be shown using an analogue of the diagonalization argument.
The answer is yes, and it will show that [math] | \mathcal{P}(\mathbb{R}) | > | \mathbb{R} | [/math].
If you like, I can tell you what exactly this proof would look like.
>>7978470
So what Cantor demonstrated was not that |R| > |N| but that there exists a construction method, i.e. Diagonalization, which produces a set with cardinality equivalent to that of a power set?
I'm just trying to see if |R| > |N| or if Cantor is an epic troll :P
>>7978464
But how is infinite expansion of digits to the left of the decimal point any different in this respect from expansion of digits to the right of decimal point? Both kinds of numbers are constructed by summing digits multiplied by a power of ten raised to an integer exponent of a certain range. - If range goes to -inf, you get infinite expansion to the right of DP, if range goes to +inf, you get infinite expansion to the left of DP. Depending on where the range starts you get N, Z, or R.
>>7978734
Cantor did demonstrate that [math] |\mathbb{R} | > | \mathbb{N} | [/math]. Diagonalization does not "produce" a set of cardinality equivalent to the power set, but rather is a method of showing that the power set is of cardinality greater than the original set.
Clearly [math] |\mathbb{R} | \geq | \mathbb{N} | [/math] since there exists an injection from the latter to the former: namely, map each natural number to itself.
Two sets are of the same cardinality iff there is a bijection between them. So to show the above inequality is strict, it suffice to show there is no bijection [math] f : \mathbb{N} \rightarrow \mathbb{R} [/math].
Suppose toward contradiction that there were such a bijection [math]f[/math].
Then we can list the real numbers
[math] f(0) [/math]
[math] f(1) [/math]
[math] \, \vdots [/math]
If we write out each of the above real numbers in decimal form, with the decimal points aligned, we can do precisely cantor's diagonalization argument, and thus generate a real number not in the image of [math]f[/math].
Thus [math]f[/math] is not surjective, so is not a bijection.
Therefore the inequality [math] |\mathbb{R} | \geq | \mathbb{N} | [/math] is strict, so [math] |\mathbb{R} | > | \mathbb{N} | [/math].
>>7978440
Sum an infinite recursion of "add 1 to d1 - > dn" along 10^-1 through 10^-inf range?
Sorry if my notation is shit.
>>7978774
>thus generate a real number not in the image of f.
I might have the same trouble as you, OP.
0 has exactly one binary representation: .000...
Every rational number other than zero has exactly two binary representations: ...0111... and ...1000...
Every irrational number has one unique binary representation in Cantor's table. I haven't read the full argument front to back in a while, but as far as I remember it, it ignores that I can construct [0,1] inclusively by playing bitch with the dual-mode of non-zero rationals expressed in binary digits. If it says anything at all, it says that the rationals are as countable as the irrationals, and nobody ever interprets it that way.
My advice is to never take anyone's interpretation at face value. If a proof doesn't make sense to you then it probably doesn't actually make sense at all.
>>7978753
Because you can have a decimal with an infinite number of decimal places but you can't have a natural jnumber with an infinite number of digits.
The analogue of S_0 in that pic would not be a natural number - it would be an *infinite* string of 0-9 s.
>>7978847
That's an arbitrary limitation of what natural number can be, no? What is the upper bound for a natural number?
>>7978834
>If a proof doesn't make sense to you then it probably doesn't actually make sense at all.
Yeah, no. A proof long accepted by the mathematical community makes sense, and if you don't understand it, it just means you don't understand it.
Let me answer your question.
Let's work in binary. Note that every real number as at most two binary representations. For example, 1 can be represented as [math] 1. 000 \ldots [/math] or [math] 0.111\ldots [/math].
In fact, it is not hard to show that a real number has two distinct representations iff there is some point in its binary expansion after which every digit 0, or some point its binary expansion after which every digit is 1.
Because each number has at most two representations, then if there is a countable enumeration of all the real numbers, there is a countable enumeration of all possible binary expansions (even ones that may represent the same real number).
This is because, given a list [math] r_0, r_1, r_2, \ldots [/math] of all real numbers, each with some given binary representation, we can consider the list [math] r_0, r_0', r_1, r_1', r_2, r_2', \ldots [/math] where [math] r_i' [/math] is the (unique) possible alternative binary representation of [math] r_i [/math], if it exists, and is [math] r_i [/math] otherwise.
Now do the diagonalization argument on this. The resulting number will not be any number on the list, because for every real in the list, all of its possible representations were on the list.
This is a very small detail that is usually glossed over in the proof because it's obfuscatory, but noteworthy nonetheless. As you can see, the diagonalization argument remains perfectly valid.
>>7978916
>The resulting number will not be any number on the list
I don't know that. It sounds to me like you're saying it because you've been told the argument is valid, not because you actually understand why it's valid. Rather than a small, obfuscatory, noteworthy detail, it sounds to me like you haven't processed the fact that the new diagonal number can both share no digits in common with r as well as be contained in r with a separate representation.
"Just do it again" is the only argument I've ever had in response to my questioning of the diagonal argument. That's not good enough. No matter how many times I do it, I still don't see an argument that r doesn't fully contain [0,1]. "But the new number must be different by the manner in which we construct it!" Just makes me think that the construction is invalid in a way that few people bother recognizing. I don't want to just imagine it over and over again, I want to see where YOU make the jump from it being a constructible number to r being only countable and [0,1] not being countable. Some people I've spoken to seemed convinced that the diagonal argument can be interpreted differently if you change the axiom of infinity and that this change in axioms doesn't lead to any contradictions in the resulting formalism.
I'll also post the rant that follows after
>>7978361
>Are you tell
Not him, but every natural number has a finite number of digits. The result of the sum you propose isn't a natural number.
>>7978953
you first normalize the numbers by their representation.
in binary it's easy, if it has two different representations then one of them has infinite 1s at the end and another one has infinite 0s as the end. normalize them all to have infinite 1s, or just take out the finite numbers altogether since you don't care about them.
>>7979032
I should have added in that one line that we arrive at [math] \neg(f(x)=D_f) [/math] also for x not n D_f (and arguing with X<->Y switched)
>>7979072
Literally none of that explains the jump from the constructed number to "these sets can't be the same infinite size." I understand how to construct the number perfectly fine. What I don't get is how the jump is made and why its apparent implication is called "uncountability."
>>7978953
I understand the argument perfectly well, and explained it with complete coherence, and >>7979072 is an alternate way to address your issue.
In your second paragraph, what is "r"? The list? The list is, by definition, a countable list.
The validity of the construction, and the existence of the real number it produces, follows from the Zermelo-Frankel axioms of set theory.
>>7978953
>>7979104
Two sets are, by definition, of the same "size" or cardinality iff there is a bijection between them. Note that cardinality is transitive -- that is, if A and B have the same cardinality, and B and C have the same cardinality, then A and C have the same cardinality.
A set [math]X[/math] being "countable" means that there is a bijection [math] f: \omega \rightarrow X[/math], where, recall, [math]\omega[/math] is the set of natural numbers. Thus "countability" is one of the possibly "sizes", or cardinalities, of infinite sets.
The whole point of the diagonalization argument is to show that [math] \mathbb{R}[/math] is not countable, and thus by definition uncountable.
The method of proof is to assume that it is countable, i.e. assume that there exists such a bijection, and then derive a contradiction. If an assumption results in a contradiction, then the assumption is false. Therefore, if we derive a contradiction from this assumption, the assumption that [math] \mathbb{R} [/math] is countable is false, so [math] \mathbb{R} [/math] is uncountable.
The diagonalization argument shows this contradiction. It assumes that there exists such a bijection [math]f[/math], which in turn yields a (countable) enumeration, or list, of all real numbers. To get a contradiction, we then construct a real number [math]r[/math] that can't possibly be in that list. But the existence of a such a real contradicts that [math]f[/math] is, by assumption, a bijection (and thus an onto function). Therefore the assumption is false, so [math] \mathbb{R} [/math] is not countable.
>>7979146
>The list is, by definition, a countable list.
If that's the case then [0,1] is countable. Contradicting the definition of countability doesn't tell me that [0,1] is uncountable, it doesn't tell me that [0,1] is a superset of r, and it sure doesn't tell me that the notion of countability is self-consisent.
>follows from the Zermelo-Frankel axioms of set theory
That doesn't really help if those axioms only arose when the diagonal argument was accepted prior to their formalization.
>to show that R is not countable
Yes, I understand the conclusion. I understand bijection and countability. Personally I really like the idea of uncountable infinities, but I don't see a logical jump from contradicting countability to the pre-supposed conclusion that R is uncountable. I can *easily* take the conclusion at face value and I have no problems using it for later formalism. My problem is exactly and precisely that I don't see a logical reason to make the jump to the conclusion.
>we then construct a real number r that can't possibly be in that list
Except it can, because the method of constructing that number explicitly allows for two numbers to have ones and zeros at the same binary index while also representing the same value.
The assumption that differing by one binary bit is enough to prove one number distinct from another number is false. Countability isn't the assumption that gets contradicted. Unique binary representations in R is the contradiction that turns up invalid no matter how many times I look at it.
>>7979213
You still haven't told me what "r" is. Please do this first thing if you respond.
I'll enumerate your paragraphs (a) through (d)
a) The whole assumption is that [0,1] is countable. Yes, we assume it is countable and be put in a list, and then derive a contradiction. Therefore the interval [0,1] is not countable.
b) The axioms of ZF are all self-evident, and were accepted long before they were formalized. Everything done in the argument is something one can obviously do with sets.
c) If it's infinite and isn't countable, it's uncountable. That's all there is to it.
d & e) I addressed this in >>7978916 in which I present a slight modification of Cantor's argument in which every possible binary representation of every number on the list is on the list. Thus the binary represented constructed cannot be that of any real number on the list, so represents a real number not on the list.
To expound, if, for [math] every [/math] binary representation of [math] every [/math] real number represented in the list, some digit differs from some digit of the constructed binary representation, then that constructed binary representation represents a real not on the list, since it can't be any representation of any real number in the list. As cited, >>7978916 presents how to expand any countable list of reals into a list with this property, on which we then do the diagonalization argument. The resulting binary sequence represents a real not in the expanded list, and thus not in the original list.
>>7979246
>the binary represented constructed cannot be that of any real number on the list
Except that yes, it can, because the entire notion of, "differs by one bit, therefore not identical," is a wrong assumption. It doesn't matter how many [math]r_i[/math] you use because no single bit string has been shown to hold a different value from *every* other bit string, let alone proving that every such [math]r_i[/math] will necessarily be distinct from every other such [math]r_i[/math].
>if, for every binary representation of every real number represented in the list, some digit differs from some digit of the constructed binary representation
Yes...
>then that constructed binary representation represents a real not on the list
No, because:
>it can't be any representation of any real number in the list
It CAN be BECAUSE single bit differentiation is insufficient criteria to call two binary string distinct in terms of the real number they represent. It does not matter that the bits differ because differing has no uniform trait that necessarily exhibits distinctness. Bit differences only *sometimes* say that two binary strings represent different numbers.
The trait you use to measure distinctness isn't a trait that can necessarily denote distinctness. The constructed bit string doesn't *necessarily* diverge from every such [math]r_i[/math] the way you say it should.
>>7979281
>It CAN be BECAUSE single bit differentiation is insufficient criteria to call two binary string distinct in terms of the real number they represent.
Why don't you provide a counterexample then, or at least prove a counterexample exists?
The only cases where one number has two different representations in the same base are the cases of replacing a trailing 0 with an infinite string of nines (or n-1s, for some other base).
It's plainly obvious that doesn't apply here.
If you don't like the diagonal argument, try another proof. For example, the Lebesgue measure of any countable set is 0, but the measure of [0,1] is 1.
>>7979281
Yes, you are right that differing by a bit does not mean the two bit-strings represent different numbers.
But read that one sentence you quoted again:
>If, for every binary representation of every real number represented in the list, some digit differs from some digit of the constructed binary representation, then that constructed binary representation represents a real not on the list.
I emphasized both instances of the word "every" in my original statement for a reason.
The constructed real will differ in [math]some[/math] digit from [math]every[/math] representation of [math]every[/math] real on the list.
Therefore it cannot represent any real on the list!
[math]Every[/math] representation of [math]every[/math] real in the list is already in the list, and the constructed real thus differs from [math]every[/math] representation of [math]every[/math] real in the list.
Therefore it cannot represent any real in the list.
It is impossible to state this more clearly.
>>7979288
>It's plainly obvious that doesn't apply here.
It does. Cantor's diagonalization shows absolutely no numerical distinctness between bit strings in R. It merely supposes that differing by a single bit is sufficient to show that two number corresponds to different values in R, but it isn't. There is literally no logic in his argument that necessarily shows any two numbers to be at all distinct. Rather than "suppose equivalent countability" I see an argument that supposes bit pattern correspondence.
>>7979296
That's not gonna work for me either. Even if Cantor is right about their cardinality being separate, the diagonal construction DOESN'T show it. As I said, I can accept distinctness of cardinality, but I don't see it *IN* Cantor's argument.
>>7979298
>Therefore it cannot represent any real on the list!
Differing by representation means NOTHING to me.
It doesn't matter if it differs by a thousand bits; it'd still be the same number if the bits that differ are ...0111... and ...1000... They literally differ *in representation* by an infinite number of bits but still have THE SAME NUMERIC VALUE.
In other words... For every real in the list, you either have a fixed bit that can't change because the given bit is fixed to a non-repeating sequence in the real or you have a non-fixed bit that can take either value because the real number enumerated has TWO distinct representations. Constructing a number via diagonalization given an infinite number of bit patterns is INCOHERENT. The constructed number literally doesn't exist UNTIL you create the list from (non-unique) bit patterns or "collapse" the "wave function" of every "particle" representation of divergent values in R.
Generating via bit strings creates non-unique lists, and generating via R creates infinitely many decisions about the bits of the "constructed" diagonal "number."
Either your construction does exist and does NOT denote value-wise distinctness or it *doesn't exist*.
(In any formal sense.)
>>7979319
>The constructed number literally doesn't exist UNTIL you create the list from (non-unique) bit patterns or "collapse" the "wave function" of every "particle" representation of divergent values in R.
we've reached the point where you're 100% either trolling or 13
>>7979331
Pick one:
1. The list is generated from actual R values.
2. The list is generated from bit patterns.
Until you pick one I literally have to assume you're flip-flopping between two mathematically distinct notions of constructing a diagonal number.
>>7979319
Perhaps this is where you mis-understand the proof:
The list is not a list of literal reals, but a list of their binary representations.
It is all about the representations!
So suppose we can list all the reals. Then as given in >>7978916 we can list every binary representation of every real. We then construct a representation (bit-string) that can't be that of any real represented by any bit-string in the list.
At this point, we've broken it down so thoroughly that the details I'm trying to explain are like trying to explain like 1+1 = 2.
>>7979331
Also this, which is absurd, but which I can actually understand given that he's thinking of it as a list of bona-fide reals, rather than as of representations. He's imagining that for each real, you have to "choose" a representation, which "collapses" the real to something we can write down as a decimal expansion.
In reality, we don't have to choose representations. Because every real has at most two representations, if we can list every real, we can list every single possible representation, and then we diagonalize to find a bit-string (representation) not equal to any in our list of representations, and thus not equal to any real in our original list (since every representation of every real in our original list is in our list of representations).
>>7979344
Glad someone else interpreted his misunderstanding the same way. It's a bizarre misunderstanding, but whatever. Hopefully this clears it up.
>>7979331
>you're 100% either trolling or 13
or possibly both
>>7979348
>a list of their binary representations
So #2 from >>7979344 then. Thank you.
>suppose we can list all the reals
Seeming intuitively possible, yes.
>every binary representation of every real
That will necessarily include both representations of every ...1000... terminating number, yes.
>We then construct a representation
Excellent, we can do that, yes.
>that
Eh...
>can't
Not sure about that.
>be
Law of identity, yes.
>that of any real represented by any bit-string in the list
No, wrong. It could represent literally any real that already has a bit-string representation elsewhere in the list. The value of any given bit in the string we construct is dependent on the ordering of the list. By rearranging the list we can adjust which bit string the constructed string numerically collides with. By being very clever with the ordering we can make the constructed number correspond to a unique irrational number that has no bit string at a different point in the list, but to do so we need to duplicate at least one bit string in the list. Prove me wrong if we can do it without duplicating at least one bit string, because that's what I need to hear to accept that the contradiction relates to the nature of countability rather than the nature of dual representation of terminating reals. I can easily see how generating random bits by negating other random bits would SEEM to create distinctness in binary representations of R values, but "lolrandom" is NOT the same as a PROOF. You need to show me that you can actually construct the number in a way that doesn't violate the uniqueness of every other bit string in the list. (Or else give up because we're not seeing the same constructing logic. If it's not provable to me then it's not provable to me.)
I HOPE you can see how I'm seeing this problem, but if you don't then feel free to stop. I WANT to understand this proof iff it is a logically consistent argument but I don't see it yet. I see only intuitive approximations so far.
>>7979381
This is absolutely insane levels of not understanding elementary things.
>>7979381
>The value of any given bit in the string we construct is dependent on the ordering of the list.
No. The real corresponding to a bit-string does not depend on its position in the list. The list need not list the reals in order, and even if it did, it wouldn't matter.
Now read the sentence
>We then construct a representation (bit-string) that can't be that of any real represented by any bit-string in the list.
and try again.
>>7979348
>the details I'm trying to explain are like trying to explain like 1+1 = 2
Axiomatic reasoning I understand. You can tell me that we can construct a number and I can accept it for the sake of argument. That's easy, that's fine. It's when you say that among multiple disparate assumptions, that the one made first at the lexical beginning of the argument is the one that must be wrong that I stop accepting your reasoning. I can't see a way to construct the number you suppose we can construct, or else I can't see any way to show that the constructed number is distinct from all the other numbers represented in the list, or I've run out of ways to explain that using an axiom to support itself is a form of circular reasoning that is entirely invalid for constructing a proof.
>rather than as of representations
I have been thinking of it as representations. What happens with option #2 from >>7979344 is that we either can't construct a number or that number has a collision with a number already in the list. It's not automatically a different number even if an infinite number of bits are different. (...011... and ...100...)
>for each real, you have to "choose" a representation
No, I just wanted to put that out there in case I was misreading your argument. I've been assuming bit strings from the start.
>and thus not equal to any real in our original list
Except that does *not* follow. 1000... and 0111... differ by literally every single bit in their infinite bit strings while still being *the same exact value* in terms of their correspond binary-represented real. Bitwise difference DOES NOT GENERALIZE TO a form of logic that I can recognize as PROVING the real distinctness of any two bit strings. They are only distinct /under certain conditions/ and in my mind we need to discuss those conditions in depth before we can mouth off about any two bit strings not representing the same real number.
>>7979344
THIS POST WAS MINE.
I'm the guy who's been walking this guy through this in excruciating detail for most of the thread.
I do not think he is trolling.
However, I've come to the conclusion that there is something really, really wrong with his brain that scrambles logical thought.
Yeah.
There is something actually, literally wrong with his brain.
He will never understand. His brain scrambles logic too much in some way he can't help.
>>7979390
>in the string we construct
As in, the one we suppose is somehow outside the list. Its bits are *DEFINED* by a subset of the ordering of the list from which it is supposed to be generated.
>>7979407
See >>7979406
>1000... and 0111... differ by literally every single bit in their infinite bit strings while still being *the same exact value* in terms of their correspond binary-represented real.
Literally ever bit is different and they still have the same exact value as per the real number they represent: 1/2. Bitwise distinctness of binary representations does not generalize to numerical distinctness as a real number.
>>7979411
0.0111... = 0.1000... = 0.1 = 1/2
Literally different at every bit, literally equivalent as numerical values.
>>7979420
If you're baiting, may you truly burn in Hell.
Otherwise,
.01111...
.10000...
If you're different at some bit from the first string, and different at some bit from the other string, you're different from both strings.
If you're different from both strings, you're not 1/2.
So whatever the constructed real is, it won't be 1/2.
Same with any other real, even if it has two representations, since both representations are on the list and the constructed string is different from both of them.
>>7979439
This has nothing to do with the reals. The logic of "well the bits are different so the real number being represented must be different" FAILS in the case of 1/2. Between the two bit strings that 1/2 can be encoded in you'll find that literally ever bit is the opposite of the corresponding bit in the other string and—despite that literally ever bit is distinct between the two strings—they have the same exact value. Bitwise distinctness does not generalize to numerical distinctness, period. Long before Cantor ever came up with diagonalization, bitwise distinctness did not generalize to numerical distinctness. Before the axioms of infinite and ZFC and everything you know and love about modern mathematics came about, bitwise distinctness did NOT generalize to numerical distinctness.
It might seem intuitively logical, but .0111... and .1 are bitwise distinct by literally ever bit bit still they have the same numeric value, 1/2. Therefore, if we sample 1/2's representation for bitwise distinctness and say that 0111... != 1000... because it has at least one bit of difference, we'd be wrong and the generalization would be false.
This isn't about Cantor or diagonalization anymore. Bitwise distinctness does not generalize to numeric distinctness. Period.
>>7979501
>bitwise distinct by literally ever bit but still they have the same numeric value
Fixed.
>>7979146
>>The method of proof is to assume that it is countable, i.e. assume that there exists such a bijection, and then derive a contradiction.
do you have proof which is more constructive ?
OP here. Thanks for trying to explain this thing to me but eventually all explanations boiled down to restatement of Cantor's proof and its ever problematic final step of constructing the diagonal number.
Basically, my issue is that this step should produce a number that should already be eventually produced by the infinite construction of the original list of real numbers. I just want to understand how the diagonal construction can contradict the countability assumption since any number constructed by the diagonal procedure can be claimed to have been produced by the procedure used to construct the original list?
At this point, the best hook I got on this problem is that introduction of the diagonal constructor creates a logical paradox where one claims that since you can talk about inf digits then you can talk about "inf_digits + 1_digit" and somehow, just by being able to state the latter, we apparently demonstrate that we can create numbers with more digits than infinite digits produced by the original inf_digits constructor.
I know some mathbros mentioned other proofs of |R| > |N|. Anyone cares to explain those?
>>7979501
Unless you choose a unique decimal for each real i.e exclude 0.999... etc.
>>7980174
>Basically, my issue is that this step should produce a number that should already be eventually produced by the infinite construction of the original list of real numbers.
Oh! I get the problem now.
OP, if I understand correctly, is your problem "At every individual step n, the partially constructed number Cn is a number I will eventually find on the list, so where's the contradiction?"
Question to all:
Does this have anything to do with the Lambdoma harmonic matrix?
the only difference seems to me like Cantor used integers and Lambdoma uses reciprocals.
or am I missing something here?
>>7980301
And also
>"Since I could also list the naturals as strings of digits and start listing digits diagonally, changing each one (with the naturals properly ordered to avoid collisions) and also end up with a number I haven't listed at every step, how does the diagonal argument distinguish between these cases? Why not simply assume this is what's going on, instead of postulating "uncountability"?
Have I understood your main problems correctly?
>>7980306
Basically, the answer is that only the infinite string generated by diagonalizing over all the numbers matters.
For the naturals, the "number" you have produced is an infinitely long string of digits ... which is just infinity. You can't meaningfully write down an infinite value as a digit string, at least not in the naturals. That string isn't on your list, but it's not supposed to be.
For the reals, though, every infinite string of digits is a valid real number, so if you've listed all the reals, that string would have to be on your list somewhere, which it isn't.
(But real representations aren't unique! How do you know your constructed real number isn't on the list somewhere? Well, it's provable that any real number has exactly and only two digit string representations, so make your list twice as long to make sure it has both representations of each number. Now you know your number isn't represented on the table in different form.)
If you don't like binary expansions just use decimal expansions and put only 0 and 1s in the constructed number to avoid any ambiguity.
>>7979881
The proof is constructive though. It provides an explicit algorithm for constructing a real number that is computably different from every number in the range set.
>>7979501
by the diagonalization proof we show that atleast one binary representation of a real number doesnt appear in the aupposedly complete list. There might be another representation of the same "numeric value" in the list though.
>>7978868
Not really. Given a natural number we can always find the number of digits in it, which is finite.
>>7980306
Yes. That's it.
Basically, it seems that Diagonalization is trivial in the eay that "n+2" is a trivial spin on "n+1" and it seems like Cantor is just saying "Nu-Uh! For any n+2, n+4 always yields number two higher and therefore produces a set of larger cardinality". Even though n+2 would eventually produce any number that n+4 can in principle.
It seems like a twisted game theory argument saying that constructor 1 will never be able to catch up to constructor 2 because constructor 2 is always x steps ahead.
>>7980301
Yep.
>>7980762
The construction is irrelevant.
What it's saying is that there is no bijection [math]f: \mathbb{N} \rightarrow \mathbb{R} [/math], and that's all it's saying.
>>7980847
Yes. No bijection, no 1:1 correspondence. I get it. It's the argument that I don't get.
>>7980762
>Basically, it seems that Diagonalization is trivial in the eay that "n+2" is a trivial spin on "n+1" and it seems like Cantor is just saying "Nu-Uh! For any n+2, n+4 always yields number two higher and therefore produces a set of larger cardinality".
No, they would have the same cardinality. This is not analogous at all. The point is not that some other set produces numbers not in the set, the point is that you can't list the entire set. Obviously you can list every number iterated by n+1 or n+4. Cantor's diagonal argument on the other hand actually produces a number not in the list. If the reals are countable then this could not occur.
>>7980925
But that's the core of my problem... The diagonal number is just another real number made of digits and the only way to claim that it doesn't exist in the original list is to arbitrarily limit the expansion of the list at a certain position, say n=100, and then create a number through the diagonal procedure and place it in the next row, 101. Thereafter triumphantly declaring that diagonal procedure is 1 step ahead because the original constructor ran out of moves by the 100th row. Couldn't Cantor just as easily have argued with "construct a number past the last row with the last digit of previous number incremented by one" - "Checkmate Atheists"?
>>7980969
>But that's the core of my problem... The diagonal number is just another real number made of digits and the only way to claim that it doesn't exist in the original list is to arbitrarily limit the expansion of the list at a certain position, say n=100
No. The list is infinite. The diagonal number not contained in the list is also infinite. Therefore the reals cannot be listed. It's that simple.
>>7980963
So Reals get out of jail because infinite expansion of decimal digits is axiomatically different than expansion of natural numbers?
>>7980979
Not axiomatically. The naturals can be placed in an infinite list. The reals cannot. That is what uncountable means.
>>7980978
OK. So, if I understand correctly. Construction of reals is infinite in two dimensions (for lack of better term) and that is why they are in a sense super-infinite when compared to natural numbers?
>>7980986
I visualize construction of a list of reals by infinite listing of rationals. Is that the issue?
>>7981005
The rationals can be listed. For example if you draw a grid where the x axis is the numerator and the y axis is the denominator, then every rational will appear on this grid. You can then list them by drawing a spiral starting at the origin and running through every rational.
>>7981005
Yes. The rationals are, in fact, completely countable.
>>7981012
I think I'm starting to get a handle on this.
I'll need to let it steam in my head for a bit. Thanks Anon.
Here's an extremely simple proof that there are different cardinalities, and thus uncountable cardinalities. People who dislike the diagonalization may prefer this. I find it much more elegant.
Let [math]\mathcal{P}(X) [/math] denote the powerset of [math]X [/math].
[math] \texttt{Theorem} [/math]: For any set [math]X[/math], [math]|\mathcal{P}(X) | > | X | [/math].
Proof: Clearly [math] |\mathcal{P}(X) | \geq | X | [/math]. It suffices to show strictness. Toward this end, assume toward contradiction that there is a bijection [math] f: X \rightarrow \mathcal{P}(X) [/math].
Let [math] Y = \{ x \in X : x \notin f(x) \} [/math]
Let [math] y = f^{-1} (Y) [/math].
Is [math] y \in Y [/math]? By the definition of [math] Y [/math], if [math] y \in Y [/math] then since [math] Y = f(y) [/math] we have [math] y \in f(y) [/math] and thus [math] y \notin Y [/math]. Similarly, if [math] y \notin Y [/math] then [math] y \in Y [/math].
Thus we have a contradiction. So there is no bijection [math] f: X \rightarrow \mathcal{P}(X) [/math], so for any set [math]X[/math], [math]|\mathcal{P}(X) | > | X | [/math]. [math] \, \, \, \, \, \, \, \, \, \Box [/math]
[math]\texttt{Corollary} [/math]: There is an uncountable set. In fact, there are infinitely many cardinalities. (And in fact, [math] | \mathbb{R} | = | \mathcal{P} ( \mathbb{N} ) | [/math], and thus the reals are uncountable, but this is not necessary for the above pure demonstration of uncountable infinities.)
boop
>>7980298
>Unless you
No. No "unless." Bitwise distinctness does not generalize to numerical distinctness. Period. Any logic built on the assumption that bitwise distinctness *necessarily* indicates numerical distinctness is flat out wrong. Discard any intuition you had on the matter; it simply doesn't generalize.
>>7980375
DOES NOT GENERALIZE. While SOME numbers thus constructs MIGHT be unique not ALL of them NECESSARILY will be. Differing by one digit, no matter which digit it is, will NOT generalize. 0.0999... IS 0.1000...
>>7980472
>an explicit algorithm
No it doesn't. The "constructed" number might or might not exist. There is no step-by-step algorithm that completes in finite time that can be used to analyze a given list. I don't know how the halting problems deals with infinitely long inputs either.
It gives an intuitively imaginable pseudoalgorithm that rests on the idea of bitwise distinctness which does not generalize to numerical distinctness. I'm pretty sure I can write an algorithm that would take such a list and construct a number [math]S_w[/math] that differed from [math]S_0[/math] by one digit of any arbitrary swapping rule and was still identical to either [math]S_0[/math] or some [math]S_i[/math]. I just haven't had the patience to write it yet because every time I go to confront someone about this shit they dismiss me before explaining the magic jump in "logic" that lets them generalize something that I see no logical way to generalize. I'm seriously on the verge of constructing a triangular argument to refute this shit once and for all. (Something about the relationship of number values of three digit strings that each differ by one digit from the other two.)
>>7980554
>There might be another representation of the same "numeric value" in the list though.
Then [0,1] is NECESSARILY a subset of the countable list of binary strings. NECESSARILY.
>>7980762
>It seems like a twisted game theory argument saying that constructor 1 will never be able to catch up to constructor 2 because constructor 2 is always x steps ahead.
Yes! Exactly! Thank FUCK someone else sees it.
It is literally a formal-sounding "nu-uh" that rests on intuitive notions that DO NOT GENERALIZE.
>>7980894
The argument is bunk. It's circular bullshit and you can see past it just like I can. Never take anyone at their conclusion if they can't construct their conclusion without constructing their conclusion.
>>7980978
>It's that simple.
Bullshit fucking circular reasoning. OP is right.
>>7980988
MAYBE! BUT until you understand *WHY* it's like that, you don't actually have a formal non-intuitive PROOF that |N| < |R|. Don't just accept it at face value as if your intuition is sufficient for the study of infinite cardinalities.
>>7981104
>Let y=f^−1(Y).
I don't get this step. How is passing a set to an inverse function possible? What does it mean?
>>7982418
He implicitly uses the injectiveness of the bijective f.
Anyway, his set theoretic proof line of reasoning has been given already in this thread before.
>>7981104
yeah, this demonstration shows how set theory in classical logic is despicable
>>7980305
anyone?
>>7982542
No. Cantor's is showing that the set of real rational numbers, ones that can be written p/q where p and q are integers is countable infinite.
That is, he sets up this matrix with all the components and shows that you can traverse it in a way that counts every different rational number.
>>7982409
>Bitwise distinctness does not generalize to numerical distinctness.
This is totally irrelevant, though, because it is provable that any real number has exactly and only two bit-string representations.
Just make your hypothetical list twice as long, so you list both representations of all real numbers.
>>7983197
>any real number
Correction, any nonzero real number.
>>7982542
The sets of reals is uncountable while the set of rationals is countable. "There are more real numbers than rational numbers".
>>7982462
Did you misspell "elegant", or what?
I just can't believe that some people think classical logic is wrong.
Mathematical theorems are those that follow from classical logic. Reject classical logic, and you reject mathematical truth.
You know how 4chan feels about frogposters? That's how I feel about intuitionists.
>>7983199
>>7983197
No. [math]\pi[/math] has precisely one representation in any base.
What is true is in any integer base [math]b[/math], a real [math]r[/math] has at most two representations, and has precisely two representations iff [math]r=\frac{n}{b^k} [/math] for some integers [math]n[/math] and [math]k[/math].
>>7983308
I like classical logic too, for what it's worth, but being all to serious about truth is very silly, imho.
Okay, if you want to use your material implication for everything, then such statements are part of your framework, but demanding if-then IS this classical notion and only this, that's just fetishism.
Logic, I'd say, is a languages in the first place.
Intutionistic logic surely has its domains, e.g. reasoning about computation (it's actually equivalent for some systems).
I'm also a fan of intuitionstic logic, but I also want to point out that "not classical logic" isn't intuitionstic logic.
E.g. modal or relevant logic.
https://en.wikipedia.org/wiki/Relevance_logic
Do dump more shit, I played around and came up with a neat modal logic example akin to
https://en.wikipedia.org/wiki/Temporal_logic
I might post it on request (adding the math tags is work)
E.g. why deny someone to use a mode of reasoning that doesn't let him express stuff like
>If I have two eyes, then Moscow is in Russia
Or e.g. the classical nonempty logics prove
[math] \exists x. \, (P(x) \implies \forall y. \, P(y))[/math]
(As either P holds for all x, in which case you can exemplify one such term and get "true implies true"=true. Or it doesn't hold for all x, in which case "false implies false"=true)
There are animals which are dogs in the world, so classical logic proofs shitty sentences like
>There is an animal, so that if it's a bird, every animal is a bird
Or this sematics problem: If you go to your mom and say I hate women or I hate people, she'll not be more shocked about the later than the former. If you're a machine like thinking sperg only being able to reason via the predicate formalism, you'd be confused because if you hate people, you also hate women and the second message includes the first one.
As a related funfact when it comes to logic without more setty axioms, this is interesting
https://en.wikipedia.org/wiki/Nonfirstorderizability
(and a funny word)
>>7982415
>Bullshit fucking circular reasoning. OP is right.
Where exactly is the circular reasoning? You are arguing as if the diagonilization argument is a finite list. It's not. If you can't have an infinite list that contains all reals, the reals aren't countable. The diagonilization argument proves any list will not contain all reals. Therefore the reals are not countable.
>>7983348
I just don't see how you find "set theory in classical logic despicable".
I may agree that excluded middle may not apply to non-mathematical propositions. But I see mathematical objects as precisely those that are sufficiently concrete and "full" as to have classical logic apply.
Classical logic must be valid on mathematical objects, because mathematical objects are those on which classical logic is valid.
>>7983411
>I just don't see how you find "set theory in classical logic despicable".
Oh, that wasn't me.
>>7983411
>But I see mathematical objects as precisely those that are sufficiently concrete and "full" as to have classical logic apply.
But then that's your philosophical stance and not much more.
Consider this: Without assuming the continuum hypothesis, ZFC cannot prove that if a set Y is bigger than another set X (i.e. |X|<|Y|), then it also has more subsets (i.e. |P(X)|<|P(Y)|). That's something most people would want of sets I guess.
In fact, there are models of ZFC where the continuum hypothesis fails and there's a set Y with |N|<|Y|<|R| and |P(Y)|=|R|.
I've commented on the sense in which in which some logic and some axioms really often doesn't capture your stuff so well in >>7979036.
I'd say logic doesn't apply to them in the sense that logic applies to describing relations of more a priori phyiscal object, because those thing wouldn't be without your language. What are the "mathematical objects" (apart from the constructive ones)? They are created as possibility in the act of writing down the logic and the theory - yes, then logic "applies" to them by construction.
-----
Now here that modal logic example. First some notation
Modal operators:
[math] \Box_R [/math] ... necessarily
[math] \Diamond_R = \neg \Box_R \neg [/math] ... possibly
Semantics (you may ignore this):
[math] \langle W , R \rangle [/math] ... "Kripke frame"
where
[math] W [/math] ... (type of) worlds
[math] R \subseteq W\times W [/math] ... binary accessibility relation
[math] w R v [/math] ... "[math] v [/math] is accessible from [math]w[/math]"
[math] P(w) [/math] ... predicate
[math] (\Box_R P)(w) [/math] ... [math] \forall v.\, w R v \implies P(v) [/math]
[math](\Diamond_R P)(w)[math] ... [math] \exists v.\, w R v \land P(v) [/math]
The modal operators are similar to [math] \forall [/math] and [math] \exists [/math], except instead of maping predicates [math] P(w) [/math] to propositions (as in [math] \forall w. \,P(w) [/math]), they map predicates to predicates (as in [math] ( \Box P)(w) [/math]).
Okay, the example
[math] W [/math] := legal board configurations in chess
[math] w R v [/math] := there is a game development from w to v
call [math]w_0[/math] the initial position for which [math] \forall v. \, w_0 R v [/math]
We use modal operators on predicates of the -current- state to form predicates of what might happen
[math] \Box [/math] = will hold till the end of the game
[math] \Diamond [/math] = might occur till the end of the game
(this makes for sort of temporal logic which is trivial in that it has no time steps)
[math] P(w) [/math] = in the //current// state w, you have a pawn on the board
[math] K(w) [/math] = in the //current// state w, you have a king on the board
[math] B(w) [/math] = in the //current// state w, you have a dark-squared bishop
we can formulate:
[math] B(w_0) [/math] ... at the start, you have a dark-squared bishop
[math] \forall v. \,( \Box K)(v) [/math] ... in all possible states, you do have a king on the board
[math] \neg( \Box P)(w_0) [/math] ... it's not a given that some of your pawns will stay on the board till the end
[math] ( \Diamond \neg P)(w_0) [/math] ... equivalently, it might happen that at one point you have no pawns on the board
[math] \forall v. \, ( \neg P(v) \land \neg B(v) ) \implies ( \Box \neg B)(v) [/math] ... if you have no pawn on the board and no dark-squared bishop, then, till the end of the game, you'll have no dark-squared bishop
(cont.)
From the last line, using classical predicate logic on the body, we can make the following derivation:
[math]( \neg P(v) \land \neg B(v)) \implies ( \Box \neg B)(v) [/math]
- postulate
[math] \neg P(v) \implies \neg B(v) \implies ( \Box \neg B)(v)[/math]
- currying
[math] \neg( \neg B(v) \implies ( \Box \neg B)(v)) \implies \neg \neg P(v) [/math]
- A implies B [math] \vdash [/math] not B implies not A
[math] \neg( \neg B(v) \implies ( \Box \neg B)(v)) \implies P(v) [/math]
- [math] \neg \neg[math] A [math] \vdash [/math] A
[math] \neg( \neg \neg B(v) \lor ( \Box \neg B)(v)) \implies P(v) [/math]
- A implies B [math] \vdash [/math] not A or B
[math] \neg(B(v) \lor ( \Box \neg B)(v)) \implies P(v) [/math]
- [math] \neg \neg[/math] A [math] \vdash [/math] A
[math]( \neg B(v) \land \neg( \Box \neg B)(v)) \implies P(v) [/math]
- neither A nor B [math] \vdash [/math] not A and not B
[math]( \neg B(v) \land ( \Diamond B)(v)) \implies P(v) [/math]
- [math] \neg \Box \neg A \vdash \Diamond A [/math]
So we showed:
If you have no dark-squared bishop but it's still possible that it might happen, then you have a pawn on the board.
Sorry for derailing this a bit..
>>7983474
Btw. of course the axioms
∀v.(¬P(v)∧¬B(v))⟹(◻¬B)(v)
>if you have no pawn on the board and no dark-squared bishop, then, till the end of the game, you'll have no dark-squared bishop
refers to the fact that having a pawn is the only was to get a lost bishop back (if one pawn makes it to the opposite edge)
The point here is you can formal proof, or automize on a computer, a nontrivial relationship without pulling up set theoretical semantic to model every chess ingredient
bojonpk
>>7983308
>Reject classical logic, and you reject mathematical truth.
logics are about reasonings, aka valid inferences
formal logics are about deductions so far
classical logic of deduction takes the preservation of the truth value T as validity of inference. Truth values is just a name, and so it the truth value T, 1, top, true whatever.
So far, classical logic and ANY LOGIC has nothing to do with truth.
Classical logic is one of the many attempts to formalize *how truth behaves* but is not about truth directly.
Classical logic and any other logic so far is about ''what can we expect from the word truth ?'', just like you ask, in set theory, ''what can we expect form a set ?'' then of course, you posit the existence of a set and go on your formalization, NOT of a what a set is, but rather of what can we do with a set.
Some people love to think that the powerset exists for each set, so they formalize this into some axiom (since formalizing your speculations will never ever be about existence of anything that you fancy, you must posit the existence of you like and the nonexistence of what you dislike)
Some people love to think that ur-elements make sense, so they formalize it in their formalization of set theory.
Same thing with validity of inferences. You ask YOURSELF, ''what is the validity of an inference'' and, for this, most people choose to dwell in deductive logic. Then , even in deductive logic, each people formalizes their notion of validity of inference and then they compare and seek a hierarchy amongst all the proposals.
it is your CHOICE to conflate truth value with truth and it is a very very dubious choice.
No formalization of any anything so far speaks about truth. In fact, it is even dubious to think of your speculations, not matter how formalized, gives you a truth.
>>7984598
Why do you carry "so far" along your text.
In what sense could the situation change?
>>7984963
>>Why do you carry "so far" along your text.
so far, because most people choose to think in terms of time (and space), so everything they think and say is cast in this structure. Rigorously, when you choose to think in terms of space and time (at any point in your speculations, but typically it is at the beginning), you do not now that, tomorrow, some rationalist will invent a new rationalism establishing once and for all that his rationalism, his formalization will bring truth, objectivity and other memes that people love to cling to.
the goal of most the rationalists today is to:
-think in terms of space and time (they claim that these ''concepts'' (in quote, since nobody has a clue what is behind those words) are relevant and they are always the starting point of their reflection
-claim that their relevant statements (about the world) escape precisely space and time
(typically in claiming that their statements are not inductive (through space or time), because they are got through pure deduction)
I use so far only to re-frame, in time, in history, the claims of those people who think that their formalizations do indeed talk about truth and what not.
>>7985851
As soon as you re-cast their statements in terms of history, you show the failure of the people before who claimed, just like people today, to have found the truth and objectivity.
By induction on these failures from the rationalists (going back to several millennium), you can claim that no rationalism will ever give you truth and so on.
Of course, this relies on induction, which means that you remain a rationalist in clinging to induction applied to some concept (like the concept of past and the one of the knowing the various doctrines of the past) (and the bit of deduction through the principle of induction (as an inference rule)).
This so far is really to be nice to those people, not to destroy their hope to think truth, necessity, objectivity, universality through their speculations.
Why? because it permits those rationalists to fall back on the notion of the scientific models as myths, stories, narratives [like Quine, kuhn and so on].
This notion of science as another story about the world really pisses the most rationalist-scientists (since they never ever took a class in philosophy of science) so it is a good compromise in a debate with them.
It permits to win, without going full empiricism, this doctrine where you stop speculating, stop inventing concepts and linking your concepts together in some structure, (and do reach what would the rationalist call truth, necessity, absolute ans so on), so where you only have a practice and refuse to have narrative about the world, always loaded with inferences (from induction, or deduction).
>>7978361
You can sum arbitrarily big naturals and get as a result even bigger, but still finite, number
reminder that you can have set theories without cardinality.
>>7987760
How? You surely have injections and surjections, so that the cocept is close?
