Fdtxjr

Why did the EU agree to delay the Brexit deadline?

Are Captain Marvel's powers affected by Thanos' actions in Infinity War

Can a stoichiometric mixture of oxygen and methane exist as a liquid at standard pressure and some (low) temperature?

Using substitution ciphers to generate new alphabets in a novel

How do apertures which seem too large to physically fit work?

Review your own paper in Mathematics

Why is so much work done on numerical verification of the Riemann Hypothesis?

Is aluminum electrical wire used on aircraft?

What are some good ways to treat frozen vegetables such that they behave like fresh vegetables when stir frying them?

Angel of Condemnation - Exile creature with second ability

Why does AES have exactly 10 rounds for a 128-bit key, 12 for 192 bits and 14 for a 256-bit key size?

Yosemite Fire Rings - What to Expect?

Why does the Sun have different day lengths, but not the gas giants?

Picking the different solutions to the time independent Schrodinger eqaution

Unexpected behavior of the procedure `Area` on the object 'Polygon'

What should you do if you miss a job interview (deliberately)?

How do you make your own symbol when Detexify fails?

Why should universal income be universal?

Biological Blimps: Propulsion

Calculating total slots

Store Credit Card Information in Password Manager?

When were female captains banned from Starfleet?

Open a doc from terminal, but not by its name

Creepy dinosaur pc game identification

General methods for proving countability and uncountability

Proving the uncountability of $[a,b]$ and $(a,b)$Countable subset of $A$ with cluster points in $A$Clarification on separability in RudinGeneral strategy for proving that one interval is a subset of anotherIf A is an infinite set and B is at most countable set, prove that A and $A cup B$ have the same cardinalityQuestion about a peculiar sigma-algebra and a measureTheorem 2.14 in Walter Rudin's Principles of Mathematical AnalysisCan we have a countable region in a perfect set?Show that the set of of functions that are neither even nor odd is not meagerSigma Algebra and Countability/Cocountability

1

$begingroup$

I'm trying to get a broad intuition for which methods exist for proving that a set $S$ is either countable or uncountable. This is my intuition based on what I have seen so far in Baby Rudin:

It seems that, to prove that $S$ is countable, one must either

1. Find a function $f : S rightarrow mathbbN$ and show that it is bijective (i.e., show that it is both injective and surjective), or


2. Use Theorem 2.12, which essentially states that the union of a countable collection of countable sets is countable.

The only method that I have seen used to prove that $S$ is uncountable is to

1. Show that $S$ is infinite by showing that $S$ is equivalent to one of its proper subsets.

But since a set is uncountable if and only if it is neither finite nor countable, I'm not sure how one would approach the argument from the opposite direction, by showing that $S$ is not countable.

What is an example of a situation where one might need to show that something is uncountable because it is not countable, and how would one go about proving such a claim?

Additionally, are there other general arguments for showing that something is countable?

Thanks!

real-analysis

share|cite|improve this question

asked Mar 15 at 2:27

onesixonesix

224

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Schroeder-Bernstein theorem states that if you can find an injection $f:A rightarrow B$ and another injection $g:B rightarrow A$, then sets must have the same cardinality.
  $endgroup$
  – Hyperion
  Mar 15 at 2:32
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  To prove a set is uncountable, you can take your unknown set $S$, and a known uncountable set $U$ (e.g. $BbbR$, $BbbN^BbbN$, $mathcalP(BbbN)$, etc), and find either an injection $U to S$, or a surjection $S to U$.
  $endgroup$
  – Theo Bendit
  Mar 15 at 2:46
  

  
  
  
  

add a comment | 

1

$begingroup$

I'm trying to get a broad intuition for which methods exist for proving that a set $S$ is either countable or uncountable. This is my intuition based on what I have seen so far in Baby Rudin:

It seems that, to prove that $S$ is countable, one must either

1. Find a function $f : S rightarrow mathbbN$ and show that it is bijective (i.e., show that it is both injective and surjective), or


2. Use Theorem 2.12, which essentially states that the union of a countable collection of countable sets is countable.

The only method that I have seen used to prove that $S$ is uncountable is to

1. Show that $S$ is infinite by showing that $S$ is equivalent to one of its proper subsets.

But since a set is uncountable if and only if it is neither finite nor countable, I'm not sure how one would approach the argument from the opposite direction, by showing that $S$ is not countable.

What is an example of a situation where one might need to show that something is uncountable because it is not countable, and how would one go about proving such a claim?

Additionally, are there other general arguments for showing that something is countable?

Thanks!

real-analysis

share|cite|improve this question

asked Mar 15 at 2:27

onesixonesix

224

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Schroeder-Bernstein theorem states that if you can find an injection $f:A rightarrow B$ and another injection $g:B rightarrow A$, then sets must have the same cardinality.
  $endgroup$
  – Hyperion
  Mar 15 at 2:32
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  To prove a set is uncountable, you can take your unknown set $S$, and a known uncountable set $U$ (e.g. $BbbR$, $BbbN^BbbN$, $mathcalP(BbbN)$, etc), and find either an injection $U to S$, or a surjection $S to U$.
  $endgroup$
  – Theo Bendit
  Mar 15 at 2:46
  

  
  
  
  

add a comment | 

$begingroup$

I'm trying to get a broad intuition for which methods exist for proving that a set $S$ is either countable or uncountable. This is my intuition based on what I have seen so far in Baby Rudin:

It seems that, to prove that $S$ is countable, one must either

1. Find a function $f : S rightarrow mathbbN$ and show that it is bijective (i.e., show that it is both injective and surjective), or


2. Use Theorem 2.12, which essentially states that the union of a countable collection of countable sets is countable.

The only method that I have seen used to prove that $S$ is uncountable is to

1. Show that $S$ is infinite by showing that $S$ is equivalent to one of its proper subsets.

But since a set is uncountable if and only if it is neither finite nor countable, I'm not sure how one would approach the argument from the opposite direction, by showing that $S$ is not countable.

What is an example of a situation where one might need to show that something is uncountable because it is not countable, and how would one go about proving such a claim?

Additionally, are there other general arguments for showing that something is countable?

Thanks!

real-analysis

share|cite|improve this question

asked Mar 15 at 2:27

onesixonesix

224

$endgroup$

share|cite|improve this question

asked Mar 15 at 2:27

onesixonesix

224

share|cite|improve this question

asked Mar 15 at 2:27

onesixonesix

224

asked Mar 15 at 2:27

onesixonesix

224

asked Mar 15 at 2:27

onesixonesix

224

1 Answer
1

active

oldest

votes

1

$begingroup$

The most famous uncountability argument is Cantor's diagonalization, i.e. given an arbitrary enumeration $f: mathbbN to S$, you construct an element of $S$ that is not in the range of $f$ (i.e. show that it is not surjective).

Alternatively, and analogously to your point 1 for countable sets, you could find $f: S to mathbbR$ (or any other known uncountable set) and show that it is bijective (or just surjective).

share|cite|improve this answer

answered Mar 15 at 2:47

Michael BiroMichael Biro

11.1k21831

$endgroup$

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3148820%2fgeneral-methods-for-proving-countability-and-uncountability%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

1

$begingroup$

The most famous uncountability argument is Cantor's diagonalization, i.e. given an arbitrary enumeration $f: mathbbN to S$, you construct an element of $S$ that is not in the range of $f$ (i.e. show that it is not surjective).

Alternatively, and analogously to your point 1 for countable sets, you could find $f: S to mathbbR$ (or any other known uncountable set) and show that it is bijective (or just surjective).

share|cite|improve this answer

answered Mar 15 at 2:47

Michael BiroMichael Biro

11.1k21831

$endgroup$

add a comment | 

1

$begingroup$

The most famous uncountability argument is Cantor's diagonalization, i.e. given an arbitrary enumeration $f: mathbbN to S$, you construct an element of $S$ that is not in the range of $f$ (i.e. show that it is not surjective).

Alternatively, and analogously to your point 1 for countable sets, you could find $f: S to mathbbR$ (or any other known uncountable set) and show that it is bijective (or just surjective).

share|cite|improve this answer

answered Mar 15 at 2:47

Michael BiroMichael Biro

11.1k21831

$endgroup$

add a comment | 

$begingroup$

The most famous uncountability argument is Cantor's diagonalization, i.e. given an arbitrary enumeration $f: mathbbN to S$, you construct an element of $S$ that is not in the range of $f$ (i.e. show that it is not surjective).

Alternatively, and analogously to your point 1 for countable sets, you could find $f: S to mathbbR$ (or any other known uncountable set) and show that it is bijective (or just surjective).

share|cite|improve this answer

answered Mar 15 at 2:47

Michael BiroMichael Biro

11.1k21831

$endgroup$

share|cite|improve this answer

answered Mar 15 at 2:47

Michael BiroMichael Biro

11.1k21831

answered Mar 15 at 2:47

Michael BiroMichael Biro

11.1k21831

answered Mar 15 at 2:47

Michael BiroMichael Biro

11.1k21831