Prove Inequality: Symmetry, Transition & Reflexion

[solakis1]

How can we prove that the two properties of equality, namely,symmetry and transition do not imply that of reflexion??

needless to say that i do not know ,even how to start

 

[Nono713]

Hint: a set of properties {P1, P2, ...} is said to imply a conclusion C if C holds whenever all of {P1, P2, ...} hold. So to show that these properties do not in fact imply C amounts to finding a counterexample, that is, a situation where C holds but not all of P{1, P2, ...} hold. Specifically if you can find examples where {P1, P2, ...} all hold and C holds, and also examples where C holds but not all of {P1, P2, ...} hold, then that logically means that {P1, P2, ...} cannot on their own imply C - that is, the two are logically independent.

In this case {P1, P2, ...} are just symmetry and transition (transitivity?) and C is the property of reflexion (reflexivity?). Can you complete?

 

[solakis1]

Hint: a set of properties {P1, P2, ...} is said to imply a conclusion C if C holds whenever all of {P1, P2, ...} hold. So to show that these properties do not in fact imply C amounts to finding a counterexample, that is, a situation where C holds but not all of P{1, P2, ...} hold. Specifically if you can find examples where {P1, P2, ...} all hold and C holds, and also examples where C holds but not all of {P1, P2, ...} hold, then that logically means that {P1, P2, ...} cannot on their own imply C - that is, the two are logically independent.

In this case {P1, P2, ...} are just symmetry and transition (transitivity?) and C is the property of reflexion (reflexivity?). Can you complete?

the1st thing i liked for was a counterexample.but I could not find one

 

[Evgeny.Makarov]

How can we prove that the two properties of equality, namely,symmetry and transition do not imply that of reflexion??

Equality is reflexive, so the fact that equality is reflexive is implied by anything: If $B$ is true, then $A\to B$ is also true regardless of $B$.

Hint: a set of properties {P1, P2, ...} is said to imply a conclusion C if C holds whenever all of {P1, P2, ...} hold. So to show that these properties do not in fact imply C amounts to finding a counterexample, that is, a situation where C holds but not all of P{1, P2, ...} hold.

A counterexample to $P_1\land\dots\land P_n\to C$ would be a situation where all $P_i$ hold, but $C$ does not.

Specifically if you can find examples where {P1, P2, ...} all hold and C holds, and also examples where C holds but not all of {P1, P2, ...} hold, then that logically means that {P1, P2, ...} cannot on their own imply C

The second set of examples would show that $C$ does not imply all of $P_i$, but it wouldn't show whether $P_1\land\dots\land P_n$ implies $C$.

 

[solakis1]

Equality is reflexive, so the fact that equality is reflexive is implied by anything: If $B$ is true, then $A\to B$ is also true regardless of $B$.
$.

Sorry I do not get it.You mean that symmetry and transition imply reflexion in equality??

 

[Nono713]

A counterexample to $P_1\land\dots\land P_n\to C$ would be a situation where all $P_i$ hold, but $C$ does not.

The second set of examples would show that $C$ does not imply all of $P_i$, but it wouldn't show whether $P_1\land\dots\land P_n$ implies $C$.

Yes, indeed, my mistake, got a bit mixed up there.. shouldn't be posting too late!

 

[Evgeny.Makarov]

You mean that symmetry and transition imply reflexion in equality?

Briefly, yes. If you want to go deeper, we should start by clarifying terminology, in particular, the meaning of transition and reflexion (post #2 has proper terms for what you likely have in mind).

 

[solakis1]

Briefly, yes. If you want to go deeper, we should start by clarifying terminology, in particular, the meaning of transition and reflexion (post #2 has proper terms for what you likely have in mind).

Then the following is provable:
{$$(\forall A \forall B[A=B \Longrightarrow B=A])\wedge (\forall A \forall B \forall C [(A=B \wedge B=C)\Longrightarrow A=C])$$} $$\Longrightarrow \forall A[A=A]$$

I don't understand what you mean by clarifying terms... etc etc

 

[Evgeny.Makarov]

Then the following is provable:
{$$(\forall A \forall B[A=B \Longrightarrow B=A])\wedge (\forall A \forall B \forall C [(A=B \wedge B=C)\Longrightarrow A=C])$$} $$\Longrightarrow \forall A[A=A]$$

Yes.

I don't understand what you mean by clarifying terms... etc etc

Clarifying terms means making their meaning clear. The meaning of the terms "transition" and "reflexion", when they are used in the context of relations, is unclear to me. Please reread what others have said about these terms in this thread.

 

[solakis1]

Yes.

.

Please show me a syntactical proof

 

[Evgeny.Makarov]

For this I need the logical calculus (Hilbert style, natural deduction, natural deduction in Fitch style, sequent calculus, etc.) and axioms.

I expect that there is an axiom $\forall x.\,x=x$. It is a part of all so-called theories with equality. Then your formula is obtained by simply adding vacuous assumptions.

 

[solakis1]

For this I need the logical calculus (Hilbert style, natural deduction, natural deduction in Fitch style, sequent calculus, etc.) and axioms.

I expect that there is an axiom $\forall x.\,x=x$. It is a part of all so-called theories with equality. Then your formula is obtained by simply adding vacuous assumptions.

In that case you allow me to say that the said formula is not provable

 

[Evgeny.Makarov]

I don't agree, and you have not provided any reasons for your opinion.

 

[solakis1]

I don't agree, and you have not provided any reasons for your opinion.

Well, in the previous formula if we put A=B=C=a we have the following formula:

{(a=a=> a=a)&[ (a=a)&(a=a)=>a]} =>a=a

Is this formula an indentity ? NO
Because if you take a=a to be false then you have : T=>F which is false.

Hence a=a for all a , is not a theorem implied by the other two properties of equality ,thus it may be considered as an axiom

 

[Evgeny.Makarov]

Hence a=a for all a , is not a theorem implied by the other two properties of equality ,thus it may be considered as an axiom

I agree that it is an axiom, and that's what I said back in post #4 and repeated in post #11. If you are talking about equality, then it comes with axioms ensuring at least that it is an equivalence relation and in particular reflexive. If you are talking about some arbitrary relation, then, indeed, symmetry and transitivity do not imply reflexivity. A counterexample is the relation $\{(2,2),(3,3),(2,3),(3,2)\}$ on the set $\{1,2,3\}$. However, if a relation $R$ on $X$ is left-total in addition to being symmetric and transitive, then it is reflexive. The fact that $R$ is left-total means $\forall x\in X\,\exists y\in Y\;xRy$. In the counterexample above, 1 is not related to any number, so the relation is not left-total.

When I talked about clarifying terminology in post #7, I was hoping that along with correcting your terms for reflexivity and transitivity, you would explain what you mean by equality: the identity (also called the diagonal) relation or some arbitrary relation. However, you have done neither.

Well, in the previous formula if we put A=B=C=a we have the following formula:

{(a=a=> a=a)&[ (a=a)&(a=a)=>a]} =>a=a

The relationship between
\[
(\forall x,y.\;x=y\to y=x)\land (\forall x,y,z.\,x=y\land y=z\to x=z)\to\forall x.\,x=x\quad(*)
\]
and
\[
(a=a\to a=a)\land (a=a\land a=a\to a=a)\to a=a\quad(**)
\]
is not clear to me. If you have a universal formula $\forall x.\,P(x)$ and a term (say, a constant) $a$, then $P(a)$ is called an instance of $\forall x.\,P(x)$ and is implied by it. However, (*) has nested universal quantifiers, so it is not immediately clear whether truth or falsity of (**) implies that of (*).

Is this formula an indentity ? NO

You probably mean a tautology, not an identity.

 

[solakis1]

Well, in the previous formula if we put A=B=C=a we have the following formula:

{(a=a=> a=a)&[ (a=a)&(a=a)=>a]} =>a=a

Is this formula an indentity ? NO
Because if you take a=a to be false then you have : T=>F which is false.

Hence a=a for all a , is not a theorem implied by the other two properties of equality ,thus it may be considered as an axiom

Yes you are right, i agree.
And surely I meant tautology, not identidy.