Why is f being an injection equivalent to this ?

  • Context: MHB 
  • Thread starter Thread starter fatineouahbi
  • Start date Start date
  • Tags Tags
    Equivalent Injection
Click For Summary
SUMMARY

The discussion focuses on proving the equivalence between the injectivity of a function f and the relationship between the images of sets under f. Specifically, it establishes that f(A⋂B) ⊂ f(A) ⋂ f(B) and f(A) ⋂ f(B) ⊂ f(A⋂B) are equivalent if and only if f is an injection. The proof involves assuming f(a) = f(b) for elements a and b in sets A and B, leading to the conclusion that a must equal b, thus confirming f's injectivity. The participants also explore the implications of assuming f is an injection to demonstrate the subset relationship.

PREREQUISITES
  • Understanding of set theory and set operations
  • Knowledge of functions and their properties, specifically injective functions
  • Familiarity with mathematical proofs and logical reasoning
  • Basic experience with notation in mathematics, including set intersection and function notation
NEXT STEPS
  • Study the properties of injective functions in detail
  • Learn about set theory, focusing on operations like intersection and union
  • Explore different proof techniques in mathematics, such as direct proof and proof by contradiction
  • Investigate the implications of function properties in real-world applications, such as database indexing
USEFUL FOR

Mathematicians, computer scientists, and students studying discrete mathematics or set theory, particularly those interested in function properties and proofs of injectivity.

fatineouahbi
Messages
10
Reaction score
0
1.Prove f(A⋂B) ⊂ f(A) ⋂ f(B)
2.Prove f(A) ⋂ f(B) ⊂ f(A⋂B) ⟺ f is an injection

I've solved the first question , as for the second I started with f(A) ⋂ f(B) ⊂ f(A⋂B) ⇒ f is an injection this way :
Let's suppose f(a) = f(b) = p
If we consider A = {a} and B = {b} then f(A) = f(B) = p
then f(A) ⋂ f(B) = p
then f(A⋂B) = p (because f(A) ⋂ f(B) ⊂ f(A⋂B) from the supposition and f(A⋂B) ⊂ f(A) ⋂ f(B) from the first question)
then A⋂B ≠ ∅
then a=b
then f is an injection .

But I don't know how to solve "f is an injection ⇒ f(A) ⋂ f(B) ⊂ f(A⋂B)" :confused:
 
Physics news on Phys.org
$(\implies)$ Assume $f(A)\cap f(B) \subset f(A\cap B)$ for all sets $A$ and $B$. Suppose $A=\{x\}$ and $B=\{y\}$ are singleton sets. Further assume that $f(x)=f(y)$. Then $f(A)=f(B)$, so $f(A)\cap f(B)$ is nonempty. By assumption, $f(A\cap B)$ is nonempty, since $f(A)\cap f(B)\subset f(A\cap B)$. This implies $A\cap B$ is nonempty. Since $A$ and $B$ are singletons, this implies $A=B$, or $\{x\}=\{y\}$, or $x=y$. Hence, $f$ is an injection.

$(\impliedby)$ This is a "what do you know" kind of proof. Can you write it out?
 

Similar threads

  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 1 ·
Replies
1
Views
1K
  • · Replies 5 ·
Replies
5
Views
2K
  • · Replies 2 ·
Replies
2
Views
2K
  • · Replies 2 ·
Replies
2
Views
3K
  • · Replies 10 ·
Replies
10
Views
4K
  • · Replies 41 ·
2
Replies
41
Views
3K
  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 2 ·
Replies
2
Views
1K