is there a function that is a member of its domain?

Printable View

July 12th 2010, 09:40 AM
avonm

is there a function that is a member of its domain?

or is there a proof that such function doesn't exist?
July 12th 2010, 09:49 AM
Plato

Quote:

Originally Posted by avonm

is there a function that is a member of its domain?
or is there a proof that such function doesn't exist?

That question makes absolutely no sense whatsoever.
It is a violation of types.
Try to explain what you are trying to ask.
Give an example of what you think you are asking.
July 12th 2010, 10:08 AM
avonm

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'.
July 12th 2010, 10:27 AM
Plato

Quote:

Originally Posted by avonm

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

I think that you are the one that does not understand what a function is.
Here is the definition.
Suppose that each of $A~\&~B$ is a set.
The statement that $f$ is a function from $A$ to $B$ means.
1. $f\subseteq (A\times B)$
2. if $x\in A$ then $\left( {\exists y \in B} \right)\left[ {(x,y) \in f} \right]$
3. $\left[ {(x,y) \in f \wedge (x,z) \in f \to y = z} \right]$

Please explain your question using the correct definition of function.
July 12th 2010, 10:44 AM
avonm

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)
July 12th 2010, 11:35 AM
undefined

You are looking for $\displaystyle f$ such that $\displaystyle f \in A$ and $\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 A = \{\emptyset\}, B = \emptyset, f: A \to B$ . It seems then that $(A \times B) = \emptyset$ and that $\displaystyle f$ is unique and that using Plato's definition $f = \emptyset$ giving $\displaystyle f \in A$ and $\displaystyle f \subseteq (A \times B)$ as desired.. but I am shaky on this.
July 12th 2010, 01:05 PM
Jose27

Quote:

Originally Posted by undefined

You are looking for $\displaystyle f$ such that $\displaystyle f \in A$ and $\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 A = \{\emptyset\}, B = \emptyset, f: A \to B$ . It seems then that $(A \times B) = \emptyset$ and that $\displaystyle f$ is unique and that using Plato's definition $f = \emptyset$ giving $\displaystyle f \in A$ and $\displaystyle f \subseteq (A \times B)$ as desired.. but I am shaky on this.

I think there cannot be a function with codomain $\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 $B$ there exists exactly one function $f_B:\emptyset \rightarrow B$ , in which case $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.
July 12th 2010, 01:14 PM
Plato

Quote:

Originally Posted by undefined

Edit: To clarify, suppose $\displaystyle A = \{\emptyset\}, B = \emptyset, f: A \to B$ . It seems then that $(A \times B) = \emptyset$ and that $\displaystyle f$ is unique and that using Plato's definition $f = \emptyset$ giving $\displaystyle f \in A$ and $\displaystyle f \subseteq (A \times B)$

The is at least one difficulty with that example.
Using the notation $B^A$ to stand for all functions from $A\to B$ .
Here is a standard exercise from Halmos’ little book. (p33)
Exercise: (i) $Y^{\emptyset}$ has exactly one element, namely $\emptyset$ , whether $Y$ is empty or not; and (ii) if $X$ is not empty then $\emptyset^X$ is empty.

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

Also look the requirement #2 in the definition. Consider the existential operator.
July 12th 2010, 01:18 PM
undefined

Quote:

Originally Posted by Jose27

I think there cannot be a function with codomain $\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 $B$ there exists exactly one function $f_B:\emptyset \rightarrow B$ , in which case $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.

You're right, I got that backwards.
July 12th 2010, 01:36 PM
undefined

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..
July 12th 2010, 02:25 PM
undefined

Quote:

Originally Posted by undefined

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

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 \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.
July 13th 2010, 08:58 AM
MoeBlee

Quote:

Originally Posted by avonm

is there a function that is a member of its domain?

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.
July 16th 2010, 10:38 AM
avonm

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