3
$\begingroup$

I'm teaching myself set theory, and I'm not sure how detailed I should be when asked to prove things.

Here is my proof that $A\subseteq A$ (the subset relation is reflexive):

$A \subseteq B$ iff $((x \in A) \implies (x \in B))$

$A \subseteq A$ iff $((x \in A) \implies (x \in A))$

$(x \in A) \implies (x \in A)$ is always true, as something implying itself must be true (is there a formal way to write this?)

Hence $ A \subseteq A$ is always true.

Is this proof formal enough, and does it contain the right amount of detail?

$\endgroup$
1
  • $\begingroup$ this proof Is formal enough and it contains the right amount of detail $\endgroup$
    – user147308
    Jun 25, 2014 at 14:22

3 Answers 3

4
$\begingroup$

Your proof is right.

Two comments :

(i) Instead of $A⊆B \implies ((x∈A) \implies (x∈B))$ I prefer :

$A⊆B$ iff $((x∈A) \implies (x∈B))$

because the RHS is the definition of set inclusion.

(ii) $x \in A \implies x \in A$ is an instance of the "logical law" :

$\mathcal A \implies \mathcal A$

which is a tautology of propositional logic.

The rules of logic allow us to substitute for the propositional letter $\mathcal A$ a formula whatever, and the result is still true, provided that we replace all the occurrences of $\mathcal A$ with the same formula.

$\endgroup$
3
  • $\begingroup$ So how would I write (ii) in the proof? Would I just write "which must be true by the logical law"? $\endgroup$
    – rlms
    Jun 25, 2014 at 14:43
  • 1
    $\begingroup$ @sweeneyrod - exactly as you did. $(x∈A) \implies (x∈A)$ is always true, because it is an instance of the "logical law" (tautology) : $A \implies A$. My second comment was only intended to "supplement" your proof, specifically answering to "(is there a formal way to write this?)". $\endgroup$ Jun 25, 2014 at 14:46
  • $\begingroup$ @sweeneyrod - additional comment (maybe superfluous) : $\subseteq$ is also antisymmetric. Thus, it is a Partial order $\endgroup$ Jun 25, 2014 at 14:50
2
$\begingroup$

User wrote:

$(x \in A) \implies (x \in A)$ is always true, as something implying itself must be true (is there a formal way to write this?)

This is certainly more than rigorous enough for most math courses, even at the highest level.

However, to make it a truly formal proof, depending on the axioms and rules you are allowed, you would need something along the lines of:

  1. $x\in A$ (Premise)

  2. $x\in A\implies x\in A$ (Conclusion)

  3. $\forall a:[a\in A\implies a\in A]$ (Universal Generalization)

On each numbered line, you would have to cite the specific axiom or rule used to obtain that result. In my example, I refer to axioms of logic called Premise, Conclusion and Universal Generalization (names and usage will vary). Generally, in a formal proof, it's one line, one rule. Fortunately, most courses will not require this level of detail.

$\endgroup$
1
$\begingroup$

I'm practicing my set proving skills. Maybe somebody could benefit from it, or point out an error in the solution.

The proof for

${A \subseteq A}$

${\forall_x, [(x \in A) \to (x \in A)]}$ def subset

${\forall_x, [\lnot(x \in A) \lor (x \in A)]}$ implication conversion law

${\forall_x, T}$ law of excluded middle

So the statement is reduced to a tautology, so therefor it must be true.

$\endgroup$

You must log in to answer this question.

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