Is <-> an Equivalence Relation on Propositions?

In summary, the conversation is about proving the equivalence relation A <-> B to be true. The person suggests using a proof by contradiction and shows that the given assumption leads to a contradiction, proving the equivalence relation between A and B to be true. They also mention the three requirements for an equivalence relation to hold and suggest using truth tables and the definition of <-> in terms of -> and "AND" to prove them.
  • #1
soopo
225
0

Homework Statement



We have an equivalence relation such that
A <-> B.

Prove that the equivalence relation is true.

The Attempt at a Solution



Let
P: A -> B
Q: B -> A

Let's prove the relation by contradiction.
Assume
[tex]\neg A -> \neg B [/tex]

The previous assumption is the same as Q. Thus, we have a contradiction, since
it is impossible that both of the following Q and [tex] \neg Q[/tex]
are true at the same time, where

Q: B -> A and
[tex]\neg Q: \neg A -> \neg B [/tex] which is the same as B -> A.

Thus, the equivalence relation is true between A and B.
 
Physics news on Phys.org
  • #2
soopo said:

Homework Statement



We have an equivalence relation such that
A <-> B.

Prove that the equivalence relation is true.

Is A <-> B given or is that what you're trying to prove?
 
  • #3
Are you trying to show that <-> is an equivalence relation on propositions?

If that is the case, you have to show the following three things:

A <-> A for all A.
if A <-> B then B <-> A.
if A <-> B AND B <-> C then A <-> C.

How should you show these? I'd probably use truth tables and the definition if <-> in terms of -> and "AND".
 

1. What is an equivalence relation?

An equivalence relation is a mathematical concept that defines a relationship between elements of a set. It is a binary relation that satisfies three properties: reflexivity, symmetry, and transitivity.

2. How do you prove that a relation is reflexive?

A relation is reflexive if every element in the set is related to itself. To prove this, you must show that for every element a in the set, (a, a) is in the relation.

3. What is symmetry in an equivalence relation?

Symmetry means that if two elements are related, then the reverse relation is also true. In other words, if (a,b) is in the relation, then (b,a) is also in the relation.

4. How can you show that a relation is transitive?

A relation is transitive if whenever (a,b) and (b,c) are in the relation, then (a,c) is also in the relation. To prove this, you must show that for any elements a, b, and c in the set, if (a,b) and (b,c) are in the relation, then (a,c) is also in the relation.

5. What is the importance of proving equivalence relations?

Proving equivalence relations is important in mathematics because it allows us to categorize objects into equivalent classes. This helps us to understand the structure of a set and make connections between different elements. It also allows us to simplify complex problems by breaking them down into smaller, equivalent parts.

Similar threads

Replies
1
Views
728
  • Precalculus Mathematics Homework Help
Replies
2
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
9
Views
1K
  • General Math
Replies
4
Views
2K
  • Precalculus Mathematics Homework Help
Replies
2
Views
1K
Replies
11
Views
365
  • Set Theory, Logic, Probability, Statistics
Replies
4
Views
911
  • Precalculus Mathematics Homework Help
Replies
20
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
2K
  • Precalculus Mathematics Homework Help
Replies
7
Views
940
Back
Top