This tag is for elementary questions on set theory, spanning topics usually found in introductory courses in set theory, in addition to review sections of graduate textbooks in the same field. Topics include intersections and unions, de Morgan's laws, Venn diagrams, relations, functions, ...

learn more… | top users | synonyms

0
votes
1answer
41 views

Set Relations (anti-symmetrical)

I need to determine whether the relation $R$ on the set of all people is antisymmetric where $(a,b)$ is an element of $R$ if and only if ...
0
votes
2answers
193 views

Proving there are uncountably many continuous functions on an interval

How can I prove that the set of real-valued continuous functions on a non-degenerate interval $[a,b]$ is uncountable? Can I use cardinality?
-2
votes
1answer
46 views

Bounded perfect-free sets in $\mathbb{R}$ are countable?

I refine the question, if $A\subset \mathbb{R}$ is bounded and contains no nonempty perfect subsets, then $A$ must be countable? (Without denying the continuum hypothesis.)
-1
votes
4answers
58 views

How to prove (A ⊆ B) ∧ (B ⊆ C) ⇒ (A ⊆ C)

How would I go about proving that, given A, B, C are sets; $[(A⊆B)∧(B⊆C)]⇒(A⊆C)$ Thanks for the help.
0
votes
2answers
34 views

Regarding countable sets

Please help to to prove that if a collection of sets $A$ is countable, then the set of all finite intersections of members of $A$ is also countable. I couldn't find the bijection between them.
1
vote
1answer
62 views

Help with an elementary set theory proof

"If $A$ and $B$ are two sets, then prove that $A$ is the union of a disjoint pair of sets, one of which is contained in $B$ and one of which is disjoint from $B$." Can somebody help me understand ...
1
vote
2answers
90 views

Are the perfect-free sets countable?

Let $A$ be subset of $\mathbb{R}$ that contains no nonempty perfect subsets. Is $A$ countable?
2
votes
2answers
77 views

Euclidean algorithm for ordinals

I am trying to prove the Euclidean algorithm for ordinals. More specifically: For any ordinals $\alpha, \beta$ where $\beta >0$, there are unique $\gamma, \delta$ such that $\alpha = ...
2
votes
3answers
63 views

Prove $A \cap B = A − (A − B)$

$A$ and $B$ are sets, how would I prove the following equality: $A∩B = A-(A-B)$ Would I be correct in saying that if I take $x$ to be in $A-(A-B)$, it means that $x$ is in $A$, but not in $A-B$. ...
0
votes
1answer
32 views

increasing sequence of sets

suppose $A_n \subseteq \mathbb{R}$ for all $n$. Also if $A_{k} \subseteq A_{k+1} $, does it follow that $\bigcup_{k=1}^{\infty} A_k = \mathbb{R} $?. I know this is obvious but I dont know how to show ...
2
votes
1answer
27 views

Different implicit definitions

I'm Dutch, and my books are written in Dutch, so appologies if technical terms are incorrectly translated. $\in$ means 'element of' $\mathbb{Z}$ is the set of 'whole numbers' $\leq$ is 'less than or ...
2
votes
1answer
55 views

$ \{ x : f(x) > 0 \} = \bigcup_n f^{-1}([\frac{1}{n}, \infty )) $

$ \{ x : f(x) > 0 \} = \bigcup_n f^{-1}([\frac{1}{n}, \infty )) $ My try: Pick $$x \in \bigcup_n f^{-1}([\frac{1}{n}, \infty )) \implies x \in f^{-1}([\frac{1}{n}, \infty )) \text{ for some $n$ } ...
1
vote
1answer
44 views

What is the lower bound of the subset $2^n,\; n\in\mathbb{N}$

Let: $$ A = \{2^n,\; n\in\mathbb{N}\},\quad A\subset \mathbb{R} $$ Is the lower bound: $(-\infty,0]$ $(-\infty,1]$ $(-\infty,1)$ ? I think it can be the first because ...
0
votes
3answers
93 views

Injection from $\Bbb N$ to the set of functions from the naturals to $\{0,1\}$.

Let $\Bbb N$ be the set of natural numbers and let $F$ be the set of total functions from $\Bbb N$ to $\{0,1\}$. Construct a total injective function $g_1\colon \Bbb N\to F$. Sounds easy, but sorta ...
2
votes
0answers
1k views

Is this proof for the definition of the symmetric difference of two sets rigorous enough?

My real analysis text asks me to show that the symmetric difference of two sets $A$ and $B$ is given by $D = (A \backslash B) \cup (B \backslash A)$ In the second part of the question, it then ...
1
vote
2answers
75 views

What's wrong with this proof about the cardinality of N^N?

Cantor's diagonalisation argument shows that $|N^N| = |R|$ so obviously $|N^N| > |N|$. $N^N$ is $N$ times itself, $N$ times. This is the set of $N$-tuples with elements in $N$. To prove that ...
0
votes
1answer
153 views

Proving Equality of 2 Functions

I have a general question, illustrated by a specific example. The general question is how to methodically prove that two functions are equal. Much like trying to prove an "if-and-only-if" statement ...
5
votes
6answers
636 views

A set is infinite iff there is a one-to-one correspondent with one of its proper subsets?

Maxwell Rosenlicht claims in "Introduction to analysis" that a set is infinite if and only if it may be placed into one-to-one correspondence with a proper subset of itself. He says this is ...
1
vote
3answers
1k views

Show that if $A$ and $B$ are sets, then $A \subseteq B$ if and only if $A \cap B = A$.

I'm working through a real analysis textbook, and it starts out with set theory. The first exercise is Show that if $A$ and $B$ are sets, then $A \subseteq B$ if and only if $A \cap B = A$. I ...
1
vote
3answers
218 views

Show that Function Compositions Are Associative

My intent is to show that a composition of bijections is also a bijection by showing the existence of an inverse. But my approach requires the associativity of function composition. Let $f: X ...
1
vote
2answers
93 views

The complement of the closed subset of a closed set

Suppose that I had a closed set. Suppose that I made it so that there was nothing else outside such closed set. I will call this set "A". Now, suppose that I picked a closed subset from A. I will call ...
3
votes
1answer
458 views

Cross product intersection sets

Here's what I'm, trying to prove. Let $A, B, C$ be non-empty sets. Prove that $A \times (B \cap C) \subseteq (A \times B) \cap (A \times C)$ First I would need to prove $A \times (B \cap C) = (A ...
0
votes
1answer
57 views

Does $\bigcup _{j\in\mathbb{N}}A_j=A$

I'm reading R. Schilling's Measure, Integrals and Martingales and in a proof he makes the following statement. "Since $A=\bigcup _{j\in\mathbb{N}}A_j$...", is this allways true? The context: The ...
0
votes
1answer
80 views

How can I solve this recursion function task?

I really need help on this task. Im stuck at it and I really would appreciate your help here. Give a recursive function $r$ on $A$ that reverses a string. For instance, $r(logikk) = kkigol$ and ...
0
votes
1answer
121 views

Proofs sets exclusive or

I know this might be easy for you but I am struggling with this question. $\oplus$ means XOR: How would you break down $\overline{B} \oplus A$. I have to show that its equal to ...
1
vote
0answers
83 views

How to solve a inductively defined set?

I'm new to induction. Right now iIm working on a task which I'm not sure if I've solved it correctly. Here is the task: Give an inductive definition of the given language below: ...
1
vote
2answers
150 views

Problem with injective and surjective functions

prove that $$\forall f:X \to Y \ \exists Z$$ $$\mbox{, injective function -}$$ $$h : X \to Z $$ $$\mbox{and surjective function -}$$ $$g: Z \to Y$$ $$\mbox{so that}$$ $$f = gh$$ How should I ...
0
votes
1answer
57 views

Proof of sets operations equivalency 2

I'm studying set theory at University and I just discovered this site. I hope it's not too anoying if I keep asking questions about this subject. This is the exercice: Let X, Y and Z be sets. Prove ...
1
vote
1answer
99 views

Inductive definition of a given language

I'm having some difficulties solving a induction task. Here is the task i'm working on: Give an inductive definition of the given language below: $\{a^n,b^n\mid ...
0
votes
1answer
48 views

Trouble understanding $l_0 = \{\{x_j\}_{j \in \mathbb{N}} : \exists N \in \mathbb{N}, x_j = 0 \forall j \ge N\}$ …

Here's the question: "Let \begin{equation} l_0 = \{\{x_j\}_{j \in \mathbb{N}} : \exists N \in \mathbb{N}, x_j = 0 \forall j \ge N\} \end{equation} be the space of sequences with only finitely many ...
1
vote
2answers
68 views

How to prove that two sets are equaivalent

There's this book iI'm reading and its definition of two sets being equivalent is that they have to have a one-to-one correspondence. So there's this question I'm trying to prove and it goes: Prove ...
0
votes
3answers
698 views

Verify proof that $\varnothing \in F$ implies $\cap F = \varnothing$

Hi so I want to know if my proof attempt is correct, so here's the question: Suppose that $F$ is a family of sets. Prove that if $\varnothing\in F$ then $\cap F=\varnothing$. Proof. Suppose ...
0
votes
1answer
260 views

A supposed incorrect theorem

Hi i'm new here and here's my question: Suppose $A\subseteq$$P(A)$. Prove that $P(A)\subseteq$$P(P(A))$. I am using the book How to prove it by Velleman and i was wondering if anyone had a link to ...
1
vote
4answers
97 views

Proof of sets operations equivalency having a hypothesis

This is the exercice: Let $A, B$ and $C$ be sets. Suppose that $C \subseteq A$. Prove that $A - (B - C) = (A - B) \cup C$. This is what I do: $x \in A-(B-C) \Longleftrightarrow x \in A \neg \wedge ...
8
votes
0answers
230 views

Is there an elementary introduction to higher order functions?

I am teaching a pre-calculus course (using the textbook by Michael Sullivan if it helps), and I realized that higher order functions seem to show up in with some frequency in pre-calculus and ...
0
votes
2answers
121 views

Countable unions and sigma-algebras

Let C be a countable partition of E, and let G be the collection of all sets that are countable unions of elements taken from C. Show that G is a sigma-algebra. Can someone explain this step by step, ...
1
vote
3answers
303 views

Standard notation for the set of integers $\{0,1,…,N-1\}$?

I was wondering if there exist a standard notation for the set of integers $\{0,1,...,N-1\}$. I know for example $[N]$ could stand for the set $\{1,2,...,N\}$ but what about the former, i.e. ...
1
vote
1answer
40 views

Countability over indexed families

I'm strugling with countability over indexed sets compared to ordinary sets. Basically we say that any set $A$ is countable if there is a bijective function $f$ such that $f:\mathbb{N}\longrightarrow ...
0
votes
2answers
42 views

Proving surjectivity of a function

$$Y\setminus f(A) \subseteq f(X\setminus A) \leftrightarrow f= \mbox{surjective}$$ $$\forall A\subseteq X$$ I need some help proving this.
1
vote
1answer
54 views

If $x$ is transitive, so is $x \cup \{x\}$.

If $x$ is transitive, then so is $x \cup \{x\}$. I need help proving this. I know that a set $A$ is transitive if every member of $A$ is a subset of $A$: $\forall x( x \in A \rightarrow x ...
4
votes
1answer
204 views

Fast bijective $\mathbb{Z} \times \mathbb{Z} \rightarrow \mathbb{Z}$

I am looking for a fast pairing function which maps two integers (cartesian coordinates) to a single unique integer. In other words, $$ \mathbb{Z} \times \mathbb{Z} \rightarrow \mathbb{Z}, $$ thats ...
0
votes
1answer
40 views

Prove that $\bigcap \{A_i : i \in \{ \}\} = U$

In the book General Topology, by Lipschutz, there is a specific note that $\bigcap \{A_i : i \in \{ \}\} = U$, where ${A_i}$ is an arbitrary indexed family of sets and $U$ \is the universal class. ...
1
vote
2answers
86 views

Sigma algebras…

"Let $\mathcal{C}$ = {A,B,C} be a partition of E. List the elements of the smallest sigma algebra containing $\mathcal{C}$." Let me see if I got this right...because $\mathcal{C}$ is a partition of ...
2
votes
3answers
114 views

Closed under intersections

I read this definition: "A collection C of subsets of E is said to be closed under intersections if A ∩ B belongs to C whenever A and B belong to C." How could the intersection of ANY A and B ...
1
vote
1answer
68 views

Equivalence class help

I have a question that goes as follows: Let d be a positive integer. Define the relation Rho on the integers Z as follows: for all m,n element of the integers. m rho n if and only if d|(m-n) Prove ...
0
votes
2answers
46 views

$1_{\limsup A_n} = \limsup 1_{A_n} $

Do you have some hints on how to prove the following relation? I think it should be quite straightforward, but I cannot see it. $$ 1_{\limsup A_n} = \limsup 1_{A_n} $$
0
votes
2answers
46 views

Proving function's injectivity

$$f(X/A)\subseteq Y/f(A) \forall A\subseteq X \leftrightarrow f= \mbox{injective}$$ I know that I should prove this in 2 ways. First I should assume that the first part is true and f is not ...
0
votes
2answers
63 views

$A_k\subset\mathbb{R}$ such that $\lim\sup A_k=\mathbb{R}$ but $\lambda(A_k)=1$ (Lebesgue measure) for all $k$.

Construct a sequence of measurable sets $A_k\subset\mathbb{R}$ such that $\lim\sup A_k=\mathbb{R}$ but $\lambda(A_k)=1$ (Lebesgue measure) for all $k$. My thoughts: Since $\lim\sup ...
0
votes
3answers
122 views

Is $\complement(A\setminus B)=(\complement A) \setminus (\complement B)$ true or false?

The problem I have is to calculate this term $(\complement A) \setminus (\complement B)$ when I (forexample) let $A=\left \{ a,b,c,d \right \}$ and $B=\left \{ b,c,e,g\right \}$. How do I calculate ...
2
votes
1answer
68 views

How would you “count” $\omega^\omega$

$\omega^\omega$ can be seen as the limit of $\omega^n$ which are all countable sets, and is thus countable. For the latter sets, there is an "easy" way list the elements out, but how would you do it ...