# Thread: Set theory problem

1. ## 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))\}$ ?

2. 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.

3. Originally Posted by MoeBlee
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.

4. Originally Posted by Ester
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?

5. 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".

6. Originally Posted by MoeBlee
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.

7. 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.

8. 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.

9. I have few questions:
Originally Posted by MoeBlee
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 $ \in g$ so dom(g) = A and if y = g(x), then yRx (*)."

Originally Posted by MoeBlee
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?

10. 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.