Logic - 2017-12-01

« first day (471 days earlier) ← previous day next day → last day (2351 days later) »

Michelle

5:09 AM

How to find a formula logically valid such that it;s not an instance of a tautology?

user21820

6:08 AM

@Michelle Every logically valid sentence is a tautology.

@LeakyNun: Could you help me check my post here:

A: Bijection between closed uncountable subset of $\Bbb R$ and $\Bbb R$.

Here is a proof that does not use any transfinite induction at all! Take any uncountable closed subset $S$ of $\mathbb{R}$. Let $S_n = S \cap [n,n+1]$ for each integer $n$. Then $S_n$ is uncountable for some integer $n$, so we can assume that $S \subseteq [a,b]$ for some reals $a,b$. Let $p...

Just in case I made some mistake somewhere. I am slightly concerned just because the top-voted accepted answerer used transfinite induction up to ω[1], whereas I think I didn't use any replacement at all.

2 hours later…

Leaky Nun

7:47 AM

@user21820 very interesting

I have never thought about it like this

I would be more careful about $S \subseteq [a,b]$. It isn't valid before I finished reading your whole post.

4 hours later…

user21820

11:45 AM

@LeakyNun Why is it not valid right at the start? S[n] is uncountable for some integer n, so of course we can assume that S is contained within [n,n+1] for some integer n, and that is weaker than assuming that S is contained within [a,b] for some reals a,b.

Am I missing something?

3 hours later…

Leaky Nun

3:06 PM

@user21820 well, $\Bbb R \not\subseteq [a,b]$

user21820

@LeakyNun Well it's a standard technique to say "we can assume" if it is clear how to get from the restricted to the full version.

In this case, I first argued that S[n] must be uncountable for some integer n, and every interval [n,n+1] is of the form required by the assumption.

So it suffices to prove the case where S is contained in a bounded interval, because it would then apply to the original problem as well via the reduction in the first step.

Is it clear now? By the way, I just edited the post to add in the remark that my initial comment about countable choice was false; see the comments for the discussion and my logical error. Lol!

@LeakyNun To make it in strictly forward order of reasoning, you could rearrange the proof to settle the restricted case first, and then run the first step to obtain the general case.

But in some formal systems it is allowed to make reductions of this form.

4 hours later…

user21820

7:26 PM

@LeakyNun: I just asked a follow-up question:

Q: Uncountable closed set of reals biject with reals without replacement or choice

I recently gave a proof of this theorem: Every uncountable closed set of reals is in bijection with the reals. My proof used the axiom of countable choice. Asaf Karagila stated in a comment that Arnie Miller showed in "A Dedekind Finite Borel Set" (Arch. Math. Logic 50, No. 1-2, 1-17 (2011)...

2 hours later…

Leaky Nun

9:17 PM

@user21820 @MatheinBoulomenos I’m going to give a talk to a bunch of undergraduates on Ax-Grothendieck theorem and its model-theoretic proof, but it will be quite more focused on model theory; what should i name the talk?

« first day (471 days earlier) ← previous day next day → last day (2351 days later) »

all rooms