MHB Proving Equivalency Relations: Help from Henry

  • Thread starter Thread starter henry1
  • Start date Start date
  • Tags Tags
    Relations
AI Thread Summary
The discussion focuses on proving that the relation S, defined on the set of real numbers where x S y if x - y is an integer, is an equivalence relation. It is established that S is reflexive since the difference of a number and itself is zero, symmetric because the negative of any integer is also an integer, and transitive as the sum of two integers is an integer. The second part of the problem involves showing that S is a congruence relation with respect to addition, which is demonstrated by manipulating the definitions of S for pairs of related elements. The conclusion confirms that the properties of S align with the requirements for equivalence and congruence relations.
henry1
Messages
1
Reaction score
0
I'm having copious amounts of trouble with this question and an amount of help would really be appreciated.

Let S be the relation on the set of real numbers defined by

x S y iff x-y is an integer

1. prove that S is an equivalence relation on R.

2. Prove that if x S x' and y S y' then (x+y) S (x'+y').

Thanks,

Henry.
 
Physics news on Phys.org
Can you show what you have tried so far so our helpers can see where you are stuck or may be going astray?
 
My thoughts:

S is reflexive because 0 is an integer.

S is symmetric because -k is an integer whenever k is.

S is transitive, because the sum of two integers is another integer.

The second part of the problem is to show S is a congruence with respect to addition (of real numbers). This really just amounts to working through the definition of S:

Suppose x S x'. Then x - x' = k, for some integer k. Similarly, y S y' means y - y' = m, for some integer m.

Consequently:

(x + y) - (x' + y') = (x - x') + (y - y') = k + m, which is, of course, an integer.
 
I was reading documentation about the soundness and completeness of logic formal systems. Consider the following $$\vdash_S \phi$$ where ##S## is the proof-system making part the formal system and ##\phi## is a wff (well formed formula) of the formal language. Note the blank on left of the turnstile symbol ##\vdash_S##, as far as I can tell it actually represents the empty set. So what does it mean ? I guess it actually means ##\phi## is a theorem of the formal system, i.e. there is a...
Back
Top