Comments by "MC116" (@angelmendez-rivera351) on "Spanning Tree"
channel.
-
@theodoregossett9230 It does have to do with surjective functions, though, since the "size" of a set (technically, its cardinality or numerousity) is defined in terms of bijective functions. Two sets X, Y are equinumerous if and only if a bijection f : X —> Y exists. This is how equinumerousity is defined. Equinumerousity is an equivalence relation, and it partitions the universe of sets into equivalence classes, called cardinality classes. The cardinality class of a set X can be denoted |X|, and with the axiom of choice, these cardinality classes can be totally ordered. Now, we can say that for two sets X, Y, |X| =< |Y| if and only if there exists an injective function g : X —> Y. If X and Y are finite sets, then in order for them actually be finite, it must be the case that there exist functions p0 : X —> N, p1 : Y —> N which are injective, where N is the set of natural numbers, since this is how the finitude of a set is defined. To be able to say that |X| < |Y| is to be able to say that that some injective function g : X —> Y exists, but that no surjective function h : X —> Y exists. Your "formulation" of the pigeonhole principle, that if |X| < |Y| < |N|, then there is no injective function g : X —> Y, is a tautology, since the consequence is precisely the definition of the condition, and thus, this is not actually a formulation of the pigeonhole principle.
Technically, the pigeonhole principle actually is the following statement: if |X| < |N|, and |Y| < |N|, and there exists a surjection h : X —> Y which is not injective, then |X| < |Y|. In essence, this is just saying that surjectivity and injectivity are dual, in the sense of category theory, at least when it comes to finite sets.
Another formulation is to say that if |X| < |Y|, and Y is a subset of the power set of X, then there exists some S in Y such that |S| > 1. This one is the more straightforward formulation from the English wording.
5
-
@SplendidKunoichi The pigeonhole principle is neither obscure nor confusing, and it does serve a purpose, as it is used in multiple applications, several of which were mentioned in this very video, which I realize you may have not watched at all.
Your claim about the reason these are called principles is completely unsubstantiated. In fact, the reality is, the way these theorems are named is completely arbitrary. There is no rhyme or reason behind things being named laws, principles, lemmas, corollaries, etc. These names are merely a matter of historical relic, not of actual epistemic substance.
5
-
3
-
2
-
2
-
2
-
@MrElmattias They did not "blow their own theory," you simply misunderstood the entirety of the contents of the video, and then rushed to comment without carefully processing the fact that the video explicitly acknowledged that they way modern Tetris is played works nothing like what was stated in the video. You not having the composure to process the disclaimer carefully enough is not an oversight on the video's part. And, by the way, this analysis is not "the video's," it is an analysis that is well-established in the professional mathematical study of Tetris. If you look at the description of the video, which I know you never bothered to look at, you will actually find the published paper "How to Lose at Tetris" by Heidi Burgiel. What the video is doing is just relaying the contents of the paper in a fashion that the lay audience can understand, while also clarifying that you are not supposed to think that these results apply to games in practice.
Anyway, I realize this conversation is going to be a waste of my time, so I will stop replying. I said what needed to be said, so I am done here.
2
-
1
-
1
-
@kiraPh1234k It quite literally is counting.
The pigeonhole principle is the following sentence in first-order set theory: for all sets X, Y, if there exists an injective function f : X —> Y, and there exists no surjective function g : X —> Y, then there exists no injective function h : Y —> X. In Zermelo-Fraenkel set theory, this is a direct consequence of the Schröder-Bernstein theorem. This is not counting. The mathematics of counting are founded on first-order set theory, but set theory is not synonymous with counting.
That's even being more polite than the truth, because truth is that it's a useless tautology.
Can you demonstrate how the sentence "for all sets X, Y, if there exists an injective function f : X —> Y, and there exists no surjective function g : X —> Y, then there exists no injective function h : Y —> X" is a tautology?
It states if n > m, then n > m.
No, it does not. In the theory of orders, the sentence "for all m, n, if n > m, then n > m," is indeed a tautology, but this statement is not the pigeonhole principle.
We use the underlying mathematics to solve the problems, not these useless tautologies.
I agree, but the pigeonhole principle is not a tautology, and it is nontrivial.
1
-
@kiraPh1234k I think you are just misunderstanding the video, quite frankly. It is true to say that, for example, if m, n are natural numbers, and n < m, then there is an injective function from n to m, and no surjective function from n to m, and therefore, no injective from m to n, but this is only a special case, which I think is fine for illustrative purposes.
1
-
1
-
The pigeonhole principle is a mathematical theorem, and as such, it is impossible for it to be false. The fact that it is stated solely in terms of pigeons and pigeonholes is done merely to make the principle intuitive. The actual statement of the pigeonhole principle is as follows: for all sets X, Y, if there exists an injective function f : X —> Y and there exists no surjective function g : X —> Y, then there exists no injective function h : Y —> X.
To prove this, notice that the Schröder-Bernstein theorem states that for all sets X, Y, if there exists an injective function f : X —> Y and there exists an injective function h : Y —> X, then there exists an injective and surjective function j : X —> Y. All theorems are semantically equivalent to their contrapositive statements, and the contrapositive statement of the Schröder-Bernstein theorem is that, for all sets X, Y, if for all functions f : X —> Y, f is not injective, or not surjective, then, there exists no injective function k : X —> Y, or there exists no injective function h : Y —> X. This, in conjunction with there existing an injective function f : X —> Y, implies that f is not surjective, and implies that there is no injective function h : Y —> X.
1
-
1
-
@ianbelletti6241 every theorem has underlying assumptions.
Those would be the axioms of set theory, but beyond that, no, your statement is false.
The pigeon hole theorem, in order to always ring true mathematically relies on no limit to the number of "pigeons" each "pigeon hole" can hold.
No, it does not. In fact, as I have stated already multiple times, this is a general theorem in set theory. It actually has nothing to do with pigeons and holes. The pigeons and holes are used only for visualization purposes. You are continuing to ignore the formal statement I presented to you in my previous sentences, which is fairly irritating.
If you make the limit 1 per hole, you can never double up items per hole and the theorem falls apart very easily.
As I said, the theorem actually has nothing to do with holes at all.
Therefore, the theorem relies on not placing limits to how many "pigeons" you can fit in each hole.
It does not.
Your proof falls flat on its face because it ignores that core principle of the theorem.
No, it does not, because my proof says absolutely nothing about holes. My proof is about injective functions, sets, and surjective functions. It is very clear to me that you have not understood my proof even the slightest bit at all.
1
-
@ianbelletti6241 You can only double up items in the smaller set if the rules of the sets allow you to. This rule cannot apply if the rules of the specific sets prohibit that proposition. Remember, set theory does have real world applications. Calling it a general theorem is fine, but the rule for it to work is that positions in the smaller set are allowed to hold multiple values or items at once. If the smaller set cannot do this, then the theorem cannot be used for that situation.
You almost have a point, but the insinuation here is that the axioms of set theory may be such that they allow for singletons, or the empty set, but no other sets. However, I do not know of any nontrivial, non ad hoc set theory, in which this is actually true. Any set theory in which the pigeonhole principle is false would also have to be a set theory in which the Schröder-Bernstein theorem is false, and even Cantor's theorem.
There are situations where the theorem is false. It's the nature of these general theorems.
There are no situations where the theorem is false. That is simply not how theorems work. You may say that there are situations where the theorem is not applicable, but by definition, a theorem is a sentence which can be proven, and the deduction rules used in mathematics are sound, meaning that it is impossible to prove false sentences from true sentences. Therefore, if a sentence is provable, then it cannot be false. Since the pigeonhole principle is provable, it cannot be false.
In many cases they work, but under certain circumstances they don't. It's like the formula P=IE for power. It works in many cases but won't give you the true power because it doesn't take into account how many phases of electricity you're using and the impedance of the circuit.
This analogy is invalid. The formula P = I•E is not a theorem, it is a scientific observation, a scientific law, and scientific laws do not work like theorems at all. You are comparing mathematics to physics here. This is like comparing apples and pineapples. Besides, no competent scientist would ever actually claim under any circumstances that the law works for all physical circuits. If someone tells ypu that it does, then they are lying to you. It is as simple as that.
The same thing is happening with this theorem.
No, it is not. Theorems are not scientific, and they do not work like scientific laws. They do not describe physical systems.
In general it works, but it doesn't apply to all sets where you're inserting a larger set into a smaller set.
I have no idea how you came to this conclusion. This is incoherent. No one is claiming you can embed the elements of a set into a smaller set. That is literally not what the pigeonhole principle states.
1
-
1
-
1
-
1
-
1
-
1
-
It is not an axiom, it is a theorem. Formally, the pigeonhole principle states that, for two sets X, Y, if there exists an injective function f : X —> Y, and there exists no surjective function g : X —> Y, then there is no injective function h : Y —> X. You can prove this by appealing to the Schröder-Bernstein theorem, which states that for any two sets X, Y, if an injective function f : X —> Y exists, and an injective function h : Y —> X exists, then an injective and surjective function j : X —> Y exists.
1
-
1
-
1
-
1
-
@SplendidKunoichi Uh, well... for starters, you can search "pigeonhole principle" on Wikipedia, and if you read the various sections of the article, then you will see what I mean when I say that the pigeonhole principle is a mathematical theorem. There are several formulations of it too. As for the usage of the word "theorem," a theorem is simply any mathematical sentence that can be proven to be true. A sentence not having the name "theorem" does not mean it is not a theorem. Again, you can search on Wikipedia for more details. Now, I understand Wikipedia is not a scholarly source, but as we are just discussing the introductory concepts, I think it should be fine. The pigeonhole principle is also known as Dirichlet's principle, not to be confused with Dirichlet's theorem, which is a different theorem that is unrelated (well, there are multiple theorems by that name). If you are curious for details beyond what the article states, then I can tell you this: the pigeonhole principle is a direct consequence of the Schröder-Bernstein theorem, which again, you can read about on Wikipedia. If you are familiar with set theory, then the proof is fairly straightforward.
1
-
1