1
$\begingroup$

Please check whether my understanding of some proof writing aspects is correct. I will write down those aspects in the form of questions.

Firstly, I'm looking at the "proof" that $A × B = B × A$ only if $A = B$:

So, our goal is $\forall$$x$$(x$$\in$$A$$\implies$$x$$\in$$B$$)$ $\wedge$ $\forall$$x$$(x$$\in$$A$$\impliedby$$x$$\in$$B$$)$ while we have

$\forall$$t($$\exists$$x$$\exists$$y$$(t=xy$ $\wedge$ $x\in A$ $\wedge$ $y\in B$ $\implies$ $t\in B × A)$

Now I'll spot all the possible mistakes in it and then give some thoughts about them.

1) Let a be arbitrary element of A. Using our first given we let $t_{0}$ be an element of $A × B$ such that t=(x,y) ,where x=a and y equals to some element of B. Proceeding now with our implication we get work done.

Considerations: If we use our given as existential instantiation we can't choose for $t$.

2) Second proof. Let's consider our goal, it is a form of conjuction so we treat it as two separate goals $\forall$$x$$(x$$\in$$A$$\implies$$x$$\in$$B$$)$, $\forall$$x$$(x$$\in$$A$$\impliedby$$x$$\in$$B$$)$.

Now we proceed by removing quantifiers from these goals by introducing new arbitrary variables x from A and y from B(first goal justifies introducing x and second introducing y).

Now that we have our x and y we can form $t=(x,y)$ thus passing through our implication antecedent, so now we know that $t\in B × A$, thus x is B and y is in A. Done.

Considerations: As for conjuction we should treat our goals separately, meaning that we choose only one of them at time and completely forget about other(s). This way we would have only one introduced variable.

But those were all just my considerations, question still remains:

  1. Do we treat a goal of the form $P$$\wedge$$Q$ as i considered?

  2. How can we use a given of the form $\forall$$x\in A$$P(x)$? Can we regard it as $\exists$$x\in A$$P(x)$? Can we use it for any a from $A$, that has been introduced earlier(by the use of givens/goals)? Can we use it for an element that we have explicitly constructed from scratch ourselves?

  3. Name me all the ways we can justify introducing a new variable into a proof.

  4. Does the phrase "Let x from A be arbitrary" serve to be an indicator for and only for a goal of the form $\forall$$x\in A$$P(x)$?

  5. Are my mistake explanations in the proofs correct?

(There are a lot of questions but i hope it's enough of mere yes or no to most of them)

$\endgroup$
10
  • $\begingroup$ You're making formatting more difficult than it needs to be. For instance: note that the line $\forall$$x$$(x$$\in$$A$$\implies$$x$$\in$$B$$)$, $\forall$$x$$(x$$\in$$A$$\impliedby$$x$$\in$$B$$)$ can be more nicely written as $\forall x (x \in A \implies x \in B )$, $\forall x (x \in A \impliedby x \in B )$. Note also that the latter yields $\forall x (x \in A \implies x \in B )$, $\forall x (x \in A \impliedby x \in B )$, which now has the correct spacing. $\endgroup$ – Ben Grossmann May 24 '17 at 12:59
  • $\begingroup$ sorry, i'm noob, thanks for advice $\endgroup$ – famesyasd May 24 '17 at 13:02
  • $\begingroup$ Not clear what are you asking.... $\endgroup$ – Mauro ALLEGRANZA May 24 '17 at 14:22
  • $\begingroup$ To 1. A "goal" of the form $P \land Q$ must be proved showing that (under the same assumptions) $P$ holds and $Q$ holds. If I read the context well, you have to prove that $A \subseteq B$ and $B \subseteq A$ (under the "common" assumption that $A \times B = B \times A$) and then conclude with $A=B$. $\endgroup$ – Mauro ALLEGRANZA May 24 '17 at 14:23
  • $\begingroup$ @MauroALLEGRANZA ok, if anything helps i'm reading Velleman's "How to prove it" currently so one of the questions is what the mistake in proofs on pages 165 and 170(chapter 4:relations, section 4.1: ordered pairs and Cartesian products, right before theorem 4.1.4 and second "proof" is on exercises #12. $\endgroup$ – famesyasd May 24 '17 at 15:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.