Talk:Zermelo–Fraenkel set theory

From Wikipedia, the free encyclopedia

WikiProject Mathematics
Mathematics Portal
This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.
Mathematics rating: Start Class High Priority  Field: Foundations, logic, and set theory

Archives:

Contents

[edit] "Union" textual vs. equation

For any set x, there is a set y such that the elements of y are precisely the members of the members of x.

The text says (all) the members of (all) the members. However, the equation says '\exist D', that is 'one member'. Is this correct ? I'm tagging the article as contradictory. --Hdante 08:13, 5 March 2006 (UTC)

The axiom of union is here correctly formulated. The axiom defines B := ∪A. B is called the union set of A. B collects precisely all sets C which are member of any set D in A. Otto ter Haar 12:02, 5 March 2006 (UTC)

That's true ! :-) --Hdante 17:26, 5 March 2006 (UTC)
The current formula doesn't say that, though. That formula says that B contains all the sets which are members of sets in A, but it doesn't say it contains only those sets. The formulation given in Axiom_of_union avoids this problem. Rsmoore (talk) 16:22, 17 March 2008 (UTC)
Both formulations are common; there's no problem. The formulation in the axiom of union article follows from the one here and a comprehension axiom. The axioms here are, for the sake of consistency, all taken from a single source (Kunen's book). The text here does not claim that the set A is literally the union, only that it contains all the elements that are in the union. As Kunen points out, this formulation is easier to work with when the goal is to verify that the axiom is satisfied by a particular model. — Carl (CBM · talk) 17:52, 17 March 2008 (UTC)

[edit] replacement implies comprehension

The article used to say that the ZFC axioms minus comprehension imply comprehension. Here is one proof that this is true when the empty set is assumed to exist. Let A be any set and assume we want to form the set W = \{ x \in A \mid \phi(x)\}. Let Z be any set in A such that φ(Z) (if there is no such set Z then W is the empty set). Let ψ(x,y) say that either y = x and φ(x) or y = Z and \lnot \phi(x). Thus ψ defines a function from A to A such that any element satisfying φ maps to itself, and all the other elements map to Z. Then the range of ψ is exactly the set that we are trying to construct, and this exists by replacement on the formula ψ. This proof doesn't need to be in the article, but I think the statement is interesting. CMummert 23:53, 4 September 2006 (UTC)

The problem is that you are assuming a version of the axiom of replacement which is not the one in the article. The one in the article says:
\forall A\,\forall w_1,\ldots,w_n [ \forall x \in A \exists ! y \phi \rightarrow \exists Y \forall x \in A \exists y \in Y \phi].
Notice that there is no limit on how many extra elements one can put into Y and thus it could be that Y might just be the same as A in your example. One needs the axiom of separation to convert this version of replacement into the one which you are assuming. JRSpriggs 08:20, 5 September 2006 (UTC)

While I expect the version stated in the article to be equivalent to the one CM is thinking of, there remains a problem. The description of replacement still states that the generated set Y is the co-domain of the function, which is no longer true. Correct me if I'm wrong, but the cryptic mention of a restriction to avoid paradox can't possibly account for this discrepancy since making the set larger risks creating more paradoxes, if anything.

I rephrased the English description to make it agree with the formal axiom. The cryptic comment about a restriction is referring to the restriction on the free variables of the formula. I don't think the two versions of replacement are equivalent in the absence of comprehension, which is why JRSpriggs's comment settled the matter for me. CMummert · talk 23:52, 27 January 2007 (UTC)
Let me expand on what CMummert said about the restriction on free variables. Y should not appear free in φ. If it did, then the existential quantification over it on the right side of the implication would cause trouble because then the function implicitly defined by φ would change from what it was on the left. JRSpriggs 12:40, 28 January 2007 (UTC)

[edit] Why no mention of the axiom of the empty set?

nt —Preceding unsigned comment added by 86.146.254.177 (talk) 07:10, 16 December 2007 (UTC)

Presumably Kunen chose to omit it because it can be deduced from the other axioms. From the axiom of infinity we get the existence of a set. From the axiom schema of specification we can reduce that set to the empty set. It is unique by the axiom of extensionality. JRSpriggs (talk) 08:08, 16 December 2007 (UTC)
The current article is incorrect in its treatment of the empty set. In the preamble to the axiom of infinity, The current article asserts the existence of the null set is derived from extensionality, regularity, specification, pairing, union, and replacement. This is false, because each of those axioms are (vacuously) true if no set exists. Hurkyl (talk) 09:19, 1 February 2008 (UTC)
I tried to fix this problem. How do you like the new version? Notice that the axiom of infinity itself supplies the existence of a set which is needed to show that the empty set exists. JRSpriggs (talk) 06:47, 3 February 2008 (UTC)
I don't see anything false, so I'm mostly content. However, I notice another problem. The presentation invokes the axiom of infinity in order to prove the existence of the empty set -- and yet the statement of the axiom of infinity presupposes that the empty set exists! I think it's not possible to simultaneously: write a correct article, keep Kunen's axioms in the form he wrote them, and to omit the axiom of the null set (or whatever equivalent Kunen used). Hurkyl (talk) 03:32, 5 February 2008 (UTC)
First-order logic, with no axioms at all, proves that something exists--if you want to allow the opposite possibility you have to go out of your way to do it. Then by applying separation, you get that the empty set exists. You don't need the axiom of infinity for this. --Trovatore (talk) 03:37, 5 February 2008 (UTC)
That depends on your choice of logical axioms, or semantically speaking, on what you define to be a model. While customary axioms prove \forall x \varphi \to \exists x\varphi or \exists x (x=x), and customary model theory does not consider the empty set as a model, it may be convenient to also consider empty models (e.g, in algebra, when you would like to have a theorem "the intersection of two subsemigroups is a subsemigroup), and hence to use a system of logical axioms in which "there exists something" is not derivable.
In set theory we are of course not interested in empty models; all the more reason to explicitly postulate the empty set, just to make this point clear.
Since the ZFC axioms are anyway not independent of each other, I think that the derivability of the empty set axiom is not a good reason to exclude it. (The fact that Kunen excludes it, on the other hand, is a good reason. Just not a very good one.)
A reason to include it is the role that it plays in the relationship between replacement and separation. Replacement in its strict form (namely, that the class of function values is a set, not only contained in a set), implies separation in the case that the set \{x \in z: \varphi(x)\} is nonempty, but you need the empty set axiom to get the full separation axiom from replacement. (Of course all this is not relevant when we use the ZFC axioms, but it might be worth a remark when we discuss them.)
Aleph4 (talk) 12:13, 5 February 2008 (UTC)

See also Talk:Axiom of empty set#Does logic imply the existence of the empty set?. JRSpriggs (talk) 09:24, 6 February 2008 (UTC)

Of course, I should have checked there... Aleph4 (talk) 14:00, 6 February 2008 (UTC)
Trovatore is right in that I didn't consider shunting the postulate that something exists off to the logical axioms -- but as Aleph4 points out, that postulate only exists in certain formulations of first-order logic. If the intent is for the article to rely on this postulate, then I assert that it needs to be explicitly stated someplace.
The problem, as I see it, is that the choices made in the article has many drawbacks. The restriction to a certain kind of logic is unnecessary, it complicates the exposition, and it diverges from traditional presentations of ZFC. The benefits are... fewer axioms?
The previous discussion sounds like Kunen's list of axioms actually did include an axiom asserting the existence of a set. Am I reading that correctly? Hurkyl (talk) 02:51, 14 February 2008 (UTC)
Well, what is standardly called "first-order logic" does imply that something exists. Modifications of FOL that avoid that implication are called free logic. --Trovatore (talk) 03:10, 14 February 2008 (UTC)

[edit] Zermelo-Fraenkel-Skolem set theory

To my knowledge, the more inclusive name has it's third contributor - Skolem - included. The article should be changed accordingly, in my view. See: [1]. --151.202.103.127 (talk) 21:20, 12 January 2008 (UTC)

See WP:COMMONNAMES. --Trovatore (talk) 21:21, 12 January 2008 (UTC)

[edit] Equality without equality

The defining properties of equality are reflexivity (x=x) and the substitution property. The substitution property says that if x=y, then any predicate containing x implies the result of replacing some (or all) of the occurrences of x in the predicate by y. From these one can also show that equality is symmetric and transitive.

If the logic being used does not provide equality, then it can be defined as a macro (abbreviation) for the substitution property. In the case where there is only the one binary relation, ∈, this becomes ∀z[z∈x↔z∈y] ∧ ∀z[x∈z↔y∈z] . This definition works regardless of the axioms used.

However, Palnot has been putting in ∀z[z∈x↔z∈y] which is not the full definition. True, it is equivalent in the presence of the axiom of extensionality (when suitably formulated). But we should not make a definition dependent on an axiom being present. JRSpriggs (talk) 11:35, 15 April 2008 (UTC)

[edit] Rephrasing "The Axioms" intro, and Axiom of Infinity

I think it's again worth bringing up the article's inconsistent handling of the empty set and infinity. I cite three specific problems:

  • The article claims to present Kunen's axioms, but to the best of my knowledge, Kunen does include an axiom 0 asserting the existence of a set. Previous revisions of the page stated that that axiom was omitted, but that seems to have been removed.
  • The statement of the axiom of infinity assume makes use of the empty set symbol, which has not been previously defined.
  • The discussion following infinity asserts that infinity (together with other axioms) imply the empty set, making the presentation circular. Also, given the current convention that 'first-order logic' implies the existence of an object (which is Kunen's omitted axiom), infinity is not needed to prove the existence of the empty set. (which is the original reason why the axiom was stricken from the Wikipedia article)

I think the best solution would be to actually include Kunen's axiom 0, and follow it with comments that the axiom is redundant given Wikipedia's conventions, and define the empty set there. But due to the fierce resistance against it seen in the past, I offer the following compromise:

Use this as the introductory paragraph: (addition in bold)

There are many equivalent formulations of the ZFC axioms; for a rich but somewhat dated discussion of this fact, see Fraenkel et al. (1973). The following particular axiom set is from Kunen (1980). Kunen's axiom 0 asserting the existence of a set is implied by Wikipedia's conventions regarding first order logic, and omitted from the list below. The axioms per se are expressed in the symbolism of first order logic. The associated English prose is only intended to aid the intuition.

and use this as the discussion following infinity (after mentioning omega)

... \varnothing is defined to be the unique set satisfying \forall x: x \notin \varnothing. It's existence is assumed by this statement of infinity, and can be proven from the axiom of specification and Wikipedia's convention that first-order logic asserts a set exists. Its uniqueness follows from the axiom of extensionality.

--Hurkyl (talk) 02:17, 29 April 2008 (UTC)

This is partly an argument over what First-order logic is, and partly an argument over how to present the axiom of infinity clearly to the reader.
I disagree with having an existential assumption built into first order logic. Thus I believe that some axiom must explicitly affirm the existence of a set (in order for this to be the ZFC we know and love, which does have sets). The axiom of infinity does assert the existence of a set (intended to be an infinite set) — a set which contains any empty set which might exist and any successor of any set which might be a member of this infinite set.
The article states the axiom as:
\exist X \left [\varnothing \in X \and \forall y (y \in X \Rightarrow S(y) \in X)\right ].
Many people would be able to (sort of) understand this version of the axiom who would be unable to understand a more correct version such as:
\exist x \left [\forall e (\forall k \lnot (k \in e) \Rightarrow e \in x) \and \forall y \forall z ([y \in x \and \forall w (w \in z \iff (w \in y \or w = y))] \Rightarrow z \in x)\right ].
This more correct version does not assume the existence of the empty set nor of the successor of a set, but once one has it one can prove that they do exist. JRSpriggs (talk) 14:20, 29 April 2008 (UTC)
There's the third option,
\exist x \left [\exists e (\forall k \lnot (k \in e) \and e \in x) \and \forall y \forall z ([y \in x \and \forall w (w \in z \iff (w \in y \or w = y))] \Rightarrow z \in x)\right ].
I think we can finesse the issue of free first order logic by again pointing out that Kunen (and ZFC, really) assumes that there is at least one set, and that in some formalizations this is built into the semantics of FOL.
Really, I am not fond of emphasizing the analysis of which axioms imply which other axioms. While this is of technical interest, it's only a minor point in the study of ZFC as an axiomatic framework for set theory, because ZFC does include all the axioms, regardless whether they are independent or not. So I favor solutions that don't make the reader dwell on independence too long. — Carl (CBM · talk) 15:22, 29 April 2008 (UTC)
I tend to agree with both of you. In my humble opinion, the absolute most important things are correctness and reader friendliness; my intent was a compromise with what I perceived as a resistance against reintroducing redundancy in hopes of getting an improvement accepted by the community. But if I'm just imagining things, I'd be happy to draft up a bolder suggestion. --Hurkyl (talk) 03:21, 1 May 2008 (UTC)
I added a paragraph to discuss the existence of at least one set - I am relatively satisfied by that. I also moved and lengthened the discussion of the existence of the empty set. I am less happy with that, I hope others can improve it. — Carl (CBM · talk) 12:14, 1 May 2008 (UTC)