The subtle definition of the ordered pair (x,y).

[@PixelSergey]

I love these sorts of "trivial-seeming" proofs. Great to see them opened up!

[@yyeeeyyyey8802]

When using this definition, higher order tuples should be defined recursively, that is, (a,b,c) is defined as ((a,b),c), and so on. Note that the definition (a,b,c) = { {a} , {a,b} , {a,b,c} } does not work, even though it looks like a natural generalization, as shown in the following example (assume a and b are distinct): (a,a,b) = { {a} , {a,a} , {a,a,b} } = { {a} , {a} , {a,b} } = { {a} , {a,b} } = { {a} , {a,b} , {a,b} } = { {a} , {a,b} , {a,b,b} } = (a,b,b) that is, the definition (a,b,c) = { {a} , {a,b} , {a,b,c} } would imply the equality (a,a,b)=(a,b,b) which is unwanted for ordered pairs. Very interesting definition nonetheless. It's always interesting how the equality {a,b}={a} when a=b affects calculations in unintuitive ways.

[@schweinmachtbree1013]

@@angelmendez-rivera351 *it is ad hoc to choose a right-recursion and not a left-recursion, especially since there is a natural isomorphism between the two. It would be better to incorporate the equivalence right into the generalization itself* Disagree. Showing that there is an isomorphism (especially a unique/natural one) between different definitions proves that it doesn't matter which definition one uses, in the precise sense that the *properties* of the thing being defined (which is for the most part how one actually reasons about it mathematically) are independent of whichever concrete definition one chooses (which often has more to do with personal preference). This is the categorical philosophy of reasoning - where possible - by _what things do_ rather than _what things are_ . A simple example is given by this video: ordered pairs can be defined by {{x}, {x, y}} or {{x, y}, {y}} or {x, {x, y}} or {{{x}, {}}, {{y}}} or {{x, 0}, {y, 1}} or {{0, x}, {1, y}} and so on*, but whichever concrete definition one decides to use, the first job is to show that (x,y) = (z,w) x=z and y=w, and then one just denotes pairs by (a, b) and reasons about them using this property, at which point there is no need to ever go back and "look under the hood" at the specific definition, so in this case it makes no difference at all which concrete definition one decides to use. A more advanced example would be mathematical objects governed by universal properties, e.g. the tensor product. There are different ways of constructing the tensor product (e.g. there are two main ones that I am aware of), but once you have chosen a definition, which for a lot of mathematicians comes down to personal preference, one of the first orders of business is to show that it satisfies the universal property - since any other definition of the tensor product also satisfies the same universal property, there is a unique isomorphism between any two concrete constructions of U⊗V. Most category theorists prefer to *define* tensor products/free groups/polynomial rings/etc. by their universal properties, and then specific constructions of these objects can be seen as existence theorems showing that the universal property in the definition does actually correspond to some mathematical object. Using this philosophy, one could (and I personally I think one should) *define* ordered pairs as sets which we denote by (x, y) and which satisfy the property (x,y) = (z,w) x=z and y=w - then giving a concrete construction e.g. {{x}, {x, y}} and showing that it satisfies the pair property can be seen as a little theorem establishing that the definition by the *property* does actually correspond to something within formal ZFC/NBG/whatever. In conclusion, specific constructions of mathematical objects can at times be technical or fiddly or ugly or a matter of personal preference (e.g. an example of the latter is defining tuples from X so that X^n is the special case of X^Y where Y is a natural number viewed as a set and defining subsets of Y so that P(Y) is the special case of X^Y where X = 2), and therefore it is sometimes most elegant to define a mathematical object by what it does rather than what it is. When one does this, the definition on its own doesn't actually establish the existence of the mathematical object, but only that *if* it exists then it is unique (/unique up to isomorphism/unique up to canonical isomorphism), so one follows the definition by an explicit construction which serves as proving existence (and sometimes one will immediately forget about/"throw away" the precise construction as soon as one has written the QED on this existence proof). (*modulo some technical details, e.g. the third definition requires the background set theory to be well-founded)

[@Nikolas_Davis]

Very interesting! This reminds me of how you can define a natural number (or rather, its ordinal), as the set of all natural numbers preceding it. It may seem perverse to our human intuition (we conceive numbers as a model, by analogy), but in an axiomatic system that only knows of the set as a building block, there is little choice - everything has to be built from sets. I remember how weird this felt when I was first introduced to it. To my mind, the set is a secondary object, a collection of things that are *not* (necessarily) sets (and this is in fact how naive set theory defines them, or rather doesn't define them). But in axiomatic set theory, it is the *set* that is primary, and all other objects are constructs made of sets. Takes a while to get used to :-)

[@lilyhayden5732]

my own preferred definition of the naturals, personally, is one that utilizes isomorphism classes in the category of sets, though it's not as overly formal or metaphysical; I just prefer it because it's a way within the framework of category theory to replicate my intuitions about the naturals, as you can define a strict ordering with non-epic monomorphisms and define multiplication with products and addition with coproducts, pretty easily.

[@88Magician88]

Natural numbers (and more over numbers) can't actually be defined in a classical sense. It's called Tarski's undefinability theorem. This is why you can do things like represent natural numbers as the set of all natural numbers preceding it. There is an infinite way to represent every number. On a deep level math gets fuzzy.

[@schweinmachtbree1013]

@@88Magician88 Can you elaborate? There is a sentence ϕ in first-order set theory such that ϕ(x) is true if and only if x is a natural number: namely, ϕ(x) is given by "x is an ordinal which is either 0 or a successor ordinal, and all elements z of x (necessarily also ordinals) are either 0 or successor ordinals" - formally I guess this is "x in Ord & (x=0 or ∃y in Ord: x = y U {y}) & (∀z ϵ x: x=0 or ∃w in Ord: z = w U {w})". Thus {n : n in Ord & ϕ(n)} is the set of natural numbers throughout, "Ord" is the proper class of ordinals, which is similarly defined by a first-order formula (which iirc says that an ordinal x is a ϵ-transitive set which is well-ordered under ϵ)

[@88Magician88]

@@schweinmachtbree1013 Sure I'll do my best. Tarski's theorem is actually very broad and doesn't just encapsulate numbers but any logical system. It ultimately states that fundamental truths of a system cannot be explained by that same system. I'm other words if you take the number 1, you can represent 1 as 3-2, sin(π/2), {1}, etc but you can never find a simpler representation than 1. You can only find more complex representations. Therefore 1 is undefined like all numbers. Because what is 1? Just some value we made up, it has no actual meaning and therefore it is undefinable. It is what it is. The truth of a system cannot be reasoned by the system. All it really means is that 1={1}=sin(pi/2)=10-7-2=5/5 Arithmetically there is no "correct" answer because you can't prove that 1 is 1 but you can show that many things can be 1. Like I said math gets pretty fuzzy on a philosophical level. For example, in physics, if you take the simplest building blocks (currently quarks, but maybe strings or constructor fields) what are they actually? Energy? But what really is energy? There in lies the problem, Energy (a truth of the universe) is like a number, it's undefinable. It simply must be accepted. It can take many forms but ultimately, you can't use particles or fields or anything to "define" it. It simply is what it is, a truth. Hope that makes sense!

[@88Magician88]

Essentially numbers are the the family of sets that make up that number. However, there in lies the problem. That's a recursive definition and therefore not a definition at all. Obviously sets are also more complex structures than numbers and definitions are supposed to simplify, not complicate. It's really a commentary on truth as a whole. Truth is just that, something that must be accepted so progress can be made but ultimately something that is undefinable in the system which it is used.

[@francocosta1]

Wow, i've never found a texbook with the proof(only the definition), is so elegant and clear. Thanks a lot!

[@andrewlitfin1977]

Fun fact: in view of Separation you can weaken Pairing to get the same theory. Specifically, rather than Pairing being "For all x, for all y, there exists z such that for all w, w in z iff w=x or w=y", you can weaken it to "For all x, for all y, there exists z such that x in z and y in z" and then use Separation with formula p(w)="w=x or w=y" to separate out the subset containing *only* x and y. (I learned this from Kunen's "Set Theory" section I.4)

[@schweinmachtbree1013]

cute! just to do this justice, here are both first-order sentences so it's easier to see the difference: the former is "∀x∀y∃z∀w(wϵz (w=x or w=y))", z being denoted by {x,y}, and the latter is "∀x∀y∃z(z϶x and z϶y)", and we separate out the pair set with {x,y} := {wϵz | w=x or w=y}. It is now perhaps easier to see that the second formula is (logically equivalent to) the first formula but with just

[@jimmymontoki743]

Thank you so much. I had seen that definition in a book and didn't understood it. Now it's way more clear

[@biblebot3947]

Can you make a video on the Darboux Derivative?

[@Fine_Mouche]

3:30 why it's not, if a = b : {a,b}={a,a} ? because for me it's weird that {a,b}={a}, because it's mean that a set of 2 elements = a set of 1 elements, it's little like saying 1=2 for me.

[@duncanw9901]

This is actually a pretty intuitive way to define an ordered object from a collection of unordered ones; you're just distinguishing the element that's first by pairing it with the whole object. I see the generalization to n-tuples too I think: you'd just have a subset of the unordered collection corresponding to the k-th element of the tuple where the k-th element is the one not found in all the smaller sets in the collection. It's a pretty important construction too. If I recall correctly set theorists these days define functions as subsets of the Cartesian product (maybe a power set is involved?) in a subtle way that always escaped me...

[@ulrichs.3228]

IIRC n-tuples are often defined as mapping the numbers 1,...,n onto the elements of the tuple. My algebra prof would get very upset about students treating Kuratowski ordered pairs (a;b) as in the video as 2-tuples (a,b) without at least mentioning that there's a trivial isomorphism iota that we omit for readability. (And yes, a function is just the set of ordered pairs (x; f(x)), so you'll need ordered pairs to bootstrap functions to bootstrap tuples.) I miss algebra.

[@lifthrasir1609]

Yeah, as a matter of fact the definition of n-tuple can be derived recursively as (a_1, ... , a_n) := ( (a_1, ..., a_n-1), a_n) As for the set theory definition of a function, the main challenge there is to assure that every element of the domain is mapped to exactly one element of the codomain. That is, function f: X -> Y can be defined as set F c X * Y (where X * Y is Cartesian product) such that for every x є X: If (x,y) є F and (x,z) є F then y = z, (y, z є Y) meaning that there is at most one tuple in F that has x as its first element.

[@ulrichs.3228]

Oh, and of course you could go along the CS route, where a list is empty or has a first element and a remainder, but that makes "a five-tuple doesn't have a sixth element" something that would need an actual proof, which seems awkward.

[@schweinmachtbree1013]

@@ulrichs.3228 Interesting, I hadn't heard of this. So like natural numbers can be defined as an inductive type by "n is a natural number iff n=0 or n=s(m) where m is a natural number", this CS definition defines tuples with entries from a set A as an inductive type by "T is a tuple from A iff T = ( ) or T = (a) + S where a ϵ A and S is a tuple from A". I suppose you can then formally define the length of a tuple inductively by l( ) := 0 and l((a) + S) := 1 + l(S). I don't understand what you mean by 'that makes "a five-tuple doesn't have a sixth element" something that would need an actual proof' though, since applying the inductive definition of tuples n times (and finishing with the "T = ( )" path at the (n+1)st step) tells us that any tuple is of the form T = a_1 + (a_2 + (a_3 + ... + (a_n + ( )))) = (a_1, a_2, ..., a_n) for some natural number n, and this tuple has length n and n elements, so it seems clear to me that a k tuple doesn't have a (k+1)st element I'm 90% sure the last paragraph can be made rigorous pretty straightforwardly with a proof by induction or two, and it doesn't seem to be that "awkward" (especially if one is familiar with areas of math where there are lots of inductive definitions, e.g. mathematical logic).

[@theheckl]

yup, a function is a special case of a relation, wich is a subset of the cartesian product of two sets

[@angel-ig]

Nice! I was wondering this the other day and then forgot about it. Thanks for making it clear now!

[@mueezadam8438]

Great concept to showcase. I remember coming across this more precise definition in Munkres’ Topology.

[@LeeDeVilleMath]

Excellent... I was just prepping a lecture on exactly this so love to see it. You've definitely highlighted the key ideas in a really nice way. I'll send my students this way when the topic comes up!

[@NicholasPellegrino]

Great video. Thanks for sharing!

[@natepolidoro4565]

Very nice video, I enjoy this kind of foundational stuff.

[@abrahammekonnen]

I don't usually comment on videos(and I'm sorry for that), but I really enjoyed this video and I hope you'll have more like it. I'll add some questions I have about the material later.

[@hypergaming2051]

I learned first time set theory , Nicely explained.

[@punditgi]

Great videos! These are a good place to start!

[@xrhsthsuserxrhsths]

What interests me the most about this is that in a cartesian closed category, or even in just a cartesian category, the kuratowski definition is not needed, because of the use of global elements. But to prove that SET iss a cartesian category, a definition of the ordered pair is still necessary. But then again the question is how to define the composition function between homsets?

[@barbietripping]

Prof be reading my mind again. Been reading and writing about this

[@vinuthomas7193]

When you're formally proving {a,b} = {a,d}, shouldn't you have to consider the situation where a=d, and show that results in a=b?

[@feynmanaruda8063]

Valeu!

[@allanbois7172]

What if a and b was always an input number and C D was something like a derivitive a couple or few number's in pair to read always on a critical line? The number would level back to its roots using a stag kinda number and count's from an information line. Input something like 101^-1(information line or room for 2 place holders... - 0.0616300000825779682462795349708 --2.9384199999174220317537204650292- At this point your at negative 3 always, -1.9691201000206015277207798477888e-30... You be back right on the information line again.

[@synaestheziac]

I don’t think I’ve ever heard the word ‘doubleton’, but I love it

[@sharpnova2]

first set theory i ever saw was that one could unambiguously (with respect to order) define (x, y) as {{x}, {x, y}} and i was instantly in love. though it wasn't till my teens that i actually delved deeply into the subject and started reading all the seminal works. i was much more of an analysis kiddie. i could evaluate variational derivatives before i could ride a bike!

[@alexandersanchez9138]

5:45 Why wouldn't you look at {c} at this point, instead of {c,d}?

[@raph-ko1706]

Because if you do this, you get that {c} belongs to { {a} , {a,b} }. This implies two cases: either {c}={a} and c=a. Or {c}={a,b}. Thus b=a but at this point b is not equal to a. To resume we have a=c but we didn't proved that b=d. By chosing {c} instead of {c,d} we're lossing informations to get a conclusion for the value of d. So that's why he chose {c,d} ^^

[@alexandersanchez9138]

@@raph-ko1706 I don't see the problem: First, c=a, since otherwise a=b. Then, {a,b} = {c,d} (since {a,b} has to be in {{c},{c,d}}). Thus, b=d. Seems much shorter to me.

[@SlipperyTeeth]

@@alexandersanchez9138 I do prefer your approach to depicting the proof. There is a reason to show it the video's way (relating to the structure of the proof). The proof has 3 steps. Step 1: associate the elements of (c,d) to the elements of (a,b). Step 2: show c=a from the pairing {c}={a} Step 3: show d=b from the pairing {c,d}={a,b} and the result of step 2 Your way was that you realized you can finish step 2 before finishing step one - handling the pairings associated to step 2 and 3 individually but in the right order to immediately execute the associated step 2/3 - making it seem like there's only 2 steps. This is nice because it feels faster - and in computing would be faster via instruction pipelining and related techniques. However, the video's way is better at showing the structure of the proof - keeping different steps separate - which is probably better for beginners to understand the structure. Then again, your way gives purpose to the pairing faster which might improve motivation during the first viewing. What I really liked was your idea to show that {a,b} = {c,d} instead of that {c,d} = {a,b}. It's a lot nicer - we don't have to use the case 1 argument - we just appeal directly to the case 2 description like we did to show {c}=/={a,b}.

[@alexandersanchez9138]

@@SlipperyTeeth That's a great perspective. I was just thinking, "what's the fastest/least painful way to prove the proposition?" not even considering the intrinsic value of the hitting those """lemmas""" in order. I now see the video's exposition in a new light. Thanks!

[@mollystewart-gallus537]

It's always funny coming from a background in type theory to this subject. In type theory constructing unordered pairs is basically impossible. You want a quotient of the ordered pair A * A/(a, b) ~ (b, a) but constructive quotient types are really hard. You can have quotient inductive types as primitive but really it brings up higher Inductive types which are a mess. `forall C (f: A -> A -> C), (forall a b, f a b = f b a) -> C` almost works but doesn't have a proper induction principle and requires functional extensionality to use properly.

[@schweinmachtbree1013]

so I suppose the cleanest way to do things would be to define the unordered pair {a, b} to be (a, b) together with (b, a), so if a=/=b you have (a, b) and (b, a) while if a=b you just have (a, a) (although maybe taking it with multiplicity, (a, a) and (a, a), would be more uniform). Would you say this is accurate?

[@mollystewart-gallus537]

@@schweinmachtbree1013I would have to think about it. In general quotients are not easy but I probably overlooked something for unordered pairs. I still have to think about { '((a, b), (b', a')) | a = a' /\ b = b' } though. In a similar vein you can use point line duality to work around quotients for fields. I forget the exact details though.

[@martinepstein9826]

@@schweinmachtbree1013 I don't know anything about type theory but your definition of an unordered pair seems circular. Isn't "(a,b) together with (b,a)" an unordered pair of two ordered pairs?

[@schweinmachtbree1013]

​@@martinepstein9826 that's why I was intentionally vague by saying "together with" haha. I suppose we are taking ordered pairs as given and trying to define unordered pairs (so to be clear, this has nothing to do with sets/set theory). What I think you're getting at is that the definition {a, b} := ((a, b), (b, a)) doesn't work because then {a, b} =/= {b, a} - like molly says, we would have to quotient by some equivalence relation (presumably in a type-theoretical sense instead of a set-theoretical one). Luckily I think I can weasel my way out of the problem: if I am allowed to work within a background logic (as one does in set theory) then I have the notions of "and", "or", "not", "if", "only if, "iff", "all", "some", etc., and I can use the commutativity of "and". So I think I can define {a,b} as the type which contains x iff x=(a,b) or x=(b,a), i.e. yhe type inhabited by (a,b) and (b,a). Like you though I don't know much about type theory so this might not make sense - the logic in type theories is actually internal to the type theory (which is really *really* cool) so I would have to look into the type-theoretical definitions of logical connectives to be sure.

[@martinepstein9826]

@@schweinmachtbree1013 Thanks for elaborating! I'm thinking if you did get this work then you could cut out the ordered pairs. However you construct "(a,b) together with (b,a)" you could do the same thing to get "a together with b" and let that be the unordered pair.

[@backyard282]

How about defining it as a function ( . , . ) : {1, 2} ---> S and {a,b} is a subset of S. Basically it's just a two element sequence. And I don't think we need the concept ordered pairs to define a function so it's not circular reasoning.

[@schweinmachtbree1013]

A set theorist would say that you do need a prior notion of ordered pairs to define functions (functions being a special kind of relation), since a function from X to Y is a set of ordered pairs (x, y) where x in X, y in Y, and for each x there is exactly one y such that the pair (x, y) is present. However, set theory really isn't the best foundational system for mathematics (I believe the tides are due to turn in the next decade or so), and if you choose to use foundations other than set theory then you can define functions so that they are prior to the notion of ordered pairs - for example, you could take the notion of a function (between sets) to be a primitive, just like set theory takes sets to be primitive. This latter paragraph kind of turned into a rant and isn't relevant to your question, so feel free to skip: Yes you *can* define functions between sets in terms of sets alone, as is traditionally done in ZFC etc., but just because you can doesn't mean you should. For example I think it is nicer (it is certainly much less technical) to do set theory without worrying about trying to be as minimal/economical as possible - e.g. I would take the primitives to be not only sets but also tuples (which includes ordered pairs), multisets, ordered sets, natural numbers, relations, and functions, and probably a few more. All of these primitives would be subject to axioms, for example we would have the Peano axioms for the natural numbers, and we would have an axiom (a_1, ... a_n)=(b_1, ..., b_n) a_i=b_i for all i for ordered tuples, as opposed to the corresponding theorem in this video (where n=2). Another reason I prefer to go about things this way is because constructions like "(x, y) := {{x}, {x, y}}" or "0 := { }, 1 := {{}}, 2 := {{}, {{}}}, 3 := {{}, {{}}, {{}, {{}}}}, ..., n := {0, ..., n-1}" are not really 'mathematical', since they do not provide you with any better understanding or appreciation of what ordered pairs/natural numbers actually *are* - these constructions are more like "coding"; it just demonstrates that one *can* encode various mathematical objects within set theory. Once one has built up the tower of common mathematical objects, this leads to humorous things like real numbers being sets of sets of sets of ... sets of sets of sets. (real numbers can be defined as equivalence classes of Cauchy sequences of rational numbers, rational numbers are defined as equivalence classes of pairs of integers, integers are defined as equivalence classes of pairs of natural numbers, and natural numbers are defined as certain sets. since all of this is taking place in a set theory, everything is a set: namely in this example, equivalence classes are sets, Cauchy sequences are sets, and pairs are sets).

[@backyard282]

@@angelmendez-rivera351 I didn't know you needed an ordered pair to define a function. If I said that a function is just a mathematical object defined by two non-empty sets A and B that assigns every element of a to exactly one element of B written as f(b)=a, would that be not enough rigorous?

[@peterdecupis8296]

Such kind of "trivial" demonstrations are very common in modern axiomatic Set Theories; in the case of point, Mick is treating the Kuratowski definition, that is mainly employed in the magnificent GB Theory, which distinguishes pure Classes and Set classes: the first ones can be only subjects of the fundamental transitive action (i.e. pure Classes can only contain), whilst the second ones can be both subjects and objects (i.e. sets can contain and be contained). An axiom that is implicitely employed in the video is the extensional definition of the equality relation "="; this states that a pair of symbols a, b represent the same container-class (i.e. we shall pose: a=b) iff for any containable set x: x belongs to a iff x belongs to b. In the GB theory the "Couple" Axiom that Mick cited states that for any pair of symbols representing containable sets a,b the container Class {a,b}, that can be built via Separation axiom (throgh the well-posed proposition p(x)= "x=a VEL x=b"), is a proper Set, i.e. {a,b} may be contained by other classes or sets. The unicity of this non-order couple-set is a consequence of the extensional definition of the equality. The GB Theory, provided with the Choice Axiom, allows a rigorous foundation of Ordinal Numbers; for instance, finite ordered n-plets are defined as functions of finite ordinal domain n; this definition can be generalized to infinite ordered sequences which are represented by functions with a transfinite ordinal domain.

[@peterdecupis8296]

@F F right, the couple definition works the same both in ZF theory and in GB theory, as like as the Euclidean Gometry works the same both for the Ptolomaeus model and the for the Kopernicus model😉; obviously I am joking... Anyhow, I deeply studied at University the ZF theory and I liked it; then I studied, as a researcher and teacher, the GB theory and I loved! Then, as far the "irrelevance" of my comment is concerned, I think that such "spaces" should be mainly oriented to the free informal exchange of suggestions between Mathematics; obviously, it is not a good idea to write down unpondered or disrespectful comments...

[@antoniomello1620]

Just a little remark: Michael showed why the sets {a,b} and {{a}, {a,b}} exist by using the Axiom of Pairing, but to actually ensure the existence of the latter, you must first also show why {a} exists. For this there is another axiom of set theory that states the existence of the singleton {x} given a set x.

[@martinepstein9826]

True, but you don't need another axiom to get {a}. Just use pairing but let both sets be 'a'.

[@lyde73]

What's the intuition behind this? I can see that it works, but not why {{a},{a,b}} intuitively is the same as (a,b)

[@strikeemblem2886]

the intuition is: when talking about sets, we do not have an ordering, but we do have a notion of size (the ability to distinguish between singleton and doubletons.) so we DEFINE the ordering indirectly by falling back to the notion of sizes . "the contents in the singleton {a} will take the first spot in the ordered pair (a,b)"

[@thefranklin6463]

I love sets so much it hurts sometimes

[@General12th]

Is there any value in the approach of trying to show that for a != b, (a,b) must not be equal to (b,a)? Is there any way we could assume they are and set up a proof by contradiction?

[@schweinmachtbree1013]

I don't think this would help too much with proving (a, b) = (c, d) => a=c and b=d, but taken on its own, (a, b) =/= (b, a) for a =/= b justifies the "ordered" in "ordered pair". Using the definition given in the video, we have (a, b) := {{a}, {a, b}} while (b, a) := {{b}, {b, a}}. If a =/= b then these are both two-element sets each containing a singleton and a doubleton: supposing for a contradiction that (a, b) = (b, a), since the singletons must be the same we have {a} = {b} and hence a = b, which is what we want. P.S. proof by contradiction is slightly overkill here (but one shouldn't worry about this at first; one shouldn't expend effort thinking about simplifying ones proofs until one has actually found a proof!) - in this case we can go by contrapositive instead of contradiction, i.e. prove that (a, b) = (b, a) => a = b. So suppose (a, b) := {{a}, {a, b}} = {{b}, {b, a}} =: (b, a). Since {a} ϵ (a, b) it must also be in (b, a), and so {a} = {b} or {a} = {b, a} - in the former case we're done, so suppose that {a} = {b, a}. Then b is an element of the right hand side so it must also be an element of the left hand side, so again a = b.

[@SlipperyTeeth]

Notice that the contrapositive of this statement follows from the proposition proved in the video. If (a,b)=(b,a), then a=b and b=a. So this does show that defining it this way makes it so that order matters.

[@goodplacetostop2973]

9:50

[@Holital]

Would there be a problem defining an ordered pair as: (a,b) = {a, {a, b}}? So, using "a" instead of "{a}". I remember seeing this definition while I was in undergrad, curious what your thoughts are.

[@schweinmachtbree1013]

This is fine - Wikipedia calls it is "short" set-theoretical ordered pair, and notes that proving the defining property (a, b)_{short} = (c, d)_{short} a=c and b=d requires the axiom of regularity (a.k.a. the axiom of foundation).

[@c_dorado]

No problem if you can prove that the membership relation is a partial order (which is true). Otherwise, you could have a={c, d} and c={a, b} and the pair (a, b) would be equal to the pair (c, d) for any b and d. (a, b)={{c, d}, {a, b}}={{a, b}, {c, d}}=(c, d).

[@lifthrasir1609]

I loved this video! Please do more on Zermelo-Fraenkel ST

[@LemoUtan]

Compare, then, A×B×C as the set of ordered pairs, the first of which is itself an ordered pair [e.g. ((a,b),c)] with A×B×C interpreted as a set of ordered pairs the _second_ of which is itself an ordered pair [e.g. (a,(b,c))]. Are these the same thing?

[@schweinmachtbree1013]

they are what is called "naturally isomorphic". I prefer to use neither (A×B)×C nor A×(B×C) but rather A×B×C := {(a, b, c) : a in A, b in B, c in C}, where (a, b, c) is an ordered triple not defined independently of ordered pairs (e.g. one can define an n-tuple of elements of a set _X_ as a function from _f_ : { 1, ..., _n_ } -> _X_ , writing "(a, b, ..., z)" for the function _f_ : 1->a, 2->b, ..., _n_->z)

[@LemoUtan]

@@schweinmachtbree1013 indeed I deliberately left off the parentheses to allow for the triple as a third 'interpretation'. Structurally they could be seen as distinct rooted tree structures, one with a leaf on the left and a two leaf branch on the right, another its obvious mirror, and the straight triple as a three leaf tree all at the same level. It depends on your point of view (combinatorially, what it is that you're enumerating). Seems as if you have to choose to deem them identical by such natural isomorphism, but the universe isn't forcing you to do it? It's a problem that doesn't seem to arise with ordered pairs, only with triples (and of course above).

[@schweinmachtbree1013]

@@LemoUtan You could argue that the same thing sort of happens for pairs, since in english we write from left to right whereas in other languages one writes from right to left. Therefore in english we have the Cartesian product A×B with its first projection p: (a, b) → a and its second projection q: (a, b) → b, whereas in Ancient Greek or something one would have the Cartesian product B×A with it's first projection a

[@LemoUtan]

@@schweinmachtbree1013 Ooh! I think that's quite a different category of critique. Of course you're right to bring it up but - in case of any doubt - I hereby formally agree that this is what we're doing (so we need not concern ourselves with boustrophedonic arbitrariness :)), i.e. that we pre-agreed that the composition '×' was non-commutative. Surely the bother over compositional associativity can't even come up until you have at least three animals to play with?

[@schweinmachtbree1013]

​@@LemoUtan I think that mathematicians (particularly category theorists) just use the natural isomorphism (A×B)×C == A×(B×C) == A×B×C to make rigorous the fact that it doesn't matter which definition we use (i.e. I doubt that anyone has ever actually done anything with this natural isomorphism other than prove that it is a natural isomorphism). Indeed, if you use one of the iterated-binary definitions (A×B)×C or A×(B×C) then you're probably going to denote it as A×B×C with elements (a,b,c), so you will be writing down exactly the same symbols on the page as somebody using a ternary definition A×B×C. Of course it is not the Cartesian product which is at the root of the matter here, but rather any associative binary operation × (or in the case of the Cartesian product, associative-up-to-isomorphism): there are lots of ways to parenthesise x_1 × x_2 × ... × x_n (since you bring up combinatorics you probably know that the number of ways is given by the Catalan numbers), but by the associative law (a×b)×c = a×(b×c) they are all equal (or in the case of the cartesian product, isomorphic). That is, independence on parenthesizations for 3 elements implies independence of parenthesizations for all greater numbers of elements. To answer your question, the Catalan numbers begin 1, 1, 2, ... - there are 2 parenthesizations for three terms, but only 1 parenthesization for two terms or one term*. So yes, parenthesizations of binary operations do not come into play until we have three terms because the Catalan numbers begin 1, 1, and if the binary operation is associative or associative up to isomorphism/natural isomorphism then we don't have to worry about parenthesizations at all. *for zero terms the "empty ×-product" either does or doesn't make sense depending on whether × has an identity element - the cartesian product has an identity element up to isomorphism which is any 1-element set, so a nullary cartesian product is, up to bijection, any 1-element set, which if you do things in terms of tuples is the set containing the empty tuple, {( )}.

[@darpanpatel8023]

Amazing video!

[@carly09et]

ha hhha I wondered where the handedness came from - this is hard to think about -

[@M.athematech]

The Kuratowski definition might be the most convenient but the definition I prefer (that almost no one else uses) is putting (a,b) = {{1,a}, {2,b}} where 1 and 2 are according to their standard definition as natural numbers. This is the most intuitive definition, although it has the annoyance of dealing with the special cases of a,b in {1, 2}.

[@nHans]

Yeah, how _do_ you deal with that 'annoyance'? That apart, if you're starting with set theory axioms-ZFC or any other-you know that natural numbers don't appear by themselves. You have to explicitly define them. In ZFC for instance, natural numbers (including zero) are defined in a somewhat analogous way to how Michael defined ordered pairs: 0 = { } = ∅ 1 = {0} = {∅} 2 = {0, 1} = {∅, {∅}} 3 = {0, 1, 2} = {∅, {∅}, {∅, {∅}}} n+1 = {0, 1, 2, ..., n} Having accepted that, Michael's definition of ordered pairs (and by extension, n-tuples) is more straightforward than using natural numbers. No exceptions, no annoyances. But, I suppose, to each their own.

[@M.athematech]

@@nHans People do not restrict themselves to ZFC (or to any formal first order axiom system for that matter, you can't even define a first order system without already having numbers and set theory), and you can get the definition of the natural numbers without needing ordered pairs. Once you have 1 and 2 one can define (x,y) = {{1,x},{2,y}} then there are several annoying cases with sub-cases that one has to deal with one by one.

[@liyi-hua2111]

hi there, I'm a little bit confused by the reason why does an ordered pair need to be defined in the manner of sets. In my simple mind, I always thought a tuple is a weirdly shaped element (like 🎂 is an element of S), and in order to manipulate such weirdly shaped element we define (a,b)=(c,d) iff a=c, b=d and because I can manipulate such elements so I proceed to make thm about tuples. as you can see the thought from above never encounter defining tuple in the sense of sets. So would you kindly tell me where did I think wrong or the reason why Michael said AxB needs to be more rigorous in ZFC from the start of the video.

[@M.athematech]

@@liyi-hua2111 We want to be able to form collections of ordered pairs. Your definition merely defines equality of ordered pairs as a notational abbreviation, it doesn't define the ordered pair itself outside the context of an equational statement.

[@liyi-hua2111]

@@M.athematech at first glance, I thought your collection(set of sets) of ordered pairs is something like this “{ {(a,c),(a,d)} , {(b,d)} }”, but this probably isn't what you meant. after a quick review of ZFC, I think you meant any element described in ZFC should form as a legit permutation of braces (like 0=phi) is that correct? and I do think that a relation of equality is sufficient to describe relations of sets containing ordered pairs.

[@synaestheziac]

Don’t we also want to show that it’s possible for (a, b) to be not equal to (b, a), so that it’s actually an *ordered* pair that we’ve defined?

[@martinepstein9826]

Well, he showed that if (a,b) = (c,d) then a = c and b = d. An instance of this is if (a,b) = (b,a) then a = b. Hence if a =/= b then (a,b) =/= (b,a).

[@synaestheziac]

@@martinepstein9826 nice, you’ve proved the corollary I was looking for!

[@louisreinitz5642]

I remember the first time I encountered this, many years ago in grad school.

[@i_amscarface_the_legend9744]

Nice vid, i am so curious to see how the axiom of choice will be used to define the cartesian product ? Since, to define the first element, u have to choose ! Is there any equivalence in between Cartesian product and axiom of choice ?

[@schweinmachtbree1013]

The axiom of choice is not needed to define Cartesian products of finitely many sets, e.g. the usual product _X_ × _Y_ of two sets (the axiom of choice is only needed when choosing an element from each of infinitely many sets for which "there is no method that reliably singles out elements"* - it is easy to prove by induction that one can choose an element from each of finitely many - say _n_ - sets, and it is clear that you can choose elements from each of infinitely many sets for which there is a method for singling out elements). Therefore you do "have to choose to define the first element", but just this first choice on its own doesn't require the Axiom of Choice. However, when it comes to infinite Cartesian products, it turns out that you are spot on about there being an equivalence between Cartesian products and the axiom of choice (and in my opinion it is quite alarming when one first sees it): the axiom of choice is equivalent to the statement that the Cartesian product Π_{iϵI} X_i of any family of non-empty sets (X_i)_{iϵI} is non-empty. (the Cartesian product Π_{iϵI} X_i is defined as the set of tuples (x_i)_{iϵI} where x_j ϵ X_j for each j ϵ I) *for example you don't need the axiom of choice to be able to choose one element from each of the sets {n, n+1, ..., 2n+5} for n in *N*, even though there are infinitely many sets, because there are methods for reliably singling out elements of sets of natural numbers: e.g. just choose the smallest element (or the second smallest, or more complicated procedures like: choose the smallest odd element if there are any odd elements, otherwise choose the second smallest even element if there are multiple even elements, and otherwise choose the unique even element)

[@i_amscarface_the_legend9744]

@@schweinmachtbree1013 Thank u ! So well explained !

[@schweinmachtbree1013]

@@i_amscarface_the_legend9744 you're welcome :D

[@peterdecupis8296]

the axiom of choice is employed for the cartesian product of an infinite set of sets in the Goedel Bernais Theory: if W is an infinite set with non-vacuum elements, the cartesian product ×W is defined as the Set of Choice Functions from W to UW (the minimal Set containing all the elements of any set that belongs to W); the Axiom of Choice has to be employed in order to warrant that xW is not the null set.

[@twwc960]

Good video, but for once, I think you might have said "and this is a good place to stop" a bit too soon. You were trying to obtain the Cartesian product of sets A and B. Defining ordered pairs gets you 90% of the way there, but to finish off and demonstrate the existence of AxB you need a couple of applications of the Power Set Axiom together with one application of Separation. Good video though.

[@Stelios.Posantzis]

I'm not sure they teach that in secondary school now but I think that if not, soon they will or they should. Naive set theory is a great way to get students to think about maths more abstractly and how to circumvent its problems - i.e. how to invent maths.

[@panadrame3928]

Since Michael mentionned the pairing axiom to be a ZF-axiom this is not naïve set theory

[@anonymous_4276]

Sounds good but I think very few secondary-schoolers would even understand what axioms really are. They might use statements they consider obvious (but they haven't proven those statements from axioms) etc. It's probably a bit difficult to understand for secondary-schoolers.

[@bongo50_]

In UK secondary schools, set theory is taught to a very basic level. It pretty much just covers intersections, unions and complements. It would be great if it was taught more extensively.

[@pwmiles56]

This reminds me of the New Math of the 1960s. The part I remember was based off Brouwer's intuitionism. This is the idea our innate conception of the number zero is the empty set {}, of 1 is {{}}, of 2 is {{},{{}}} etc. I caught the tail end of this during my own schooldays but I think it fizzled soon after that. It certainly seemed pretty pointless to 16 year old me. We did do Venn diagrams. With experience of maths teaching, I think they are the better introduction to sets, being visual. Maybe Peano's axioms would suit some very bright students

[@mathboy8188]

I don't see much value in the average adult learning this. The very basics of set theory is a different story, but this kind of elegant mathematical trickery should be reserved for those who seek it out instead of being required of everyone. If you want to cram more stuff into the general public's math education, I'd recommend more probability and (especially) statistics.

[@BethKjos]

3:46 - 3:50 deserves repetition

[@malicksoumare370]

Great video

[@matematyka1358]

It's the Kuratowski's definition, after Kazimierz Kuratowski, a very famous Polish mathematician.

[@deltalima6703]

What are you trying to show here?

[@l.p.7585]

that (a,b)==(c,d) implies that a==c and b==d

[@SlipperyTeeth]

He gives the standard definition of an ordered pair in set theory. Then the proposition he proves is that this definition works how we expect ordered pairs to work - that if two ordered pairs are equal then they're equal in the first entry and equal in the second entry. The other direction wasn't proved, because it's pretty much instant - "If a=c and b=d, then (a,b)=(c,d)".

[@deltalima6703]

Seems trivial. I thought maybe he was suggesting (x,y) can be ordered, which would be interesting because I was fairly sure it cannot.

[@juandesalgado]

In common usage we are accustomed to see ordered pairs as vectors... where a "vector" would be a member of a vector space. But a "vector space" is a higher construct, which uses Cartesian products in its definition (specifically, in the definition of the addition and multiplication operations in the space). "Cartesian product" is such a basic concept, part of the very basics of set theory (where supports virtually all of the rest of mathematics), that warrants the definition of an "ordered pair" without the common resource of thinking of vectors.

[@abebuckingham8198]

@@deltalima6703 Foundational issues often seem trivial. We could, instead of constructing ordered pairs simply assume them as a basic object but in mathematics we typically try to minimize the number of assumptions. Since we can construct ordered pairs from unordered pairs we do so. It seemed like academic navel gazing to me at first but low level logic like this actually has applications in computer science. It's a thriving field these days.

[@alvarezjulio3800]

Set theory is the porn of math: love it!

[@samuelmarger9031]

My head hurts trying to understand, but I enjoyed it nontheless.

[@Janox81]

As a computer scientist, this video feels like a sin.

[@manucitomx]

Set theory is never easy, but it can be fun. Thank you, professor.

[@CM63_France]

Hi, Nice proof using those "set of sets", it reminds me a definition of the integers, which goes like this: 0 = void set n+1 (or the successor of n) = n U {n} So: 1 = {void set} 2 = {void set,{void set}} 3 = {void set,{void set},{{void set,{void set}}}} etc... We see that, with this definition, card(n)=n Ooops @Nikolas Davis 😁

[@tomholroyd7519]

⭐⭐⭐⭐⭐

[@hugohugo37]

Waaaay too picky for me. I'm fine with just saying, "hey here's an ordered pair (x,y) boom we're done"

[@schweinmachtbree1013]

This is the correct approach imo - there's no need to define everything in terms of sets just for the sake of defining everything in terms of sets; working mathematicians don't do mathematics in gory set-theoretical detail anyway, even in their published papers.

[@schweinmachtbree1013]

@@angelmendez-rivera351 Notice how I said "working mathematician". It has been long established that everything in undergraduate and postgraduate mathematics is either free from contradictions or that its consistency, if consistent, is unprovable. Therefore it is simply unnecessary for most mathematicians (even most pure mathematicians) to know about foundations - all they need to know is that sound foundations have been worked out by mathematicial logicians (in response to the foundational crisis brought on by infinitesimal calculus and the like), and if this peaks their interest then they can go and learn about ZF or homotopy type theory or what have you - but foundations don't peak the interest of most people, for example the OP of this thread. To suggest that my preferred approach and the working mathematician's approach (which includes every math paper published outside of set theory/type theory/etc. itself) is on the level of mathematics in the 1600s is a little ridiculous.

[@stephenbeck7222]

schweinmachtbree you should probably definite ‘working mathematician.’ Are mathematicians writing papers in this set theory not working?

[@schweinmachtbree1013]

@@stephenbeck7222 The term "working mathematician" means "average mathematician" or "typical mathematician", and I believe it is moreso used in the pure mathematics sphere (the term was coined by the founders of category theory Saunders and MacLane in their book "Categories for the Working Mathematician"). And there is a difference between set theory and set-theoretical foundations; not even the working set theorist would bog themselves down by going all the way down to the foundational level, e.g. implementation details like (x, y) := {{x}, {x, y}}. (a set theorist would have a good idea of what things look like "under the foundational hood", but there is no reason for them to lift up the hood because they're using set theory to do mathematics, not foundations)

[@buxeessingh2571]

And this is why I think everyone who expects to go to grad school in math needs to learn things from foundations of mathematics from the ground up.

[@schweinmachtbree1013]

Why though? - how does this help a grad school mathematician? This video just shows that ordered pairs *can* be defined formally only in terms of sets, but why would you want to? - there is simply no reason to go right down to the foundational level when doing "normal mathematics". Once the definition {{x},{x,y}} has been demonstrated one never actually does anything with it* and just "hides it under the hood" by denoting pairs by (x,y) and manipulating them according to the property (x,y)=(z,w) iff x=y and z=w. *there is perhaps one exception which is to show that the Cartesian product of two sets is a set, and hence (first-order definable) relations and functions from a set to a set are sets, but again, once this has been demonstrated that's that: as soon as one has shown that these things are sets (and hence exist as objects inside formal ZFC or whatever set theory one is using) there is no point to ever go back and look at what the fiddly definitions were

[@buxeessingh2571]

@@schweinmachtbree1013 When I started taking classes in the major, learning all these niceties forced me to learn how to think more abstractly. At the US undergraduate level outside the top schools, in advanced calculus, complex analysis, linear algebra, algebra, point-set topology, and differential geometry, I could rely on my physical intuition to get me through without needing complete precision. In foundations and category theory, I had to learn to think more abstractly on what the terms and ideas really mean beyond the obvious. Those classes forced me to grow up mathematically.

[@schweinmachtbree1013]

@@buxeessingh2571 That's a great point that I hadn't considered. As a whole I completely agree that mathematical logic and set theory improves ones abstract thinking, but I guess I have a personal pet peeve for the fiddliness of some parts of set-theoretical foundations. I think category theory is even better for abstract thinking than set theory (at least for pure math), so personally I'm hoping that category theory/categorical foundations will eventually take the place of set theory/set-theoretical foundations in the undergrad and postgrad curriculum, but again that's just my view.

[@nHans]

For Python programmers who are wondering if ordered pairs (tuples) in Python are defined the same way Michael defined it here, the short answer is: No. 😁 Now Guido van Rossum, the creator of Python, is a mathematician and computer scientist, and has incorporated many ideas from mathematics into Python. So naturally, it was worth checking if the Python tuple too would stand up to pedantic mathematical scrutiny. x = "hello" y = "world" {x, y} == {y, x} True (x, y) == (y, x) False (x, y) == {{x}, {x,y}} Traceback (most recent call last): File "", line 1, in (x, y) == {{x}, {x,y}} TypeError: unhashable type: 'set' Oops! Now what? Should Python programmers continue coding as before, ignoring the fact that the tuple is not built on solid axiomatic foundations? Is that safe? Or should we all propose and support a PEP that *(x, y) == {{x}, {x,y}}* always evaluates to *True?*

[@JGHFunRun]

@@gregorymorse8423 I think it was a joke comment. If you are correct that he's serious I'd agree that he's very wrong but I think he's making a joke