This tag is for elementary questions on set theory - the sort of material covered in "Chapter 0" of graduate texts and in undergraduate set theory texts. Topics include intersections and unions, de Morgan's laws, Venn diagrams, relations, functions, countability and uncountability, power sets, ...

learn more… | top users | synonyms

8
votes
6answers
1k views

Improving my understanding of Cantor's Diagonal Argument

I studied Cantor's Diagonal Argument in school years ago and it's always bothered me (as I'm sure it does many others). In my head I have two counter-arguments to Cantor's Diagonal Argument. I'm not ...
8
votes
3answers
241 views

Intersection of two 'huge' sets in the plane

Consider two sets on the plane $A=\mathbb{Q}\times \mathbb{R}$ and $B=\mathbb{R}\times \mathbb{Q}$. We know that $A\cap B=\mathbb{Q}\times \mathbb{Q}\neq\emptyset$. What about the general cases? That ...
8
votes
1answer
907 views

Prove: If $A \subseteq C$ and $B \subseteq D$, then $A \cap B \subseteq C \cap D$

Is the form and correctness of my elementwise proof of this correct? I don't have any other way of getting feedback for my proofs and I want to improve. Proof. Suppose $A, B, C, D$ are sets such ...
8
votes
2answers
84 views

How should one think about results that depend on AC?

I just encountered this: "(Theorem of A. H. Stone) Every metric space is paracompact... Existing proofs of this require the axiom of choice... It has been shown that neither ZF theory nor ZF ...
8
votes
2answers
164 views

Set theory based on inclusion

There are several axiomatizations of set theory based on inclusion rather than membership. I found only two papers, but they are both in German, and I could not read them even using a disctionary. Can ...
8
votes
2answers
593 views

Meaning of pullback

I was wondering if the following two meanings of pullback are related and how: In terms of Precomposition with a function: a function $f$ of a variable $y$, where $y$ itself is a function ...
8
votes
3answers
167 views

Existence of a certain subset of $\mathbb{R}$

To every real $x$ assign a finite set $\mathcal{A}(x)\subset \mathbb{R}$ where $x\not\in \mathcal{A}(x)$. Does there exist $\mathcal{W}\subset \mathbb{R}$ such that: $$1.\;\;\mathcal{W}\cap ...
8
votes
2answers
133 views

Name for a function whose image has smaller cardinality than its domain

I asked this question in the comments of this question, whose title would have done just as well for mine. But I suppose it should be a separate question. Is there a name for functions ...
8
votes
1answer
762 views

What is the number of bijections between two multisets?

Let $P$ and $Q$ be two finite multisets of the same cardinality $n$. Question: How many bijections are there from $P$ to $Q$? I will define a bijection between $P$ and $Q$ as a multiset $\Phi ...
8
votes
1answer
208 views

An exercise in infinite combinatorics from Burris and Sankappanavar

Exercise 6.7 in chapter IV of Burris and Sankappanavar's A Course in Universal Algebra starts as follows: Show that for $I$ countably infinite there is a subset $S$ of the set of functions from ...
7
votes
4answers
500 views

How to Decompose $\mathbb{N}$ like this? [duplicate]

Possible Duplicate: Partitioning an infinite set Partition of N into infinite number of infinite disjoint sets? Is it possible to find a family of sets $X_{i}$, $i\in\mathbb{N}$, such ...
7
votes
7answers
3k views

difference between maximal element and greatest element

I know that it's very elementary question but I still don't fully understand difference between maximal element and greatest element. If it's possible, please explain to me this difference with some ...
7
votes
4answers
1k views

Why is an empty function considered a function?

A function by definition is a set of ordered pairs, and also according the Kurastowski, an ordered pair $(x,y)$ is defined to be $$\{\{x\}, \{x,y\}\}.$$ Given $A\neq \varnothing$, and ...
7
votes
5answers
1k views

how do we assume there is infinity?

Definition of infinite: A set is infinite iff it is equivalent to one of its proper subsets. We know that our universe doesn't contain infinite number of elements, so how do we assume there is ...
7
votes
3answers
859 views

The largest number system

If my number set construction memory doesn't fail me (I'll edit if errors are pointed out), we start out with Peano's axioms to get to $\mathbb{N}$, and in the need of an additive inverse for its ...
7
votes
6answers
725 views

Why is the supremum of the empty set $-\infty$ and the infimum $\infty$? [duplicate]

I read in a paper on set theory that the supremum and the infimum of the empty set are defined as $\sup(\{\})=-\infty$ and $\inf(\{\})=\infty$. But intuitively I can't figure out why that is the case. ...
7
votes
7answers
2k views

Partition of N into infinite number of infinite disjoint sets?

Is it possible to have a countable infinite number of countable infinite sets such that no two sets share an element and their union is the positive integers?
7
votes
3answers
3k views

What is a null set?

I am very confused with null sets. I get that a set which has no elements will be called a null set but I am not getting the examples given below. Please help me by explaining how $P,Q,R$ are all ...
7
votes
4answers
482 views

How many subsets of $\mathbb{N}$ have the same cardinality as $\mathbb{N}$?

How many subsets of $\mathbb{N}$ have the same cardinality as $\mathbb{N}$? I realize that any of the class of functions $f:x\to (n\cdot x)$ gives a bijection between $\mathbb{N}$ and the subset ...
7
votes
6answers
304 views

Why should $|2^\mathbb{N}|>|\mathbb{N}^2|$ be true?

I've been thinking a bit about infinite things lately, and this question I had wondered about came back to me. One of the classic expository demonstrations of Cantor's work is the two equally ...
7
votes
2answers
653 views

Troll Maths : Bijection between P(N) and N?

I just wanted to know what's wrong in the following argument: Say I take a number and rewrite as a binary. e.g 155 = 10011011 Then I can relate the number with a subset of N, which contains the ...
7
votes
5answers
283 views

If $\mathcal{P}(A)=\mathcal{P}(B)$, then $A=B$? [duplicate]

Prove, disprove, or give a counterexample: If $\mathcal{P}(A)=\mathcal{P}(B)$, then $A=B$. Assume $\mathcal{P}(A)=\mathcal{P}(B)$. Since we know $A \subseteq A$, we know $A \in ...
7
votes
3answers
423 views

If $f \circ g = f$, prove that $f$ is a constant function.

Suppose $A$ is a nonempty set and $f: A \rightarrow A$ and for all $g:A \rightarrow A,$ $f \circ g = f$. Prove that $f$ is a constant function. This result seems obvious, but I can't seem to find ...
7
votes
2answers
548 views

countable group, uncountably many distinct subgroup?

I need to know whether the following statement is true or false? Every countable group $G$ has only countably many distinct subgroups. I have not gotten any counter example to disprove the statement ...
7
votes
4answers
1k views

Interpretation of limsup-liminf of sets

What is an intuitive interpretation of the 'events' $$\limsup A_n:=\bigcap_{n=0}^{\infty}\bigcup_{k=n}^{\infty}A_k$$ and $$\liminf A_n:=\bigcup_{n=0}^{\infty}\bigcap_{k=n}^{\infty}A_k$$ when $A_n$ are ...
7
votes
2answers
376 views

Is $\emptyset \in \emptyset$ or $\emptyset \subseteq \emptyset$?

Can someone give an argument, if possible using only the axioms of set theory, because I'm very weak there and have virtually no background, except the usual knowledge of the operation with sets one ...
7
votes
2answers
312 views

Must $g$ be the identity if $f = g \circ f$?

I am finding it hard to solve the following problem. Let $A$ is a set and $f : A \rightarrow A$ and $g : A \rightarrow A$. If $f = g \circ f$, must $g$ be an identity function always? Will there be ...
7
votes
2answers
189 views

cartesian product $A^2 = A$, possible?

Do there exist non-empty sets $A$ such that $A\times A = A$? $A\times A = A$ looks a little strange to me, since $A\times A$ seems somehow more complicated than $A$, hence it is unlike that they are ...
7
votes
4answers
1k views

Formal proof for A subset of the real numbers, well ordered with the normal order of $\mathbb R$, is at most $\aleph_0$

I tried to write a formal proof for the theorem: $A$ subset of $\mathbb R$ well ordered by the normal order $\implies A$ is at most of cardinality $\aleph_0$. Any suggestions? Thanks.
7
votes
5answers
4k views

How can one prove that the union of two finite sets is again finite, without the use of arithmetic?

The notion that the union of two finite sets is again finite is something I took as intuitively true for quite a while. A proof using arithmetic is relatively straight forward. Suppose $A$ and $B$ ...
7
votes
3answers
628 views

Building the integers from scratch (and multiplying negative numbers)

Now I understand that what I am about to ask may seem like an incredibly simple question, but I like to try and understand math (especially something as fundamental as this) at the deepest level ...
7
votes
4answers
275 views

Supremum and ordinals

Question: Show that sup{$ \xi \dotplus 1 : \xi \in A $} is the least ordinal that is greater than each element of $A$. I tried to get a better feel for this by letting $A=3=${$0,1,2$}. Then I know ...
7
votes
3answers
582 views

Bijecting a countably infinite set $S$ and its cartesian product $S \times S$

From Herstein's Topics in Algebra (exercise 14, section 1.2): If $S$ is infinite and can be brought into one-to-one correspondence with the set of integers, prove that there is one-to-one ...
7
votes
3answers
154 views

Prove that if $\mathcal P(A) \cup \mathcal P(B)= \mathcal P(A\cup B)$ then either $A \subseteq B$ or $B \subseteq A$. [duplicate]

Prove that for any sets $A$ or $B$, if $\mathcal P(A) \cup \mathcal P(B)= \mathcal P(A\cup B)$ then either $A \subseteq B$ or $B \subseteq A$. ($\mathcal P$ is the power set.) I'm having trouble ...
7
votes
1answer
290 views

Why is the collection of all groups considered a proper class rather than a set?

According to Wikipedia, The collection of all algebraic objects of a given type will usually be a proper class. Examples include the class of all groups, the class of all vector spaces, and ...
7
votes
4answers
271 views

Is this proof correct for : Does $F(A)\cap F(B)\subseteq F(A\cap B) $ for all functions $F$?

Is this proof correct? To prove $F(A)\cap F(B)\subseteq F(A\cap B) $ for all functions $F$. Let any number $y\in F(A)\cap F(B)$. We want to show $y\in F(A\cap B).$ Therefore, $y\in F(A)$ and ...
7
votes
2answers
566 views

Is there an empty set in the complement of an empty set?

Currently taking a logic class and trying to understand this. You have two set $A$ and $B$. Both sets are empty sets. Is set $A$ a subset of the complement of set $B$? Assume the context is the ...
7
votes
5answers
637 views

Definition of the Infinite Cartesian Product

(1) If $X$ and $Y$ are two sets, we define the Cartesian product $X \times Y$ as the set of ordered pairs $(x,y)$, such that $x \in X$ and $y \in Y$. (2) On the other hand [Folland, Real Analysis, ...
7
votes
2answers
327 views

If the diagram is commutative, $f$ is one-one and $g$ is onto.

Let $f:A \to B$ , $g:B \to A$, and $\operatorname{id}:A \to A$ be the identity. If the diagram $\hspace{4cm} $ commutes, prove that ${ f}$ is one-one and ${ g}$ is onto. THEOREM If the diagram ...
7
votes
5answers
654 views

Dependence of Axioms of Equivalence Relation?

This question is problem 11(a) in chapter 1 in 'Topics in Algebra' by I.N. Herstein. These are the properties of equivalence relation given in this book. Prop 1 $a \sim a$ Prop 2 $a \sim b$ ...
7
votes
2answers
293 views

Why is $|Y^{\emptyset}|=1$ but $|\emptyset^Y|=0$ where $Y\neq \emptyset$

I have a question about the set of functions from a set to another set. I am wondering about the degenerate cases. Suppose $X^Y$ denotes the set of functions from a set $Y$ to a set $X$, why is ...
7
votes
3answers
186 views

Can any subset of $x$ be moved out of $x$?

Let $x$ be a set and let $y\subset x$. Does it exist a set $z$ such that: (1) $z\cap x=\emptyset$ and (2) there exists a bijection $y \to z$ ? It is quite intuitive that the answer should be ...
7
votes
2answers
189 views

Countability of irrationals

Since the reals are uncountable, rationals countable and rationals + irrationals = reals, it follows that the irrational numbers are uncountable. I think I've found a "disproof" of this fact, and I ...
7
votes
2answers
278 views

What are the sub-sets of a null set?

What are the sub-sets of a null set? I don't get any other set than {}. Please help me out. Thanks.
7
votes
2answers
312 views

For which $P$ can one claim the existence of the set of all sets that satisfy $P$?

Given a property $P$, is there some rules that are sufficient or necessary to determine if there exists a set of all sets with property $P$?
7
votes
2answers
164 views

Plausibility argument for Zorn's Lemma

In "Mathematical Physics" by Robert Geroch, the following 'plausibility argument' is given for Zorn's Lemma [If every totally ordered subset of a partially ordered set $S$ is bounded above, $S$ has a ...
7
votes
2answers
149 views

Trying to understand set theory? Subset vs Member?

So I'm learning set theory and wanted to know if I'm understanding some of the basics correctly. I have a feeling 1 and 2 are correct, but I'm not sure about 3 and 4. ...
7
votes
1answer
218 views

Is every element in a set also an element of the powerset?

From my understanding of powersets, a powerset contains all the possible subsets of a set. So if we want the power set of {1} then the powerset of {1} is {{}, {1}}. I was speaking to my tutor who was ...
7
votes
3answers
322 views

Intuition behind Cantor-Bernstein-Schroeder

The book I am working from (Introduction to Set Theory, Hrbacek & Jech) gives a proof of this result, which I can follow as a chain of implications, but which does not make natural, intuitive ...
7
votes
4answers
155 views

Mustn't a function map every element of its domain to range (but not codomain)? [Richard Hammack, P228]

How to Prove It, D Velleman P226, P228: Suppose $f$ is a relation from $A$ to $B.$ Then $f$ is a function from $A$ to $B$ means: $\forall \; \color{#009900}{a \in A}, \exists \; ! \; b \in ...