Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Until now, I've been presented to several proofs of uniqueness:

  • $\emptyset$
  • $1$
  • $0$

For set theory, fields, etc. And it seems that they all rely in proof by contradiction. At least, at the present moment, I've searched a bit for it and all the proofs seems to employ this technique. So is it possible to prove it without it?

share|cite|improve this question
4  
What do you mean by $\varnothing, 1, 0$ being examples of uniqueness? As in, they're the unique objects satisfying a certain property? – Clive Newstead Mar 13 at 0:08
11  
Normally, to prove that something is unique, you assume that you have two objects with a given property - which may or may not be distinct - and prove that the objects are equal. This is not a proof by contradiction, it is just a proof that all objects with that property are equal to each other. – Carl Mummert Mar 13 at 0:14
    
@CarlMummert Weird. It's often presented as: "Suppose there are two..." - and it really seems a contradiction. – Voyska Mar 13 at 1:35
5  
@Voyska: you assume there are two, but there is need to assume they are not distinct. You just need to prove that if someone gives you two, they are actually equal to each other. It can be phrased, sometimes, as a contradiction, by adding the unnecessary assumption that the two objects that were given are distinct. – Carl Mummert Mar 13 at 1:47
1  
@Voyska I think the confusion was that $\emptyset$, $1$, and $0$ are not proofs. You say "...several proofs of uniqueness:" and then give a list, and one would expect that the items in the list are proofs of uniqueness. What you've actually shown are objects that satisfy uniqueness theorems. If you want to improve the question, you should probably state the theorems, e.g. that $\emptyset$ is the only empty set, that $1$ is the only multiplicative identity, etc. – David Z Mar 13 at 9:13

There is often no need for contradiction; to say that there is a unique object $x$ satisfying some formula $\varphi(x)$ is to say that

  • There exists $x$ satisfying $\varphi(x)$ — symbolically, this is $\exists x\, \varphi(x)$;
  • If $x,y$ are such that $\varphi(x)$ and $\varphi(y)$ are true, then $x=y$ — symbolically, this is $\forall x \forall y (\varphi(x) \wedge \varphi(y) \to x=y)$.

So you can prove uniqueness by first supposing $x$ and $y$ are objects for which $\varphi(x)$ and $\varphi(y)$ are both true, and deriving $x=y$. You've probably done this a thousand times without realising. For example

  • There is a unique empty set. To see this, suppose that $A$ and $B$ are empty sets. For any $x$, the statements $x \in A$ and $x \in B$ are both false, so that $x \in A \Leftrightarrow x \in B$ is true. By the axiom of extensionality, $A=B$.
  • Every group (or even monoid) has a unique identity element. To see this, let $G$ be a group and suppose $u,v \in G$ satisfy $ug=g=gu$ and $vg=g=gv$ for all $g \in G$. Then $u=uv$ since $v$ is an identity element, and $uv=v$ since $u$ is an identity element, so $u=v$.
  • Every time you prove a function is injective, you're proving a uniqueness result. To say a function $f : X \to Y$ is injective is to say that, for all $y \in \mathrm{im}(f)$, there exists a unique $x \in X$ such that $f(x)=y$. This is proved by showing that if $x,x' \in X$ with $f(x)=f(x')$ ($=y$), then $x=x'$.
share|cite|improve this answer
    
I don't get it. Aren't you imposing the uniqueness instead of proving it? You say that if there are $x,y $ such that $\phi (x)$ and $\phi (y) $, then they are the same. This seems more that you're forcing it to be that way instead of showing it as a consequence of some earlier assumption. – Voyska Mar 13 at 18:49
1  
Hm? I'm not imposing or proving anything, I'm defining 'uniqueness'. Specifically, 'uniqueness' means that if two things satisfy a property, then they must be equal. This definition of 'uniqueness' then guides what a (direct) proof of uniqueness would look like. – Clive Newstead Mar 13 at 19:19

You're probably structuring uniqueness proofs like, "We assume there are two different things, we prove they are the same, a contradiction." Just delete the word "different". Now it's not by contradiction.

This is a common quasi-error where people start by assuming the opposite out of some sort of training or conditioning, then don't actually use the false assumption.

Per your comment, I really do see why this feels against the grain. You really shouldn't think of a proof that says, "Suppose there are two objects satisfying a certain property, then *insert math* it turns out they were the same object all along!" as a contradiction.

With that attitude you'll probably fall for bogus proofs that $0=1$, like: Let $a=b$. Then $a-a=b-a$ so $\frac{a-a}{b-a} = 1$. But $a-a=0$ so $0=1$. If you don't see the flaw, here's a hint: think about what $b-a$ is. This is the kind of mistake you will make when your intuition thinks of something called $a$ and something called $b$ as two different objects because they have different labels. If $x=y$ is that a contradiction? No, that sounds silly and it is.

On a tangent, have you thought of the proof that $0.999\ldots = 1$? It's an amazing problem and many, many people have the wrong intuition - that the numbers must be different - because they are written differently. It turns out the same number may have two different ways to write it down by decimal expansion. People are very uncomfortable with that. They've never thought of numbers as abstract entities existing independently of their decimal representations, and if the decimal representations - ink on paper - are different, then the numbers must be. But this is false. For a given real number $x$, there are always (I think) two decimal representations, one ending in $000$s and one ending in $999$s.

share|cite|improve this answer
    
But then, we usually have to prove the uniqueness. Isn't "suppose there are two" (without the different) a contradiction towards the uniqueness? – Voyska Mar 13 at 18:53
    
@Voyska: To prove that there exists a unique object satisfying some property, you need to prove that if $x$ and $y$ both satisfy the property, then $x = y$. That is not (necessarily) a proof by contradiction. – Ilmari Karonen Mar 13 at 21:51
    
Think of it as keys opening a lock. If I say "only this key can open this lock", I mean "only a key with this shape" can open the lock. I can still have two keys open the same lock, but they must be copies of each other. – Nate 8 Mar 13 at 23:56
    
@Voyska it's really not. With that attitude you could fall for a bogus proof that 1=0 like, "assume a=b. Then a-a = a-b, so (a-a)/(a-b) = 1. a-a = 0 so 0=1." You really shouldn't think of "assume there are two objects satisfying a certain property, it turns out have in fact been the same object all along" as contradiction. – djechlin Mar 14 at 4:39
    
On your tangent - It's not true that all real numbers have two decimal representations. $ \frac{1}{3} = 0.333\ldots $ has no other decimal representation (if one digit isn't a 3, the digits after it can't make up for the difference). – cardboard_box Mar 19 at 0:32

You can phrase a uniqueness proof so that it's not a proof by contradiction, but it retains the same character. For example, let's suppose you want to prove that the additive identity in a field $F$ is unique.

Proof by contradiction: Let $0 \in F$ be an additive identity, and suppose there exists another additive identity $0' \in F$, with $0' \not= 0$. Then: $0 = 0 + 0' = 0'$. This contradicts the assumption that $0' \not= 0$.

Other proof: Suppose $0' \in F$ has the property that $a + 0' = a$ for all $a \in F$. Then consider the case when $a = 0$; we see that $0 = 0 + 0' = 0'$. Therefore the only additive identity in the field is $0$.

Same idea, different words :)

share|cite|improve this answer

To prove uniqueness we use the injective property.

Suppose we want to prove that the solution to $2x + 1 = 0$ is unique.

Let $f(x) = 2x + 1.$ Let $a, b \in \mathbb R$. Assume $f(a) = f(b).$ Then $2a + 1 = 2b + 1$ implying $a = b.$ So, $f$ is injective and the solution is unique.

share|cite|improve this answer
    
and how do you prove that that function is injective? – Ittay Weiss Mar 13 at 0:24
    
You mean the function $f$? I am not sure about your question. Can you elaborate? – user322231 Mar 13 at 0:27
    
Yes, the function $f$. You appealed to its injectivity to prove the uniqueness of the solution. But the two claims are trivially equivalent, so you have to prove one of them. You might as well have said "Suppose we want to prove that the solution to $2x+1=0$ is unique. Well, it's solution is unique, so there you go". – Ittay Weiss Mar 13 at 0:29
    
Well, the point was to say that injectivity is a way for us to talk about uniqueness of solutions just like how surjectivity is way to talk about existence. – user322231 Mar 13 at 0:32
2  
It would be if you provided a proof of the injectivity of the function that does not use contradiction. Right now, all you stated is a tautology. You did not prove anything. Moreover, you say "we use the injectivity property" but then you go ahead and seem to deduce the injectivity of the function". It is not clear what you are trying to do in this answer. – Ittay Weiss Mar 13 at 0:42

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.