MHB Functions and Relations: Proving R is a Function from A to B

AI Thread Summary
To prove that a binary relation R from set A to set B is a function, it must satisfy two conditions: R^-1(not) R must be a subset of the identity relation idB, and R not a R^-1 must hold. The discussion elaborates on how the identity relation ensures that for every element a in A, there exists a unique corresponding element b in B. Additionally, if two pairs (a,b) and (a,b') exist in R, it must follow that b equals b', reinforcing the uniqueness required for a function. The conversation also touches on the need for clarity in problem-solving and adherence to forum rules. Understanding these principles is essential for establishing R as a function.
Sharon
Messages
1
Reaction score
0
Let R\subseteq A*B be a binary relation from A to B , show that R is a function if and only if R^-1(not) R \subseteq idB and Rnot aR^-1 \supseteq both hold. Remember that Ida(idB) denotes the identity relation/ Function {(a.a)|a€ A} over A ( respectively ,B)
Please see the attachment ,I couldn't write the question properly, and this is only one question but I need help with another one too.
 

Attachments

  • received_307247869875543__01.png
    received_307247869875543__01.png
    36.4 KB · Views: 101
Physics news on Phys.org
$\text{id}_A\subseteq R\circ R^{-1}$ means that for every $a\in A$ we have $(a,a)\in R\circ R^{-1}$. By the definition of composition of relation, there exists a $b\in B$ such that $(a,b)\in R$ and $(b,a)\in R^{-1}$. In fact, $(a,b)\in R$ implies $(b,a)\in R^{-1}$, so $(b,a)\in R^{-1}$ does not add useful information, but we have shown that for every $a\in A$ there exists a $b\in B$ such that $(a,b)\in R$.

Suppose now that $(a,b)\in R$ and $(a,b')\in R$ for some $a\in A$ and $b,b'\in B$. Then $(b,a)\in R^{-1}$, so $(b,b')\in R^{-1}\circ R$. But since $R^{-1}\circ R\subseteq\text{id}_B$, it follows that $b=b'$.

It is left to prove the other direction, where the fact that $R$ is a function implies the two inclusions.

Concerning problem 7, could you write what you have done and what is not clear to you? Also, please read the https://mathhelpboards.com/rules/, especially rule #11 for the future.
 
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