# Proving a function is well defined

The question I'm working on asks:

Let $J_4 =\{0,1,2,3\}$. Then $J_4 −\{0\}=\{1,2,3\}$. Student C tries to define a function S: $J_4 -\{0\}\to J_4 -\{0\}$ as follows: For each $x \in J_4 - \{0\}$, $S(x)$ is the number $y$ so that $(xy) \bmod 4 = 1$. Student F claims that $S$ is not well defined. Who is right: student C or student D? Justify your answer.

I have several questions:

1. What is the salience of $J_4 - \{0\}$ ? I see that it removes $0$ from the list of elements, but this notation confuses me. I'm not sure exactly what it does, and it appears to be done twice (See function $S$).

2. Does subscript in $J_4$ mean $\bmod 4$ anything in the set?

3. The statement "$S(x)$ is the number $y$ so that $(xy) \bmod 4 = 1$" is also confusing me. $x$ remains the input and $y$ is the result of function $S$, right?

4. To show that this is ill-defined would require showing that for an $x$, there are multiple $y$, making this not a function. To that it is well-defined I would have to do the opposite, right? For a problem like this, should I start off by just plugging numbers in and seeing what happens, or is there a systematic approach I should be aware of?

• If student C tries to define the function, and student F claims that the function is not well defined... then I have a tough time saying student D is right! – Benjamin Dickman Dec 2 '16 at 23:56

1. If you keep $0$ in the set, then $S(x)$ is undefined, and that is because there is no number $y$ such that $(xy) \mod 4 =1$, becasue that would mean that $(0y) \mod 4 =1$, i.e. that $0 \mod 4 =1$, which is false.

2. We can't tell why they put the $4$ in $J_4$; it is just an index that typically serves to differentiate that $J$ from other sets $J$ ... it has no other meaning. My guess is that they used the $4$ to indicate that it has 4 elements, but again, nothing is forced here; they might just as well have used $J_5$

3. Yes, x is the input, and y is the output. So, for example, for $x=1$, you get $y=1$, since that is the only y for which $(xy) \mod 4 = 1$, so $S(1) =1$

4. Proceeding with the idea in 3: what is $S(2)$, i.e. what is 'the' $y$ such that $(2y) \mod 4 = 1$? Well, there is no such y! Hence, this function value is undefined. And, since we typically want function values to be defined, we would say that this is an ill-defined function.

• Thank you, this is much clearer now :) – Chris T Dec 2 '16 at 18:18
• Also it does not specify which set y comes from, so S(1) could be 1, 5, 9 etc. – abligh Dec 2 '16 at 19:47
• @abligh Well, it says $S : J_4 - \{ 0 \} \rightarrow J_4 - \{ 0 \}$, so they do specify the co-domain to be $J_4 - \{ 0 \}$. – Bram28 Dec 2 '16 at 19:51
• @Bram28: my apologies, you are quite right. – abligh Dec 2 '16 at 20:02
• @abligh Don't worry! To be honest: I am not sure if I had consciously paid attention to the definition of the co-domain myself ( I think I just sort of assumed it), so you could have saved me from a mistake! – Bram28 Dec 2 '16 at 20:21

1) "$J_4 - \{0\}$" describes a set. It doesn't mean "remove $\{0\}$ from $J_4$. It is equivalent to defining $X = J_4 - \{0\}$ and then using $X$ in both places

2) No. I think it's just a name.

3) That is correct.

4) A function is ill-defined if it is ambiguous what the output should be, or ( I think ) if the output is not in the range, or there is no output for some given input. So, for example "$S(x)$ is the greatest integer larger than $x$" is ill-defined. As is "$S(x)$ is the number $y$ such that $y$ divides $x$".

• Thank you for writing this out - so $J_4$ is not changed by - {0}, but "$J_4$ -{0}" constitutes a new set in its entirety. – Chris T Dec 2 '16 at 18:19
• This is however in the same sense that the integer $4$ is not changed by $4-1$. The statement $4-1$ is just another way of writing $3$. You might be used to programming, where you could have some set of numbers from which you actually remove elements with another "minus"-function, but in some languages it might create another set for you instead. This is very much up to the coder/user. In mathematics (and in this case in particular), an operation (which is a type of function), such as $+,-,\setminus$ is a relation between two sets (domain/codomain), so it does not change the domain in any way. – Christopher.L Dec 2 '16 at 18:41
• Yes, exactly. Computer science has really changed the conceptual difficulties in acquiring mathematics knowledge. – Callus Dec 2 '16 at 18:46

1.) I take $J_4-\{0\}$ in this context to just mean $J_4 \setminus \{0\}$, which is a more common notation in set theory, i.e $J$ "minus" $\{0\}$. There does not seem to be any ambiguity here.

2.) No, this is just standard (more or less) notation for $J_n=\{0,1,2,...,n-1\}$, which will have $n$ elements. Modulo is then a relation that you could invoke on the set. So we could say that we are "counting in $\mathbb{Z}_4=\{0,1,2,3\}$". This would usually refer to counting modulo $4$, in which we only use the numbers in $\mathbb{Z}_4$. (To be formal one defines these things using equivalence classes, but that is somewhat out of scope.)

3.) I understand how it can sound confusing but yes, it is exactly as it is written (I assume of course, I did not write it). So $S(x)=y$.

4.) If you think about it for a while, what is $S(1)$? It can only be sent to any of the elements in $J_4\setminus \{0\}$, i.e to any of $1,2,3$. But what number(s) $y$ has the property that $(xy)=1 \mod 4$? In conclusion, that it is not well defined refers to that it is not defined for all elements of its domain, i.e $J_4\setminus \{0\}$ in this case.

Hope this helps.

• It most definitely does help, as does your comment :) – Chris T Dec 2 '16 at 18:55