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, (un)...

learn more… | top users | synonyms

2
votes
1answer
46 views

Cardinality of $L$, $L = \{(x,y) \in \mathbb{R} \times \mathbb{R} \mid x + y = 5\}$

Like the title says, $L = \{(x,y) \in \mathbb{R} \times \mathbb{R} \mid x + y = 5\}$ I need to find the cardinality of L, I have an idea of an answer, but I don't know what function I need to build,...
0
votes
2answers
116 views

If two sets (including A) are mutually exclusive, then A is the union of the sets.

In Mathematical statistics with applications, problem 2.5 they ask: Show that $(A\cap B)$ and $(A\cap \bar{B} )$ are mutually exclusive, and therefore that $A$ is the union of two mutually ...
2
votes
1answer
70 views

Build a bijection $f: \mathbb{Q} \to \mathbb{Q}\setminus[0,1].$

Build a bijection $f: \mathbb{Q} \to \mathbb{Q}\setminus[0,1].$ What about $f(x)=x+1$ if $x>0$ and $f(x)=x-1$ for $x<0?$
2
votes
2answers
71 views

Build a bijection $\mathbb{R} \to \mathbb{R}\setminus \mathbb{N}$ [duplicate]

Build a bijection $f: \mathbb{R} \to \mathbb{R}\setminus \mathbb{N}$. What about $f(x)=\pi \cdot x?$
-1
votes
2answers
243 views

How do we know establishing a bijection between two infinite sets suffices to prove they have the same number of elements?

The method works for finite sets, but what proof do we have that the method extends for counting elements of infinte sets aswell? How do you justify that results obtained from using the method such as ...
3
votes
2answers
591 views

An example in the fundamental theorem of equivalence relations?

I've read about the fundamental theorem of equivalence relations. The idea that an equivalence relation on a set $X$ partitions $X$ is understandable. But the idea that for any partition of $X$ there ...
2
votes
2answers
326 views

Strictly monotonically increasing sequences of natural numbers

I have several questions with regards to these sequences: What is the cardinality of the set of all such sequences? I assume that it is equal to the cardinality of $\mathbb{R}$, is that correct? ...
3
votes
3answers
141 views

Set notation and the difference between $\subseteq,\in,\subset$.

What does it mean to say $\mathcal F$ is a family of subsets? (an example would be much appreciated :)) What would be a layman's example? When $B=\{b,c\}$ is it appropriate to write $\{a,\{b,c\}\...
0
votes
0answers
49 views

Books on contemporary set theory [duplicate]

I have gone through Halmos' Naive Set Theory. Now, could you recommend me a good follow-up book for a rigorous treatment of contemporary set theory? (For example, I've been suggested to look at Devlin'...
3
votes
2answers
166 views

A ⊆ B ∪ C -> x ∈ B or x ∈ C.

This is one of the problem I have been working from Velleman's How to Prove it book: Theorem: Suppose A, B, and C are sets and A ⊆ B ∪ C. Then either A ⊆ B or ...
1
vote
1answer
27 views

Show Trans$(x)\rightarrow$ Trans$(S(x))$

Unsure of case (2) in my proof: Question: Assume Trans$(x)$, show Trans$(S(x))$ Definition: Trans$(x)\leftrightarrow_{df}\forall p\in x(p\subseteq x)$ Question symbollically: Show [$y\in x\...
2
votes
1answer
69 views

Help me find my mistake set theory basics

Please help me find the mistake I made in a set theory exercise. I have a function $f:\Bbb N\times\Bbb N\to\Bbb N$ defined by $$f((a,b))=\frac{(a+b)(a+b+1)}2+a\;.$$ I'm trying to prove that $f$ is ...
2
votes
3answers
282 views

Natural numbers in set theory is {0,1,2,…}?

The set of natural numbers $\mathbb{N}$ in set theory is defined with the axiom of infinity as the smallest inductive set and then it is usually proven that $\mathbb{N}$ satisfies the Peano axioms and ...
0
votes
0answers
36 views

Is there a injective polynomial function from $R^2$ to $R$? [duplicate]

There is an injective polynomial function from $N^2$ to $N$ (the Cantor-pairing function for example, which is of degree 2), and also one of degree 4 from $Z^2$ to $Z$. I believe the question is open (...
1
vote
2answers
60 views

Is $x\in\{\{x\}\}$ [duplicate]

Is $x\in\{\{x\}\}$. I understand that $x\in\{x\}\in\{\{x\}\}$ does this mean $x\in\{\{x\}\}$? Very simple just unsure about the properties of $\in$, not looking for an extravagant answer, thanks in ...
0
votes
1answer
61 views

Let $\mathcal{B}$ be the class of all ordered pairs. Show that $\mathcal{B}$ is a proper class

Let $\mathcal{B}$ be the class of all ordered pairs. Show that $\mathcal{B}$ is a proper class - that is - it is not a set [Hint: suppose for a contradiction it was a set; apply the axiom of union] ...
2
votes
0answers
89 views

Checking if a relation is complete

I have a transitive relation $\subset$ on a (finite and small) set S and a list of pairs $x_i\subset y_i.$ I would like to check if my list is complete in the sense that if $x\subset y$ then there are ...
3
votes
1answer
120 views

Completing my proof of exercise 1.6 in Jech - Set Theory

Theorem. If $X$ is inductive, then so is the set $V = \{x\in X:x\text{ is transitive and every nonempty subset has an}\in\text{-minimal element}\}.$ Proof (incomplete). Clearly $\emptyset\in V$, so ...
0
votes
1answer
29 views

If $\alpha\in X/R$ is an equivalence class, then $F:X/R\to Y$ defined by $F(\alpha)=f(a)$, is well-defined, 1-1 and onto.

Let $f:X\to Y$ be a surjection. Let $R$ be the subset of $X\times X$ consisting of those pairs $(x,x')$ such that $f(x)=f(x')$. Then $R$ is an equivalence relation. Let $\pi:X\to X/R$ be the ...
3
votes
2answers
57 views

Open neighborhoods in ordinals with the order topology

While learning about ordinals, my teacher made some remarks about any ordinal α being equipped with the order topology, and some facts, one of which was basically that the finite ordinals and ω are ...
4
votes
2answers
61 views

Proving or disproving $\{\{a\},b\}=\{\{c\},d\}\iff a=c \land b=d$

Prove/disprove: $\{\{a\},b\}=\{\{c\},d\}\iff a=c \land b=d$ I know the LHS isn't like in the definition of ordered sets so it's probably false but I can't find any numbers as counter example, nor ...
0
votes
4answers
32 views

Is it true $f^{-1} (B^C)=(f^{-1}(B))^C$? Is it true $f (B^C)=(f(B))^C$?

Is it true $f^{-1} (B^C)=(f^{-1}(B))^C$? Is it true $f (B^C)=(f(B))^C$? I feel really confused about this. Can anyone tell me whether it is true and why? Thanks so much!
0
votes
1answer
145 views

Set builder form for representing strings

Is there a way to represent strings or palindromes using set notation? For representing palindrome using set notation, I arrived at this notation $$S=\{ab^{n}c:N\; |\; n \geq 1 \land n \leq 3\}$$ I ...
1
vote
1answer
35 views

Stuck on basics: How to prove that {subst($\alpha$,s)} is well defined?

So I feel like this is a really basic point that I'm missing and I can't really manage to prove that: So I have a substitution function $s: Var \rightarrow WFF$ and a subst function: $WFF \times WFF^{...
0
votes
2answers
64 views

The cardinal of the set of all measures on $\mathbb{R}$

It is a very simple question that I don't know how to do: Let $M = \{\mu \colon \mathcal{B}(\mathbb{R})\to \mathbb{R} \colon \mu \text{ is a measure}\}$ $$|M| = \ ?$$ Any help will be appreciated.
3
votes
1answer
84 views

If $X,Y$ are equivalence relations, so is $X \times Y$

If $X,Y$ are reflexive, symmetric, and transitive, then $X \times Y$ is an equivalence relation where ${(a,b):a\in X, b\in Y}$. I am trying to self learn these topics. I do know what an equivalence ...
1
vote
0answers
83 views

Prove $X\times Y$ is an equivalence relation [duplicate]

(Relation between two sets) If $X$ and $Y$ are sets, a relation between $X$ and $Y$ is a subset $R \subset X \times Y.$ For a relation $R \subset X\times Y$ and $a \in X$ and $b \in Y$ if $(x,y) \in R,...
5
votes
2answers
1k views

Inverse of a set, possible?

Just like ordinary algebraic operations have inverses, could we imagine the inverse of a set? Like $x\in\{x\}$ then maybe the inverse denoted $[|x|]$ would mean $$\{\ [|x|]\ \}=x$$ Would this idea ...
1
vote
1answer
65 views

The empty set as an Indexing set. [duplicate]

For each $\alpha\in I$, let $A_\alpha$ be a subset of some nonempty set $S$. So if $I=\emptyset$, then $$ \bigcup_{\alpha\in I} A_\alpha=\emptyset $$ and $$ \bigcap_{\alpha\in I} A_\alpha=S. $$ Why ...
3
votes
0answers
113 views

What are some examples of isotrophic sets?

What are some examples of isotrophic sets? and is there a "good" way to describe them? Isotrophic meaning that a random vector X uniformly distributed in the set has the isotrophic property for all $...
0
votes
2answers
59 views

Set theory: Why are these two sets different?

I'm currently working through a set theory book and one of the exercises is to explain why $\{z|z\subseteq \{\emptyset\}\}$ and $\{x|x\in \mathbb{Z}, 0<x<1\}$ are different. I'm just completely ...
2
votes
0answers
49 views

Clarification on the definition of $X^{\omega}$

I have never seen this notation before (graduated with a math degree a few months ago; not in school currently). Here's what I gather from Munkres' Topology: Given a set $X$, an $\mathbf{\omega}$ -...
2
votes
4answers
103 views

Is there numbers that don't fit in our sets of numbers?

It is said that the first numbers we used were natural numbers like $0$, $1$ ,$2$... in $\mathbb{N}$. Then we discovered negative numbers $-1$,$-2$... , and classified them all in $\mathbb{Z}$. Then ...
3
votes
2answers
64 views

Cardinal Arithmetic proof issues.

Let $X$ be a finite set and let $x$ be an object which is not an element of $X$. Then $X \cup \{x\}$ is finite and $|X \cup \{x\}| = |X| + 1$. Proof. Let X be a finite set with cardinality n, ...
2
votes
1answer
62 views

Existence of finite sets of infinite set without using AC

Is it possible to prove that every infinite set $B$ has a subset of cardinality $n$, for every natural $n$, without using AC? I know how to prove this claim by induction. In the induction step I chose ...
1
vote
3answers
233 views

Is natural numbers set $\mathbb N$ infinite set?

A set with uncountable number of elements is called an infinite set. Is that the set of all natural numbers, $\Bbb N=\text{{$1,2,3,\ldots$}}$ infinite set? As far i know $\Bbb N$ is "countably" ...
4
votes
1answer
57 views

Question concerning the universe of sets.

I am reading Charles Pinter's Introduction to Set Theory Every proper class is in one-to-one correspondence with the universal class $\mathscr{U}$, that is, the class of all sets [emph. added]. ...
1
vote
2answers
191 views

Disjoint Exhaustive Subsets with Alternate Elements and equal Cardinality

Suppose $U$ is an ordered infinite set, I want to construct subsets $A$ and $B$ such that: (1) (Disjoint) $A \cap B = \phi $ (2) (Exhaustive) $A \cup B = U$ (3) (Alternate elements) $\forall x,y ...
1
vote
5answers
2k views

Prove that if sets $A$ and $B$ are countable, then their union $A\cup B$ is countable

Prove that if sets $A$ and $B$ are countable, then their union $A\cup B$ is countable. I'm really confused because I'm not sure if $A$ and $B$ are finite or infinite. If I have to consider every ...
2
votes
2answers
158 views

Set theory intersections and unions

I'm in an intro to discrete mathematics course, and this is a question on my first homework. I showed what I have so far, I think the answer to the first part of the question may be right, but I'm ...
-5
votes
1answer
136 views

How to describe the Cartesian product $\mathbb{R} × \mathbb{R}$?

I am taking a discrete mathematics course in the spring and in an attempt to fully understand the material I am reading ahead. I came across this statement Let $\mathbb{R}$ denote the set of all real ...
1
vote
1answer
61 views

Basic Set Theory regarding the set $\{0\}$

For each nonnegative integer $n$, let $U_n = \left \{n,−n\right \}$. Find $U_1,\:U_2,\:\text{and}\:U_0$. $U_1 = \left \{1,−1\right \}, U_2=\left \{2,−2\right \}, U_0 = \left \{0,−0\right \} = \left \{...
1
vote
4answers
111 views

Show the inverse of a bijective function is bijective

We have a function $\varphi:G\rightarrow H$ is an isomorphism, show its inverse $\varphi^{-1}:H\rightarrow G$ is also an isomorphism I am fine with showing it to be a homomorphism and surjective, ...
1
vote
1answer
53 views

Show an equivalence via induction

Let $f$ be a set function $f: 2^{V} \rightarrow \mathbb{N}_{0}$; let $S,T\subset V$ be such that $S \subset T$ and let $j$ be any element such that $j \in (V \setminus T)$ (so $j$ doesn't belong to $T$...
4
votes
4answers
181 views

Rigorous proof that countable union of countable sets is countable

I am unsuccessfully trying to understand the proof of the fact that countable union of countable sets is countable.The argument presented till now is: Let $\displaystyle \bigcup S_n$ be a countable ...
0
votes
1answer
57 views

Properties of Image and Inverse Image

Let $f:X\rightarrow Y,A\subset X$ and $B\subset Y$. If $f^{-1}(B) \subset A$, then $B \subset f(A)$ I cannot understand that why this statement is false. Any counterexample?
1
vote
1answer
54 views

How to denote the set of all students who take the same class as some given student $s'$?

I have a set of Students: $S = \{s_1, \ldots, s_2 \}$. Now each student takes some class (doesn't matter what class). Now I need to have a set $X$ that contains all students that take the same class, ...
2
votes
2answers
24 views

How to prove this statement about this relation:

Let $p$ be a prime. On $\mathbb{Z}_{>0}$ we define the relation $\sim$ as $a\sim b\iff [\forall n\in \mathbb{Z}_{>0}: p^n|a \iff p^n|b]$. Prove that $[\forall x,y \in \mathbb{Z}_{>0}: x\sim x^...
1
vote
1answer
36 views

What is the cardinality of the following equivalence classes?

We have the relation $\sim$ on $\mathbb{R}$ defined by $a\sim b \iff [\exists q\in \mathbb{Q}: a-b=q\pi]$. What are the possible cardinalities of the equivalence classes?
0
votes
0answers
88 views

Undergraduate Set theory

I'm reviewing some set theory notes and I know its a basic question, but I just want confirmation. Let the universe of discourse be $\mathbb{Z}$. What is $\{x \mid x\geq 0 \wedge x>0\}$ equal to?...