[Edit: I have extended the deadline until the day of the final exam.]

Here are some extra credit problems. They are due at the latest by November 1, the day of the second midterm (just turn them in when you come to take the test), but you can of course turn them earlier. You can turn in as many as you want, this is completely voluntary.

All these problems can be solved arguing by contradiction. They tend to require at least one additional idea. The problems come for Loren C. Larson’s book “Problem-solving through problems.”

In a party with 2000 people, among any set of four there is at least one person who knows each of the other three. There are three people who are not mutually acquainted with each other. Prove that the other 1997 people know everyone at the party. (Assume that whenever a person knows a person , then also knows .)

Prove that there are no positive integers , , , and such that .

Every pair of communities in a country are linked directly by exactly one mode of transportation: bus, train, or airplane. All three modes of transportation are used in the country; no community is served by all three modes, and no three communities are linked pairwise by the same mode. For example, four communities can be linked according to these stipulations in the following way: bus, , , , ; train, ; airplane, .

Give an argument to show that no community can have a single mode of transportation leading to each of three different communities.

Give a proof to show that five communities cannot be linked in the required manner.

Let be a set of rational numbers with the property that whenever and are (not necessarily distinct) elements of , then also and . Moreover, suppose that for any rational number , exactly one of the following is true: , , .

Prove that 0 does not belong to .

Prove that all positive integers belong to .

Prove that is the set of all positive rational numbers.

43.614000-116.202000

Advertisements

Like this:

LikeLoading...

Related

This entry was posted on Monday, October 10th, 2011 at 12:02 am and is filed under 187: Discrete mathematics. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

I thought about this question a while ago, while teaching a topics course. Since one can easily check that $${}|{\mathbb R}|=|{\mathcal P}({\mathbb N})|$$ by a direct construction that does not involve diagonalization, the question can be restated as: Is there a proof of Cantor's theorem that ${}|X|

First of all, note (as Monroe does in his question) that if $\mathbb P,\mathbb Q$ are ccc, then $\mathbb P\times\mathbb Q$ is $\mathfrak c^+$-cc, as an immediate consequence of the Erdős-Rado theorem $(2^{\aleph_0})^+\to(\aleph_1)^2_2$. (This is to say, if $\mathbb P$ and $\mathbb Q$ do not admit uncountable antichains, then any antichain in their product ha […]

The technique of almost disjoint forcing was introduced in MR0289291 (44 #6482). Jensen, R. B.; Solovay, R. M. Some applications of almost disjoint sets. In Mathematical Logic and Foundations of Set Theory (Proc. Internat. Colloq., Jerusalem, 1968), pp. 84–104, North-Holland, Amsterdam, 1970. Fix an almost disjoint family $X=(x_\alpha:\alpha

At the moment most of those decisions come from me, at least for computer science papers (those with a 68 class as primary). The practice of having proceedings and final versions of papers is not exclusive to computer science, but this is where it is most common. I've found more often than not that the journal version is significantly different from the […]

The answer is no in general. For instance, by what is essentially an argument of Sierpiński, if $(X,\Sigma,\nu)$ is a $\sigma$-finite continuous measure space, then no non-null subset of $X$ admits a $\nu\times\nu$-measurable well-ordering. The proof is almost verbatim the one here. It is consistent (assuming large cardinals) that there is an extension of Le […]

R. Solovay proved that the provably $\mathbf\Delta^1_2$ sets are Lebesgue measurable (and have the property of Baire). A set $A$ is provably $\mathbf\Delta^1_2$ iff there is a real $a$, a $\Sigma^1_2$ formula $\phi(x,y)$ and a $\Pi^1_2$ formula $\psi(x,y)$ such that $$A=\{t\mid \phi(t,a)\}=\{t\mid\psi(t,a)\},$$ and $\mathsf{ZFC}$ proves that $\phi$ and $\psi […]

A notion now considered standard of primitive recursive set function is introduced in MR0281602 (43 #7317). Jensen, Ronald B.; Karp, Carol. Primitive recursive set functions. In 1971 Axiomatic Set Thoory (Proc. Sympos. Pure Math., Vol. XIII, Part I, Univ. California, Los Angeles, Calif., 1967) pp. 143–176 Amer. Math. Soc., Providence, R.I. The concept is use […]

The power of a set is its cardinality. (As opposed to its power set, which is something else.) As you noticed in the comments, Kurepa trees are supposed to have countable levels, although just saying that a tree has size and height $\omega_1$ is not enough to conclude this, so the definition you quoted is incomplete as stated. Usually the convention is that […]

The key problem in the absence of the axiom of replacement is that there may be well-ordered sets $S$ that are too large in the sense that they are longer than any ordinal. In that case, the collection of ordinals isomorphic to an initial segment of $S$ would be the class of all ordinals, which is not a set. For example, with $\omega$ denoting as usual the f […]