Undergrad Proof involving functional graphs and the injective property

Click For Summary
SUMMARY

The discussion centers on the proof involving functional graphs and their injective properties. The user questions the necessity of the functional graph definition in proving that a graph \( G \) is injective, given the problem statement that \( G \) is a functional graph. The user presents a proof that does not utilize the functional graph premise, leading to concerns about the validity of the proof. The conclusion drawn is that the functional graph classification is essential for establishing injectivity in this context.

PREREQUISITES
  • Understanding of functional graphs and their definitions
  • Knowledge of injective functions and their properties
  • Familiarity with graph theory concepts, particularly biconditional statements
  • Ability to construct proofs by contradiction
NEXT STEPS
  • Study the properties of functional graphs in detail
  • Learn about injective functions and their implications in graph theory
  • Explore biconditional proofs in mathematical logic
  • Review examples of proofs involving contradictions in functional graphs
USEFUL FOR

Mathematicians, computer scientists, and students studying graph theory, particularly those interested in the properties of functional graphs and injective functions.

Uncanny
Messages
36
Reaction score
1
TL;DR
The problem I’ve attempted is number 12 in the attached thumbnails. Also included a bit above the problem statement is the relevant definition (i.e. that of a functional graph). My proof is also attached.
My only qualm is that the statement “Let G be a functional graph” never came into play in my proof, although I believe it to be otherwise consistent. Can someone take a look and let me know if I missed something, please? Or is there another reason to include that piece of information?
 

Attachments

  • image.jpg
    image.jpg
    52.9 KB · Views: 316
  • image.jpg
    image.jpg
    65.3 KB · Views: 253
Physics news on Phys.org
Here’s an update with things written out:

Definition:

Let ##G## be a graph. ##G## is a functional graph if and only if ##(x_1,y_1) \in G## and ##(x_1,y_2) \in G## implies ##y_1=y_2##.

Problem statement, as written:

Let ##G## be a functional graph. Prove that ##G## is injective if and only if for arbitrary graphs ##J## and ##H##: ##G \circ (H \cap J) = (G \circ H) \cap (G \circ J).##

I am concerned with the direction of the biconditional proving that ##G## is injective. I have completed a proof which seems consistent to me, but does not utilize the premise of ##G## being a functional graph anywhere in the argument (including the other direction of the biconditional). Is it simply necessary, a priori, for a graph to be a functional graph in order for it to be considered injective?

I can post my proof if needed, but here is the gist: I suppose the antecedent (assume for arbitrary graphs ##J,H## that the equality written above holds). Then I proceed via contradiction, supposing (to the contrary) ##G## is not injective. This brings into existence two elements (ordered pairs) of ##G## with unequal first elements, but equal second elements. From here, I construct ##J,H## such that I may use the equality given above to show that the unequal first elements, in fact, are equal- a contradiction.

*Nowhere do I use the fact that ##G## is a functional graph. For some reason, this isn’t sitting well. Is my conjecture above true about graphs unable to be considered injective if they are not first classified as functional?
 
If there are an infinite number of natural numbers, and an infinite number of fractions in between any two natural numbers, and an infinite number of fractions in between any two of those fractions, and an infinite number of fractions in between any two of those fractions, and an infinite number of fractions in between any two of those fractions, and... then that must mean that there are not only infinite infinities, but an infinite number of those infinities. and an infinite number of those...

Similar threads

  • · Replies 3 ·
Replies
3
Views
1K
  • · Replies 15 ·
Replies
15
Views
7K
  • · Replies 3 ·
Replies
3
Views
2K
  • · Replies 7 ·
Replies
7
Views
2K
  • · Replies 1 ·
Replies
1
Views
1K
  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 4 ·
Replies
4
Views
2K
  • · Replies 5 ·
Replies
5
Views
2K
  • · Replies 3 ·
Replies
3
Views
5K
  • · Replies 15 ·
Replies
15
Views
2K