Curious question about cardinality of finite setsWork-at-home days such that the office is always staffedUsing matrix theory to solve this problemChoose unique numbers from different setsProve that the intersection of all the sets is nonempty.Curiosity about large and small setsInvolution that brings sets to disjoint setsNumber of elements in a finitely generated Dynkin systemCan all convex $3n$-iamonds be tiled by $3$-iamonds?Is |A − B| = |A| − |B| always true or sometimes false?
Splice or replace
Where can I get an anonymous Rav Kav card issued?
Are there any non-WEB re-implementation of TeX Core in recent years?
Why does Coq include let-expressions in its core language
How is Team Scooby Doo (Mystery Inc.) funded?
Eccentric keepers
How to help my 2.5-year-old daughter take her medicine when she refuses to?
My research paper filed as a patent in China by my Chinese supervisor without me as inventor
A medieval fantasy adventurer lights a torch in a 100% pure oxygen room. What happens?
What is my breathable atmosphere composed of?
Is there a reliable way to hide/convey a message in vocal expressions (speech, song,...)
Napkin Folding Problem / Rumpled Ruble Problem
What's the biggest organic molecule that could have a smell?
Is there a real-world mythological counterpart to WoW's "kill your gods for power" theme?
What is a realistic time needed to get a properly trained army?
Fight a biblical flood apart from building barriers
How seriously should I take a CBP interview where I was told I have a red flag and could only stay for 30 days?
Selecting 2 column in an Inner join
Confirm the ending of a string
Glue or not to glue boots
Random point on a sphere
Where does the expression "triple-A" come from?
Why would "an mule" be used instead of "a mule"?
Will replacing a fake visa with a different fake visa cause me problems when applying for a legal study permit?
Curious question about cardinality of finite sets
Work-at-home days such that the office is always staffedUsing matrix theory to solve this problemChoose unique numbers from different setsProve that the intersection of all the sets is nonempty.Curiosity about large and small setsInvolution that brings sets to disjoint setsNumber of elements in a finitely generated Dynkin systemCan all convex $3n$-iamonds be tiled by $3$-iamonds?Is |A − B| = |A| − |B| always true or sometimes false?
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty margin-bottom:0;
$begingroup$
Suppose we are given three finite, non-empty sets $A, B, C$ such that $|C|leq |A| leq |B|$. Is it always true that $fracAcap C + fracBcap CB leq 1 + fracB$?
I have tried countless examples for days and I haven't found any counterexample so far... This is just a curious question. But if it's true, there has to be a proof, right?
combinatorics
edited 8 hours ago
Asaf Karagila♦
316k35 gold badges454 silver badges793 bronze badges
asked 8 hours ago
CastorCastor
582 bronze badges
$endgroup$
add a comment
|
$begingroup$
Suppose we are given three finite, non-empty sets $A, B, C$ such that $|C|leq |A| leq |B|$. Is it always true that $fracAcap C + fracBcap CB leq 1 + fracB$?
I have tried countless examples for days and I haven't found any counterexample so far... This is just a curious question. But if it's true, there has to be a proof, right?
combinatorics
edited 8 hours ago
Asaf Karagila♦
316k35 gold badges454 silver badges793 bronze badges
asked 8 hours ago
CastorCastor
582 bronze badges
$endgroup$
$begingroup$
Since these cardinals are necessarily finite (otherwise the division has no meaning), the question is not a set theory question, but rather a combinatorial question.
$endgroup$
– Asaf Karagila♦
8 hours ago
$begingroup$
"But if it's true, there has to be a proof, right?" Not necessarily. Gödel's theorems guarantee the existence of statements that are true but not provable. But in this simple case, I think it is safe to say that yes, if it's true then there has to be a proof. I'm working on it:-)
$endgroup$
– TonyK
7 hours ago
add a comment
|
$begingroup$
Suppose we are given three finite, non-empty sets $A, B, C$ such that $|C|leq |A| leq |B|$. Is it always true that $fracAcap C + fracBcap CB leq 1 + fracB$?
I have tried countless examples for days and I haven't found any counterexample so far... This is just a curious question. But if it's true, there has to be a proof, right?
combinatorics
edited 8 hours ago
Asaf Karagila♦
316k35 gold badges454 silver badges793 bronze badges
asked 8 hours ago
CastorCastor
582 bronze badges
$endgroup$
Suppose we are given three finite, non-empty sets $A, B, C$ such that $|C|leq |A| leq |B|$. Is it always true that $fracAcap C + fracBcap CB leq 1 + fracB$?
I have tried countless examples for days and I haven't found any counterexample so far... This is just a curious question. But if it's true, there has to be a proof, right?
combinatorics
combinatorics
edited 8 hours ago
Asaf Karagila♦
316k35 gold badges454 silver badges793 bronze badges
asked 8 hours ago
CastorCastor
582 bronze badges
edited 8 hours ago
Asaf Karagila♦
316k35 gold badges454 silver badges793 bronze badges
asked 8 hours ago
CastorCastor
582 bronze badges
edited 8 hours ago
Asaf Karagila♦
316k35 gold badges454 silver badges793 bronze badges
edited 8 hours ago
Asaf Karagila♦
316k35 gold badges454 silver badges793 bronze badges
edited 8 hours ago
Asaf Karagila♦
316k35 gold badges454 silver badges793 bronze badges
316k35 gold badges454 silver badges793 bronze badges
asked 8 hours ago
CastorCastor
582 bronze badges
asked 8 hours ago
CastorCastor
582 bronze badges
asked 8 hours ago
CastorCastor
582 bronze badges
582 bronze badges
$begingroup$
Since these cardinals are necessarily finite (otherwise the division has no meaning), the question is not a set theory question, but rather a combinatorial question.
$endgroup$
– Asaf Karagila♦
8 hours ago
$begingroup$
"But if it's true, there has to be a proof, right?" Not necessarily. Gödel's theorems guarantee the existence of statements that are true but not provable. But in this simple case, I think it is safe to say that yes, if it's true then there has to be a proof. I'm working on it:-)
$endgroup$
– TonyK
7 hours ago
add a comment
|
$begingroup$
Since these cardinals are necessarily finite (otherwise the division has no meaning), the question is not a set theory question, but rather a combinatorial question.
$endgroup$
– Asaf Karagila♦
8 hours ago
$begingroup$
"But if it's true, there has to be a proof, right?" Not necessarily. Gödel's theorems guarantee the existence of statements that are true but not provable. But in this simple case, I think it is safe to say that yes, if it's true then there has to be a proof. I'm working on it:-)
$endgroup$
– TonyK
7 hours ago
$begingroup$
Since these cardinals are necessarily finite (otherwise the division has no meaning), the question is not a set theory question, but rather a combinatorial question.
$endgroup$
– Asaf Karagila♦
8 hours ago
$begingroup$
Since these cardinals are necessarily finite (otherwise the division has no meaning), the question is not a set theory question, but rather a combinatorial question.
$endgroup$
– Asaf Karagila♦
8 hours ago
$begingroup$
"But if it's true, there has to be a proof, right?" Not necessarily. Gödel's theorems guarantee the existence of statements that are true but not provable. But in this simple case, I think it is safe to say that yes, if it's true then there has to be a proof. I'm working on it:-)
$endgroup$
– TonyK
7 hours ago
$begingroup$
"But if it's true, there has to be a proof, right?" Not necessarily. Gödel's theorems guarantee the existence of statements that are true but not provable. But in this simple case, I think it is safe to say that yes, if it's true then there has to be a proof. I'm working on it:-)
$endgroup$
– TonyK
7 hours ago
add a comment
|
2 Answers
2
active
oldest
votes
$begingroup$
As Asaf Karagila already noted, this is not a set theory question (nor a combinatorial one, I'd say), since it basically follows from an algebraic approach.
Define $|A|=a, |B|=b, |C|=c$ and $|Acap Bcap C|=x.$ Also, let $|(Acap B)setminus C|=r,$ $|(Acap C)setminus B|=s$ and $|(Bcap C)setminus A|=t.$ We can now rewrite the given inequality as $$fracs+xa+fract+xbleq 1+fracr+xbimplies fracs+xa+fract-rbleq 1implies b(s+x)+a(t-r)leq ab.$$ Since all the variables are non-negative and $cleq aleq b,$ we have that $$b(s+x)+a(t-r)leq b(s+x)+atleq b(s+x)+bt=b(s+t+x).$$ However, notice that $s+t+xleq c$ since $(Acap C)setminus B, (Bcap C)setminus A$ and $Acap Bcap C$ are disjoint subsets of $C,$ thus $b(s+t+x)leq bcleq ab,$ as desired.
answered 7 hours ago
FedeX333XFedeX333X
684 bronze badges
$endgroup$
$begingroup$
This is beautiful! It never occurred to me to consider those extra cardinals. You have ended my frustration, sir.
$endgroup$
– Castor
7 hours ago
add a comment
|
$begingroup$
Points of $C$ outside of $Acup B$ do not occur in your inequality. Therefore we may assume $Csubset Acup B$. It follows that $Acap Csubset A$ and $Bcap Csubset Bcap A$. This implies
$$Acap C+leq 1+ .$$
answered 6 hours ago
Christian BlatterChristian Blatter
182k10 gold badges123 silver badges342 bronze badges
$endgroup$
$begingroup$
How do you get $Bcap Csubset Bcap A$? This doesn't follow from $Csubset Acup B$. Take $A=1,2,3,4,B=3,4,5,6,C=3,5.$ Then $Bcap C =3,5,Acap B=3,4$
$endgroup$
– saulspatz
5 hours ago
add a comment
|
Your Answer
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/4.0/"u003ecc by-sa 4.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3353113%2fcurious-question-about-cardinality-of-finite-sets%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
As Asaf Karagila already noted, this is not a set theory question (nor a combinatorial one, I'd say), since it basically follows from an algebraic approach.
Define $|A|=a, |B|=b, |C|=c$ and $|Acap Bcap C|=x.$ Also, let $|(Acap B)setminus C|=r,$ $|(Acap C)setminus B|=s$ and $|(Bcap C)setminus A|=t.$ We can now rewrite the given inequality as $$fracs+xa+fract+xbleq 1+fracr+xbimplies fracs+xa+fract-rbleq 1implies b(s+x)+a(t-r)leq ab.$$ Since all the variables are non-negative and $cleq aleq b,$ we have that $$b(s+x)+a(t-r)leq b(s+x)+atleq b(s+x)+bt=b(s+t+x).$$ However, notice that $s+t+xleq c$ since $(Acap C)setminus B, (Bcap C)setminus A$ and $Acap Bcap C$ are disjoint subsets of $C,$ thus $b(s+t+x)leq bcleq ab,$ as desired.
answered 7 hours ago
FedeX333XFedeX333X
684 bronze badges
$endgroup$
$begingroup$
This is beautiful! It never occurred to me to consider those extra cardinals. You have ended my frustration, sir.
$endgroup$
– Castor
7 hours ago
add a comment
|
$begingroup$
As Asaf Karagila already noted, this is not a set theory question (nor a combinatorial one, I'd say), since it basically follows from an algebraic approach.
Define $|A|=a, |B|=b, |C|=c$ and $|Acap Bcap C|=x.$ Also, let $|(Acap B)setminus C|=r,$ $|(Acap C)setminus B|=s$ and $|(Bcap C)setminus A|=t.$ We can now rewrite the given inequality as $$fracs+xa+fract+xbleq 1+fracr+xbimplies fracs+xa+fract-rbleq 1implies b(s+x)+a(t-r)leq ab.$$ Since all the variables are non-negative and $cleq aleq b,$ we have that $$b(s+x)+a(t-r)leq b(s+x)+atleq b(s+x)+bt=b(s+t+x).$$ However, notice that $s+t+xleq c$ since $(Acap C)setminus B, (Bcap C)setminus A$ and $Acap Bcap C$ are disjoint subsets of $C,$ thus $b(s+t+x)leq bcleq ab,$ as desired.
answered 7 hours ago
FedeX333XFedeX333X
684 bronze badges
$endgroup$
$begingroup$
This is beautiful! It never occurred to me to consider those extra cardinals. You have ended my frustration, sir.
$endgroup$
– Castor
7 hours ago
add a comment
|
$begingroup$
As Asaf Karagila already noted, this is not a set theory question (nor a combinatorial one, I'd say), since it basically follows from an algebraic approach.
Define $|A|=a, |B|=b, |C|=c$ and $|Acap Bcap C|=x.$ Also, let $|(Acap B)setminus C|=r,$ $|(Acap C)setminus B|=s$ and $|(Bcap C)setminus A|=t.$ We can now rewrite the given inequality as $$fracs+xa+fract+xbleq 1+fracr+xbimplies fracs+xa+fract-rbleq 1implies b(s+x)+a(t-r)leq ab.$$ Since all the variables are non-negative and $cleq aleq b,$ we have that $$b(s+x)+a(t-r)leq b(s+x)+atleq b(s+x)+bt=b(s+t+x).$$ However, notice that $s+t+xleq c$ since $(Acap C)setminus B, (Bcap C)setminus A$ and $Acap Bcap C$ are disjoint subsets of $C,$ thus $b(s+t+x)leq bcleq ab,$ as desired.
answered 7 hours ago
FedeX333XFedeX333X
684 bronze badges
$endgroup$
As Asaf Karagila already noted, this is not a set theory question (nor a combinatorial one, I'd say), since it basically follows from an algebraic approach.
Define $|A|=a, |B|=b, |C|=c$ and $|Acap Bcap C|=x.$ Also, let $|(Acap B)setminus C|=r,$ $|(Acap C)setminus B|=s$ and $|(Bcap C)setminus A|=t.$ We can now rewrite the given inequality as $$fracs+xa+fract+xbleq 1+fracr+xbimplies fracs+xa+fract-rbleq 1implies b(s+x)+a(t-r)leq ab.$$ Since all the variables are non-negative and $cleq aleq b,$ we have that $$b(s+x)+a(t-r)leq b(s+x)+atleq b(s+x)+bt=b(s+t+x).$$ However, notice that $s+t+xleq c$ since $(Acap C)setminus B, (Bcap C)setminus A$ and $Acap Bcap C$ are disjoint subsets of $C,$ thus $b(s+t+x)leq bcleq ab,$ as desired.
answered 7 hours ago
FedeX333XFedeX333X
684 bronze badges
answered 7 hours ago
FedeX333XFedeX333X
684 bronze badges
answered 7 hours ago
FedeX333XFedeX333X
684 bronze badges
answered 7 hours ago
FedeX333XFedeX333X
684 bronze badges
684 bronze badges
$begingroup$
This is beautiful! It never occurred to me to consider those extra cardinals. You have ended my frustration, sir.
$endgroup$
– Castor
7 hours ago
add a comment
|
$begingroup$
This is beautiful! It never occurred to me to consider those extra cardinals. You have ended my frustration, sir.
$endgroup$
– Castor
7 hours ago
$begingroup$
This is beautiful! It never occurred to me to consider those extra cardinals. You have ended my frustration, sir.
$endgroup$
– Castor
7 hours ago
$begingroup$
This is beautiful! It never occurred to me to consider those extra cardinals. You have ended my frustration, sir.
$endgroup$
– Castor
7 hours ago
add a comment
|
$begingroup$
Points of $C$ outside of $Acup B$ do not occur in your inequality. Therefore we may assume $Csubset Acup B$. It follows that $Acap Csubset A$ and $Bcap Csubset Bcap A$. This implies
$$Acap C+leq 1+ .$$
answered 6 hours ago
Christian BlatterChristian Blatter
182k10 gold badges123 silver badges342 bronze badges
$endgroup$
$begingroup$
How do you get $Bcap Csubset Bcap A$? This doesn't follow from $Csubset Acup B$. Take $A=1,2,3,4,B=3,4,5,6,C=3,5.$ Then $Bcap C =3,5,Acap B=3,4$
$endgroup$
– saulspatz
5 hours ago
add a comment
|
$begingroup$
Points of $C$ outside of $Acup B$ do not occur in your inequality. Therefore we may assume $Csubset Acup B$. It follows that $Acap Csubset A$ and $Bcap Csubset Bcap A$. This implies
$$Acap C+leq 1+ .$$
answered 6 hours ago
Christian BlatterChristian Blatter
182k10 gold badges123 silver badges342 bronze badges
$endgroup$
$begingroup$
How do you get $Bcap Csubset Bcap A$? This doesn't follow from $Csubset Acup B$. Take $A=1,2,3,4,B=3,4,5,6,C=3,5.$ Then $Bcap C =3,5,Acap B=3,4$
$endgroup$
– saulspatz
5 hours ago
add a comment
|
$begingroup$
Points of $C$ outside of $Acup B$ do not occur in your inequality. Therefore we may assume $Csubset Acup B$. It follows that $Acap Csubset A$ and $Bcap Csubset Bcap A$. This implies
$$Acap C+leq 1+ .$$
answered 6 hours ago
Christian BlatterChristian Blatter
182k10 gold badges123 silver badges342 bronze badges
$endgroup$
Points of $C$ outside of $Acup B$ do not occur in your inequality. Therefore we may assume $Csubset Acup B$. It follows that $Acap Csubset A$ and $Bcap Csubset Bcap A$. This implies
$$Acap C+leq 1+ .$$
answered 6 hours ago
Christian BlatterChristian Blatter
182k10 gold badges123 silver badges342 bronze badges
answered 6 hours ago
Christian BlatterChristian Blatter
182k10 gold badges123 silver badges342 bronze badges
answered 6 hours ago
Christian BlatterChristian Blatter
182k10 gold badges123 silver badges342 bronze badges
answered 6 hours ago
Christian BlatterChristian Blatter
182k10 gold badges123 silver badges342 bronze badges
182k10 gold badges123 silver badges342 bronze badges
$begingroup$
How do you get $Bcap Csubset Bcap A$? This doesn't follow from $Csubset Acup B$. Take $A=1,2,3,4,B=3,4,5,6,C=3,5.$ Then $Bcap C =3,5,Acap B=3,4$
$endgroup$
– saulspatz
5 hours ago
add a comment
|
$begingroup$
How do you get $Bcap Csubset Bcap A$? This doesn't follow from $Csubset Acup B$. Take $A=1,2,3,4,B=3,4,5,6,C=3,5.$ Then $Bcap C =3,5,Acap B=3,4$
$endgroup$
– saulspatz
5 hours ago
$begingroup$
How do you get $Bcap Csubset Bcap A$? This doesn't follow from $Csubset Acup B$. Take $A=1,2,3,4,B=3,4,5,6,C=3,5.$ Then $Bcap C =3,5,Acap B=3,4$
$endgroup$
– saulspatz
5 hours ago
$begingroup$
How do you get $Bcap Csubset Bcap A$? This doesn't follow from $Csubset Acup B$. Take $A=1,2,3,4,B=3,4,5,6,C=3,5.$ Then $Bcap C =3,5,Acap B=3,4$
$endgroup$
– saulspatz
5 hours ago
add a comment
|
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3353113%2fcurious-question-about-cardinality-of-finite-sets%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
Since these cardinals are necessarily finite (otherwise the division has no meaning), the question is not a set theory question, but rather a combinatorial question.
$endgroup$
– Asaf Karagila♦
8 hours ago
$begingroup$
"But if it's true, there has to be a proof, right?" Not necessarily. Gödel's theorems guarantee the existence of statements that are true but not provable. But in this simple case, I think it is safe to say that yes, if it's true then there has to be a proof. I'm working on it:-)
$endgroup$
– TonyK
7 hours ago