Results 1 to 15 of 15

Math Help - theorem about two sets (enderton)

  1. #1
    Member
    Joined
    Oct 2010
    From
    Mumbai, India
    Posts
    203

    theorem about two sets (enderton)

    Hi

    Here's a problem from Enderton's set theory book (1977) page 39.

    "Assume that A and B are given sets and show that there exists a set C such that
    for any y

    y\in C\Leftrightarrow  \exists x \in A(y=\{x\}\times B)

    In other words, show that \{\{x\}\times B\lvert x\in A\} is a set "

    since this is an existence statement, I am unsure as to how to cook up C.

    can anybody give some direction ?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4

    Re: theorem about two sets (enderton)

    Think of ways to cook sets:

    The obvious way is to cook "up" to make a set and then cook "down" using separation to get your desired set.

    Now, what are some ways to cook "up" sets? Well, pairing, union, power, for example ... Think of using one of those.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Oct 2010
    From
    Mumbai, India
    Posts
    203

    Re: theorem about two sets (enderton)

    I was thinking if we can choose

    C=\{\{x\}\times B\;\lvert x \in A\}
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4

    Re: theorem about two sets (enderton)

    That's the set we want to PROVE exists as described.

    We have sets A and B, so we want a set S constructed (by already given methods) from A and B such that for each x in A, we have {x} X B is in S. Then we'll use separation to cut S down to ONLY those sets of the form {x} X B for some x in A.

    One of our already given methods is Cartesian products. So we have A X B. Now, think about applying one of these - pairing, union, power set - to A X B to get our set S.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Oct 2010
    From
    Mumbai, India
    Posts
    203

    Re: theorem about two sets (enderton)

    moeblee

    let me put the problem in complete logical langauge.
    Assume that A and B are given sets.. show that

    \exists C\forall y[y\in C\Leftrightarrow  \exists x \in A(y=\{x\}\times B)]

    in existence theorem, we first claim that let x be such an object and then set out to prove that x satisfies the properties given in the theorem. since the problem i stated is an existence problem , can't we claim that C be equal to

    C=\{\{x\}\times B\;\lvert x\in A\}

    and then set out to prove the property that

    \forall y[y\in C\Leftrightarrow  \exists x \in A(y=\{x\}\times B)]

    and another question.... when Enderton says that "show that ..... is a set"
    what does it mean ? how does one show that some thing is a set. according to
    Set (mathematics) - Wikipedia, the free encyclopedia
    set is taken as an "undefined primitive" in axiomatic set theory. so how do we prove something is a set if definition of set is not there.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Feb 2011
    Posts
    147
    Thanks
    3

    Re: theorem about two sets (enderton)

    The only set whose existence is explicitly stated by the standard axioms of set theory is \emptyset. Several other axioms give rules of creating new sets out of sets whose existence we have already estabilished. For example, the axiom of pairing tells us that if A and B are sets, then also {A,B} is a set. Without knowing that some sets A and B do actually exist, this wouldn't tells us much. But we do know that the empty set exists. So let

     A :=\emptyset
     B :=\emptyset

    The axiom of pairing now tells us that \{\emptyset,\emptyset\} is a set. By the axiom of extensionality we have \{\emptyset,\emptyset\}=\{\emptyset\}.
    Thus \{\emptyset\} is a set.

    This is how it works.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4

    Re: theorem about two sets (enderton)

    Quote Originally Posted by issacnewton View Post
    show that

    \exists C\forall y[y\in C\Leftrightarrow \exists x \in A(y=\{x\}\times B)]
    Right.

    Quote Originally Posted by issacnewton View Post
    in existence theorem, we first claim that let x be such an object and then set out to prove that x satisfies the properties given in the theorem.
    What we need to do in this problem is find a C that satisfies the property:

    Ay(y in C <-> Ex(x in A & y = {x} X B))

    Quote Originally Posted by issacnewton View Post
    can't we claim that C be equal to

    C=\{\{x\}\times B\;\lvert x\in A\}
    As long as you keep in mind that merely wrtiting out something in set abstraction notation doesn't entail (in all this, we're in Z set theory, or in later chapters, ZF or ZFC) that there is an object that has the property described. For example:

    We can write

    J = {y | y not in y}

    but there is no J such that Ay(y in J <-> y not in y).

    Quote Originally Posted by issacnewton View Post
    \forall y[y\in C\Leftrightarrow \exists x \in A(y=\{x\}\times B)]
    Okay, but that's not advancing the answer any further than from where you started.

    The problem is simpler than you seem to think it is. I gave you a direct hint:

    Take A X B. Find a set C that you can build up from A X B so that if x in A we have {x} X B is in C. To build up such a C from A X B, which of these do you think is a good building tool in this case - pairing, union, or power? Answer that question and you've basically solved the problem.

    Quote Originally Posted by issacnewton View Post
    [when Enderton says that "show that ..... is a set"
    You already stated it okay. For example, in this case, to say show "{y | Ex(x in A & y = {x} X B} is a set" means: Using first order logic (whether formal or informal) applied to the axioms of set theory show ECAy(y in C <-> Ex(x in A & y = {x} X B)). In other words, show that the set abstraction notation "{{x} X B | x in A}" PROPERLY refers, i.e. that there is a set C having the property Ay(y in C <-> Ex(x in A & y = {x} X B)).

    Quote Originally Posted by issacnewton View Post
    Set (mathematics) - Wikipedia, the free encyclopedia
    set is taken as an "undefined primitive" in axiomatic set theory. so how do we prove something is a set if definition of set is not there.
    (1) Enderton is not using 'set' in such a formal sense, as an actual predicate (whether primitive or defined). He's using it in the informal sense just discussed. Indeed, in the context of Z set theories (including, e.g., Z , ZF, ZFC), we don't have to mention the word 'set' at all. When Enderton uses the word 'set' in such a context we can couch whatever he says without using the word 'set'. For example, in the problem you quoted, you could just as well state it:

    Show that there exists a C such that for all y, we have y in C <-> Ex(x in A & y = {x} X B).

    That's all there is to it in Z set theories. Mentioning the word 'set' in that context is not necessary.

    (2) As to the more technical point, if we're very precise about the matter (and not just speaking somewhat loosely as some set theory intro chapters are wont to do) it is NOT the case that 'set' is a primitive of Z set theories. Yes, in CLASS theories such as NBG, the predicate 'is a set' is primitive. But it is NOT primitive in Z set theories. As a mere formality we could DEFINE 'is a set' in Z set theory, but it would be trivial since, in Z set theory, our definition would provide the thereom "Ax x is set". (In NBG it is NOT the case that "Ax x is set" is a theorem.)
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4

    Re: theorem about two sets (enderton)

    Quote Originally Posted by ymar View Post
    The only set whose existence is explicitly stated by the standard axioms of set theory is \emptyset.
    Actually, the existence of a unique empty set is provable from the axiom schema of separation.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member
    Joined
    Feb 2011
    Posts
    147
    Thanks
    3

    Re: theorem about two sets (enderton)

    Quote Originally Posted by MoeBlee View Post
    Actually, the existence of a unique empty set is provable from the axiom schema of separation.
    That's true, but the axiom is usually included nevertheless, at least in my country.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762

    Re: theorem about two sets (enderton)

    naively, i would think it helpful to note that {x} x B ought to be a subset of A x B given that {x} is a subset of A....so i would be inclined to obtain all subsets of A x B to have at my disposal...
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Member
    Joined
    Oct 2010
    From
    Mumbai, India
    Posts
    203

    Re: theorem about two sets (enderton)

    moeblee, I think I sort of get what you are saying. Maybe I read too much in that problem. I have downloaded another book by J. Donald Monk, which is about Morse-Kelley set theory. In that book, he says set is something which belongs to something other. If some object is not member of some bigger stuff, then that object is not a set. Thats how he eliminates Russell's paradox. So there is this sharp distinction between sets and classes. I find that a better approach. There is more clarity. I don't know why ZFC is follwed more widely. I know only basic logic, so lot of things which are discussed about the differences between these theories is beyond me. That's why I decided to learn set theory from Enderton, which follows ZFC.
    Quote Originally Posted by MoeBlee View Post
    Take A X B. Find a set C that you can build up from A X B so that if x in A we have {x} X B is in C. To build up such a C from A X B, which of these do you think is a good building tool in this case - pairing, union, or power? Answer that question and you've basically solved the problem.
    I played with some example sets A and B. I think we will first need to take \mathcal{P}(A\times B). C can be extracted from there, right ?
    But which axioms then we use to extract the required C ?
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762

    Re: theorem about two sets (enderton)

    perhaps the separation schema could then be invoked to specify the element of P(AxB) which has the properties you seek? just a random guess....
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Member
    Joined
    Oct 2010
    From
    Mumbai, India
    Posts
    203

    Re: theorem about two sets (enderton)

    is separation schema same as subset axioms ? enderton talks about subset axioms but there is no mention of separation schema.......
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4

    Re: theorem about two sets (enderton)

    Quote Originally Posted by issacnewton View Post
    [a] set is something which belongs to something other.
    A set is a class that belongs to a class. Urelements (if they are any) also belong to a class, but are not sets.

    Usually, we have a certain distinguished object, that I'll call 'the empty class', and the empty class has no members. Then for any object x there are six possiblities:

    (1) x is the empty class and x is a member.
    (1a) x is the empty class and x is not a member.
    (2) x is not the empty class and x has no members and x is a member.
    (2a) x is not the empty class and x has no members and x is not a member.
    (3) x has members and x is a member.
    (4) x has members and x is not a member.

    With (1) we call x 'the empty set' or '0'.
    Usually, (1a) does not occur.
    With (2), we say x is an urelement.
    Usually, (2a) does not occur.
    With (3) we say x is a non-empty set.
    With (4) we say x is a proper class.

    Then also:

    x is a set iff (x is the empty set of x is a non-empty set)
    x is a class iff (x is a set or x is a proper class)

    Quote Originally Posted by issacnewton View Post
    I don't know why ZFC is follwed more widely.
    Possible reasons (1) We don't need proper classes to do the mathematics that set theory is called on to do, so it is easier to not have to qualify whether something is a set or a proper class. (2) Z set theories require only one primitive non-logical symbol, viz. 'e', but class theories require two primitive non-logical symbols, viz. 'e' and 'is a set'. (3) Z set theory historically came before class theory and so it got more use through habit among mathematicians.

    There are advantages to using class theories though. For example, sometimes we do want to talk about certain classes that are "too big" in set theory and to do that with set theory we end up going to the meta-language to talk about formulas in place of classes. For example, with Z set theories, instead of talking about the class of ordinals, we have to instead, in the meta-language, talk about the FORMULA 'x is an ordinal' and formulate theorems as schemata.

    Quote Originally Posted by issacnewton View Post
    take \mathcal{P}(A\times B). C can be extracted from there, right ?
    Right.

    Quote Originally Posted by issacnewton View Post
    But which axioms then we use to extract the required C ?
    As is typical for such problems, we take an instance of the axiom schema of separation.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4

    Re: theorem about two sets (enderton)

    Quote Originally Posted by issacnewton View Post
    is separation schema same as subset axioms ?
    With Z set theories, we often refer to the axiom schema of separation as "subset axioms", but in class theories, such as NBG, the subset axiom is a somewhat different thing.

    Quote Originally Posted by issacnewton View Post
    enderton talks about subset axioms but there is no mention of separation schema
    I don't have the book with me, but are you sure Enderton doesn't call it the 'axiom schema of separation'?

    Anyway, in Z set theories, the basic concept of the axiom schema of separation is that when we have a set S, we also have any subset of S defined by a formula. The axiom schema of separation is what provides us subsets of sets as those subsets are defined by some condition.

    So in the case, let S = P(A X B) and the condition is "Ex(x in A & y = {x} X B)". Then the axiom schema of separation gives us the subset of S that is {y | Ex(x in A & y = {x} X B)}.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Enderton 3.7 Problem 2
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: January 14th 2012, 08:32 AM
  2. [SOLVED] theorem about finite sets
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 12th 2011, 04:31 PM
  3. Enderton 3.1 Problem 6 (p. 193)
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: December 3rd 2011, 12:12 PM
  4. [SOLVED] theorem about family of sets
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: July 30th 2011, 10:48 PM
  5. Bayes Theorem Problem Sets
    Posted in the Advanced Statistics Forum
    Replies: 6
    Last Post: September 10th 2009, 06:05 AM

Search Tags


/mathhelpforum @mathhelpforum