or is there a proof that such function doesn't exist?

Printable View

- Jul 12th 2010, 09:40 AMavonmis there a function that is a member of its domain?
or is there a proof that such function doesn't exist?

- Jul 12th 2010, 09:49 AMPlato
- Jul 12th 2010, 10:08 AMavonm
i think my question is clear since you should know what is a function, you should know what is the domain of a function, and you shoud know what is a member of a set.

So, to be even more clear, i am asking if there is a function f such that f belongs to the domain of f (or if there is a proof that such f does not exist).

It's unclear what you mean by 'violation of types'. - Jul 12th 2010, 10:27 AMPlato
I think that you are the one that does not understand what a function is.

Here is the definition.

Suppose that each of $\displaystyle A~\&~B$ is a set.

The statement that $\displaystyle f$ is a function from $\displaystyle A$ to $\displaystyle B$ means.

1. $\displaystyle f\subseteq (A\times B)$

2. if $\displaystyle x\in A$ then $\displaystyle \left( {\exists y \in B} \right)\left[ {(x,y) \in f} \right]$

3. $\displaystyle \left[ {(x,y) \in f \wedge (x,z) \in f \to y = z} \right]$

Please explain your question using the correct definition of function. - Jul 12th 2010, 10:44 AMavonm
if you prefer i'll use your definition

i'm asking to prove

there are A, B sets and f function from A to B such that f belongs to A

or to prove this is false

(i.e. for each A, B sets and f function from A to B f does not belong to A) - Jul 12th 2010, 11:35 AMundefined
You are looking for $\displaystyle \displaystyle f$ such that $\displaystyle \displaystyle f \in A$ and $\displaystyle \displaystyle f \subseteq (A \times B)$. I think you might be able to get away with this using a bunch of empty sets, but I'm not sure.

Edit: To clarify, suppose $\displaystyle \displaystyle A = \{\emptyset\}, B = \emptyset, f: A \to B$. It seems then that $\displaystyle (A \times B) = \emptyset$ and that $\displaystyle \displaystyle f$ is unique and that using Plato's definition $\displaystyle f = \emptyset$ giving $\displaystyle \displaystyle f \in A$ and $\displaystyle \displaystyle f \subseteq (A \times B)$ as desired.. but I am shaky on this. - Jul 12th 2010, 01:05 PMJose27
I think there cannot be a function with codomain $\displaystyle \emptyset$, since the very definition of function requires the existence of an element in the codomain (if the domain is not empty). On the other hand for every set $\displaystyle B$ there exists exactly one function $\displaystyle f_B:\emptyset \rightarrow B$, in which case $\displaystyle f_B$ (the empty function) satisfies the requirements. On any other case this makes no sense without identifying the domain with some subset of the product.

- Jul 12th 2010, 01:14 PMPlato
The is at least one difficulty with that example.

Using the notation $\displaystyle B^A$ to stand for all functions from $\displaystyle A\to B$.

Here is a standard exercise from Halmos’ little book. (p33)

Exercise: (i) $\displaystyle Y^{\emptyset} $ has exactly one element, namely $\displaystyle \emptyset$, whether $\displaystyle Y$ is empty or not; and (ii) if $\displaystyle X$ is**not empty**then $\displaystyle \emptyset^X $ is empty.

Now look at your example again. Recall that $\displaystyle \{\emptyset\}$ is no empty.

Also look the requirement #2 in the definition. Consider the existential operator. - Jul 12th 2010, 01:18 PMundefined
- Jul 12th 2010, 01:36 PMundefined
At the risk of embarrassing myself further, is it legal to construct the following infinite sets A and F?

A = {a, {(a,b)}, {(a,b), ({(a,b)},b)}, ...}

B = {b}

F = {(a,b), ({(a,b)}, b), ({(a,b), ({(a,b)},b)}, b), ...}

In case it's hard to follow, start with

A_0 = {a}

Look at the function from A_0 to B

F_0 = {(a,b)}

Now take

A_1 = A_0 U {F_0} = {a, {(a,b)}}

Iterate indefinitely.. - Jul 12th 2010, 02:25 PMundefined
Seems I've violated the axiom of regularity and created a non-well-founded set. Is it so? Because the A and F constructed above seem very similar to

X_0 = {x}

X_1 = {x, {x}}

X_2 = {x, {x}, {x, {x}}}

X = {x, {x}, {x, {x}}, ...}

which would mean X is a member of itself, which is a contradiction according to the axiom of regularity. And it looks like this is very close to the one of the ways the naturals are defined, which would mean we are essentially taking X to be the limit of n as n approaches infinity, which does not exist because the sequence diverges.

Edit: Sorry to have to revise what I just wrote; maybe I should not have posted to this thread.. :( It now seems to me that X in this post is akin to $\displaystyle \displaystyle \mathbb{N}$ and the error isn't in claiming that it exists, but rather in claiming that it is a member of itself, even though X_0 is a member of X_1 which is a member of X_2 etc. In other words, the chain of membership does not imply that X is a member of X. Anyway for what it's worth I believe Plato is correct from the beginning, I was just trying to see if there were some "special cases" for which we can find such an f. - Jul 13th 2010, 08:58 AMMoeBlee
You shouldn't be hassled by anyone claiming that the question makes no sense. The question makes perfect sense.

With the axiom of regularity, we prove there is no function that is a member of its domain. Whether we can prove this without the axiom of regularity, I don't opine.

Actually, we can generalize: With the axiom of regularity, there is no S such that S is a member of the domain of S. Proof:

Def: dom(S) = {x | Ey <x y> in S}

Toward a contradiction, suppose S in dom(S).

So let <S y> in S.

So (using the Kuratowski definition of '< >'), we have S in {S} in <S y> in S, which violates a theorem from regularity. - Jul 16th 2010, 10:38 AMavonm
Thank you very much MoeBlee, it seems to me that yours is the best answer, the only one that makes sense actually and gives serious references. I've seen you were banned .. it seems that this forum is working in a strange way ..