the reason P(X) connected this well with Z2 is that if we interprete 1 as "this element is in the subset" and 0 as the opposite we can easily connect pairs of numbers to subsets, and turns out these operations correlate too. this even works in the general case of X being any other cardinality
The z2 addition is basically the xor operator, while z2 multiplication is basically the and operator, and this "power ring"'s + function is basically the same as doing xor for every element's existence inside the set, while this "power ring"'s x function is basically the same as doing and for every element's existense inside the set. (This is basically what you said).
an n-tuple of Z2 entries pretty much is a subset of a set of n elements - each entry just says whether the i-th element is or isnt in the subset. However, I do wonder if this ring structure has any relation to the symmetric group over n elements...
Interestingly, the first time I came across this operation was during a Linear Algebra Course last year, as an example of a vector space. So only considering the sum, i.e., symmetric difference, the set P(X) is a vector space over the field with only 2 elements (this is sometimes denoted Z_2, or Z/2Z or F_2) where scalar multiplication with the scalars is defined in the obvious way, multiplication with 0 gives the empty set and multiplication with 1 gives the set itself
It is not: It would be a boolean algebra using the union instead of the symmetric difference (which is the usual thing). In a boolean algebra, A + (-A) = 1, and not 0 like happens in a ring (because of the group structure with the + operstion). The interesting thing of the video is that shows how to give to P(X) a ring structure, instead of the more common boolean algebra structure, using a different + operation.
@@pacojacomemaura2129 It is true that the multiplication and addition defined here do not correspond to the conjugation and disjunction from the boolean algebra. The ring shown in the video is, however, the boolean ring arising from the standard boolean algebra of the power set.
I really have to thank you for teaching me how much i love abstract algebra, i didnt even know that I loved it until I checked out your series on mathmajor
If you use the set {0,1} and the definition for addition in the video, it is interesting that there are other ways to define addition that are equivalent. It is addition mod 2. It is also (A+B)*(~A+~B).
A nice "natural" derivation of this ring (and its alternative): A subset of some set S is uniquely identified by its characteristic function: a function F:S→{0,1} that maps elements belonging to a subset to 1 and not belonging to 0. It is easy to see that subsets are in one-to-one relation with functions of such signature. This way, the powerset of S can be seen as a set of functions, whose argument is S, and value belongs to {0,1}. Now, if we give the set {0,1} some structure (such as ring structure, or group structure), then this stucture naturally induces the same structure on functions S→{0,1} where all operations are defined pointwise. Talking about rings, there is only one ring with 2 elements, the ring ℤ₂ or integers modulo 2. Therefore, there are 2 ways to assign ring structure to the set {0,1}. One is the obvious, that maps 0 to 0 and 1 to 1. This induces the ring of powersets in the video. The alternative way is to map 0 of {0,1} to 1 of ℤ₂, and 1 of {0,1} to 0 of ℤ₂. It would be the same ring, but with unconventionally named elements. With this assignment, summation table on {0,1} would become: 0+0 = 1, 0+1=0, 1+0=0, 1+1=1 (thus, 1 is the zero of this ring), and multiplication would be: 0*0=0, 1*0=1, 0*1=1, 1*1=1 (thus, 0 is the multiplicative identity). This induces an alternative ring structure on the powerset: A+B=(Aᶜ∩Bᶜ)∪(A∩B) where Aᶜ is the complement of A (this is NOT XOR logical operation) A*B=A∪B Additive identity would be the entire set S, and multiplicative identity would be the empty set. Indeed, this alternative ring is isomorphic to the one in the video, with isomorphism being the complement function. This corresponds to the only non-identity isomorphism of the set {0,1}
In the requirements for a ring, you also need a multiplicative identity element ("1"). Here it would be X, the whole set. Also, the commutativity of the addition is not required, since it is ensured by the distributivity law: (1+1)(A+B) = A+B+A+B (left distri) = A+A+B+B (right distri) therefore A+B = B+A.
It's a bit of a tangent, but with modular arithmetic I like to use a slightly different basis that includes negative numbers rather than the normal one. For example, the video shows Z₆. Instead of using {0,1,2,3,4,5} as the equivalence class labels, though, let's use {-2, -1, 0, 1, 2, 3} . Note that, mod 6, we have 4 AxB -2 -1 0 1 2 3 -2 -2 2 0 -2 2 0 -1 2 1 0 -1 -2 3 0 0 0 0 0 0 0 1 -2 -1 0 1 2 3 2 2 -2 0 2 -2 0 3 0 3 0 3 0 3 -2 and 5 ≡ -1, so all we're really doing is relabeling the classes for 4 and 5 as -2 and -1 respectively. When you use this alternative basis, though, for your addition and multiplication tables, some of the symmetries stand out. Here's the multiplication table for instance: Multiplication table AxB -2 -1 0 1 2 3 -2 -2 2 0 -2 2 0 -1 2 1 0 -1 -2 3 0 0 0 0 0 0 0 1 -2 -1 0 1 2 3 2 2 -2 0 2 -2 0 3 0 3 0 3 0 3 Note for example that 3 ≡₆ -3 so 3 * -1 ≡₆ 3 . Also -1 is unsurprisingly its own inverse, which translates to in the video when Michael comments about 5 being its own inverse as well (since 5 ≡₆ -1). And you get the visible symmetries when you swap a + or - sign in a product as well (e.g. the -2 row is the inverse of the 2 row).
If X is a set then the power set equipped with the symmetric difference and the action of set intersections cannot be a division ring since if A is a subset of X that isn’t the empty set or X and A^c is the compliment, then A*A^c = A n A^c = the empty set=0. It follows that A is a zero divisor, the only element with a multiplicative inverse is X itself.
What is the reason to use such a strange operation like A+B (instead of the reunion)? It is very arbitrary. I know an operation can be as arbitrary as you want, but it must describe something.
I'm not sure if that's already exactly what boolean algebra means, but this ring is isomorphic to the set of the sets of cases, where events can happen, with X being the set of all cases. When we assign each case with a probability, we can easily calculate the probability of all possible events, because + and * (in the way they're defined here) for the sets of cases work exactly like XOR and AND for the events.
I'm not sure I understand your question but it is easy to show that the power set of X is isomorphic to Z2^card(X) (I've just written the proof and it takes only one page. Try to prove it, it is a nice exercise!)
@@azmah1999 I had brought cardinality into this because I felt like it would be Z/2Z^n for finite sets of cardinality n, but I wasn’t sure for infinite sets. Idk why l thought it should have been different, come to think of it!
20:20 More generally speaking, for any power set ring, if 1 is the entire set, then 1 + X = Xᶜ (i.e. the compliment of X). So in the video, where 1 = {a,b}, it follows that since A and B are compliments that 1 + A = B and 1+B = A.
You can see this pretty directly from the "mistake" finding -A: we found that A + A complement was 1, and then that -A=A. If you take that first equation and add A to both sides and cancel A+A, you get A complement = 1+A.
20:00 When filling in the multiplication tables, note the the 0 row and column are always 0. This is in fact true for all rings, i.e. if you multiply anything by the additive identity in a ring you get the additive identity back. The proof follows immediately from the axioms for rings. For all x in a ring x0 = x(0+0) (since 0 is the additive identity) x0 = x0 + x0 (by multiplicative distribution) x0 - x0 = x0 + x0 - x0 (adding the inverse of x0 to both sides) 0 = x0 + 0 (adding together x0 and its additive inverse is 0) 0 = x0 (since 0 is the additive inverse) So therefore if you multiple any number in a ring by the additive inverse 0 the result is the additive inverse 0.
Michael, I have to say that you have an astounding talent for Maths communication; one could only hope for as much clarity and concision from a textbook!
Plenty of textbooks in circulation which are both lucid and concise. Vanden Eynden number theory texts come to mind. In fact, a metric for math talent could be related to how much math one can learn on their own without being spoon fed by another person who took the time to assimilate the subject matter from a textbook.
@@MyOneFiftiethOfADollarI feel as though the mythos that perptuates itself about this revered and elusive character of the autodidact comes from a particularly haughty point of view. Humans are, innately, story-tellers, and there is simply no substitute that can compare to the student-teacher dynamic; one can cannot conjure humility from within. It is a rare aspect, only to be meted out charitably to those passionate few along the line of inheritance. After all, arrogance is not that which defines the genius, but only a symptom! An educator's goal is to inspire and encourage, and I believe that no book, no matter how dense or involved its contents were to be, could convey those quintessential elements of our goal to grow and learn as humans. Personally, I find Penn does that marvellously well, and I can appreciate the great humility that he takes with his knowledge.
Once you got to Z2x2 and then mentioning isomorphisms I was expecting a bit of talk about how this ring is effectively Boolean algebra, + is XOR and * is AND. When I took a course in digital electronics at the local technical college one of the assignments was not just to fill out the tables - instead we were also asked to wire up on a breadboard a 7408 (AND) and a 7486 (XOR) and other 7400 series chips to actually demonstrate these operations in a live logical circuit.
Just an inverter gate. Then we jumped to the 7400 series chips. Most of the stuff dealing directly with transistors was done in other classes, and there the focus was mostly on analog circuits.@@bobh6728
It's not hard to see that the equivalence shown by Penn generalizes, i.e. this ring for the power set of a set with k elements is isomorphic to the ring on (Z_2)^k, which as he mentioned in passing, is a boolean ring with 2^k elements. I'm a bit surprised he didn't mention this.
@@herghamoo3242 are those ring structure uniquely identified by the number of element? Or are there different boolean rings with the same number of elements?
