2
$\begingroup$

To prove a proposition is false, do you need to find an explicit example for which the proposition is not true, or can you just assume stuff and show it leads to a contradiction?

For example: Suppose $R_1$ is a total order on $A_1$, $R_2$ is a total order on $A_2$, and $A_1\cap A_2=\emptyset$. Then $R_1\cup R_2$ is a total order on $A_1\cup A_2$.

Now this is a proposition of the form: "for all x, .." right?
So then to show that it is false, you would need to prove that there exists an x such that the statement is false, right?

Is the example in this screenshot valid? enter image description here

He is supposed to prove existence of $x$ and $y$, but he starts by saying suppose $x$.., so he basically assumes that such an $x$ and $y$ exist, right? You need to show explicit examples, because that proves existence.

Here's my version: enter image description here

What should I write at the start when proving a proposition is false? If you prove a theorem, you state the premises and the conclusion, and then prove it. But if you are proving a proposition is false, should you say something like: "The proposition X is false". In my version, I state the premises and then a conclusion, but i dont mention anything about a proposition is false, but i would like to.

$\endgroup$

1 Answer 1

1
$\begingroup$

The screenshot counterexample is (essentially) correct. The only thing missing is the (implicit) assertion that $A$ and $B$ are nonempty. Your more carefully specified counterexample is a little better.

The general answer to

can you just assume stuff (and show it leads to a contradiction)?

depends on the context. There is always an implicit assumption between writer and reader about how much background can be assumed, how much must be made explicit. What's appropriate for a homework problem is not the same as for a research paper. In a class, take this question up with your instructor.


Edit in answer to this comment from the OP:

Why is the screenshot correct? You need to prove existence, and he hasn't proven existence? Or are you saying that he can assume those variables exist, because of the context? (tbh its pretty clear those variables are possible, so it might be ok to assume?) –

The OP hasn't stated the question asked, just posted two possible answers. If the question was

Prove or disprove: Suppose $R_1$ and $R_2$ are total orders on $A_1$ and $A_2$ respectively. Then $R_1 \cup R_2$ is a total order on $A_1 \cup A_2$.

I would rewrite the start of the screenshot answer this way

The implication is false. For a counterexample, suppose $R_1$ and $R_2$ are total orders on nonempty disjoint sets $A_1$ and $A_2$ respectively. The union $A_1 \cup A_2$ is not a total order on $R_1 \cup R_2$ because ...

This version of the argument is actually stronger than the OP's example showing that the union of two particular total orders need not be a total order. It shows that the claim is true for disjoint sets only when at least one of the $A_i$ is empty.

That said, when I was teaching discrete mathematics I would have marked the screenshot answer or the OP's as essentially correct and then suggested better wording.

$\endgroup$
1
  • 1
    $\begingroup$ Why is the screenshot correct? You need to prove existence, and he hasn't proven existence? Or are you saying that he can assume those variables exist, because of the context? (tbh its pretty clear those variables are possible, so it might be ok to assume?) $\endgroup$ Commented May 31, 2023 at 20:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .