Problem 1 asks to show that the relation defined as follows is antisymmetric: Given a set the relation is defined on the subsets of by setting for iff where denotes set-theoretic difference of sets.

To show that is antisymmetric, we need to show that whenever are such that and then Suppose satisfy these assumptions. We need to show that they are equal as sets, i.e., that they have the same elements.

By definition, holds iff and holds iff Recall that if are sets, then It follows that iff every element of is also an element of and that iff every element of is also an element of But these two facts together mean precisely that and have the same elements, i.e., that as we needed to show.

Problem 2(a) of quiz 6 asks to consider the relation defined on by setting for iff and to show that is an equivalence relation. This means that is reflexive, symmetric, and transitive. Problem 2(a) of quiz 5 asks to show one of these properties.

To show that is reflexive, we need to show that for any we have that i.e., that But is certainly divisible by 5.

To show that is symmetric, we need to show that for any if it is the case that then it is also the case that Suppose then that This means that i.e., there is an integer such that But then showing that also i.e.,

To show that is transitive, we need to show that if and both and hold, then also holds. But if and then and But then it is certainly the case that Since this proves that, indeed or as we needed to show.

(If one feels the need to be somewhat more strict: That means that there is an integer such that Similarly, means that there is an integer such that But then showing that there is an integer such that namely, we can take )

Problem 2(b) asks to find all natural numbers such that where is as defined for problem 2(a).

That means exactly the same that Since and an integer is a multiple of 5 iff it ends in 5 or 0, we need to find all natural numbers such that ends in or Since and is even for all naturals we actually need to find all natural numbers such that ends in 8. For this, we only need to examine the last digit of the numbers and we find that these last digits form the sequence which is periodic, repeating itself each 4. This means that the numbers we are looking for are precisely i.e., the natural numbers of the form with

Advertisements

Like this:

LikeLoading...

Related

This entry was posted on Sunday, March 14th, 2010 at 10:44 pm 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 was working with one of students(Josue Gomez) in your class.
From problem 2 (b,)
I guess 5 divides 0 since 5*0 = 0. so need to say n is the form 4k + 3 where k is greater than or equal to 0.
I understand 0 is not natural number. I guess k can be 0 also.

(As I pointed out in a comment) yes, partial Woodinness is common in arguments in inner model theory. Accordingly, you obtain determinacy results addressing specific pointclasses (typically, well beyond projective). To illustrate this, let me "randomly" highlight two examples: See here for $\Sigma^1_2$-Woodin cardinals and, more generally, the noti […]

I am not sure which statement you heard as the "Ultimate $L$ axiom," but I will assume it is the following version: There is a proper class of Woodin cardinals, and for all sentences $\varphi$ that hold in $V$, there is a universally Baire set $A\subseteq{\mathbb R}$ such that, letting $\theta=\Theta^{L(A,{\mathbb R})}$, we have that $HOD^{L(A,{\ma […]

A Wadge initial segment (of $\mathcal P(\mathbb R)$) is a subset $\Gamma$ of $\mathcal P(\mathbb R)$ such that whenever $A\in\Gamma$ and $B\le_W A$, where $\le_W$ denotes Wadge reducibility, then $B\in\Gamma$. Note that if $\Gamma\subseteq\mathcal P(\mathbb R)$ and $L(\Gamma,\mathbb R)\models \Gamma=\mathcal P(\mathbb R)$, then $\Gamma$ is a Wadge initial se […]

Craig: For a while, there was some research on improving bounds on the number of variables or degree of unsolvable Diophantine equations. Unfortunately, I never got around to cataloging the known results in any systematic way, so all I can offer is some pointers to relevant references, but I am not sure of what the current records are. Perhaps the first pape […]

Yes. Consider, for instance, Conway's base 13 function $c$, or any function that is everywhere discontinuous and has range $\mathbb R$ in every interval. Pick continuous bijections $f_n:\mathbb R\to(-1/n,1/n)$ for $n\in\mathbb N^+$. Pick a strictly decreasing sequence $(x_n)_{n\ge1}$ converging to $0$. Define $f$ by setting $f(x)=0$ if $x=0$ or $\pm x_n […]

All proofs of the Bernstein-Cantor-Schroeder theorem that I know either directly or with very little work produce an explicit bijection from any given pair of injections. There is an obvious injection from $[0,1]$ to $C[0,1]$ mapping each $t$ to the function constantly equal to $t$, so the question reduces to finding an explicit injection from $C[0,1]$ to $[ […]

One way we formalize this "limitation" idea is via interpretative power. John Steel describes this approach carefully in several places, so you may want to read what he says, in particular at Solomon Feferman, Harvey M. Friedman, Penelope Maddy, and John R. Steel. Does mathematics need new axioms?, The Bulletin of Symbolic Logic, 6 (4), (2000), 401 […]

"There are" examples of discontinuous homomorphisms between Banach algebras. However, the quotes are there because the question is independent of the usual axioms of set theory. I quote from the introduction to W. Hugh Woodin, "A discontinuous homomorphism from $C(X)$ without CH", J. London Math. Soc. (2) 48 (1993), no. 2, 299-315, MR1231 […]

This is Hausdorff's formula. Recall that $\tau^\lambda$ is the cardinality of the set ${}^\lambda\tau$ of functions $f\!:\lambda\to\tau$, and that $\kappa^+$ is regular for all $\kappa$. Now, there are two possibilities: If $\alpha\ge\tau$, then $2^\alpha\le\tau^\alpha\le(2^\alpha)^\alpha=2^\alpha$, so $\tau^\alpha=2^\alpha$. In particular, if $\alpha\g […]

Fix a model $M$ of a theory for which it makes sense to talk about $\omega$ ($M$ does not need to be a model of set theory, it could even be simply an ordered set with a minimum in which every element has an immediate successor and every element other than the minimum has an immediate predecessor; in this case we could identify $\omega^M$ with $M$ itself). W […]

Dr. Caicedo,

I was working with one of students(Josue Gomez) in your class.

From problem 2 (b,)

I guess 5 divides 0 since 5*0 = 0. so need to say n is the form 4k + 3 where k is greater than or equal to 0.

I understand 0 is not natural number. I guess k can be 0 also.

Thanks for your lecture!

Ei

The

natural numbersbegin with 0. That is the definition we are using. The integers that are larger than 0 are, naturally, thepositive integers.Oh thank you!