Sets are truly amazing things. In the history of mathematics, they’re
a remarkably recent invention – and yet, they’re now considered to be the
fundamental basis on which virtually all of mathematics is built. From simple things (like the natural numbers), to the most abstract and esoteric things (like algebras, or topologies, or categories), in modern math, they’re pretty much all understood
in terms of sets.
So what is a set? A set is really just an abstract way about talking about a
collection of distinct things. Really, in the simplest version of set theory,
that’s it. Such a simple notion! And yet – from there, the entire world of math opens up. (As an aside, in the rest of this article, I’m going to be talking about simple set theory, or naive set theory; there is a more advanced variant that was part of the attempt to create a more restrictive version of set theory that avoided paradoxical statements.)
Sets don’t have any intrinsic concept of ordering – that is, you can’t talk about the “first” thing in a set, or which of two things in a set comes first. Doing that involves creating an operation on the members of the set – and then you’re talking about the ordering properties of the operation, not of the set itself.
When we write sets, we typically write them as a list of members surrounded by curly braces: {1, 2, 3}, {“bob”, “joe”, “mike”, “sam”}, etc. The set with no members,
called the empty set is written either {}, or ∅. We also often use a notation called a set comprehension, which specifies the members of a set in terms of some property. {x | x is a friend of mine}, {x | x < 200}, etc.
Commonly, we talk about a very small number of basic fundamental operations that we can talk about for sets:
- Membership, written a∈B. Given an object “a”, a∈B is a predicate which is true if and only if “a” is one of the objects in B.
- Intersection, written A∩B. Given two sets A and B, A∩B is a set containing the things that are members of both A and B – that is {x | x∈A and x∈B}.
- Union, written A∪B. Given two sets A and B, A∪B is a set
containing everything that is in either A or B – that is, {x | x ∈ A or x ∈ B} - Subset (written A ⊆ B) and equality. Given two sets A and B, A⊆B if and only if every element of A is an element of B. If both A⊆B and B⊆A, then we say that A=B; if A⊆B but B⊄A, then we say that A is a proper subset of B, written A⊂B.
- Difference, written AB. Given two sets A and B, AB is the set consisting
of the elements of A that are not also elements of B; that is,
{x : x∈A and x∉B}. - Symmetric difference, written AΔB. Given two sets A and B, AΔB is
the set consisting of the union of AB and BA: {x : (x∈A and x∉B) or (x∉A and x∈B)}.
So, why is this stuff so fundamental? What’s so powerful about this? Let’s
look at one simple example. We saw the natural numbers the other day – let’s look at
how to define the natural numbers using sets:
- We start by saying that ∅ is the number 0.
- One is the set containing 0: {∅}.
- Two is the set containing 0 and 1: {∅,{∅}}.
- Three is the set containing 0, 1, and 2: {∅,{∅},{∅,{∅}}.
- The number N={0,1,…,N-1}.
- Given a number N, the successor to N consists of the set N∪{N}.
Within this construction, N<M if and only if N∈M. And if you take the time
to work it through, you can see that this construction satisfies the Peano axioms –
these are the integers.
The main problem with this version of set theory is that it’s very easy to
create paradoxical statements. Since we can have sets that contain sets, and there are no restrictions, then we can create all kinds of strange structures. The classic example is: X={S | S∉S } – that is, the set of all sets that are not members of
themselves. It’s a simple paradox: is X∈X? If X is a member of itself, then by the definition of X, it’s not a member of itself; but if it’s not a member of itself, then by its definition, it must be a member of itself!
The existence of things like this in naive set theory were considered unacceptable, a sign that there was something wrong with the construction of set theory that needed to be fixed. A lot of effort went into creating more structured versions of set theory that tried to avoid paradoxes, but Gödel ultimately showed that no matter how much you did to restrict it, you were trapped – either you wind up with a theory that is incomplete (includes true statements that can’t be proven) or inconsistent (contains paradoxical statements). But that is definitely not a subject for a basics post!
Also not for a basics post: Sets are monads.
It really should be pointed out that this construction of the natural numbers is just one construction from set theory. What it tells us is that if we have a model for the axioms of set theory, we can use it to construct a model of the natural numbers. This construction is by no means unique.
Interestingly, we were taught this at the very beginniing of the 1st grade elementary school, before even learning how to write numbers.
I had always wondered why one couldn’t just add an ordering to sets. You one line explanation cleared up that two year confusion for me :).
Instead of just writing these blog posts, you should write a comprehensive manual that starts with sets and logic and goes all the way up to Haskell!
I’m assuming that you can also define the real numbers in a conceptually similar fashion? How might one do that?
grad: First, you need to define negative numbers. That’s easy. You represent a negative number as a pair of whole numbers (x,y) which means x-y.
Then, you define fractions. Once again, that’s a pair of integers (x,y) which means x/y.
Finally, you can then construct the reals by defining the set that includes the rationals, but is closed under infimum and supremum, such as via Dedekind cuts.
Only set theory is required.
I’m glad to see this series of articles on mathematical basics. However, I have to take issue with the last paragraph.
Which is exactly what it was. A set fitting this definition can’t exist, as you yourself showed, so something was wrong with the principles used in the construction.
One way to fix this is to say that you’re not allowed to use “weird” formulas like S∉S. This was Russell’s and Quine’s position, and it leads to a theory called New Foundations. I don’t know much about it, but what I do know looks broken.
The other fix is to say you’re not allowed to take all the objects in the universe into a single set. This was Zermelo’s position, and arguably Cantor’s, and the one which prevails today in mainstream mathematics in the form of Zermelo-Fraenkel set theory.
Well, no, you’re not trapped, if you keep your goals modest. It’s true that one can’t generate a consistent, complete, comprehensible set theory (by Gödel’s 1st incompleteness theorem). However, it appears that Zermelo-Fraenkel theory, which is comprehensible in the sense of the above theorem, is consistent — in your turn of phrase, it “avoids paradoxes”. (Of course, thanks to Gödel’s 2nd incompleteness theorem, we can never be sure of that!)
True enough.
I guess one can quibble about the basic operations in naive set theory. I have seen symmetric difference before, but quite frankly forgot about it by disuse.
What I was taught early (but never really used either) was the universe construction. The universal set U is defined by the context, and that allows to define the complement to a subset A; C(A) := { x : x ∈ U and x ∉ A }. (I see that the symbolism has changed to AC now.)
You can define complete and consistent theories, just not ones that allow you to do number theory (for example). There’s one lurking right in your post: set theory of finite sets is complete and consistent. (This isn’t the most exciting set theory, but it’s sufficient for the needs of relational databases.) This probably sounds like an incredibly pedantic point, but there’s some confusion most laypeople who’ve heard of Goedel on the impossibility of complete, consistent theories that I would like to stamp out.
Actually, the complement is of course a set too, so the old symbolism for it was really CA IIRC. (The bold C should just be larger font, but it didn’t seem to work in the comments.)
Does anyone have any idea why set theory became the fundamental basis upon which virtually all of mathematics is built? I mean, the basis concept is inconsistent and the formal substitutes are incomplete, as MarkCC says; so why? (Apparently there was even a conspiracy to silence the founder of set theory in its formative years, so there must be some good reasons why it overcame that and came to rule the roost.)
grad:
That would be a “coming soon” sort of thing… There’ll be a basics post on real numbers soon.
The main way that I know for constructing real numbers is called Dedekind cuts. That’ll be in the reals post.
Personally, I’m fond of the surreal numbers. The surreals are a very clever way of constructing numbers created by the great John Conway. They’re a remarkably clever construction. There’s some things about them that are inferior to the Dedekind cuts construction – but the surreals have the really cool property that infinitely large and infinitely small numbers can be represented and manipulated very naturally.
Enigman:
The reason why set theory became so dominant is, I think, pretty clear.
You can construct mathematics on the basis of all kinds of things – but if you look at those constructions, inevitably, they all end up requiring some notion of a collection of distinct things. Whether you start from natural numbers, or
from predicate logic, or from geometry – you still always wind up with collections of distinct objects in your basis.
Once set theory became established and accepted as valid math, it became obvious that in all of the different possible constructions, the collections at the heart were
sets.
You can get the reals from the surreals by imposing an extra condition on the construction. It’s exercise 17 in the back of Knuth’s Surreal Numbers (a problem originally suggested to Knuth by John Conway). A number x is defined to be real if -n < x < n for some integer n, and if x falls in the same equivalence class as the surreal number
({x – 1, x – 1/2, x – 1/4, …}, {x + 1, x + 1/2, x + 1/4, …)}.
This topic is also discussed in chapter 2 of Conway’s On Numbers and Games. Theorem 13 proves that dyadic rationals are real numbers, and Conway then deduces that each real number not a dyadic rational is born on day ω (“Aleph Day” in Knuth’s book).
Conway says:
Submitted without further comment.
Mark wrote: “. . . the most abstract and esoteric things (like . . . categories) . . . [are] pretty much all understood in terms of sets”
I don’t study category theory at all, but my uninformed impression was that it is a rival to set theory, not something that can be subsumed by the latter.
“Sets don’t have any intrinsic concept of ordering . . . . [Ordering] involves creating an operation on the members of the set”
We’d usually call that a relation, not an operation.
“if A⊆B but B⊄A, then we say that A is a proper subset of B”
Maybe you just couldn’t find the symbol you really wanted, but read literally that’s a false statement, because if A=B then A⊆B and B⊄A.
Do they even still teach (simple) Set Theory in K-12 anymore?
I know that it was part of the big “new math” thing in the 60s, and by the 70s it had faded in popularity (sad that topics in education can still be subject to a popularity contest). I recall that even as early as the 2nd grade, every math book between then and 6th grade had sets as the chapter 2. Every book. Only the teachers never touched it. They skipped that chapter every time, every year. Depressing to no end, ’cause I was sick and bored to tears of 3digit by 2digit multiplication after having had it for 4 years in a row. If anything, THAT repetition is what ultimately killed my study habits and created the underachiever I was through high school.
At any rate, 7th grade “pre algebra” finally actually taught this set stuff that had been denied me for so long. it was part of the pre-algebra “learn to use rules” approach that would become important in applying transformations in algebra and in geometric proofs.
Only today, its not that way anymore. I looked at a “pre algebra” book today (at a friends house; i don’t have kids, much less kids that old) and no set theory exists at all in it.
its just an extremely dense overview of *everything* of high-school mathematics up to the point of analytic geometry. just shy of actually taking a derivative. it had variables, formulas and functions, graphing, geometric functions, algebra “1” transformations, quadratic formula, all that stuff all blended into a single dense text.
i really don’t know how they are teaching math anymore, but i do recall that there were experiments in the 60s (one that my mother was subject to) that basically tried to teach “all maths at once”, a sort of integrated approach over the 4 years of high school. granted, today, she’s an elementary ed teacher and doesn’t have to use it, but it bothers her greatly that when i talk about what i considered high school math concepts so clearly she honestly can not tell whether or not she actually learned any of it. the vocabulary was all thrown at her so densely that its just a blur (and she was describing it this way 20 years ago).
but really, that book seemed like a “throw it all at ’em and see what sticks, ’cause it doesn’t matter ’cause they’ll get exactly the same next year” approach, and that bothers me because it was *exactly* that attitude when taken with arithmetic that destroyed my study habits and mentally bored me to tears, literally, when I was 11 and was told i’d be doing exactly what i’d mastered (I had the “100s” to prove it) when I was 8.
Set theory works well as a basis for much of mathematics. It’s a powerful method of expression and definition, but it’s not without its drawbacks.
One of its biggest drawbacks is that it really isn’t very applicable to geometry without a lot of trouble. The concept of sets with discrete elements and no order or structure does not blend easily with the geometric model of infinite point with measures and locations. There are ways around this, but it involves a lot of work compared to Euclid’s original method.
I think myself that set theory is used very inappropriately at times, with entire theories being presented exclusively through set theory alone. It adds even further to the esotericism of mathematics when it wasn’t really neccessary. Sets lend themselves to greater mathematical abstraction, which you want. But they also make it more difficult to present concrete examples, which you don’t want. The key is to balance these two, an art that has not been mastered by modern mathematicians.
One of its biggest drawbacks is that it really isn’t very applicable to geometry without a lot of trouble.
Hmm? The reals and functions are easily built as sets, and now it’s a simple enough matter to build a norm. Now you’ve got everything you need to do geometry.
I caught the aftereffects of the “New Math” when I studied arithmetic in elementary school. We did a lot of “regrouping” tens into ones and hundreds into tens, and there may have been some talk about “commutation”. However, we didn’t talk about sets. I first brushed against set theory (along with topology, group theory and lots of other topics) by reading Keith Devlin’s Mathematics: The New Golden Age in seventh grade.
(My mother says she was taught how to take square roots with pencil and paper. Oh, how the times change!)
Looking back at this, I don’t think omitting sets was a terrible idea. A schoolteacher can only provide material on which they can test the students later: the teacher can give word problems, quiz students on the definitions of terms and so forth. If you’re not trying to build a foundation for mathematics, explore certain paradoxes or cook up transfinite numbers, what good is set theory?
Listen to Feynman explaining what was wrong with textbooks in the 1960s:
In fourth, fifth and sixth grades, I went to a private school where they used the Mortensen Math booklets. My gripe with these is that they get you very good at shuffling numbers and filling in the blank spaces in various types of formulae, but they don’t give you a sense of what you’re actually doing. Fourth grade is a little too early to dive into mathematics for the abstract fun of it; there has to be some connection to solving everyday problems. While I could technically say that I was “doing calculus” — differentiating and integrating polynomials, really — I didn’t even have a sense that these numbers had something to do with slopes and areas.
Set theory became the foundation of mathematics because it offers an agreed-upon standard for a mathematical object to “exist”. It exists if you can show that it can be constructed in terms of sets.
The incompleteness of set theory is not limited to set theory: any sufficiently powerful theory expressible in first-order logic suffers from incompleteness. We could abandon first-order logic, but no one has found an alternative widely-agreed to be better.
Category theory can be viewed as a competitor to set theory, but it’s not necessarily so. Most mathematicians don’t regard them as in conflict.
“The incompleteness of set theory is not limited to set theory: any sufficiently powerful theory expressible in first-order logic suffers from incompleteness. We could abandon first-order logic, but no one has found an alternative widely-agreed to be better.”
Somewhere, somehow you got your wires crossed Walt. The problem is not with FOPL as this is both complete and consistent as proved by a gentleman called Kurt Gödel in his doctoral thesis.
We don’t really want to do that, because first-order logic is complete: Any theory in first-order logic is consistent if and only if it has a model. Yup, there is even a Gödel completeness theorem.
Harald:
Well… First order logic is complete, and yet, incomplete.
Given a first order logic, you can define a model for it which is complete. But there will inevitable be another equally valid model for the same logic – embeddable in the same logic – which is incomplete. That’s the trick that Gödel used – by taking statements that are about numbers and arithmetic operations in the standard model of the logic, and showing that there’s an equally valid interpretation of those as meta-statements about the logic. Those meta-statements are the classic incompleteness
statements: either statements that can’t be proved (so there’s a model in which the logic is incomplete) or inconsistent (there’s a model where the logic is contradictory).
“Given a first order logic, you can define a model for it which is complete. But there will inevitable be another equally valid model for the same logic – embeddable in the same logic – which is incomplete.”
Löwenheim-Skolem.
Thony, please assume I’m not an idiot. I’m trying to answer Enigman’s question. The completeness theorem (which I’m familiar with) is somewhat besides the point for his question, which is: why do we use set theory, even though naive set theory suffers from Russell’s paradox, etc. My point is that the problem is not limited to set theory. If you can say it more clearly, then feel free.
I meant to say, please assume I’m not an idiot until I clearly prove otherwise. It’s hard to judge tone on the Internet, but Thony’s comment really stuck in my craw.
Ew. The Dedekind cut definition is the most annoying, I think. The rigorous definition that’s useful in analysis is the one with Cauchy sequences; the intuitive way is with infinite decimals. I know the infinite decimal definition isn’t especially chic, but it’s still good enough for proving completeness, and in number theory it helps show the analogy between R and Qp.
Very true, but that’s not the sense which is meant by “competitor”. You can construct whole numbers using the set construction above, or using the Peano axioms, or using cardinality (i.e. the equivalence classes of finite sets under isomorphism), or… you get the idea.
These constructions are “competitors” in the sense that they all work, and some are seen as more “natural” than others in different contexts, but they’re formally equivalent, and hence not in conflict.
Let me try restating my point about FOL, since my first version obviously sucked. Mathematics formalized in first-order logical axioms is either a) of fairly weak power, or b) susceptible to incompleteness results. Goedel’s argument needs much less than the full power of set theory to be expressed. Essentially, once you can express number theory, you can construct Goedel’s unproveable statement. People have suggested that the solution is to abandon first-order logic, but no compelling alternative has been found.
(Goedel’s completeness theorem, somewhat ironically, does require a considerable amount of set theory to be proven. It requires a weak form of the axiom of choice.)
Blake Stacey said:
I find that if you’re trying to understand probability and statistics, set theory is very helpful and powerful. For example visualising ( or drwaing) Venn diagrams of the sets involved makes Bayes’ theorem self explanatory.
People have suggested that the solution is to abandon first-order logic, but no compelling alternative has been found.
It’s more than just that nothing better has been found. In some respects, there can be nothing better. I’d have to double check this, but I’m fairly certain FOL is the most powerful logic that satisfies Completeness and Löwenheim-Skolem.
“Thony, please assume I’m not an idiot.”
Walt please assume that I am an idiot who should turn on his brain before posting anything! I completely misunderstood and misinterpreted your post and said something really stupid and obviosly insulting, please forgive me. I made my last (Löwenheim-Skolem) posting before going to bed and took no further part in the discussion. At some point in the night I woke up and realised what I had done because I suddenly reaslised what you had actually intended with your post. A very valid and very important point. What makes it even worse is that my logic teacher with whom I have worked on and off for more than twenty-five years is a constructivist so if anybody should have understood your point then I should! Your anoyance is totally justified and I apologies once again for any offence caused. My only saving grace is that Harald obviosly made the same mistake although his posting was not quite as provokative as mine. In future I will try to remember to engage my brain before activating my keyboard.
True enough. . . but this is a matter of overlapping circles. Skirting on the edge of a No True Scotsman (or No True Set Theorist) fallacy, I have to ask just how set-theoretic it really is.
And again, the real question (or at least the one I had on my mind) was not whether one should teach set theory at all, but whether it needs to be taught at the youngest grade levels, like they did with the New Math. Is Bayesian probability a subject for third grade?
(That’s not a rhetorical question!)
I’m a “victim” of the set-theory based new math, and I actually think it’s a good thing.
I think that the problem with it is the same problem that you’ll have with any method of teaching math: it’s highly dependent on the skills of the teacher – and most elementary school teachers aren’t very good at math. I happened to get lucky, and have a couple of really good ones.
The reason that I think set theory is a good thing is mostly because it’s got a good intuition behind it (kids can grasp the idea of “a bunch of things”); it lets kids pick up the ideas of basic arithmetic not just as rote, but with some amount of meaning behind it; and it gets them thinking at least a little bit about math as more than just arithmetic. Very basic set theory is really easy, but it sets up the idea of math as abstraction in a nice way.
Personally, I think that a lot of the “new math” backlash was hype. I look at people who were taught with new math,
and compare them with people who were taught with old math, and find that the vast majority of both groups don’t really understand any of it. It’s just easier to criticize new math, because with old math, the students could recite their multiplication tables. Half of them had no clue of what the hell they meant, but they could recite them – and for a bunch of mathematically illiterate parents and politicians, it was easy to point at the old math students reciting the table and say “See, *they* learned math”; whereas the new-math students can draw venn-diagrams, which the innumerates don’t understand.
“And again, the real question (or at least the one I had on my mind) was not whether one should teach set theory at all, but whether it needs to be taught at the youngest grade levels, like they did with the New Math. Is Bayesian probability a subject for third grade?”
Blake
Because you have said that this is not a rhetorical question I will give you my thoughts on the subject. I’m am old enough that I went through the system with old maths but was still in the school system as the new maths was being introduced and so lived through the controversy. There were good arguments made for some aspects of the new math and some very good arguments made against some aspects of it. For positive aspects see some of the books of Ian Stewart (Concepts of Modern Mathematics for example). For arguments against I recommend Why Johnny Can’t Add and Why the Professor Can’t Teach both from Morris Klein. Having said that I think Mark C-C hits the nail on the head with his posting above.
On the specific question of Bayesian Probability, no it probably isn’t a good topic for third grade but naive set theory when handled right probably is and they are both together with Venn diagrams (which are actually Euler diagrams!) models of Boolean algebra so if you teach set theory in the third grade you are already laying a good basis for probability theory at a later date.
Hi Mark!
are the ‘union’ and ‘membership’ symbols supposed to be the same? I’m guessing that the union is where they have ‘co-membership’, but I seem yo remeber a big “U” or something for union?
Why Johnny Can’t Add and Why the Professor Can’t Teach both from Morris Klein!!!! That should of course read Morris Kline!
Oh, for a moment I thought you deklined the arguments against.
Thought-provoking comments, all. . . I suppose part of the problem lies in the different things a mathematics education has to do: in order to be any good at all, it has to include abstraction and application together in one package. That’s not a trivial problem, particularly when the teachers aren’t well-equipped and, as MarkCC said, the parents and the lawmakers don’t have the experience necessary to arrive at good judgments.
Maybe the topic of “what should we teach in elementary school” should be made into a top-level post. I’m sure it will attract flames, er, discussions (and MarkCC will have a little more spare cash from SEED to buy post-rock albums).
L. Luo, “On Non-Standard Set Theory Models and the Relativity of Real Numbers”, Abstracts of the AMS, Vol. 28, No. 1, Issue 147, 2007, 1023-03089, p.13.
“In a reception with students in the 1980s Hao Wang asked what was the continuum. Set theory is written in a countable language which according to LST Theorem in model theory it has a countable model S. The set of all real numbers R in S should have only countably many elements in R. Are there truly uncountably many real numbers? Using model theoretic methods we discover that most of the real numbers can not be identified, we can never know their digits, and it would not produce any defective theorems if they do not exist in a set theory model. We also propose a new idea to suggest that the number of real numbers have the relativity. It is to say that it looks different from different angles. (Received July 30, 2006)”
Nice post, MCC. Out of curiosity, is this set description of the natural numbers the one Bertrand Russell ‘sets’ forth in his Introduction to Mathematical Philosophy? I never quite grasped his definition there…
MarkCC says: “Once set theory became established and accepted as valid math, it became obvious that in all of the different possible constructions, the collections at the heart were sets.” Indeed, but why did set theory become established, as the theory of collections? Was it because it was so simple it could not be false? If so, then the paradoxes must have been upsetting, and if so then it is no wonder that mathematicians accepted a clumsy but not necessarily inconsistent substitute. Would such a substitute have become established in the first place? (It is hard to say, but there were alternative theories of collections.)
Walt says: “Set theory became the foundation of mathematics because it offers an agreed-upon standard for a mathematical object to “exist”. It exists if you can show that it can be constructed in terms of sets.” Indeed, but how did it come to be so agreed-upon? After all, my two hands are (I notice as I type this) two things, but I doubt if that is because there is something that behaves like the number 2 within set theory. Surely it is because there is something against which such a set-theoretic entity would have to be compared (for us to regard it as the “existing” 2).
davidp says: “I find that if you’re trying to understand probability and statistics, set theory is very helpful and powerful. For example visualising (or drwaing) Venn diagrams of the sets involved makes Bayes’ theorem self explanatory.” I agree that pictures help enormously in mathematics. E.g., Euclid’s axioms are good because they encapsulate (with intuitive clarity) what we think (with generality) as we follow a picture-proof. The modern set-theoretical axioms are not like that, although the inconsistent ones were almost like that. The modern ones allow Kolmogorov’s theory of probability to be built upon Lebesgue’s theory of measure (even though both of those great mathematicians were not set theorists, but Intuitionists!), but therefore they face problems, e.g. Banach-Tarki in the measure theory, and Levy’s paradox in the probability.
Blake Stacey says “Maybe the topic of ‘what should we teach in elementary school’ should be made into a top-level post.” Maybe. I loved (naive) set theory at school, and skipped it later because it seemed like it was going to be so obviously true it would be boring! I did physics instead, and discovered problems that were answered with the ‘fact’ that the maths is (axiomatic) set theory. That made me mad, and so now I do philosophy! But the sets we use in the sciences are probably OK (much as classical physics is OK if you’re only jetting about within the solar system).
Enigman said:
To my intuition, part of the explanation is in Gõdel’s completeness theorem already mentioned, which says (although from within set theory so it is a bit circular) that if a mathematical theory expressable in first order logic is consistent, a prerequisite for it existing in any reasonable sense, then it has a model as sets, that is, it exists within set theory.
Enigman: I don’t understand your objection. Set theory isn’t as simple as the number 2, but modern mathematics is not as simple as the number 2. Despite that, mathematicians are able to develop apparently correct intuition about sets. While naive set theory leads to paradoxes, Zermelo’s formulation does not seem to, and in fact there are many dramatic extensions of it that also don’t seem to lead to paradoxes. So set-theoretic paradoxes are no longer a problem. Incompleteness phenomena remain, but incompleteness arises in much weaker systems than set theory (such as Peano arithmetic).
Mathematicians ran into the problem in the nineteenth century of deciding what it meant for something to “exist”. For example, Dirichlet’s function that’s 1 if a number is rational, and 0 if a number is irrational. Does such a function exist? Mathematicians adopted the answer of “
Thanks; your points are good ones, and deserve a more professional reply than the following. A mathematical theory should be consistent I agree, but we don’t even know that set theory is consistent, so consistency relative to set theory is only informative if we have already accepted set theory as the standard; and so I circle back to my question. But you are probably right (about it being part of the answer), it would depend upon how the completeness theorem was regarded by the mathematicians of the day, I guess. Of course, an intuitionistic theory might be consistent and yet impossible to embed properly within set theory… Maybe Category Theory is better than Set Theory ? But then, maybe something even bigger would be even better; and maybe only part of that–a non-set-theoretical part–is true in the sense of corresponding with the mathematical structures instantiated by physical worlds… I like the idea of maths being true in all possible worlds (so I don’t like the idea that we might have picked the wrong foundations, and wonder why we took that risk).
(“Beep Beep Into the Night…”) Regarding the number 2 and Peano arithmetic, Walt, for me the thing about 2 is that, famously, 2 + 2 = 4, certainly (and applicably). There may be non-standard natural numbers in a first-order logical system, but we all know that they are not really natural numbers, because we have a very sound intuition about arithmetic (so this first-order model of arithmetic seems to be sufficiently inexact for it to have introduced uncertainties). The thing is, the corresponding intuitions about sets (i.e. naive sets) are demonstrably unsound!
Now, maths is indeed more complex than the number 2, so we like rigorous proofs (to eliminate human error, et al). But surely we don’t introduce rigor by regarding the natural numbers as sets; we introduce uncertainties. Personally, I would prefer to see our absolutely certain arithmetic in the foundations of mathematics, and axiomatic sets in just one branch (as one possibility). Maybe I’m wrong; but consider Fermat’s Last Theorem. There was a lot of evidence that it was true, so most of us believed it to be true, but it had not been proved. We wanted the certainty of a proof. Maybe, just maybe (we thought), it was false, only happening to be true for the numbers we had looked at. Now it has been proved… and yet there may still be reasonable doubts, the proof being within analytic number theory, if we do analysis within set theory. It seems unscientific to try to introduce mathematical rigor by replacing talk of numbers with talk of sets (e.g. von Neumann’s ordinals), as though we were replacing talk of water with talk of H2O (?) (Personally, I blame positivism, but that’s another story…(“…it goes on and on and on”))
I’m not a mathematician, but it seems to me that constructive methods aren’t as powerful or even convenient. At least physicists grab whatever expressive math they find that fit their problem.
They aren’t especially threatened by the fact that there is no mathematically proof for their quantization methods, for example. They can prove that the method works. Instead they may complain about mathematicians ‘obsessiveness’ for proof ‘instead of results’ such as new methods.
The Banach-Tarski paradox points out a bizarre consequence when using AC. I looked into my old book (Cohn, “Measure Theory”) and the only use of AC in the basics I could see was for set definition. And to show that not all subsets if R are Lebesque measurable, which can only be done by ZF set theory with AC added, apparently.
Are you sure that one can’t do measure theory based on ZF set theory, and usually uses naive theory for convenience and more power? Or are you simply complaining that the Banach-Tarski construction isn’t measurable? The later isn’t a failure of measure theory as I understand it, but a consequence of using AC.
Seems interesting. Unfortunately I can’t find any paradox mentioned with Levy’s work. Can you give a short description?
Levy’s paradox (it was attributed to him by someone else, I forget who) is the famous one that concludes with there being no uniform probability distribution over the natural numbers: 2 people choose numbers at random (with a uniform distrubution), and whichever number the first one chooses, there are only that many smaller numbers, but infinitely many larger numbers, so the second one is likely to choose a bigger number. But the same reasoning applies to the number the second one chooses: contradiction.
The reason why I think that it is a problem, is that it appears to have a modern physical instantiation, if the probabilities of quantum mechanics are single-case propensities (as argued in http://www.geocities.com/potential_continuity/physicalprobability.html (hope that link works)) and if the natural numbers form an actual infinitude.
Thank you! I have no idea why your site didn’t turn up in my googling.
It was an interesting argument, and I learned something new (or perhaps relearned something I ought to know). The inability to form an uniform probability distribution over the whole of the natural numbers seems natural in retrospect. (One side bounded, the other not.)
It seems you are philosophizing about infinity and probability from a good background of math and philosophy, which seems like a good idea. However, you have started to discuss physics, which is quite another ball game.
I’m not familiar with the more intricate aspects of quantum mechanics, but AFAIK as most other parts of theoretical physics it is using frequentist probabilities (for better or worse). Specifically here because it must formally handle infinite dimensional Hilbert spaces.
I wont knock other probability concepts, but I believe bayesian probabilities runs into formal difficulties in QM. They are, I believe, formally based on Cox axioms and thus properly defined over finite sets. Could propensities as you discuss have the same problem?
In any case, as I understand it you are also extracting single-case probabilities from QM processes. Here a frequentist would probably say that the probability for single cases isn’t well defined, and that we would get limited information from such cases. In effect, they could reject the specific use of the extracted numbers. If that is so, frequentist probability could be compatible with both QM and the Levy paradox.
With this construction of natural numbers, what is the definition of divisibility?
Foxy:
With this construction, division is exactly as you’d expect. The construction defines a multiplicative inverse; division by x is multiplication by the multiplicative inverse of x. In other words, x/y = x*(y-1).
MarkCC said, earlier: “Enigman: The reason why set theory became so dominant is, I think, pretty clear. You can construct mathematics on the basis of all kinds of things – but if you look at those constructions, inevitably, they all end up requiring some notion of a collection of distinct things.”
But for that we need only plural logic, surely? I suspect that the reason why sets are so dominant is that they give us something for nothing – the set of nothing, the set of both nothing and the set of nothing, etc. (Then maths can look as pure as it feels it must be!)
RE Torbjörn: the physics I refer to is simply such as says that the monitor you are looking at is a physical object (it probably has little to do with whatever theoretical physicists are doing these days), and the QM is just the QM of chemistry, and Young’s 2-slit experiments, etc. That is, I presume that such elementary experiments are telling us that the underlying stuff of reality is well modelled by Schrödinger’s equation. I take it for granted that there is some such stuff. And the use of the basic equations of QM does seem to be vindicated by experience.
50 years ago, Popper realised that many physicists were not really frequentists. They took the probabilities of the QM equations (which are real numbers) to be saying something about frequencies, something that could be tested against observed frequencies; but, therefore, they were not frequentists, because frequentism is either finite or infinite. If it is finite then the probabilities are not real numbers. If it is infinite then they say nothing about our finite observations – they cannot be tested against observed frequencies (since each value for the limit frequency is compatible with any initial set of values).
So, they actually believed in single-case propensities. The propensity bit is the idea that the QM equations model something real, something chancy that is tested via frequencies. The single-case bit is essentially the idea that it affects a single particle in the 2-slit experiment, and that widely separated things might be causally independent. There are many possible theories of such things, only one of which will be the true one (but who knows which one that will turn out to be – if theoretical physicists thought about such things perhaps they could help us to find out!).
ASKING ABOUT SETS
Hello there! Do you know about the common mistakes in solving sets? And can you show me how…please…
Shin:
This in not a place to get people to do your homework for you.