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

0
votes
0answers
5 views

obtaning a set from classes

is it posible to get a set by a intersection of 2 (non-set) classes? I can see it is popssible from a set and a class,simply by a set contaained in the class.Also,I think that the union/prduct of two ...
4
votes
2answers
124 views

Are there as many real numbers as there are imaginary numbers?

On the one hand, I know that $\mathbb{R}$ and $\mathbb{I}$ (the set of strictly-imaginary numbers) are both uncountable sets, so they have the same number of elements (i.e. the same cardinality). On ...
0
votes
2answers
31 views

How to define an isomorphism between $^\omega\omega$ and $\omega^\omega$?

Let $^\omega\omega$ be the set of all functions $x: \omega \to \omega$. Define $A = \{x \in ^\omega\omega \; | \; x \text{ has finite support}\}$, where by "finite support" I mean that the set $\{x(n) ...
0
votes
2answers
31 views

Bernstein sets, Well-Ordering theorem vs Axiom of Choice

In the construction of Bernstein sets (see here), is it necessary to use the well-ordering theorem? Why can't you just use the Axiom of Choice to pick two points?
-1
votes
0answers
20 views

Relation R is symmetric if and only if it is equal to its inverse [on hold]

If $R$ is a relation on set $A$. How do we prove that $R$ is symmetric if and only if $R$ = inverse of $R$?
0
votes
1answer
34 views

Understanding the difference between relations and functions.

$R=\{(1,2),(1,3)\}$ is a relation but not function. The logic for this is that if the first element of every ordered pair must remain different, then it is said to be function. Otherwise, it's just ...
0
votes
2answers
19 views

Fine partitions

I am tasked with the following: Give four different partitions $\Pi_1,\Pi_2,\Pi_3,\Pi_4$ of the set $\Bbb N$ with $\Pi_i$ Finer that $\Pi_{i+1}$ for $i =1,2,3$ I think that partition by 8, 4,2 ...
1
vote
0answers
34 views

Existence and uniqueness up to isomorphism of the real numbers from axioms

Pretty much what the title says: how does one prove the existence and uniqueness of the real number system from the ordered field axioms together with the least-upper-bound property (or maybe some ...
2
votes
5answers
635 views

The ambiguity of set theory language

When I am learning, one thing I am puzzled is the definition. For example, we define $0$ as $\emptyset$. But when we use set language, how could we know we are talking about $0$ or the empty set. ...
0
votes
4answers
14 views

Distributing Set Intersections Over an Intersection

I was working through some examples, and found this to be true: $(A \cap B) \cap (B \cap C) = A \cap B \cap C $ $(A \cap B) \cap(A \cap C) = A \cap B \cap C$ $(A \cap B) \cap(A \cap C) \cap (B ...
2
votes
2answers
40 views

Proving existence of surjective $f:\mathbb{N} \rightarrow A$ implies $A$ is at most countable.

Definition of "at most countable" used: A set $A$ is at most countable iff it's finite or there exists a bijection $f:\mathbb{N} \rightarrow A$. Problem: I want to prove that if there exists a ...
1
vote
2answers
35 views

finding a surjective function if $A=\left \{1,3,6,7,9 \right \},B=\left \{5,8,3,7 \right \}$

Given $A=\left \{1,3,6,7,9 \right \},B=\left \{5,8,3,7 \right \}$ How can I define a function $f:A\rightarrow B$ so that $f$ is a surjective function? I can write it in pairs such as: ...
4
votes
1answer
35 views

Proving a Subset Identity

Working on part A of this problem: I worked out the first part like this: 1) If $A$ is a subset of $B$ then $\forall~x~[x\in A \implies x\in B]$ 2) Same goes for $C$ being a subset of $D$ (If ...
0
votes
0answers
35 views

Is there a total disconnect between two Zermelo Theorems?

I'm referring to the Zermelo Theorems for set theory and game theory. The set theory version deals with the well-ordering principle and axiom of choice. The game theory version deals with the role of ...
-1
votes
0answers
22 views

Does there exist a cardinal $\kappa$ such that $\aleph_{\kappa} = \kappa$? [duplicate]

Does there exist a cardinal $\kappa$ such that $\aleph_{\kappa} = \kappa$ ? Moreover is there one that is regular? Thanks in advance!
2
votes
0answers
14 views

Set with relative complement forms partition

Prove that if $S$ is a set and $ \emptyset \subsetneq A \subsetneq S $ then $\Pi = \{A , S-A \}$ is a partition of $S$. Proposed Solution: Since $ A \subsetneq S$ , we have $S - A \neq ...
0
votes
3answers
24 views

Help to prove $(A \times B)\cup (C \times D) \subseteq (A\cup C) \times (B\cup D)$

Prove $(A \times B)\cup (C \times D) \subseteq (A\cup C) \times (B\cup D)$ My attempt: $\begin{align} (x,y) \in (A \times B) \cup (C \times D) & \Rightarrow & (x,y) \in (A \times B) \vee ...
2
votes
1answer
39 views

Does something that is injective, surjective or bijective imply that it is a function?

As the title says. Sorry it seems like a silly question but it's something I've been wondering because it seems like sometimes the word "function" is omitted, but other times it is included
2
votes
2answers
24 views

If $A,B$ are equinumerous, then so are their complements

I'm interested to know if the following statement is true: If $A,B \subseteq X$ are equinumerous (i.e. $|A|=|B|$, or there is a bijection $A \to B$), then $X \setminus A$ and $X \setminus B$ are ...
9
votes
4answers
960 views

Is the fact that there are more irrational numbers than rational numbers useful?

Although it is known that the cardinality of the set of irrational numbers is greater than the cardinality of the set of rational numbers, is there any usefulness/applications of this fact outside of ...
0
votes
2answers
29 views

Subsets and Cardinality

I'm confused on if I should count a subset as one element or if I should count all the elements of that subset when computing cardinality. Example: Given the set $A = \{1,2,3,\{4,5,6\}\}$ does $A$ ...
1
vote
3answers
61 views

Zermelo–Fraenkel set theory the natural numbers defines $1$ as $1 = \{\{\}\}$ but this does not seem right

If 1 can be defined as the set that contains only the empty set then what of sets which contain one thing such as the set of people who are me. number 1 does not just mean $1$ nothing, it means $1$ ...
1
vote
1answer
27 views

A question about cardinal numbers in ZF set theory.

It is well known that cardinal numbers and the relations between them can be defined in ZF set theory (using the notion of "rank"), without the need of additional axioms. Can the following statement ...
22
votes
2answers
1k views

Lamport claims there is an error in Kelley's proof of the Schroeder-Bernstein theorem. What is it?

In section 4.1 of his note How to write a proof, Leslie Lamport mentions an error in Kelley's exposition of the Schroeder-Bernstein theorem: Some twenty years ago, I decided to write a proof of ...
0
votes
1answer
16 views

Fallacy considering a relation between infinite sets and empty set

Namely I have stumbled upon a theorem due to Dedekind which says: A set is infinite iff it is equinumerous to a proper subeset of itself Since empty set is proper subset of every set except itself ...
7
votes
7answers
191 views

Is $\mathbb{C}$ equal to $\mathbb{R}^2$?

Complex numbers are usually formally defined as pairs of real numbers. Although there are operations on $\mathbb{C}$, such as complex multiplication, which are not found in operations usually applied ...
1
vote
1answer
23 views

Notation for building ordered sets of zeros

I want to define a lattice where each site is occupied by an ordered set of zeros. Later in the calculation, the zeros grow to nonnegative integers, but I need to start with zeros. At the $i$th site, ...
5
votes
3answers
247 views

Diagonalisation argument for real numbers

I know that the the set of real numbers has been proved uncountable by mathematicians, so my question is why this is wrong. In countability arguments that I have seen the numbers are laid out in a ...
1
vote
1answer
9 views

Composition of mappings on finite sets

If I'm working in the realm of finite sets on the form $\underline{n} = \{1, \ldots, n\}, n \in \mathbb{N} $. Consider any two transformations $f :\underline{n} \to \underline{m}$ and $g ...
0
votes
2answers
41 views

The intersection of ordered pairs.2

Definition of (a,b) is the set {{a},{a,b}}. Of course, (a,b) intersection with (b,a) is the set {{a,b}}. But if we represent ordered pairs as points in a plane, they do not intersect. Please explain.
2
votes
2answers
85 views

The Intersection of Ordered Pairs

I've seen that the ordered pair $(a,b)$ is defined as a set that is $(a,b)=\{\{a\},\{a,b\}\}$. Can you explain what do we mean when $(a,b) \cap (b,a) = \{\{a,b\}\}$? I feel that there should be no ...
0
votes
4answers
29 views

Empty preimage of an intersection implies empty intersection of the preimages

Assume $f:A\to A'$ is a function, $B\subset A'$, $C\subset A'$, and $f^{-1}(B\cap C)=\emptyset$ How can we see that $f^{-1}(B)\cap f^{-1}(C)=\emptyset$?
-1
votes
2answers
24 views

Prove this result about power sets [duplicate]

I have to prove this result: If $P$ be the power set, and $B$ and $C$ are two sets, then if $B \subseteq C$ prove that $P(B) \subseteq P(C)$. Now, it seems obvious to me that since all the ...
2
votes
1answer
56 views

Proving there's a set with the cardinality $\mathfrak c$ on the $x$ axis of points that do not belong to the set of disks

Prove/disprove: On the $x$ axis there's a set with the cardinality $\mathfrak c$ of points that do not belong to any disk of a set $O$ of disjoint disks of positive radius $\{(x,y)\in \mathbb ...
-1
votes
2answers
78 views

How to understand some bewildering limits of sequences of sets [on hold]

Let $(s_n)$ be the sequence of sets $s_n=\{n\}$ of natural numbers $1, 2, 3, ...$ Then the limit is the empty set $\{\}$. The sequences of sets $a_n=\{n^1\}$ or $b_n=\{n^n\}$ or ...
2
votes
2answers
19 views

How to prove that $R\cup S$ and $R\cap S$ are symmetric if R and S are symmetric?

The question is as follows- R and S are two symmetric relations on the same set A. Prove that $R\cup S$ and $R\cap S$ are symmetric. I tried it like this but I can't continue it. Any help is ...
0
votes
1answer
36 views

Help with a proof. Countable sets.

This is a Lemma from N.L. Carothers Real Analysis. Lemma. An infinite subset $A$ of $\mathbb{N}$ is countable. Proof. Since $A\ne\emptyset$, there is a smallest element $x_1\in A$. Then ...
-4
votes
1answer
57 views

To check if the function is onto or not? [closed]

Let $f \colon \mathbb N \to \mathbb N$ given by $$ f(n)=\begin{cases} (n+1)/2 & n \in\mathbb N \text{ odd}\\ n/2& n \in\mathbb N \text{ even} \end{cases} $$ The question is clear as it ...
1
vote
1answer
45 views

Proving Equivalence of Two Version of Axiom of Choice

I am working on an assignment that requires proving the equivalence of two versions of the axiom of choice. (1st form): For any relation $R$, there is a function $H \subseteq R$ with dom $H =$ dom ...
1
vote
2answers
20 views

Find all intersections of subsets.

I am having trouble with what seems like it should be a simple problem. I am trying to find intersections of connections between multiple people but I want to include any intersection of connections ...
1
vote
1answer
28 views

Finding the cardinality of $\{X\in \mathcal P(\mathbb R)| |X|=\aleph_0 \}$

Let $S$ be a relation over $\mathcal P(\mathbb R)$ such that $A,B\subseteq\mathbb R: \exists f:A\to B, \exists g: B\to A$ and $f,g$ are injections. Find the cardinality of $\{X\in \mathcal ...
1
vote
0answers
39 views

Is $2^{\alpha} < 2^{\beta}$, where $\alpha$ and $\beta$ are cardinal numbers, such that $\alpha < \beta$? [duplicate]

Let $\alpha$ and $\beta$ be cardinal numbers such that $\alpha < \beta$. Isn't it always true that $2^{\alpha} < 2^{\beta}$ ? Because if I am not wrong, $2^{\alpha}$ denotes the immediate ...
1
vote
2answers
38 views

Proof of $A \subseteq B \Leftrightarrow A \cap B = A$ (Check chain of implications)

Prove $A \subseteq B \Leftrightarrow A \cap B = A$. My attempt: Case $\Rightarrow$: $$\begin{align} A \subseteq B & \Rightarrow & [x\in A \Rightarrow x\in B] \\ &\Rightarrow &[x ...
1
vote
1answer
27 views

How many order relations there are on $A=\{1,2,3 \}$

How many order relations there are on $A=\{1,2,3 \}?$ An order relation is defined like here, I know the answer is 19 but I just can't get to it. Here's a rough sketch, each element $abc$ ...
-3
votes
0answers
50 views

Empty set, complement

is $\mathbb{R}\setminus \emptyset=\mathbb{R}$? Thanks in advance, unfortunately I am not sure right now...
1
vote
1answer
26 views

Find how many People Like dancing Only,People Like Movies

A survey was conducted among 402 persons regarding their interest in movies,dancing and games it was found that (i) 100 People Like games. (ii) 142 People Like movies or dancing but not games. (iii) ...
2
votes
1answer
29 views

Let $\alpha, \beta, \gamma$ be cardinals, $\beta \leq \gamma$, prove $\alpha ^{\beta}\le \alpha ^{\gamma}$

Let $|A|=\alpha, |B|=\beta, |C|= \gamma$ be cardinals and $\beta \leq \gamma$. Prove $\alpha ^{\beta}\le \alpha ^{\gamma}$. So from the given we know that there's an injection $f:B\to C$ and some ...
1
vote
0answers
25 views

Chains and upward directed families of sets.

A family $\mathcal F$ of subsets of a set is closed under unions of chains if and only if it is closed under unions of upward directed families. One way is straightforward. For the other one: if ...
1
vote
1answer
29 views

Question about a bijection between $\mathbb R$ and $\mathbb R \cup \{\infty\}$

About a bijection between $\mathbb R$ and $\mathbb R \cup \{\infty\}$ If we'll take a line $f(x)=\begin{cases} ax &, x\in\mathbb R\\ 0 &, x=\infty \end{cases}$ then we'll have a bijection. ...
1
vote
1answer
40 views

comparing two sets in set theory

I have two sets A and B and this condition holds: $\forall x \in A , y \in B: x \leq y$ Is there any standard term to describe the relation of A and B? something like $A \leq B$? Thanks for your ...