Axiom of Foundation in Zermelo Fraenkel Set Theory

Portrait of Ernst ZermeloI pointed out, in the earlier page of my blog, that Pat and Brian said in RDF Semantics, “Such ‘membership loops’ might seem to violate the axiom of foundation, one of the axioms of standard (Zermelo-Fraenkel) set theory, which forbids infinitely descending chains of membership”.

However, what is the axiom of foundation? And how it is related to ‘membership loop’? We cannot but step into Zermelo Fraenkel (ZF) set theory in order to understand RDF Semantics.

There are eight or nine numbers of axioms in ZF theory. The numbers depends on authors of books and texts. Please see ones listed in the bottom in this page, if you are interested in those axioms and ZF theory.

The axiom of foundation is expressed in logical expression as follows [1].

A [A≠Ø ⇒ ∃xA (xA = Ø)]

It means that with respect to any set A such that is not the empty set (Ø) there is an element set of A that do not share members with A. For example, x = {a} is a case in A = {{ }, {a}}, but not in the case of A = {a, {a}}. For A = {b, {a}}, there is x = {a} if ba.

This axiom actually appears as another representation of statement that every set is procedurally generated from the empty set by cumulative procedures [1].

Nowadays, the usual picture of the set-theoretic universe V is provided by the cumulative hierarchy. V is approximated by the partial universes V0, V1, V2,. . . , which are built by iterating the notion “subset of”, as follows. V0 is any set of basic objects that are not sets (numbers, lines,. . . ); a next partial universe Vα+1 is constructed from the previous one Vα by adding all its subsets (P(A) := { x | x A}):

        Vα+1 = VαP (Vα).                               (H.C. Doets, 2002)

Although the axiom of foundation is properly applicable for individuals and sets whose members are individuals and sets, only sets that include the empty set but not individuals are entities in the universe of ZF theory. In ZF theory, we start at V0 = { } = Ø to make the cumulative hierarchy. Then, we iteratively obtain V1 = Ø∪{Ø} = {Ø}, V2 = {Ø}∪{Ø,{Ø}} = {Ø,{Ø}}, V3 = {Ø,{Ø},{Ø,{Ø}}}, …, . For these cumulative sets, the following two important theorems hold.

x ∈ V ⇒ (xx)
xy ∈ V ⇒ xy

Thus, if we pick up any Vn, then Vn−1 ∈ Vn , Vn−2 ∈ Vn−1, Vn−3 ∈ Vn−2, …, and finally we reach V0. Therefore, “descending chains of membership” is always terminated at V0 in the ZF system.

I slightly shifted the point and introduced a new concept in the above discussion for the purpose of easy understanding the axiom. In the generative and cumulative hierarchy, sets at upper level are constructed with lower level sets. So, the direction is bottom up here from the bottom upward. However, note that the axiom of foundation does not explicitly mandate such constructive premise. Some of mathematicians strictly think that every set should be constructive. In fact, a = {a} is refused by this underlying attitude because we have no way to construct such self recursive abstruct sets before we obtain the members of set.

It is true that the axiom of foundation in ZF forbids infinitely descending chains of membership. Then, is the statement in RDF Semantics true such that “the semantic model given here distinguishes […] classes considered as objects from their extensions – […] things that are ‘in’ the class – thereby allowing the extension of a […] class to contain the […] class itself without violating the axiom of foundation” ? I think this statement in RDF Semantics is not valid, or if it is too severe, not enough to validate the statement. First, ZF theory does not include individuals. Second, although Pat and Brian claim that the paradox is avoided since aCEXTI (a), which means an entity in the universe is not equal to its class extention, the universal class rdfs:Resource and the universal metaclass rdfs:Class are included their extensions, namely rdfs:ResourceI = CEXTI (rdfs:ResourceI) and rdfs:ClassI = CEXTI (rdfs:ClassI) . We need further discussion to state RDF can avoid Russell paradox. I claim that we need to distinguish orders of these classes in the same way as ramified type theory, which is introduced by Russell in Principia Mathematica.

However, before we go to the discussion of ramified type theory, I would like to watch the set theory in KIF 3.0, in which sets include individuals as set members, and would like to see how Russell paradox is avoided in KIF later on.

[1] Doets, H.C.: Zermelo-Fraenkel Set Theory, http://staff.science.uva.nl/~vervoort/AST/ast.pdf (2002).
[2] Potter, M.: Set Theory and its Philosophy, Oxford Univ. (2004).
[3] Aczel, A.D.: The Mystery of the Aleph, Four Walls Eight Windows (2000).
[4] Tiles, M.: The Philosophy of Set Theory, Dover (1989).
[5] Quine, W. van Orman: Set Theory and its Logic, Harvard Univ. (1963, 1969).

Advertisements

About seijikoide

Please check my page as researcher of computer scientist.
This entry was posted in RDF, Semantic Web and tagged , , , , , . Bookmark the permalink.

2 Responses to Axiom of Foundation in Zermelo Fraenkel Set Theory

  1. footstep002 says:

    Thank you for your very nice article. It’s very helpful, since I’m pretty much a newbie on set theories.
    And I have questions about the first example, that you used to explain the axiom of foundation.
    You said that x = {a} is a case in A={{ },{a}}, but not A={a,{a}}. This may be a silly question, but why is this true? Is it because that a set of A={a,{a}} form cannot be constructed?
    Or is it, because a ‘set(in this case ‘x’)’ so called ‘foundation of a set’ can only be exist in the set that has a form of {{ },{a}}.
    Another question. How about set A={a}? Is this set also does not a case for the x={a} as a foundation too, like the A={a,{a}}?
    Please reply.

  2. seijikoide says:

    Thank you for your comment and interest, and I really apology that my reply is too late.
    The axiom of foundation means that we can find some x such that xA = Ø, where x is a member of any set A.
    In case of A = {{ }, {a}}, we can find {a}, because {a}∩{{ }, {a}}= { }.
    In case of A = {b, {a}}, we can find {a}, because {a}∩{b, {a}}={ } if ba.
    In case of b=a or A = {a, {a}}, for x = {a} we obtain {a}∩{a, {a}}={a}, but we can find x = a, as a∩{a, {a}}={ }, if a is a set.
    So, exactly it should be written as “not a case A = {a, {a}} for x= {a} ”, but it is “a case A = {a, {a}} for x=a”. (Sorry!)
    In fact, every entity in ZF is a set including the empty set. Therefore, the axiom of foundation is true for this postulate.
    If so, we can pick a member that satisfies the axiom of foundation. Then, furthermore we can recursively pick a member that satisfies the axiom from the previously chosen member. Thus, finally we can arrive at the empty set, because we started with a set of finite cardinal numbers, and pick a member of the set. Note that { }∩A = { }, and { }∩{ } = { }.
    Thus, descending chains of membership is terminated at the empty set in ZF.
    Oppositely, this axiom is a requirement to inhibit the infinite descending chains of membership.
    In case of A = {a}, a member is only a. Therefore, a∩{a}= ?? is a question.
    If the left side a is {a}, {a} is resulted. But a = {a} never happens. Of course, { } ≠ {{ }}.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s