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
0answers
33 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
55 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
37 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
73 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 ...
2
votes
1answer
48 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$, ...
0
votes
1answer
18 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
31 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
47 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
28 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
45 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
32 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 ...
0
votes
2answers
56 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.
1
vote
1answer
64 views

Proving this equivalence relation

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 ...
0
votes
0answers
70 views

Prove $X\times Y$ is an equivalence relation

(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 ...
5
votes
2answers
403 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
43 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
105 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 ...
-1
votes
2answers
44 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
41 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}$ ...
1
vote
4answers
74 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
36 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
45 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
120 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" ...
3
votes
1answer
39 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
78 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
91 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
70 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 ...
-4
votes
1answer
78 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
58 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
68 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
49 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 ...
1
vote
3answers
73 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
28 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
22 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 ...
1
vote
1answer
32 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
53 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 ...
3
votes
1answer
44 views

Show that $≺$ is a total ordering

Let $ℕ$ be the set of positive integers. Let $D(n)$ denotes the number of divisors of $n$. We define this binary relation: $n≺m⇔n≤m$ and $D(n)≤D(m)$ where $≤$ is the usual ordering in $ℕ$. Show ...
0
votes
2answers
65 views

Is this proof of uncountability of Cantor set true?

To construct Cantor set $C$, start with $I_1=[0,1]$ and define $$E_1=\{0,1\}=\{x:x\text{ is an end point of the set }I_1\}.$$ $\operatorname{card}(E)=\#(E)=2$. After deleting the middle open interval ...
9
votes
5answers
902 views

Contradictory definition in set theory book?

I'm using a book that defines $A\setminus B$ (apparently this is also written as $A-B$) as $\{x\mid x\in A,x\not\in B\}$, but then there was an exercise that asked to find $A\setminus A$. Wouldn't it ...
1
vote
2answers
35 views

Proof of the description of a set

We are supposed to describe the set $\bigcup_{n=1}^\infty A_n$ with a proof. $A_n = \{(x, y) \in \mathbb{R}^2 | y-x^{2n} \geq 0 \}$. This is what I have so far: "This is just the set of all points ...
1
vote
1answer
28 views

What can we say about the set X?

We have a certain set $X$ for which is valid: $\forall U\subset X:[ U\neq X ]\rightarrow U\nsim X$. What can we say about $X$? I think we've got to use the axiom of choice here. My first guess would ...
0
votes
1answer
38 views

Cantor's theorem.

If $A$ is a infinite set then the power set of $A$, $\mathcal{P}(A)$, is an uncountable set. To proof first I take $A$ countable, and I suppose $\mathcal{P}(A)$ is countable, i.e., ...
1
vote
2answers
46 views

Is there an uncountable set S, a subset of P(N), such that for any A,B an element of S; the intersection of A and B is finite? [duplicate]

I have a feeling no such uncountable set exists but have no idea how I could formulate a proof to show this. If such an uncountable set did exist I could try and use a form of the diagonalization ...
1
vote
1answer
41 views

Proving that $x \not\in B \cap C \iff x \not\in B \lor x \not\in C$.

I've got a set theory question. I'm required to show that $x \not\in B \cap C$ if and only if $x \not\in B$ or $x \not\in C$. I decided to call the universal set $S$ (which contains both and $B$ and ...
0
votes
1answer
30 views

Set notation check

Are the three statements: $(a,b,c)\in\mathbb{Q}^3$ $\{a,b,c\}\subset\mathbb{Q}$ $a,b,c \in\mathbb{Q}$ equivalent ways of saying that a, b and c are rational numbers?
2
votes
2answers
74 views

Opposite of a function being bijective?

A function is bijective if it is both surjective and injective. Is there a term for when a function is both not surjective and not injective?
0
votes
2answers
27 views

Can a surjective function have an element in the domain not mapped to the codomain?

I have seen a lot of definitions for surjectivity stating that every element in the codomain must be mapped to something in the domain. But does the opposite also have to hold true for a function to ...
7
votes
1answer
81 views

Is the limit of a recursive sequence of recursive ordinals itself a recursive ordinal?

Is the limit of a recursive sequence of recursive ordinals itself a recursive ordinal? If so, is there a nice proof of this?
0
votes
2answers
60 views

Suppose A and B are finite sets and $f : A \rightarrow B$ is surjective. Is it possible that |A| < |B|?

I am trying to understand better what surjective functions is from a set $A$ to a set $B$, and from what I understood, it basically means this: A function is subjective (onto) from set $A$ to set ...