Some of the basic axioms of ZFC set theory can seem a bit uninteresting on their own. But when you take them together, and reason your way around them, you can find some interesting things.
Let's start by looking at the axiom of extensionality. Pretty simple, right? All it does is define what set equality means. It says that two sets are equal if, and only if, they have the same members: that is, a set is completely determined by its contents.
How much more trivial can a statement about sets get? It really doesn't seem to say much. But what happens when we start thinking through what that means?
The way we normally think of sets, they're collections of objects. So, imagine a set like {red, green, blue}, where the three values are atoms: that is, they're single objects, not collections. What does the axiom of extensionality say about that? It says that red, green, and blue are not atoms?
Why? Well - let's look at the axiom of extensionality again: (∀A,B: A=B ⇔
(∀C: C∈A ⇔ C∈B)). So - does red = blue? Well, if they're atoms, then
yes, red=blue, because nothing is in red, and nothing is in blue. Since neither has any members, they're equal.
In fact, if we follow that reasoning through, there's only one possible atom: the only set with no members is the empty set. So anything else we want, we're going to have to represent using some kind of collection.
As a result of that, along with the axiom of specification, we can show that the axiom
of the empty set is actually redundant. After all - the axiom of specification basically
says that if you can describe a collection of values by a predicate, that collection is a class. So take the predicate P(x)=false; that's a set with no values. Also known as the empty set. So the empty set exists, and it's the only set with no members - aka the only atom.
- Log in to post comments
It's not obvious to me why red should have no members.
From the strongly typed object oriented programming point of view, xâred shouldn't be false, it should instead raise an exception due to red not being a set.
Or, if you like to pretend that there can be nothing but sets, and encode everything else as sets somehow, then red, blue, etc really are different sets, and their members depend in some arbitrary way on the encoding.
D. Eppstein: From an earlier post, giving all of the axioms: "Now, it's time for a first look at the basic list of axioms. An important thing to remember as you look at them is that axiomatic set theory is intended to be a foundational theory of mathematics - and so the only objects that exist in the domain of the theory are sets - no numbers, no functions, nothing. It's sets, all the way down."
So we do like to pretend that there can be nothing but sets.
So we do like to pretend that there can be nothing but sets.
I understand that you do. And I even have some idea why: because it lets you work with simpler axioms than ones allowing other kinds of objects. But what I don't understand is the attitude that, because you can code things as sets, that you must code things as sets, and that the encoding is actually meaningful. Put another way: when someone asks me what they numbers 0, 1, 2 are, I don't answer that they're really shorthand notation for the sets {}, {{}}, {{},{{}}}, etc. Rather, what 0, 1, 2 really are to me are: anything at all, as long as they behave the way one expects integers to behave. It's not their structure that's important, only their behavior. Isn't that what extensionality means, after all?
So your supposed paradox about the atoms red, blue, green has this flavor to me: rather than talking about how red, blue, and green behave (they are atoms that are all different from each other) you are talking about how they are encoded, and then being surprised when your axioms prevent you from finding an encoding of sets-with-atoms as sets-without-atoms that directly encodes a set as itself, that encodes membership of encoded objects as the same as membership of their representations, and that encodes equality of the encoded objects as equality of their representations. But, after all, why does it matter whether an encoding with those properties exists, and why should it be surprising that it doesn't?
If extensionality applies to all objects in the theory (as it does in ZFC) then, as you say, it forbids urelements -- objects that are not sets.
But it only is really able to "define" set equality in conjunction with the Axiom of Foundation.
Without Foundation, your set theory could have ill-founded sets, including sets that contain themselves as elements. Suppose I consider two different sets: Set A has just one element, itself -- A = { A }. Set B also has one element: itself B = { B }. Now, is A = B? Extensionality is silent -- by extensionality, A = B if and only if A = B -- which is just a tautology. Without foundation, our set theoretic would be allowed to have any number (including zero) of singleton sets whose only elements are themselves.
With foundation, on the other hand, we're guaranteed to get down to empty sets eventually any time we compare two sets. So it makes a little more sense to say that extensionality and foundation combine to define equality between sets -- extensionality to give the recursion, and foundation to guarantee that the recursion terminates.
D. Eppstein: It's not that you must encode them, it's that you must encode them if you want to put them in a set. In programming terms, it's a collection that expects the items to all have collection interfaces.
> Set A has just one element, itself -- A = { A }
Which axioms did you use to proof that A={A} is a set?
I think you're drifting to naive set theory, where you can define a set by specifying its elements with a formula. If you could build a set like A={A} in ZFC without the foundation axiom, the foundation axiom couldn't save ZFC from inconsistency: On the one hand the axioms without foundation would say "there is a set A={A}", on the other hand this would conflict with foundation.
So you would be able to proof "there is a set A={A}" as well as the negation "A={A} is not a set". This would be fatal to whole ZFC set theory.
(IMHO)
There is another (older) axiom of equality, ultimately traceable to Leibniz. It is wonderfully symmetrical to the axiom of extensionality. While the latter states that sets are equal when they have the same elements
A = B iff (\forall x)(x \in A iff x \in B)
according to Leibniz axiom, sets are equal when they are elements of the same sets:
A = B iff (\forall x)(A \in x iff B \in x)
Another point of symmetry is that while extensionality is incompatible with Ur-elements (atoms, sets having no elements), Leibniz axiom is incompatible with proper classes ("sets" that are not elements).
Chris, he's not asserting that ZFC minus foundation can prove the existence of such sets. Rather, he's using that ZFC minus foundation can't dissprove their existence, and thus there's a model which has them.
Yes, fine, and the only sets that exist are those that can be shown to exist, on the assumption of the empty set. No colored atoms.
But some people insist on starting with first order logic with equality. Then extensionality must become a theorem.
Yes, fine, and the only sets that exist are those that can be shown to exist,
Not so. It's consistent to assume that (Godel did, and it's how he proved the consistency of Choice and the Generalized Continuum Hypothesis), but one needn't, and we often don't.
But some people insist on starting with first order logic with equality. Then extensionality must become a theorem.
Not so. You still definitely need extensionality as an axiom.
Yes, in the cold morning light I disagree with my comment last night. Actually what I'm thinking now (contrary to what I said last night) is that without first order logic with equality, there is no "=" to axiomatize. Instead, extensionality is a definition, or abbreviation introducing a new symbol.
hmmm, I'd better check my other late night comments ;(
The axiom of extensionality sets up an equivalence relation. Non-trivially it makes it clear that crisp sets have a two-valued structure to them. It _enormously_ restricts the logical universe of set theory, as most (almost all) logical universes have more than two values. It only looks so simple and trivial, because so many people have assumed two-valued logic for so long, especially in mathematics.