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
2answers
18 views

Cannot understand a mapping function which include some sets

I have kept a screenshot of my problem below which describes about the various sets. At the last line, there is an expression where a function delta uses those sets and maps them into another. I am ...
1
vote
1answer
24 views

A question on relations

Problem Statement: Let $A$ and $B$ be sets. Many books define a relation $\mathcal R$ from $A$ to $B$ to be a subset $ \mathcal R \subseteq A \times B $. Show that such an R is a ...
-2
votes
2answers
41 views

problem undrestanding maximal defenition? [on hold]

i read in Wikipedia "a maximal element of a subset S of some partially ordered set is an element of S that is not smaller than any other element in S." (http://en.wikipedia.org/wiki/Maximal_element) ...
0
votes
0answers
22 views

How many Euler diagrams with $n$ sets exist?

Does anyone have any thoughts on this? I have been struggling with it and I'm not sure if it's a hard problem, or easy and I'm just not getting it? For $n=2$ sets (say $A$ and $B$), it's obviously 4: ...
1
vote
2answers
26 views

Problem Involving a Generalized Cartesian Product

Let $I$ be a set, and for each $i \in I$, let $U_i$ and $V_i$ be sets. Furthermore, suppose for each $i \in I$, there is a bijection $f_i:U_i \to V_i$. Prove that there is a bijection $g:\prod_{i \in ...
0
votes
3answers
39 views

What would make a function reflexive, transitive, and/or symmetric?

A binary relation $R$ is a subset of the Cartesian product between two sets $X$ and $Y$, containing a set of ordered pairs $\{(x,y) : x \in X, y \in Y\}$. $R$ is a function if each element of $X$ is ...
1
vote
3answers
18 views

How many reflexive binary relations there are on a finite countable set?

We know that binary relation is subset of Cartesian product made by set on to itself. let's say we have a set with two elements $A=\{0,1\}$ So Cartesian product is $C=A\times A = ...
1
vote
2answers
49 views

Wondering if proof is proper

so I have been working on learning some new math in order to prepare for next year. I have been trying to learn proofs, and doing practice questions however the only problem is there are not answers. ...
1
vote
3answers
119 views

Intersection of an Infinite Indexed Family of Sets

In a mathematics course, I came across the following problem: Identify (with a short proof) the following set: $\bigcap_{n\in\mathbb{N}}\left(0,1+\frac{1}{n}\right)$, where ...
13
votes
5answers
837 views

Why isn't the Cantor Set contradictory?

So you start with a 1-dimensional stick, remove the middle third of it, leaving 2 pieces. From each of these 2 pieces, remove the middle third. Etc. Whatever is left at the end of infinitely many ...
0
votes
1answer
52 views

$f(A) \cap f(B) = f(A \cap B)$ if $f$ is a bijection?

I found this statement in a Topology proof - $$f(A) \cap f(B) = f(A \cap B)$$ if $f$ is a bijection I haven't come across this statement before. Is this some axiom of set theory?
3
votes
2answers
39 views

Suppose $f: X \rightarrow Y$, and is one-to-one, and let $A \subseteq X$, prove that $f^{-1}[f[A]] = A$.

Suppose $f: X \rightarrow Y$, and is one-to-one, and let $A \subseteq X$, prove that $f^{-1}[f[A]] = A$. EDIT: Actually, this identity should hold even if $f$ is not one-to-one (injective), right? ...
-2
votes
1answer
26 views

Two distinct natural numbers are not equivalent to each other

If $m$ and $n$ are two distinct natural numbers, how to prove that they are not equivalent (one to one correspondence)to each other?
1
vote
0answers
35 views

obtaning a set from classes

Is it possible to get a set by a intersection of 2 (non-set) classes? I can see it is possible from a set and a class, simply by a set contained in the class. Also, I think that the union/product of ...
7
votes
2answers
784 views

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

On the one hand, I know that $\mathbb{R}$ and $\mathbb{I}=\{xi:x\in\mathbb{R}\setminus\{0\}\}$ are both uncountable sets, so they have the same number of elements (i.e. the same cardinality) On the ...
0
votes
2answers
33 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
38 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
22 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
37 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
21 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 ...
2
votes
0answers
49 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 ...
3
votes
5answers
688 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
41 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
37 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
36 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 ...
-1
votes
0answers
41 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
23 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
26 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
41 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
25 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
965 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
66 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
17 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
201 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 ...
-2
votes
2answers
100 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 ...