22 | January | 2008 | A kind of library

116b- Homework 2

January 22, 2008

Due Tuesday January 29 at the beginning of lecture.

Update: There is a typo in problem 2, it must be $z<y$ .

Leave a Comment » | 116b: Computability and incompleteness | Permalink
Posted by andrescaicedo

116b- Lecture 5

January 22, 2008

We showed that a function is in $\mathsf{R}$ iff it has a $\Sigma_1$ -graph. It follows that a set is r.e. iff it is $\Sigma_1$ -definable.

Leave a Comment » | 116b: Computability and incompleteness | Permalink
Posted by andrescaicedo

You are currently browsing the A kind of library blog archives for the day Tuesday, January 22nd, 2008.
Categories

Categories
Search

Mathematical links
My pages
Others
Mathoverflow
- Answer by Andrés E. Caicedo for Who introduced direct limits? April 19, 2020
  As suggested by Gerald, the notion was first introduced for groups. Given a directed system of groups, their direct limit was defined as a quotient of their direct product (which was referred to as their "weak product"). The general notion is a clear generalization, although the original reference only deals with groups. As mentioned by Cameron Zwa […]
  Andrés E. Caicedo
- Answer by Andrés E. Caicedo for Atlas-like websites on specific areas of mathematics March 8, 2020
  A database of number fields, by Jürgen Klüners and Gunter Malle. (Note this is not the same as the one mentioned in this answer.) The site also provides links to similar databases.
  Andrés E. Caicedo
- Answer by Andrés E. Caicedo for Are infinite planar graphs still 4-colorable? December 16, 2013
  As the other answer indicates, the yes answer to your question is known as the De Bruijn-Erdős theorem. This holds regardless of the size of the graph. The De Bruijn–Erdős theorem is a particular instance of what in combinatorics we call a compactness argument or Rado's selection principle, and its truth can be seen as a consequence of the topological c […]
  Andrés E. Caicedo
- Answer by Andrés E. Caicedo for Riemann series theorem and uncountable number of sums which sum to every value November 1, 2019
  Every $P_c$ has the size of the reals. For instance, suppose $\sum_n a_n=c$ and start by writing $\mathbb N=A\cup B$ where $\sum_{n\in A}a_n$ converges absolutely (to $a$, say). This is possible because $a_n\to 0$: Let $m_0
  Andrés E. Caicedo
- Answer by Andrés E. Caicedo for "Inner Regularity" of probability measure on totally ordered sets October 7, 2019
  Consider a subset $\Omega$ of $\mathbb R$ of size $\aleph_1$ and ordered in type $\omega_1$. (This uses the axiom of choice.) Let $\mathcal F$ be the $\sigma$-algebra generated by the initial segments of $\Omega$ under the well-ordering (so all sets in $\mathcal F$ are countable or co-countable), with the measure that assigns $0$ to the countable sets and $1 […]
  Andrés E. Caicedo
Math.StackExchange
- Answer by Andrés E. Caicedo for Do any proofs/properties rely on the distinction between some uncountable size and a larger uncountable size, in order for the proof/property to hold? May 12, 2020
  Sure. A large class of examples comes from the partition calculus. A simple result of the kind I have in mind is the following: Any infinite graph contains either a copy of the complete graph on countably many vertices or of the independent graph on countably many vertices. However, if we want to find an uncountable complete or independent graph, it is not e […]
  Andrés E. Caicedo
- Answer by Andrés E. Caicedo for Why is ZFC the foundational theory of mathematics? May 5, 2020
  I think that, from a modern point of view, there is a misunderstanding in the position that you suggest in your question. Really, "set theory" should be understood as an umbrella term that covers a whole hierarchy of ZFC-related theories. Perhaps one of the most significant advances in foundations is the identification of the consistency strength h […]
  Andrés E. Caicedo
- Answer by Andrés E. Caicedo for Invoking Continuum Hypothesis to prove the cardinality of a set May 2, 2020
  I'll only discuss the first question. As pointed out by Asaf, the argument is not correct, but something interesting can be said anyway. There are a couple of issues. A key problem is with the idea of an "explicitly constructed" set. Indeed, for instance, there are explicitly constructed sets of reals that are uncountable and of size continuum […]
  Andrés E. Caicedo
- Answer by Andrés E. Caicedo for One-to-one mapping from Vitali set to $\mathbb{R}$ April 26, 2020
  The question seems to be: Assume that there is a Vitali set $V$. Is there an explicit bijection between $V$ and $\mathbb R$? The answer is yes, by an application of the Cantor-Schröder-Bernstein theorem: there is an explicit injection from $\mathbb R$ into $\mathbb R/\mathbb Q$ (provably in ZF, this requires some thought, or see the answers to this question) […]
  Andrés E. Caicedo
- Answer by Andrés E. Caicedo for On the meaning of the Axiom Of Regularity in terms of " repeatedly taking the union" . April 20, 2020
  If a set $X$ is well-founded (essentially, if it contains no infinite $\in$-descending chains), then indeed $\emptyset$ belongs to its transitive closure, that is, either $X=\emptyset$ or $\emptyset\in\bigcup X$ or $\emptyset\in\bigcup\bigcup X$ or... However, this does not mean that there is some $n$ such that the result of iterating the union operation $n$ […]
  Andrés E. Caicedo
January 2008

M T W T F S S

1 2 3 4 5 6

7 8 9 10 11 12 13

14 15 16 17 18 19 20

21 22 23 24 25 26 27

28 29 30 31

« Sep Feb »
Archives
- June 2019 (2)
- February 2019 (7)
- December 2018 (1)
- October 2018 (2)
- August 2018 (1)
- February 2018 (1)
- October 2017 (1)
- July 2017 (1)
- September 2016 (2)
- August 2016 (3)
- July 2016 (2)
- April 2016 (1)
- October 2015 (1)
- June 2015 (1)
- May 2015 (1)
- April 2015 (7)
- March 2015 (5)
- February 2015 (7)
- January 2015 (11)
- December 2014 (2)
- November 2014 (5)
- October 2014 (6)
- September 2014 (3)
- August 2014 (3)
- April 2014 (3)
- March 2014 (5)
- February 2014 (2)
- January 2014 (2)
- December 2013 (2)
- November 2013 (10)
- October 2013 (6)
- September 2013 (7)
- August 2013 (5)
- June 2013 (1)
- May 2013 (8)
- April 2013 (7)
- March 2013 (5)
- February 2013 (9)
- January 2013 (2)
- November 2012 (1)
- September 2012 (1)
- August 2012 (3)
- May 2012 (3)
- April 2012 (10)
- March 2012 (4)
- February 2012 (13)
- January 2012 (15)
- November 2011 (8)
- October 2011 (14)
- September 2011 (7)
- August 2011 (1)
- April 2011 (1)
- March 2011 (3)
- February 2011 (4)
- January 2011 (7)
- December 2010 (1)
- November 2010 (7)
- October 2010 (12)
- September 2010 (13)
- August 2010 (3)
- May 2010 (4)
- April 2010 (11)
- March 2010 (6)
- February 2010 (12)
- December 2009 (9)
- November 2009 (11)
- October 2009 (13)
- September 2009 (19)
- August 2009 (10)
- June 2009 (1)
- May 2009 (2)
- April 2009 (14)
- March 2009 (17)
- February 2009 (19)
- January 2009 (15)
- December 2008 (5)
- November 2008 (12)
- October 2008 (17)
- September 2008 (10)
- August 2008 (3)
- June 2008 (3)
- May 2008 (15)
- April 2008 (21)
- March 2008 (10)
- February 2008 (13)
- January 2008 (11)
- September 2007 (1)
- July 2007 (1)
- March 2007 (4)
- February 2007 (20)
- January 2007 (23)
- December 2006 (4)
Alan Turing Alexander S. Kechris Alfred Tarski algebraic numbers Andras Hajnal Andreas Blass Andrew Michael Bruckner arithmetic mean-geometric mean inequality Arnoud C. M. van Rooij Augustin Cauchy Axel Thue Bernhard Riemann BEST bpfa compactness completeness covering property determinacy Donald A. Martin elementary embedding Emile Borel Euclidean algorithm extension field field field extension Francisco Frank Plumpton Ramsey Fred Galvin Galvin-Hajnal theorem GCH Georg Cantor Godfrey Harold Hardy Grigor Sargsyan Harvey Friedman ideal Isaac Newton James Baumgartner Jerome Keisler Johan Thim John R. Steel Karl Theodor Wilhelm Weierstrass Koenig's lemma Kurt Goedel Lech Maligranda Marion Scheepers measurable cardinal Menachem Magidor midterm mm Nowhere differentiable function Paul Erdos Paul Larson pfa propositional logic quartic equation Ramsey theorem Rene Baire Richard Rado Robert Solovay Saharon Shelah Samuel Coskey sch Silver's theorem Stefan Banach Stevo Todorcevic supercompact cardinals Tarski's conjecture Turing degrees ultrafilter ultrapower Undecidability and incompleteness Unsolvable problems W. Hugh Woodin Wacław Franciszek Sierpiński Wilhelmus Hendricus Schikhof

	Anthea M. on No durians
	580 -Some choiceless… on 580 -Some choiceless results…
	Set theory seminar -… on Set theory seminar -Forcing ax…
	Set theory seminar -… on Set theory seminar -Forcing ax…
	Set theory seminar -… on Set theory seminar -Forcing ax…
	Set theory seminar -… on Set theory seminar -Forcing ax…
	Set theory seminar -… on Set theory seminar -Forcing ax…
	Set theory seminar -… on Set theory seminar -Forcing ax…
	Set theory seminar -… on Set theory seminar -Forcing ax…
	Set theory seminar -… on Set theory seminar -Forcing ax…
	Set theory seminar -… on Set theory seminar -Forcing ax…
	Set theory seminar -… on Set theory seminar -Forcing ax…
	Set theory seminar -… on Set theory seminar -Forcing ax…
	Set theory seminar -… on Set theory seminar -Forcing ax…
	Set theory seminar -… on Set theory seminar -Forcing ax…

A kind of library

116b- Homework 2

116b- Lecture 5

Categories

Recent Comments

Mathematical links

My pages

Others

Mathoverflow

Math.StackExchange

Archives