Main Page

From ProofWiki
Jump to: navigation, search
Welcome to ProofWiki, the online compendium of mathematical proofs. Log in or create an account to contribute!

Welcome to ProofWiki!

Logo.png
Welcome to ProofWiki.org! ProofWiki is an online compendium of mathematical proofs! Our goal is the collection, collaboration and classification of mathematical proofs. If you are interested in helping create an online resource for math proofs feel free to Create an account and contribute! Thanks and enjoy!

If you have any questions, comments, or suggestions please contact webmaster at proofwiki.org , post on the discussion page, or contact one of the ProofWiki sysops. To see what's currently happening in the ProofWiki community, visit the community portal.


Proof Index ~ Definitions ~ Sandbox


Site Statistics
Proofs:5,615
Definitions:4,289
Users:1,081
Quick Tips

Latest Proof: Mapping Preimage of Intersection/General Result on 3 July 2012 by Prime.mover

Top 10 Wanted Proofs

Want to do something different? Check here for articles linked to but not created, or finish a stub article.

News

April 1, 2012

  • Now the Riemann Hypothesis has finally been solved (who would have guessed that it would be soluble relying solely upon analysis of elementary functions?) someone's going to have to go and post it up. I'll get there but I'm bogged down in tidying up the Relation Theory category. --prime mover

March 11, 2012

  • Migrating to a different RSS renderer since the one we currently use seems to no longer be maintained. It appears an upstream version in 1.19 is being supported, going to switch to that. --Joe (talk)

February 12, 2012

  • Trying out the new 2.0 beta of MathJax. --Joe

November 30, 2011

  • Check out the forthcoming AI Mashup Challenge - fancy a mathematics conference in sunny Greece?

November 10, 2011

  • Still getting a lot of what I think are spam accounts being created (since the email confirmation messages all bounce back). Trying to combat this by checking all IP's against SORBS. --Joe (talk) 11:50, 10 November 2011 (CST)

November 9, 2011

  • So, spam sucks! We're moving back to a user based, email authenticated edit system ... effective immediately. If anyone has doesn't like this, let me know. --Joe (talk) 05:49, 9 November 2011 (CST)

November 7, 2011

  • 600 registered users. Less than 2 months for 100 more users to join, but quite a few of those were spamming accounts and have now been blocked. --prime mover 17:11, 7 November 2011 (CST)

September 30, 2011

  • Using ReCaptcha for account creation and anonymous posts. Hopefully this will cut down on some of the spam we've been seeing recently. --Joe (talk) 16:36, 30 September 2011 (CDT)

September 12, 2011

  • 500 registered users. Just over 3 months for 100 more users to join. --prime mover 00:27, 12 September 2011 (CDT)

September 3, 2011

September 1, 2011

  • The 4000th proof page has been added, although the proof itself still needs to be done.
Show All News


Proof of the Week

One-to-Many Image of Intersections


Theorem

Let $\mathcal R \subseteq S \times T$ be a relation.


Then:

$\forall S_1, S_2 \subseteq S: \mathcal R \left({S_1 \cap S_2}\right) = \mathcal R \left({S_1}\right) \cap \mathcal R \left({S_2}\right)$

iff $\mathcal R$ is one-to-many.


General Result

Let $\mathcal R \subseteq S \times T$ be a relation.

Let $\mathcal P \left({S}\right)$ be the power set of $S$.


Then:

$\displaystyle \forall \mathbb S \subseteq \mathcal P \left({S}\right): \mathcal R \left({\bigcap \mathbb S}\right) = \bigcap_{X \mathop \in \mathbb S} \mathcal R \left({X}\right)$

iff $\mathcal R$ is one-to-many.


Proof

Sufficient Condition

Suppose that:

$\forall S_1, S_2 \subseteq S: \mathcal R \left({S_1 \cap S_2}\right) = \mathcal R \left({S_1}\right) \cap \mathcal R \left({S_2}\right)$

If $S$ is singleton, the result follows immediately as $\mathcal R$ would have to be one-to-many.


So, assume $S$ is not singleton, and suppose $\mathcal R$ is specifically not one-to-many.

So:

$\exists x, y \in S: \exists z \in T: \left({x, z}\right) \in T, \left({y, z}\right) \in T, x \ne y$.

and of course $\left\{{x}\right\} \subseteq S, \left\{{y}\right\} \subseteq S$.


So:

  • $z \in \mathcal R \left({\left\{{x}\right\}}\right)$
  • $z \in \mathcal R \left({\left\{{y}\right\}}\right)$

and so by definition of intersection:

$z \in \mathcal R \left({\left\{{x}\right\}}\right) \cap \mathcal R \left({\left\{{y}\right\}}\right)$

But $\left\{{x}\right\} \cap \left\{{y}\right\} = \varnothing$.


Thus from Image of Null is Null:

$\mathcal R \left({\left\{{x}\right\} \cap \left\{{y}\right\}}\right) = \varnothing$

and so:

$\mathcal R \left({\left\{{x}\right\} \cap \left\{{y}\right\}}\right) \ne \mathcal R \left({\left\{{x}\right\}}\right) \cap \mathcal R \left({\left\{{y}\right\}}\right)$

$\Box$


Necessary Condition

Let $\mathcal R$ be one-to-many.


From Image of Intersection, we already have:

$\mathcal R \left({S_1 \cap S_2}\right) \subseteq \mathcal R \left({S_1}\right) \cap \mathcal R \left({S_2}\right)$.


So we just need to show:

$\mathcal R \left({S_1}\right) \cap \mathcal R \left({S_2}\right) \subseteq \mathcal R \left({S_1 \cap S_2}\right)$.


Let $t \in \mathcal R \left({S_1}\right) \cap \mathcal R \left({S_2}\right)$.

Then:

\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle t\) \(\in\) \(\displaystyle \mathcal R \left({S_1}\right) \cap \mathcal R \left({S_2}\right)\) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \)                    
\(\displaystyle \) \(\displaystyle \implies\) \(\displaystyle \) \(\displaystyle t\) \(\in\) \(\displaystyle \mathcal R \left({S_1}\right) \land t \in \mathcal R \left({S_2}\right)\) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \)          Definition of Intersection          
\(\displaystyle \) \(\displaystyle \implies\) \(\displaystyle \) \(\displaystyle \exists s_1 \in S_1: \left({s_1, t}\right)\) \(\in\) \(\displaystyle \mathcal R \land \exists s_2 \in S_2: \left({s_2, t}\right) \in \mathcal R\) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \)          Definition of Relation          
\(\displaystyle \) \(\displaystyle \implies\) \(\displaystyle \) \(\displaystyle s_1\) \(=\) \(\displaystyle s_2\) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \)          $\mathcal R$ is one-to-many          
\(\displaystyle \) \(\displaystyle \implies\) \(\displaystyle \) \(\displaystyle s_1 = s_2\) \(\in\) \(\displaystyle S_1 \land s_1 = s_2 \in S_2\) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \)                    
\(\displaystyle \) \(\displaystyle \implies\) \(\displaystyle \) \(\displaystyle s_1 = s_2\) \(\in\) \(\displaystyle S_1 \cap S_2\) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \)          Definition of Intersection          
\(\displaystyle \) \(\displaystyle \implies\) \(\displaystyle \) \(\displaystyle \mathcal R \left({s_1}\right) = \mathcal R \left({s_2}\right)\) \(\in\) \(\displaystyle \mathcal R \left({S_1 \cap S_2}\right)\) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \)          Image of Element is Subset          
\(\displaystyle \) \(\displaystyle \implies\) \(\displaystyle \) \(\displaystyle \mathcal R \left({S_1}\right) \cap \mathcal R \left({S_2}\right)\) \(\subseteq\) \(\displaystyle \mathcal R \left({S_1 \cap S_2}\right)\) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \)          Definition of Subset          


So if $\mathcal R$ is one-to-many, it follows that:

$\mathcal R \left({S_1 \cap S_2}\right) = \mathcal R \left({S_1}\right) \cap \mathcal R \left({S_2}\right)$

$\Box$


Putting the results together, we see that:

$\mathcal R \left({S_1 \cap S_2}\right) = \mathcal R \left({S_1}\right) \cap \mathcal R \left({S_2}\right)$ iff $\mathcal R$ is one-to-many.

$\blacksquare$


Personal tools
Namespaces
Variants
Actions
Navigation
ProofWiki.org
ToDo
Toolbox
Google AdSense