Function Definition Without a Single Word

[dijkarte]

Is this correct?

A function ψ:A --> B is the set:

ψ = { (x, y) | \forallx\inA\existsy\inB\ni(((x, y) \in ψ) \wedge ((x, z)\in ψ) \Rightarrow y = z)}

Thanks.

 

[micromass]

No. Your definition is circular. Your definition of \psi already uses \psi. This is not allowed.

 

[dijkarte]

I see what you saying but this is not a circular although it looks like so. The use of the same set \psi in its definition is not for recursion.

 

[SteveL27]

Is this correct?

A function ψ:A --> B is the set:

ψ = { (x, y) | ... }

You're already in trouble here because in set-builder notation you have to say what set your elements are in. For example you need to write

ψ = { (x, y)\in something | ... }

and that something is a key part of the definition that you're missing.

(edit) This notational difficulty is actually related to the circularity people are talking about. What is (x,y), exactly? Where does it live? You are saying it lives in ψ but we don't know what that is because you're trying to define it.

 

[genericusrnme]

I see what you saying but this is not a circular although it looks like so. The use of the same set \psi in its definition is not for recursion.

ψ = { (x, y) | ∀x∈A∃y∈B∋(((x, y) ∈ ψ) ∧((x,z)∈ ψ) ⇒ y = z)}

psi is the set of (x,y) such that for all x in A there exists a y in B with (x,y) in psi and if (x,z) is in psi then y = z

You've defined psi as the objects that are in psi

 

[HallsofIvy]

I see what you saying but this is not a circular although it looks like so. The use of the same set \psi in its definition is not for recursion.

Then what is it for? "Recursion" in a definition is perfectly legitimate but, as you say, this is not recursion. In order to use that definition, you have to know which elements are in \psi and which are not. Which makes no sense in a definition of \psi.

 

[dijkarte]

This is a way of saying that if there are two pairs in this set (psi) with first coordinates equal then the pairs have to be equal. So what it serves in the definition: if such two pairs happen to exist then...happen to exist where? in this set.

Another example when we define a set of even integers: E = { x | x = 2n where n belongs to Z} notice that E is defined in terms of another set Z of which E is a subset, where it's valid to write E is a subset of Z.

 

[SteveL27]

This is a way of saying that if there are two pairs in this set (psi) with first coordinates equal then the pairs have to be equal. So what it serves in the definition: if such two pairs happen to exist then...happen to exist where? in this set.

Another example when we define a set of even integers: E = { x | x = 2n where n belongs to Z} notice that E is defined in terms of another set Z of which E is a subset, where it's valid to write E is a subset of Z.

You're doubling down on your notation error. It's this error that is causing you to not understand that you haven't told us where (x,y) lives or even what it is. You're missing a critical piece of information that's essential to the definition of a function.

 

[wisvuze]

Another example when we define a set of even integers: E = { x | x = 2n where n belongs to Z} notice that E is defined in terms of another set Z of which E is a subset, where it's valid to write E is a subset of Z.

This isn't quite the same, since Z is already defined before providing the definition of E.
In your example, you are in the process of *defining* the set psi. You can think of it as the set psi not existing until the entire formula has been correctly parsed. When you try parsing the part that says ( x, y) in psi , you will not know how to interpret this, as psi does not (..yet ) exist.

The only way your interpretation of the formula would make sense, is if psi had already been previously defined, and the set construction formula is offered as a formula ranging over the set representing the function ( then the formula will be true by definition, assuming that psi had already been properly defined ).

 

[dijkarte]

Understood. So corrected definition? Or any reference to what is and is not allowed in set definition?

 

[dijkarte]

Ok then I would correct it to:

F = { (x1, y), (x2, z) | (x1, y) and (x2 z) belong to AxB and (x1 = x2 ==> y = z) }

 

[SteveL27]

Ok then I would correct it to:

F = { (x1, y), (x2, z) | (x1, y) and (x2 z) belong to AxB and (x1 = x2 ==> y = z) }

It's good that you mentioned the Cartesian product. But you still have to account for the fact that there are a lot of different function from A to B.

Also your notation's gotten worse. Now you are saying that a function is a pair of ordered pairs?

It might help to work out some simple examples between finite sets. This problem's trickier than it looks.

 

[dijkarte]

But you still have to account for the fact that there are a lot of different function from A to B.

Incorrect, since I'm giving a general definition of a function/mapping.

Also your notation's gotten worse. Now you are saying that a function is a pair of ordered pairs?

LoL. Then does AxB = { (a, b) | ... } make it consists of only one pair? :D
Adding two pairs or 100 pairs does make no difference since the set will not allow duplicate elements.

It might help to work out some simple examples between finite sets. This problem's trickier than it looks.

Then show me a definition that works. And working out some examples in mathematical logic may help. The problem is simpler than you think. :)

 

[jgens]

LoL. Then does AxB = { (a, b) | ... } make it consists of only one pair? :D

You used the notation {(x₁,y)(x₂,z) | blah blah blah} as your definition of a function. This means that elements of the function are pairs of ordered pairs. This is most certainly not the case.

And working out some examples in mathematical logic may help. The problem is simpler than you think. :)

Evidently not. Otherwise you would have produced a correct definition by now.

 

[micromass]

And working out some examples in mathematical logic may help. The problem is simpler than you think. :)

Are you here to learn something from us or to betittle and argue with us??

 

[dijkarte]

Evidently not. Otherwise you would have produced a correct definition by now.

The show me your correct definition please.

Are you here to learn something from us or to betittle and argue with us??

To argue and learn. But you cannot tell me this is wrong without justifying your answer or at least give a reference to it. That's why I'm "arguing" or at least attempting to give a different answer even though not sure if it's correct.

 

[jgens]

The show me your correct definition please.

That defeats the learning process. I am very firmly of the belief that in order to learn something you need to struggle with it and get it wrong many times before you can really understand it.

To argue and learn. But you cannot tell me this is wrong without justifying your answer or at least give a reference to it. That's why I'm "arguing" or at least attempting to give a different answer even though not sure if it's correct.

Whenever someone has told you that your definition is wrong, they have pointed out at least one flaw with it. That is justification for their claim. Justification does not always need to come in the form of handing you the answer on a silver platter.

 

[dijkarte]

I gave a counter example to the arguement:

Also your notation's gotten worse. Now you are saying that a function is a pair of ordered pairs?

Where I said the AxB definition contains one pair { (a, b) | ... } and this does not mean it's only one element set. However no one proved me wrong.

And I'm not expecting a solution to my homework, but a good but lazy teacher can give a reference to his smart-a** students if they are not convinced. :)

 

[jgens]

Where I said the AxB definition contains one pair { (a, b) | ... } and this does not mean it's only one element set. However no one proved me wrong.

But that is not what you said. In your last attempt at defining a function, you wrote {(x₁,y)(x₂,z) | blah blah blah}. SteveL27 pointed out that this means that elements of your function are pairs of ordered pairs, which is not true. Sure he could have phrased his objection a little more clearly, but I tried to clear this confusion up with my first reply. If you did not read that part of my reply, surely no one helping you can be faulted.

And I'm not expecting a solution to my homework, but a good but lazy teacher can give a reference to his smart-a** students if they are not convinced. :)

What kind of reference do you want? Whenever you have posted a definition, someone has pointed out some flaw with your definition and given hints on how you could fix it. Whenever you have raised objections to something, someone has suggested why your objections are a little silly. I am not sure what else you want.

 

[dijkarte]

I'm here to ask, argue, suggest, try, without insulting other's intelligence and knowledge.
And unless you give a clear argument supported by a mathematical law, I will not assume your are the Euler of the century and believe you blindly. All your arguments, and sorry, are just "NO" negative answers with one common flow, create confusion!

 

[Robert1986]

Perhaps something like this might help (Note, I am not suggesting this is correct)

F = {(x,y): (x,y) in AxB and if (x1,y1) is in AxB and x=x1 then y=y1}

So, now F is a set of ordered pairs (x,y) in which x is in A, y is in B, and f(a) = b.

But, I don't really know what you mean by "function definition" in this case. Are you trying to define what a function is? In this case, the set F would depend on a particular function, f. Then perhaps we should write:

F(f) = {(x,y): (x,y) in AxB and if (x1,y1) is in AxB and x=x1 then y=y1}

But all of this is a little over my head, as I am accustomed to the definition of a function being a rule from one set to another. What you have described is more or less a set-builder notation of the graph of a function (well, if the function is like from R to R or R2 to R or something.) I guess you set-building notation is more like a "graph" of a general function.

But, I might completely misunderstand what is going on here and may be way off.

 

[jgens]

And unless you give a clear argument supported by a mathematical law, I will not assume your are the Euler of the century and believe you blindly. All your arguments, and sorry, are just "NO" negative answers with one common flow, create confusion!

I am certainly not the Euler of the century, but luckily one does not need to be in order to recognize the correct definition of a function. I think people here have been pretty clear with their objections, so what are you still confused about?

 

[dijkarte]

Robert1986, Thanks a lot for your answer. This makes a lot more sense to me. And I will study it deeply and correct my mistakes if any...

 

[jgens]

Robert1986, Thanks a lot for your answer. This makes a lot more sense to me. And I will study it deeply and correct my mistakes if any...

But there are still problems with that answer. In the definition of a function you need to specify a domain and a codomain. This is important since the functions f:\mathbb{R} \rightarrow \mathbb{R} and g:\mathbb{R} \rightarrow \mathbb{R} \setminus \{0\} defined by f(x)=\exp(x)=g(x) are different functions with the same graph. By describing only the graph of the function, you fail to capture this distinction. A function is also total, which is something not captured by that definition.

 

[dijkarte]

I'm not trying to specify or describe a function in particular. I just want to define a function as a mapping from one set to another in terms of these sets or their Cartesian product.

 

[jgens]

I'm not trying to specify or describe a function in particular. I just want to define a function as a mapping from one set to another in terms of these sets or their Cartesian product.

You are misunderstanding then. A function is an ordered triple (X,Y,\Gamma) where X is the domain, Y is the codomain and \Gamma is the graph of the function. Your general definition will have to read something like this: "A triple (X,Y,\Gamma) is a function if and only if ..."

The general notion of a function is not captured completely by its graph, so you will need to include information about the domain and codomain.

 

[SteveL27]

I'm not trying to specify or describe a function in particular. I just want to define a function as a mapping from one set to another in terms of these sets or their Cartesian product.

Right. So, here is the problem you are having.

Set builder notation defines a specific set. So if we say

A = {n \in Z | n = 2m for some m \in Z}

then I've defined the set of even integers. As I defined A, A is the set of even integers. It can't be any other set; A is exactly the even integers.

[By the way, note where the first \in is above. It's to the left of the vertical bar. That's a required part of set builder notation. You have to say what larger set your elements live in.]

But if you use the same type of set builder notation to describe a function, you will end up describing a specific function.

The function f(x) = 2x is not the same function as f(x) = 3x. So their set builder descriptions would be different.

In this problem you are not trying to define a specific function; rather, you are trying to characterize the property of a set that makes it a function. You want to capture this characterization using set builder notation.

That's why I called this a subtle problem.

(edit)
In fact to move this forward a bit I would say that you CAN'T characterize the definition of a function with one line of set-builder notation; for the reason I gave. Set-builder notation defines a particular set, not a TYPE of set.

So here is a hint. This is an easier problem. Using a single line of set-builder notation, define the set B^A = the set of all functions from A to B. This is still an interesting set theory exercise; and it has the virtue of actually being doable.

 

[dijkarte]

Thanks for you informative reply. Now I realize the mistakes I made. :)

 

[SteveL27]

Thanks for you informative reply. Now I realize the mistakes I made. :)

I wrote up a solution to this.

Problem: We want to define f: A -> B using set-builder notation.

What's a function between two sets A and B? First and foremost it's a relation. A relation is just an arbitrary collection of ordered pairs of elements (a, b) with a \in A and b \in B. In other words a relation is a subset of the Cartesian product A \times B; and another way to say that is that a relation is an element of \mathscr{P}(A \times B), where \mathscr{P} denotes the Powerset -- the collection of all subsets of A \times B.

So we say that f is a function from A to B; in symbols f: A \rightarrow B if

(1) {f \in \mathscr{P}(A \times B)}

and (2) ... what's the other condition? We have to work out the notation for the constraint that turns an arbitrary relation into a function. We want to say that if (a, b1) and (a, b2) \in f, then b1 = b2.

But what exactly are a, b1, and b2? Well, a \in A and b1 and b2 \in B.

But are they particular values of a and b1 and b2? No, what we are really saying is that for any a, b1, and b2, if (a, b1) and (a, b2) are in f, then b1 = b2. The word any tells us we need a couple of universal quantifiers.

So the function requirement becomes:

2) ( \forall a \in A)\space(\forall b1, b2 \in B)\space[(a, b1) \in f and (a, b2) \in f \Rightarrow b1 = b2 ].

So we can now say that (1) and (2) define the property of a set being a function. Writing down those two statements is the best we can do to satisfy the original problem.

If we were to put (1) and (2) together into a single set-builder spec, what would we get?

? \space = \space \{f \in \mathscr{P}(A \times B) | ( \forall a \in A)\space(\forall b1, b2 \in B)\space[(a, b1) \in f and (a, b2) \in f \Rightarrow b1 = b2 ]

This is not the definition a function in general; rather, it's a set-builder specification for some particular set. And what set is it? A little thought will convince you that it's the set of all the possible function from A to B. This set is commonly denoted as B^{A}.

Conclusion:

* We can't actually characterize the property of being a function, using only one line of set-builder notation. Instead we make a definition, saying that f: A -> B is a shorthand for the two conditions (1) and (2) above.

* If you put (1) and (2) together into a single set-builder spec, you get B^{A}, the set of all functions from A to B.

* B^{A}\space = \space \{f \in \mathscr{P}(A \times B) | ( \forall a \in A)\space(\forall b1, b2 \in B)\space[(a, b1) \in f and (a, b2) \in f \Rightarrow b1 = b2 ].

 

[dijkarte]

Interesting approach. So there's one and only one universe that contains all possible mappings from sets A to B, and any f:A --> B is an element of this. I will research the topic further.

 

[SteveL27]

Interesting approach. So there's one and only one universe that contains all possible mappings from sets A to B, and any f:A --> B is an element of this. I will research the topic further.

Well it's a set. You can get a handle on this by working out a simple example with small finite sets. For example let

A = {a1, a2, a3} and B = {b1, b2}. How many functions can there be from A to B?

Well a1 can go to b1 or b2.

a2 can go to b1 or b2.

a3 can go to b1 or b2.

So that gives us 2x2x2 = 8 possible functions from A to B. Each function is a set of exactly three ordered pairs, and there are only eight functions. Not too hard to write them all down.

Now you can see why we chose the notation B^A for the set of all functions from A to B. Because the set B^A has cardinality exactly |B|^|A|.