Results 1 to 10 of 10

Math Help - Set theory problem

  1. #1
    Junior Member
    Joined
    Mar 2010
    Posts
    35

    Set theory problem

    I have a set theory problem (something to do with cardinals, I think):

    Let A be non-empty and  R \subseteq A \times A relation in which holds  \forall x \exists y (yRx) . Show that there exists funtion  f: \omega \rightarrow A so that  f(n+1)Rf(n) with every  n \in \omega .

    I was thinking to use induction, but how construct the set for that? Is it something like

     T = \{n \in \omega \mid A \approx n \Rightarrow \exists f: \omega \rightarrow A (f(n+1)Rf(n))\} ?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    With the axiom of choice, this is trivial:

    Let x in A
    Let f(0) = x.
    Let f(n+1) = the least member v of A such that vRf(n).

    But also, it's very close to the axiom of dependent choice itself. Should poke around to see whether it is equivalent to the axiom of dependent choice.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Mar 2010
    Posts
    35
    Quote Originally Posted by MoeBlee View Post
    With the axiom of choice, this is trivial:

    Let x in A
    Let f(0) = x.
    Let f(n+1) = the least member v of A such that vRf(n).

    But also, it's very close to the axiom of dependent choice itself. Should poke around to see whether it is equivalent to the axiom of dependent choice.
    How it is trivial? I can't see it. Can you open up it little bit more to me? I assume you are talking about "real" Axiom of Choice, not the ones which are equivalent with it.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    Quote Originally Posted by Ester View Post
    How it is trivial? I can't see it. Can you open up it little bit more to me? I assume you are talking about "real" Axiom of Choice, not the ones which are equivalent with it.
    Fair enough. Good point. Actually, I mean the well ordering principle. Now do you see it?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    P.S. Even though I couched it in terms of the well ordering principle (i.e., I said "the least v"), with just a little work, one could put it in terms of the axiom of choice version "every relation has a subset that is a function with domain the same as the relation".
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Mar 2010
    Posts
    35
    Quote Originally Posted by MoeBlee View Post
    P.S. Even though I couched it in terms of the well ordering principle (i.e., I said "the least v"), with just a little work, one could put it in terms of the axiom of choice version "every relation has a subset that is a function with domain the same as the relation".
    I'm still stuck with this exercise.
    I need to use AC or some of it's other versions to solve this problem.

    This is how far I have "solved" it (It's not much):

    R \subseteq A \times A is relation, so based on AC version: "For every relation R there exists function F \subseteq R so that dom(F) = dom(R)", there exists a function F so that F \subseteq R and dom(F) = dom(R).

    And now I can't get further.
    Any help? Please...
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    Let 'w' stand for the set of natural numbers.

    By the axiom of choice, let g be a subset of R such that g is a function and dom(g) = dom(R).

    So g is a function, and dom(g) = A, and if y = g(x) then yRx.

    Now let c be some member of A.

    Define a function f with dom(f) = w as follows:

    f(0) = c
    f(n+1) = g(f(n)).

    By a trivial induction, verify that range(f) subset of A, and that for each n in w, we have f(n+1)Rf(n).

    Done.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    See how that's basically the same idea as my first proof using the well ordering principle. With the axiom of choice, I used my function g. With the well ordering principle, I used "the least v such that vRx". Basically the same idea.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Junior Member
    Joined
    Mar 2010
    Posts
    35
    I have few questions:
    Quote Originally Posted by MoeBlee View Post
    Let 'w' stand for the set of natural numbers.

    By the axiom of choice, let g be a subset of R such that g is a function and dom(g) = dom(R).

    So g is a function, and dom(g) = A, and if y = g(x) then yRx.
    How did you know that dom(g) = A?
    I did this part like this:
    "Let's define function g: \forall x \in A \exists y \in A so that <x,y> \in g so dom(g) = A and if y = g(x), then yRx (*)."

    Quote Originally Posted by MoeBlee View Post
    Now let c be some member of A.

    Define a function f with dom(f) = w as follows:

    f(0) = c
    f(n+1) = g(f(n)).

    By a trivial induction, verify that range(f) subset of A, and that for each n in w, we have f(n+1)Rf(n).

    Done.
    Why did you choose c from A and why you defined that f(0) = c?
    I have also difficulties with the second induction:
    My set is:
    T = \{n \in \omega \mid f(n^+)Rf(n) \}
    Empty set belongs to set T, because f(0) = c and f(0+1) = g(f(0)), so by the definition (*) f(0+1)Rf(0).
    Let's assume,that k belongs to set T, so f(k+1)Rf(k).
    f(k+1) = g(f(k)) and f((k+1)+1) = g(f(k+1)), so by the definition(*) f((k+1)+1)Rf(k+1). So (k+1) belongs to set T.

    Is that right?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    I got dom(g) = A from the axiom of choice that you stated. dom(R) = A, so dom(g) = A. And I got dom(R) = A from your initial statement that AxEy yRx (actually that's too great a claim - since it would make dom(R) a universal set, which does not exist in ordinary axiomatic set theory - so the statement should be Ax(x in A -> Ey yRx).

    As to the definition of g, just take it from your axiom. We have as a premise that

    R is a relation and dom(R) = A.

    So from your axiom we get that there exists a g such that

    g is function and g is a subset of R and dom(g) = A.

    It's that simple.

    /

    I chose c as an arbitrary member of A. We have as a premise that A is nonempty. So I just let c be some arbitrary member of A.

    Then, I used the definition by recursion theorem to define a function f such that dom(f) = w. That starts by setting f(0) to some value in A. So I let c be that value.

    /

    Your induction is correct. But just use the way I got g instead of your somewhat unclear "definition" of g.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. a problem about set theory
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: July 10th 2010, 10:29 AM
  2. Theory Problem
    Posted in the Calculus Forum
    Replies: 1
    Last Post: April 21st 2009, 07:53 PM
  3. Set theory problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 10th 2009, 02:43 AM
  4. Is {} same as {{}} set theory problem
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: October 13th 2007, 04:25 PM
  5. Set Theory Problem
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: February 14th 2007, 12:37 PM

Search Tags


/mathhelpforum @mathhelpforum