About Me

!nversed Poignancy!

...I am an eclectic amalgamation of many seemingly paradoxical things. This can be exemplified in both my seemingly endless persistance on many topics and arguments, as well as my careful cautiousness on other topics and arguments. This is largely due to how astute I am of the topic: more knowledge, more persistant; less knowledge, obviously more cautious. I also have times of obsessive compulsions regarding certain things (mostly just my thoughts, however)...

Life and Death

!nversed Poignancy!

Life

An assembly

Possibly impossible

Perfectly interchangeable..

Death

That lives most upright

Beyond the unspoken

Neither a squiggle nor a quibble..

She and Me

!nversed Poignancy!

She

A daffodil

Tyrannizer of me

Breaking the colors of dusk!..

Me

The rising sun

Infringed with violations

The impurity in the salt..

Love and Poetry!

!nversed Poignancy!

Love

A puerile desire

Buried in the heart

Never leaves..

Poetry

Sentimentally melodramatic

Cursively recursive

My thoughts idiotic!

Many of us have a sense for physical units like 750 mL, 12 ounces, or a six-pack. But what does it mean to have an infinite size?

The math is fascinating. Perhaps the most remarkable result is that infinity is not a single size. One can talk intelligently about different sizes or types of infinity. This was first and famously demonstrated by Georg Cantor in the late 1800s, in work that laid groundwork for the field of set theory.

Set theory is one of my favorite subjects, but perhaps it is not for everyone. Luckily there is another way to approach infinity because of a new proof using game theory.


What is the size of a set of objects?

Size is the most basic property of a set. It is the number of objects in a set. We refer to the size of a set when we say things like “there are 5 people in front of me” or “a theater has 200 seats.”

Sometimes we do not care about absolute size but instead comparative size. For instance, in an election, it is most important to know which candidate gets more votes. What we usually do is count the number of votes for each side and then make a comparison.

But amazingly we don’t have to count to compare the size of two things. My favorite set theory textbook has the explanation of why:

To see how this is done, consider the problem of determining whether the set of all patrons of some theater performance has the same number of elements as the set of all seats. To find the answer, the ushers need not count the patrons or the seats. It is enough if they check that each patron sits in one, and only one seat, and each set is occupied by one, and only one, theatergoer.


In essence, comparing size is equivalent to the process of pairing elements. If elements from two sets pair up exactly one-for-one, then the sets are the same size. If one set has unpaired elements (say unfilled seats), then it is bigger.

This is common sense when dealing with finite sets, but things get nuanced and defy physical logic when we analyze infinite sets.


Countably infinite

The numbers we count with (the set of numbers {1, 2, 3, …}) are called natural numbers. The set keeps on going forever and so there are an infinite number of elements. Because we can “count” how many objects are in the set, the set’s size is described as being countably infinite.

How do other sets compare in size? The surprising part is that many sets are also countably infinite, even though they would first appear to be smaller or larger. We have to use the pairing process and not our intuition to decide the size.


For instance, consider the set of numbers {2, 3, 4, …}, that is, the natural numbers except for 1. Though this set has one element missing, it is in fact the same size as the natural numbers. The reason is it can be paired up exactly one-for-one with the natural numbers. Every number n from the natural numbers gets paired with the number n + 1 from this new set. Since both sets keep going on indefinitely, the pairing is proper and works. Hence the new set, though seemingly smaller, is also countably infinite.


The result can be hard to swallow in a physical sense. Imagine an infinite theater with seats labeled with the natural numbers that is originally full with people. The set {2, 3, 4, …} can be thought of physically as the seating arrangement of people if we asked the first person to leave the theater and then asked everyone to move back one seat. The theater would somehow still be full despite losing one person. And even more strange is that if the first person returns, we could clear the first seat by asking everyone to move up one seat.


One mathematician, Hilbert, presented many other similar paradoxes of the infinite. He used an infinite hotel and so such problems fall under Hilbert’s Hotel paradox.


The physical analogies make the math seem absurd, but in fact everything is sound and well-derived. So I keep myself straight by thinking about things as abstract pairings.


Other sets are also countably infinite, even though they too seem to be of different size. The even numbers are exactly the same size as the natural numbers, as each number n can be paired with 2n. Similarly, the odd numbers are countably infinite, and so is any infinite subset of the natural numbers, like the prime numbers.


Amazingly the set of rational numbers–the fractions of natural numbers (and their negatives)–is also countably infinite. Here is one illustration of how you can “count” the fractions.


At this point every set we have come up with is countably infinite. So it’s worth asking: are there any sets bigger? It turns out there are bigger sets that are “uncountably” infinite. This is where the game theory proof comes in.


Game theory: proof of the uncountably infinite

I’ll summarize the proof below.

The game involves two-players, Alice and Bob, picking numbers on the interval [0,1]—the set of real numbers (all the decimals) between the numbers 0 and 1. Here are the rules:

  1. Alice initially picks some subset S of the interval [0,1].
  2. Alice starts the game by picking a number a1 between 0 and 1.
  3. Bob then picks a number b1 bigger than Alice’s choice a1 but less than 1.
  4. Alice then picks a number a2 bigger than her previous choice a1 but less than Bob’s previous choice b1.
  5. In general, Alice and Bob alternate picking numbers between the two previous numbers played. That is, on turn n Alice has to pick a number an such that an-1 < an < bn-1 and Bob has to pick a number bn such that an < bn < bn-1.
  6. A famous theorem guarantees that the sequence of numbers a1, a2, … converges to a number. Call this number X.
  7. If X is in the set S, then Alice wins. Otherwise Bob wins.

The proof that [0,1] is uncountably infinite

The above proof has three parts:

  1. If S is countably infinite, then Bob has a winning strategy.
  2. Alice can always win the game.
  3. The set [0,1] is uncountable.

Here are the details on the individual steps.


1. If S is countably infinite, then Bob has a winning strategy.

Imagine the set S is countably infinite. Then the set can be enumerated as s1, s2, and so on (like seats in an infinite theater). It turns out Bob can always make sure that the sequence does not converge to any of these values. That is, Bob can make sure X does not equal any sn.

Here’s the strategy: on turn n, Bob picks sn if it is a legal move, and otherwise picks anything. This will guarantee it.

Why? If Bob does get to pick sn, then he forces the remaining numbers to be smaller than sn so the sequence cannot converge to sn.

On the other hand, if Bob cannot pick sn, then he can pick any legal move. The only reason Bob could not pick sn is if Alice has already picked a number higher than sn. Accordingly, the remaining numbers picked in the game will be larger than sn so the sequence would converge a number larger than sn. Thus Bob can just pick any allowable number on this turn and continue.

Bob can continue this strategy to make sure that the sequence never converges to any element of S. This means X would not be in S and Bob would win. In summary, if S is countably infinite, Bob can always win the game.

Unfortunately, the odds are stacked against Bob.


2. Alice can always win the game.

Alice can pick S to be any subset of the interval [0,1]. This means Alice can pick the entire subset [0,1]–cheap, yes, but effective. Since Alice and Bob are always picking numbers between 0 and 1, the sequence must converge in the interval. Hence Alice can always win the game.


3. The set [0,1] is uncountably infinite.

This follows directly! By point 1, if [0,1] were countably infinite, then Bob could win the game. But by point 2 he cannot win, and therefore the set [0,1] must be larger and uncountably infinite.

Reported in through some reliable sources today, the private sector is arguing to the Productivity Commission that India adopt a paid parental leave scheme that allows for 28 weeks paid maternity leave, 4 weeks paid paternity leave and 4 weeks pay to employers for replacement employees. It looks like it is for full pay. So how will it be funded? The answer a payroll tax on employers of 0.5% and an increase in income taxes of 0.5% (I think, as it is stated in the form of a wage tax). Oh yes, and the baby bonus would remain to take care of those who didn’t have a job previously.

Some things need to be said about this. First, the division of taxes between employers and employees is arbitrary and doesn’t matter. That is Economics 101. So we are really talking about a 1 percent increase in taxes to fund this. Second, watch those wages rise during pregnancy. There is a massive incentive to increase pay during the last trimester. Every dollar increase during that time is a dollar benefit to the employee. Third, there is a big incentive for the highest earning parent to avail themselves on this unless you say it is for mothers only. Finally, the calculations assume that 20 percent of new mothers will not avail themselves of this scheme. With incentives like this, surely that is way overstated.

What this example demonstrates is how hard it is to enact a system of paid parental leave. In this case, it is a large tax on the non-parents and also on the lower-income segments of society. Think about it, if you have a 50 year working life with an average pay of Rs 100,000 per annum and have two children amount to 1 of those years coming back for free that is a Rs 50,000 tax in return for Rs 100,000 of payment. The difference is coming from the non-parents, spouses and somewhere else. How do we justify that cross-subsidy?

Actually, it is worse than all that. This type of scheme puts a massive incentive for parents to delay having children by many years until their income is high enough. Have them too soon and you are not getting your money's worth.

So hey buddy youths- Use a stop, read and wait protocol as of now lolz. But, taking a counter view- I can actually scent the side effects already; Does anyone see a contour of population-infaltion from the private sectorial employee bunch?! and dont you think that global melt down has paved way not only to economic deflation, but also to population deflation?! - Just some random thoughts ;)

Courage..

Scribbled by Bharath C On March 15, 2009 17 Thoughts have been Sprinkled!, Your Take?
Crashing's are violent and violent are the crashes,
Oh pity, the fragile canoe in she.
Undone was she by his and outclassed was her's by him.
Ragged out and torn apart was her feminine dignities, by the brutality in his filthy canine.
Alas!,doomed are her dreams and damned are her zeals, Her life,now a trod. So,
Get up, all you motherly angels-Fight this deadly act,
Egress forth thy anger, leathalize thy endurance-butcher out this bastardly bastardy with utmost gut and Courage!

Prompted at Acrostic Only

Phew! Yet another fiasco and it was yet another bad power-play!. The week has yet again started sober,sombre and with a snigger. But, amidst all these fabulously decorated blue light there was that little purple patch that I could see. And those were my thoughts again ;). There have been one too many occasions wherein in have run out of luck and I'm sure that each one of you would have had a similar experience, perhaps, some of you would have even had a counter-experience. All said and done, there's that lonely ray of quibble that always lies unanswered- and thats the "distribution of luck in our lives".

So, here I am- with another equally crappy thoughts pouring out yet another fabulously dumb thesis, wherein I try to explain how exactly luck plays in our lives and why is it that we are not able to predict the "degree of luck" and how are all these related mathematically. And for the uninitiated let me name this thesis as the "Bharath's ambiguous luck-density principle"[BALP in short]

Ok, Now, Let me start with the basis of the entire scenario. The BALP can often be simply explained as the statement that the measurement of luck and effort necessarily perturbs an objects life-path, and vice versa—i.e., BALP is a manifestation of the time-spacial effect.

This explanation can sometimes be misleading in a modern context, because it makes it seem that the obstructions are somehow conceptually avoidable—and that there are states of the object with definite decorum wherein its luck-density and the destiny function are known , but though the experimental facts as we have today(its almost trivial!) are just not good enough to produce those states. In fact, states with both definite luck-density and destiny-function just do not exist in life's theoretical mathematics, so it is not the measurement equipment that is at fault.

It is also misleading in another way, because sometimes it is a failure to measure the object that produces the (bad)luck. For example, if while traveling on a bike (through Bangalore roads) without a helmet on a busy last Monday of the month and still managing to get away without committing any misdemeanors. Whoa!, yeah- Its more likely that the object was not observed at all, then its luck-density becomes uncertain by a large amount.More so, because it beats all expectations!.

It is misleading in yet another way, because sometimes the measurement can be performed far away. Lets consider the "sans helmet" example and extend it to two objects that are traveling in the same or opposite directions from the decay of policetronuims and it so happens that only one of them is caught!, then the luck density of the two two are opposite. By measuring the luck denstiy of one particle, the luck-density of the other is determined. This case is subtler, because it is impossible to introduce more uncertainties by measuring a distant particle, but it is possible to restrict the uncertainties in different ways, with different statistical properties, depending on what property of the distant object you choose to measure. Now let us try to justify this claim mathematically-





So Eureka!, here we come- Dosnt that tell you that the equation truly converges to the Uncertainty Principle?!.

Lolz!, It actually does!- and thus we can trivially claim that luck and destiny plays a key role in our lives and our life cannot be predicted because of the BALP and because we cannot find the way our luck or destiny behaves.

So, for all those who believe that luck is a key factor, well Long hail- But, be lest assured that your luck will always behave the same way as you want it to..;) [ More so , because their randomness is more random than just random..:P]


PS : I'm extremely sorry for the illegibility in the equations. Thats more so because of blogger's primitive alignment and special symbol usage laws.
You can download the complete proof here.

Bloodshed

Scribbled by Bharath C On March 12, 2009 6 Thoughts have been Sprinkled!, Your Take?
Extremism at its pinnacle,
The innocents despair-
"Bloody Bloodshed by the Bastardy!"
As the innocents despair,
Extremism at its pinnacle..

Prompted at NaiSaiKu Challenge..
Well,amidst all those crap theories and un-poetically rabid thoughts that I've been posting here over the last few weeks [ More so, with many a brick-bats]. Today I thought that I could get all of you into a rather serious management stuff.

Earlier today, I happened to read these thoughts from a friend of mine, he felt that

"Considering our very recent entry to world of space technology the progress is no wonder astounding.But regardless of all these achievements, did we really need to spend such a huge amount on this? America did it, Russia did it and both said, "Senora! Nothing but heap of dust". Then why should we again go for it, spending millions of dollars? "

(Disclaimer : The quotes are pasted here as quoted; Appreciation and accolades on the above block quoted quote are to be handed over to the author only.)


I was stunned!, for a moment I thought that all we wanted to do is to just to quench our ego clashes and more so to prove others the 'blatant' powers that we posses in the field of tech. is not so 'blatant' as they think!; But, it was just about time that I invoked that minuscule processing time slice that I have been blessed with. And what followed it were these "truly blatant" thoughts of mine ;)


What at an uninitiated spur of the moment seemed like a wrong move, now, seemed to be a pretty good move for me. I also saw this as an excellent FGI (Foreign Governmental Investment) strategy too!--I felt that this on some line might just be the right approach to reduce our operational cost in the field of space research!- Guess how?- Well, yes!- See, having proved our brain force and the intellectual capital, I think they might be expecting a JV from both the blocks of nations ones who've tasted the moon mission and several others who want to take a hit at the moon.

Now, lets calculate the investments and returns ratio.:-

Officially declared total budget of chandrayaan is placed at $86 million; And if you could look at the perks that are visible(definitely not a mirage), its more or less the only huge investment that GOI would be making(or made)- Now all that they need to do is to spend a miserly amount towards this on a futurely YoY basis. Which i feel would be anywhere less than around $10 million per year [ Thats about Rs 50 crores] against the defence budget of a whopping Rs17,590 crores for research as a whole! [The total budget thought stands way ahead! a hugely staggering Rs 1,41,703 crores!].

Hmm, later coming to the point on the annual budget of ISRO alone its rated at about $17million per year, So essentially what they have done with Chandrayaan is that they have moved ahead of their budget for 4 years and 3 months- But, the key factor is that they will be heavily cutting on yearly investments by about 44% YoY- Apparently they will be repaying the deficit by around 8 years !.

Now, how far do these figures help us to find the investment to returns ratio- Well I cant actually give you a quantitative value, since I know not about the JV swap ratios; But, what i can is tell you that it would be a "investment attractor" for a minimum of 3 decades- Even if I cap the FGIs at 50million per year [Well, i think thats a very low guess] I think we'll be saving atleast around $900 million over the next 30 years!-
THATS A STAGGERING 100% RETURNS PER ANNUM IF CALCULATED OVER A 3 DECADE PERIOD!!

Isnt that astounding?! Its more like you are given 1000 bucks to prepare a cake and then later you are again paid to eat it all alone.

My thoughts though, were purely on a monetary frame of mind, but, if you take into consideration all those "mind-set","morale boost" and "global recognition" returns as an parametric point of view of investment to return ratio; Hmm, I must say that they are just too too high. [ I can only give you a properly calculated worksheet at a later point].

But, there's something that I wouldnt be able to answer and justify, and thats if you ask me as to "why spend lakhs of crores of rupees on 'useless research' ". Sadly, I have no answers for that. May be one of you might link my post on to your blog and explain this important syllogistic factor.
Ahem!. Well, I know that there’s some brickbats in store for me today..:P. This is my second math misery this week [Lolz!]. But, yeah- all said; I still feel that this one is pretty lucid and perhaps a bit spicy too- Thus paving a pathway for a nice rapot!.

Coming to the theme, I always wondered as to why probability of success could not be calculated. Now, let me explain- Last week I installed some utterly crap symbian s60v2 game on to my N72, it had these so called real-life congruent-mirror-technology behind it; The aim of the game was to help a “person”[who happens to be the hero of the game!] achieve his expectations; If the explanation sounded drifting, I’ll sneak in an example scenario here, Its like if the “person” “expects” to win the Wimbledon grand slam, you need to make him achieve that!.

Initially I felt that the game had a lot of logical fallacies and some “pot holes” of horribly blatant blunders. But after the first round of novical play- I felt that this had a very high content of rich mathematics involved- Yes! Some really cool and interesting probabilistic approaches were on cards. So, as usual (jobless me)- I started musing about this, and to my amaze – the ideas started flowing at some extra-ordinary speed, my pipe-line was overflowing, yet the processor was stable and making some fabulous round of computations. And when it all ended after a mano-man of about 60minutes, I was done. And what I ended up formulating was the success probability of a person X in the Universe of Discourse. Here’s some insight into it---

Let's apply the notion of mathematical expectation to the example of a novice player seeking admittance to a tennis club. To be admitted, the fellow had to beat in two successive games members G (good) and T (top) of the club. With probabilities g and t (t < g) of winning against G and T, the fellow had to choose between to possible orders of games: GTG or TGT. Paradoxically, the second choice appeared to be preferable gaining the fellow the membership with the probability gt(2 - t) against the smaller gt(2 - g) for the sequence GTG.
We shall be looking for the expected number of wins. Using L for a loss and W for a win for the aspiring novice, we shall consider two sample spaces. Following the havils, the space consists of 8 possible outcomes of a sequence of three games:

LLL, LLW, LWL, LWW, WLL, WLW, WWL, WWW

However note that in the sequences LLL, LLW, WLL, WLW the third game is superfluous as the result of the first two make it impossible for the fellow to win two successive games, whereas the third game is unnecessary in the last two sequences WWL, WWW because the two first wins already gain the fellow admittance to the club. This makes possible and reasonable to consider a smaller sample space:

LL, LWL, LWW, WL, WW

For the sequence TGT we have the following probabilities:

Win/Loss sequence Probability

LLL (1 - t)(1 - g)(1 - t)
LLW (1 - t)(1 - g)t
LWL (1 - t)g(1 - t)
LWW (1 - t)gt
WLL t(1 - g)(1 - t)
WLW t(1 - g)t
WWL tg(1 - t)
WWW tgt

for the first sample space and


Win/Loss sequence Probability
LL (1 - t)(1 - g)
LWL (1 - t)g(1 - t)
LWW (1 - t)gt
WL t(1 - g)
WW tg

for the second. In both cases, the probabilities add up to 1, as required. Choosing the easier way out, we verify this only for the latter:

(1 - t)(1 - g) + (1 - t)g(1 - t) + (1 - t)gt + t(1 - g) + tg
= (1 - t)(1 - g) + [(1 - t)g(1 - t) + (1 - t)gt] + t(1 - g) + tg
= (1 - t)(1 - g) + (1 - t)g + t(1 - g) + tg
= [(1 - t)(1 - g) + t(1 - g)] + [(1 - t)g + tg]
= (1 - g) + g
= 1.
Now we introduce the random variable N that denotes the number of wins for the candidate. In the first case, N may be 0, 1, 2, or 3; in the second case, the are only three possible values: 0, 1,2.

The expectations E1 and E2 are
E1(N, TGT) = 0•(1 - t)(1 - g)(1 - t)
+ 1•(1 - t)(1 - g)t
+ 1•(1 - t)g(1 - t)
+ 2•(1 - t)gt
+ 1•t(1 - g)(1 - t)
+ 2•t(1 - g)t
+ 2•tg(1 - t)
+ 3•tgt
= 2t + g

and, correspondingly,
E2(N, TGT) = 0•(1 - t)(1 - g)
+ 1•(1 - t)g(1 - t)
+ 2•(1 - t)gt
+ 1•t(1 - g)
+ 2•tg
= t + g + tg - t2g.

Similarly,
E1(N, GTG) = t + 2g and
E2(N, GTG) = t + g + tg - tg2.

Since t < g, we see that

E1(N, TGT) < E1(N, GTG),

as expected (pun intended). We also have

E2(N, TGT) < E2(N, GTG),

which ameliorates the paradoxical situation that arose from the pure count of probabilities. Although, the probability of gaining the membership playing the top guy first is larger then when playing first just a good member, the expected number of the wins is greater when postponing the confrontation with the top player.

So whats astounding is that the player can actually have very high expectations of wining the tourney. Wow!, I was stunned!!- I have heard people bog down since they are under-dogs and few other yombering around saying that they have no chance what so ever of achieving their goals. Now, all you people out there, read this mathematical snippet and get inspired to conquer the world!. Your chances are not meager by any means, its just that you need to apply things and have a solidiifed state of mind!. Lolz and talking about solidification, I hope to follow this up with some proof for the same along Chemistry of Human Physical Biology..:P

But, till then- Hold your breath and say Sigh!- I can also beat Federer!(Ok, girls and more pontificially ladies you can use Ana Ivanovic too! :P)
Just about few hours ago I just happened to read a nice quibble from a friend of mine which was hyper-centrifuged on "why is that a person(at least the majority) would not be able to lead a life as a loner". Well, I was really excited about this quote!. So, I felt that I should be able to prove it mathematically- So, I picked up my pen (yeah, ofcouse my balck pen :P - No prizes for guess ;) ) and took my way with the proof; and this was a dove-tail of the entire pipe-line.

Lets start from the grass-roots; The LONER PROBLEM requires us to relate and justify that from a set of 2n objects (Boys or girls) we would be able to associate atelast n-pairs as partially or fully functional dependent. Ok for our simplicity lets have a sex ratio of 1:1 and let our aim be to match 'n' girsl with the set of 'n' boys(or girls- But yeah, since we want to make it simple we'll go by the old tradition...lolz!). So, each girl (after a long and no doubt exhausting deliberation) submits a list of boys she likes. We also make an assumption that being of noble character no boy will break a heart of a girl who likes him by turning her(or him) down. So, although, girls appear to seize the initiative by advertising their preferences, the situation is quite symmetric and is best represented by a sparse matrix. An element aij in row i and column j is 1 iff there is a dependency between the girl #i and the boy number #j and is feasible. aij is 0, otherwise. Sometimes all the girls can be given away, sometimes no dependency is also possible.

The dependency condition can be formulated in several equivalent ways:

1. Every set of r girls, 1 ≤ r ≤ n depends on at least r boys.
Pick up any s columns. Concentrate on rows that have at least one 1 in the selected columns. The number of such rows must not be less than s.

2. Every set of s boys, 1 ≤ s ≤ n depends on at least s girls.
Pick up any r rows. Concentrate on columns that have at least one 1 in the selected rows. The number of such columns must not be less than r.

3. No zero r by s submatrix may satisfy r + s > n.
If such a matrix exists then some r girls can marry only (n - s) boys outside the submatrix. Since r > n - s, there are just too few boys to satisfy all r girls.

Proof 1.

The necessecity is obvious. The sufficient part is shown by induction. The case of n = 1 and a single pair being dependent on each other requires a mere technicality to arrange a dependency. Assume we have already established the theorem for all k by k matrices with k < n. For the case of n girls and boys, the dependency may be satisfied with room to spare or just barely. In the first case, there is enough room for the first girl to be dependent on whomever she likes; the dependency condition will still be satisfied for the remaining (n - 1) and (n - 1) boys. Indeed, every 0 < r < n girls like more than r boys. One of those boys may have been the one who is dependent on the first girl - but without whom there are still at least r boys. So, after striking off any eligible pair we shall be left with (n - 1) girls and boys for whom the dependency condition still holds and, by the inductive hypothesis, complete match is possible.

In the second case, there are r < n girls who like exactly r boys. By the inductive hypothesis, a complete match exists for these r girls so they can be dependent to the r boys they like. The trick is to show that the remaining girls can be matched to the remaining boys. Consider any s of the remaining n - r girls. The r already dependent girls plus these s girls must like at least r + s boys as assured by the second condition. Since the r already dependent girls don't like boys other than the r they are dependent on, the s girls must like s boys other than the already dependent boys. Hence the remaining n - r girls satisfy the dependency condition with the undependent boys; and so a complete match is possible for the remaining girls with the remaining boys, providing a complete match for all the girls.

Another proof based on the Inclusion-Exclusion principle deals directly with subsets A1, A2, ..., An and establishes existence of an SDR. The Inclusion-Exclusion principle asserts that for any two finite sets A and B |A∪B| + |A∩B| = |A| + |B|, where vertical bars denote the cardinality (the number of elements) of a set. Lets prove that now. [ I know its too hard to digest, but, yeah..Lets continue this for another 5 minutes- It real fun! ]

Assuming that the dependency condition holds for the sets A1, A2, ..., An, let the sets be depleted until a family F = {B1, B2, ..., Bn} is reached such that removal of 1 more element from any of the Bi would cause the dependency condition to be violated. We assert that each member of F consists of a single element; because these elements are distinct (by the dependency condition), F itself is the required SDR. Suppose, on the contrary, that, say B1 has 2 elements, Let's say, B1 contains at least two elements, x and y. By the minimality of the collection, removal of either x or y would violate the matching condition.

Therefore, there exist two sets of indices P and Q such that
X = (B1-{x})∪(∪{Bi: i P}) and Y = (B1-{y})∪(∪{Bi: i Q}) with |X| ≤ |P| and |Y| ≤ |Q|. Consequently, by the Inclusion-Exclusion priciple,
(*) |X∪Y| + |X∩Y| = |X| + |Y| ≤ |P| + |Q|
On the other hand, X∪Y = B1∪(∪{Bi: i P∪Q}) and X∩Y = ∪{Bi: i P∩Q} the dependency condition gives
|X∪Y| ≥ 1 + |P∪Q| and |X∩Y| ≥ |P∩Q|.
From here, with one more application of the Inclusion-Exclusion principle, we obtain
|X∪Y| + |X∩Y| ≥ 1 + |P∪Q| + |P∩Q| = 1 + |P| + |Q| > |P| + |Q|
which contradicts (*).
Lolz..aint that some sense?!
Bookmark and Share